Non-Local Modeling with a Mixture of PCFGs

Proceedings of the 10th Conference on Computational Natural Language Learning (CoNLL-X), pages 14–20, New York City, June 2006. c⃝2006 Association for Computational Linguistics Non-Local Modeling with a Mixture of PCFGs Slav Petrov Leon Barrett Dan Klein Computer Science Division, EECS Department University of California at Berkeley Berkeley, CA 94720 {petrov, lbarrett, klein}@eecs.berkeley.edu Abstract While most work on parsing with PCFGs has focused on local correlations between tree configurations, we attempt to model non-local correlations using a finite mix- ture of PCFGs. A mixture grammar fit with the EM algorithm shows improve- ment over a single PCFG, both in parsing accuracy and in test data likelihood. We argue that this improvement comes from the learning of specialized grammars that capture non-local correlations. 1 Introduction The probabilistic context-free grammar (PCFG) for- malism is the basis of most modern statistical parsers. The symbols in a PCFG encode context- freedom assumptions about statistical dependencies in the derivations of sentences, and the relative con- ditional probabilities of the grammar rules induce scores on trees. Compared to a basic treebank grammar (Charniak, 1996), the grammars of high- accuracy parsers weaken independence assumptions by splitting grammar symbols and rules with ei- ther lexical (Charniak, 2000; Collins, 1999) or non- lexical (Klein and Manning, 2003; Matsuzaki et al., 2005) conditioning information. While such split- ting, or conditioning, can cause problems for sta- tistical estimation, it can dramatically improve the accuracy of a parser. However, the configurations exploited in PCFG parsers are quite local: rules’ probabilities may de- pend on parents or head words, but do not depend on arbitrarily distant tree configurations. For exam- ple, it is generally not modeled that if one quantifier phrase (QP in the Penn Treebank) appears in a sen- tence, the likelihood of finding another QP in that same sentence is greatly increased. This kind of ef- fect is neither surprising nor unknown – for exam- ple, Bock and Loebell (1990) show experimentally that human language generation demonstrates prim- ing effects. The mediating variables can not only in- clude priming effects but also genre or stylistic con- ventions, as well as many other factors which are not adequately modeled by local phrase structure. A reasonable way to add a latent variable to a generative model is to use a mixture of estimators, in this case a mixture of PCFGs (see Section 3). The general mixture of estimators approach was first suggested in the statistics literature by Titterington et al. (1962) and has since been adopted in machine learning (Ghahramani and Jordan, 1994). In a mix- ture approach, we have a new global variable on which all PCFG productions for a given sentence can be conditioned. In this paper, we experiment with a finite mixture of PCFGs. This is similar to the latent nonterminals used in Matsuzaki et al. (2005), but because the latent variable we use is global, our approach is more oriented toward learning non-local structure. We demonstrate that a mixture fit with the EM algorithm gives improved parsing accuracy and test …

Content truncated to 500 words