Training Factored PCFGs with Expectation Propagation

Proceedings of the 2012 Joint Conference on Empirical Methods in Natural Language Processing and Computational Natural Language Learning, pages 1146–1156, Jeju Island, Korea, 12–14 July 2012. c⃝2012 Association for Computational Linguistics Training Factored PCFGs with Expectation Propagation David Hall and Dan Klein Computer Science Division University of California, Berkeley {dlwh,klein}@cs.berkeley.edu Abstract PCFGs can grow exponentially as additional annotations are added to an initially simple base grammar. We present an approach where multiple annotations coexist, but in a factored manner that avoids this combinatorial explo- sion. Our method works with linguistically- motivated annotations, induced latent struc- ture, lexicalization, or any mix of the three. We use a structured expectation propagation algorithm that makes use of the factored struc- ture in two ways. First, by partitioning the fac- tors, it speeds up parsing exponentially over the unfactored approach. Second, it minimizes the redundancy of the factors during training, improving accuracy over an independent ap- proach. Using purely latent variable annota- tions, we can efficiently train and parse with up to 8 latent bits per symbol, achieving F1 scores up to 88.4 on the Penn Treebank while using two orders of magnitudes fewer parame- ters compared to the na¨ıve approach. Combin- ing latent, lexicalized, and unlexicalized anno- tations, our best parser gets 89.4 F1 on all sen- tences from section 23 of the Penn Treebank. 1 Introduction Many high-performance PCFG parsers take an ini- tially simple base grammar over treebank labels like NP and enrich it with deeper syntactic features to improve accuracy. This broad characterization in- cludes lexicalized parsers (Collins, 1997), unlexical- ized parsers (Klein and Manning, 2003), and latent variable parsers (Matsuzaki et al., 2005). Figures 1(a), 1(b), and 1(c) show small examples of context- free trees that have been annotated in these ways. When multi-part annotations are used in the same grammar, systems have generally multiplied these annotations together, in the sense that an NP that was definite, possessive, and VP-dominated would have a single unstructured PCFG symbol that en- coded all three facts. In addition, modulo backoff or smoothing, that unstructured symbol would of- ten have rewrite parameters entirely distinct from, say, the indefinite but otherwise similar variant of the symbol (Klein and Manning, 2003). Therefore, when designing a grammar, one would have to care- fully weigh new contextual annotations. Should a definiteness annotation be included, doubling the number of NPs in the grammar and perhaps overly fragmenting statistics? Or should it be excluded, thereby losing important distinctions? Klein and Manning (2003) discuss exactly such trade-offs and omit annotations that were helpful on their own be- cause they were not worth the combinatorial or sta- tistical cost when combined with other annotations. In this paper, we argue for grammars with fac- tored annotations, that is, grammars with annota- tions that have structured component parts that are partially decoupled. Our annotated grammars can include both latent and explicit annotations, as illus- trated in Figure 1(d), and we demonstrate that these factored grammars outperform parsers with unstruc- tured annotations. After discussing …

Content truncated to 500 words