Sparse Multi-Scale Grammars for Discriminative Latent Variable Parsing

Proceedings of the 2008 Conference on Empirical Methods in Natural Language Processing, pages 867–876, Honolulu, October 2008. c⃝2008 Association for Computational Linguistics Sparse Multi-Scale Grammars for Discriminative Latent Variable Parsing Slav Petrov and Dan Klein Computer Science Division, EECS Department University of California at Berkeley Berkeley, CA 94720 {petrov, klein}@eecs.berkeley.edu Abstract We present a discriminative, latent variable approach to syntactic parsing in which rules exist at multiple scales of refinement. The model is formally a latent variable CRF gram- mar over trees, learned by iteratively splitting grammar productions (not categories). Dif- ferent regions of the grammar are refined to different degrees, yielding grammars which are three orders of magnitude smaller than the single-scale baseline and 20 times smaller than the split-and-merge grammars of Petrov et al. (2006). In addition, our discriminative approach integrally admits features beyond lo- cal tree configurations. We present a multi- scale training method along with an efficient CKY-style dynamic program. On a variety of domains and languages, this method produces the best published parsing accuracies with the smallest reported grammars. 1 Introduction In latent variable approaches to parsing (Matsuzaki et al., 2005; Petrov et al., 2006), one models an ob- served treebank of coarse parse trees using a gram- mar over more refined, but unobserved, derivation trees. The parse trees represent the desired output of the system, while the derivation trees represent the typically much more complex underlying syntac- tic processes. In recent years, latent variable meth- ods have been shown to produce grammars which are as good as, or even better than, earlier parsing work (Collins, 1999; Charniak, 2000). In particular, in Petrov et al. (2006) we exhibited a very accurate category-splitting approach, in which a coarse ini- tial grammar is refined by iteratively splitting each grammar category into two subcategories using the EM algorithm. Of course, each time the number of grammar categories is doubled, the number of bi- nary productions is increased by a factor of eight. As a result, while our final grammars used few cat- egories, the number of total active (non-zero) pro- ductions was still substantial (see Section 7). In ad- dition, it is reasonable to assume that some genera- tively learned splits have little discriminative utility. In this paper, we present a discriminative approach which addresses both of these limitations. We introduce multi-scale grammars, in which some productions reference fine categories, while others reference coarse categories (see Figure 2). We use the general framework of hidden variable CRFs (Lafferty et al., 2001; Koo and Collins, 2005), where gradient-based optimization maximizes the likelihood of the observed variables, here parse trees, summing over log-linearly scored derivations. With multi-scale grammars, it is natural to refine productions rather than categories. As a result, a category such as NP can be complex in some re- gions of the grammar while remaining simpler in other regions. Additionally, we exploit the flexibility of the discriminative framework both to improve the treatment of unknown words as well as to include span features (Taskar et al., 2004), giving …

Content truncated to 500 words