Probabilistic Context-Free Grammar Induction Based on Structural Zeros

Proceedings of the Human Language Technology Conference of the North American Chapter of the ACL, pages 312–319, New York, June 2006. c⃝2006 Association for Computational Linguistics Probabilistic Context-Free Grammar Induction Based on Structural Zeros Mehryar Mohri Courant Institute of Mathematical Sciences and Google Research 251 Mercer Street New York, NY 10012 mohri@cs.nyu.edu Brian Roark Center for Spoken Language Understanding OGI at Oregon Health & Science University 20000 NW Walker Road Beaverton, Oregon 97006 roark@cslu.ogi.edu Abstract We present a method for induction of con- cise and accurate probabilistic context- free grammars for efficient use in early stages of a multi-stage parsing technique. The method is based on the use of statis- tical tests to determine if a non-terminal combination is unobserved due to sparse data or hard syntactic constraints. Ex- perimental results show that, using this method, high accuracies can be achieved with a non-terminal set that is orders of magnitude smaller than in typically induced probabilistic context-free gram- mars, leading to substantial speed-ups in parsing. The approach is further used in combination with an existing reranker to provide competitive WSJ parsing results. 1 Introduction There is a very severe speed vs. accuracy tradeoff in stochastic context-free parsing, which can be ex- plained by the grammar factor in the running-time complexity of standard parsing algorithms such as the CYK algorithm (Kasami, 1965; Younger, 1967). That algorithm has complexity O(n3|P|), where n is the length in words of the sentence parsed, and |P| is the number of grammar productions. Grammar non- terminals can be split to encode richer dependen- cies in a stochastic model and improve parsing ac- curacy. For example, the parent of the left-hand side (LHS) can be annotated onto the label of the LHS category (Johnson, 1998), hence differentiating, for instance, between expansions of a VP with parent S and parent VP. Such annotations, however, tend to substantially increase the number of grammar pro- ductions as well as the ambiguity of the grammar, thereby significantly slowing down the parsing algo- rithm. In the case of bilexical grammars, where cat- egories in binary grammars are annotated with their lexical heads, the grammar factor contributes an ad- ditional O(n2|VD|3) complexity, leading to an over- all O(n5|VD|3) parsing complexity, where |VD| is the number of delexicalized non-terminals (Eisner, 1997). Even with special modifications to the ba- sic CYK algorithm, such as those presented by Eis- ner and Satta (1999), improvements to the stochastic model are obtained at the expense of efficiency. In addition to the significant cost in efficiency, increasing the non-terminal set impacts parame- ter estimation for the stochastic model. With more productions, much fewer observations per production are available and one is left with the hope that a subsequent smoothing technique can effectively deal with this problem, regardless of the number of non-terminals created. Klein and Manning (2003b) showed that, by making certain linguistically-motivated node label annotations, but avoiding certain other kinds of state splits (mainly lexical annotations) models of relatively high accu- racy can be built without resorting to …

Content truncated to 500 words