Elamur Research
☰
home / papers / 2006 / Learning Accurate, Compact, and Interpretable Tree Annotation

Learning Accurate, Compact, and Interpretable Tree Annotation

What it is about

Hand-made tree annotations, which split a category such as NP into subject and object NPs, raise parser accuracy, but they are made by people for one language. The authors learn such splits automatically: every nonterminal is split into subsymbols by repeated split and merge cycles that maximize the likelihood of the training treebank, and each symbol can be split to a different degree. The learned grammar recovers the kinds of distinctions that linguists wrote by hand, and it is more compact and more accurate than earlier automatic splits with a fixed number of subsymbols. The parser reaches an F1 of 90.2% on the Penn Treebank, which is a 27% reduction in error over the base grammar.

Ideas

For Mova

The tagger is en/src/ptag.rs with the TnT prior in en/src/tag.rs, the tag set is in en/src/ud.rs, and the explanation output is en/src/explain.rs. The chapter that the ideas touch is languages/en/10-word-classes.md. Measure first: UPOS on EWT dev with split subtags against the current tagger, run twice to confirm the result is not noise.

Library summary

The Research library's own summary of the paper, in our words — not the paper's text.

Written for the Research library (claude-opus-5-5) from the paper text, in our own words: the license "CC BY-NC-SA 3.0 (ACL Anthology, before 2016)" does not allow redistributing the text itself. Original — aclanthology.org/P06-1055.pdf

Summary

Plain PCFGs read directly off a treebank parse poorly because their independence assumptions do not fit the data. Earlier fixes either relied on hand-designed symbol annotations or split every category into the same fixed number of latent subsymbols, which made grammars huge. Petrov et al. start from a bare X-bar grammar derived from the WSJ part of the Penn Treebank using left-branching binarization. They then repeat a cycle: split each symbol in two, train the latent subsymbols with EM (inside-outside over the known trees), and merge back splits that add little likelihood. Parameters are smoothed so that heavier splitting does not lead to overfitting. As a result, frequent, complex categories such as NP and VP receive many subsymbols, while rare or simple ones stay almost unsplit. The best grammar has only 1043 symbols and reaches 90.2% F1 on section 23, which beats fully lexicalized parsers. The learned subcategories are also readable by linguists. This shows that an unlexicalized, automatically refined PCFG can be compact, accurate and interpretable at the same time.

Key points

  • Data split: WSJ Penn Treebank sections 2–21 for training, section 1 for hyperparameter validation, section 22 for development and section 23 for the final test. Scoring uses EVALB.
  • Starting grammar: 98 symbols, 236 unary rules and 3840 binary rules. It scores only 65.8/59.8 LP/LR on the development set.
  • Hierarchical splitting beats direct estimation with the same number of subsymbols:
    • 83.7% vs 83.2% F1 at 4 subsymbols;
    • 88.4% vs 87.3% F1 at 16 subsymbols.
  • Final results: 90.2% F1 with 1043 symbols, which cuts errors by 27% compared with both Klein and Manning (2003) and the system of Matsuzaki et al. (2005). This uses about 97.5% fewer symbols than Matsuzaki et al. (2005). A very small grammar with 147 symbols still reaches about 78% F1.
  • Comparison with lexicalized parsers: on all test sentences the parser scores 89.8 LP / 89.6 LR, above Collins (1999) and Charniak and Johnson (2005). With Viterbi parsing it scores 88.7/88.9 LP/LR.

Interesting ideas

  • Grow capacity in stages. Each larger model is initialized from the previous one by halving every symbol and adding about 1% noise. This gives better optima and lower variance than training a large latent model from scratch, and could apply to any latent-variable or clustering model.
  • Split everything, then merge back what doesn't help. Capacity ends up where the data actually needs it rather than being spread uniformly. This approach could guide vocabulary, cluster or tag-set design for under-resourced languages such as Ukrainian.
  • Begin from the minimal structure. Starting with no hand-crafted annotations lets the model rediscover known linguistic distinctions on its own. This avoids language-specific engineering when moving to a new treebank.
  • Exploit known structure in EM. Because the bracketing is fixed during training, inside-outside runs in linear rather than cubic time. Constraining latent inference with observed structure is a cheap general speed-up.
  • Use interpretability as an evaluation check. Inspecting the top words of each induced subcategory (for example, DT splitting into demonstratives, definites and indefinites) is a simple way to sanity-check learned latent classes.

Cite

The paper itself, not this card. BibTeX from the library's record of the work. DOI 10.3115/1220175.1220230

@inproceedings{petrov2006learning,
  title = {{Learning Accurate, Compact, and Interpretable Tree Annotation}},
  author = {Petrov, Slav and Barrett, Leon and Thibaux, Romain and Klein, Dan},
  booktitle = {Proceedings of the 21st International Conference on Computational Linguistics and 44th Annual Meeting of the Association for Computational Linguistics},
  year = {2006},
  doi = {10.3115/1220175.1220230},
  url = {https://doi.org/10.3115/1220175.1220230}
}

References

19 references, 3 of them with a card of ours. ↗ leads to the work, «find» searches for one we have no id for yet.

  1. G. Ball and D. Hall. 1967. A clustering technique for summarizing multivariate data. Behavioral Science. find
  2. S. Caraballo and E. Charniak. 1998. New figures of merit for best–first probabilistic chart parsing. In Computational Lingusitics, p. 275–298. find
  3. E. Charniak and M. Johnson. 2005. Coarse-to-fine n-best parsing and maxent discriminative reranking. In ACL’05, p. 173–180. find our card
  4. E. Charniak. 1996. Tree-bank grammars. In AAAI ’96, p. 1031–1036. find
  5. E. Charniak. 2000. A maximum–entropy–inspired parser. In NAACL ’00, p. 132–139. find
  6. D. Chiang and D. Bikel. 2002. Recovering latent information in treebanks. In Computational Linguistics. find
  7. N. Chomsky. 1965. Aspects of the Theory of Syntax. MIT Press. find
  8. M. Collins. 1999. Head-Driven Statistical Models for Natural Language Parsing. Ph.D. thesis, U. of Pennsylvania. find
  9. J. Goodman. 1996. Parsing algorithms and metrics. In ACL ’96, p. 177–183. find
  10. J. Henderson. 2004. Discriminative training of a neural network statistical parser. In ACL ’04. find
  11. M. Johnson. 1998. PCFG models of linguistic tree representations. Computational Linguistics, 24:613–632. find our card
  12. D. Klein and C. Manning. 2003. Accurate unlexicalized parsing. ACL ’03, p. 423–430. find our card
  13. T. Matsuzaki, Y. Miyao, and J. Tsujii. 2005. Probabilistic CFG with latent annotations. In ACL ’05, p. 75–82. find
  14. F. Pereira and Y. Schabes. 1992. Inside-outside reestimation from partially bracketed corpora. In ACL ’92, p. 128–135. find
  15. D. Prescher. 2005. Inducing head-driven PCFGs with latent heads: Refining a tree-bank grammar for parsing. In ECML’05. find
  16. H. Schuetze. 1998. Automatic word sense discrimination. Computational Linguistics, 24(1):97–124. find
  17. S. Sekine and M. J. Collins. 1997. EVALB bracket scoring program. http://nlp.cs.nyu.edu/evalb/. ↗
  18. K. Sima’an. 1992. Computatoinal complexity of probabilistic disambiguation. Grammars, 5:125–151. find
  19. A. Stolcke and S. Omohundro. 1994. Inducing probabilistic grammars by bayesian model merging. In Grammatical Inference and Applications, p. 106–118. find