Improved Inference for Unlexicalized Parsing

Proceedings of NAACL HLT 2007, pages 404–411, Rochester, NY, April 2007. c⃝2007 Association for Computational Linguistics Improved Inference for Unlexicalized 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 several improvements to unlexicalized parsing with hierarchically state-split PCFGs. First, we present a novel coarse-to-fine method in which a grammar’s own hierarchical projections are used for incremental pruning, including a method for ef- ficiently computing projections of a grammar with- out a treebank. In our experiments, hierarchical pruning greatly accelerates parsing with no loss in empirical accuracy. Second, we compare various inference procedures for state-split PCFGs from the standpoint of risk minimization, paying particular attention to their practical tradeoffs. Finally, we present multilingual experiments which show that parsing with hierarchical state-splitting is fast and accurate in multiple languages and domains, even without any language-specific tuning. 1 Introduction Treebank parsing comprises two problems: learn- ing, in which we must select a model given a tree- bank, and inference, in which we must select a parse for a sentence given the learned model. Pre- vious work has shown that high-quality unlexical- ized PCFGs can be learned from a treebank, either by manual annotation (Klein and Manning, 2003) or automatic state splitting (Matsuzaki et al., 2005; Petrov et al., 2006). In particular, we demon- strated in Petrov et al. (2006) that a hierarchically split PCFG could exceed the accuracy of lexical- ized PCFGs (Collins, 1999; Charniak and Johnson, 2005). However, many questions about inference with such split PCFGs remain open. In this work, we present 1. an effective method for pruning in split PCFGs 2. a comparison of objective functions for infer- ence in split PCFGs, 3. experiments on automatic splitting for lan- guages other than English. In Sec. 3, we present a novel coarse-to-fine pro- cessing scheme for hierarchically split PCFGs. Our method considers the splitting history of the final grammar, projecting it onto its increasingly refined prior stages. For any projection of a grammar, we give a new method for efficiently estimating the pro- jection’s parameters from the source PCFG itself (rather than a treebank), using techniques for infi- nite tree distributions (Corazza and Satta, 2006) and iterated fixpoint equations. We then parse with each refinement, in sequence, much along the lines of Charniak et al. (2006), except with much more com- plex and automatically derived intermediate gram- mars. Thresholds are automatically tuned on held- out data, and the final system parses up to 100 times faster than the baseline PCFG parser, with no loss in test set accuracy. In Sec. 4, we consider the well-known issue of inference objectives in split PCFGs. As in many model families (Steedman, 2000; Vijay-Shanker and Joshi, 1985), split PCFGs have a derivation / parse distinction. The split PCFG directly describes a gen- erative model over derivations, but evaluation is sen- sitive only to the coarser treebank symbols. While the most probable parse problem is NP-complete (Sima’an, 1992), several approximate methods exist, …

Content truncated to 500 words