Products of Random Latent Variable Grammars

Human Language Technologies: The 2010 Annual Conference of the North American Chapter of the ACL, pages 19–27, Los Angeles, California, June 2010. c⃝2010 Association for Computational Linguistics Products of Random Latent Variable Grammars Slav Petrov Google Research New York, NY, 10011 slav@google.com Abstract We show that the automatically induced latent variable grammars of Petrov et al. (2006) vary widely in their underlying representations, de- pending on their EM initialization point. We use this to our advantage, combining multiple automatically learned grammars into an un- weighted product model, which gives signif- icantly improved performance over state-of- the-art individual grammars. In our model, the probability of a constituent is estimated as a product of posteriors obtained from multi- ple grammars that differ only in the random seed used for initialization, without any learn- ing or tuning of combination weights. Despite its simplicity, a product of eight automatically learned grammars improves parsing accuracy from 90.2% to 91.8% on English, and from 80.3% to 84.5% on German. 1 Introduction Learning a context-free grammar for parsing re- quires the estimation of a more highly articulated model than the one embodied by the observed tree- bank. This is because the naive treebank grammar (Charniak, 1996) is too permissive, making unreal- istic context-freedom assumptions. For example, it postulates that there is only one type of noun phrase (NP), which can appear in all positions (subject, ob- ject, etc.), regardless of case, number or gender. As a result, the grammar can generate millions of (in- correct) parse trees for a given sentence, and has a flat posterior distribution. High accuracy grammars therefore add soft constraints on the way categories can be combined, and enrich the label set with addi- tional information. These constraints can be lexical- ized (Collins, 1999; Charniak, 2000), unlexicalized (Johnson, 1998; Klein and Manning, 2003b) or au- tomatically learned (Matsuzaki et al., 2005; Petrov et al., 2006). The constraints serve the purpose of weakening the independence assumptions, and re- duce the number of possible (but incorrect) parses. Here, we focus on the latent variable approach of Petrov et al. (2006), where an Expectation Maxi- mization (EM) algorithm is used to induce a hier- archy of increasingly more refined grammars. Each round of refinement introduces new constraints on how constituents can be combined, which in turn leads to a higher parsing accuracy. However, EM is a local method, and there are no guarantees that it will find the same grammars when initialized from dif- ferent starting points. In fact, it turns out that even though the final performance of these grammars is consistently high, there are significant variations in the learned refinements. We use these variations to our advantage, and treat grammars learned from different random seeds as independent and equipotent experts. We use a product distribution for joint prediction, which gives more peaked posteriors than a sum, and enforces all constraints of the individual grammars, without the need to tune mixing weights. It should be noted here that our focus is on improving parsing performance …

Content truncated to 500 words