Learning Accurate, Compact, and Interpretable Tree Annotation

Proceedings of the 21st International Conference on Computational Linguistics and 44th Annual Meeting of the ACL, pages 433–440, Sydney, July 2006. c⃝2006 Association for Computational Linguistics Learning Accurate, Compact, and Interpretable Tree Annotation Slav Petrov Leon Barrett Romain Thibaux Dan Klein Computer Science Division, EECS Department University of California at Berkeley Berkeley, CA 94720 {petrov, lbarrett, thibaux, klein}@eecs.berkeley.edu Abstract We present an automatic approach to tree annota- tion in which basic nonterminal symbols are alter- nately split and merged to maximize the likelihood of a training treebank. Starting with a simple X- bar grammar, we learn a new grammar whose non- terminals are subsymbols of the original nontermi- nals. In contrast with previous work, we are able to split various terminals to different degrees, as ap- propriate to the actual complexity in the data. Our grammars automatically learn the kinds of linguistic distinctions exhibited in previous work on manual tree annotation. On the other hand, our grammars are much more compact and substantially more ac- curate than previous work on automatic annotation. Despite its simplicity, our best grammar achieves an F1 of 90.2% on the Penn Treebank, higher than fully lexicalized systems. 1 Introduction Probabilistic context-free grammars (PCFGs) underlie most high-performance parsers in one way or another (Collins, 1999; Charniak, 2000; Charniak and Johnson, 2005). However, as demonstrated in Charniak (1996) and Klein and Manning (2003), a PCFG which sim- ply takes the empirical rules and probabilities off of a treebank does not perform well. This naive grammar is a poor one because its context-freedom assumptions are too strong in some places (e.g. it assumes that sub- ject and object NPs share the same distribution) and too weak in others (e.g. it assumes that long rewrites are not decomposable into smaller steps). Therefore, a va- riety of techniques have been developed to both enrich and generalize the naive grammar, ranging from simple tree annotation and symbol splitting (Johnson, 1998; Klein and Manning, 2003) to full lexicalization and in- tricate smoothing (Collins, 1999; Charniak, 2000). In this paper, we investigate the learning of a gram- mar consistent with a treebank at the level of evalua- tion symbols (such as NP, VP, etc.) but split based on the likelihood of the training trees. Klein and Manning (2003) addressed this question from a linguistic per- spective, starting with a Markov grammar and manu- ally splitting symbols in response to observed linguistic trends in the data. For example, the symbol NP might be split into the subsymbol NPˆS in subject position and the subsymbol NPˆVP in object position. Recently, Matsuzaki et al. (2005) and also Prescher (2005) ex- hibited an automatic approach in which each symbol is split into a fixed number of subsymbols. For example, NP would be split into NP-1 through NP-8. Their ex- citing result was that, while grammars quickly grew too large to be managed, a 16-subsymbol induced grammar reached the parsing performance of Klein and Manning (2003)’s manual grammar. Other work has also investi- gated aspects of automatic grammar …

Content truncated to 500 words