A Generative Constituent-Context Model for Improved Grammar Induction

A Generative Constituent-Context Model for Improved Grammar Induction Dan Klein and Christopher D. Manning Computer Science Department Stanford University Stanford, CA 94305-9040 {klein, manning}@cs.stanford.edu Abstract We present a generative distributional model for the unsupervised induction of natural language syntax which explicitly models constituent yields and con- texts. Parameter search with EM produces higher quality analyses than previously exhibited by un- supervised systems, giving the best published un- supervised parsing results on the ATIS corpus. Ex- periments on Penn treebank sentences of compara- ble length show an even higher F1 of 71% on non- trivial brackets. We compare distributionally in- duced and actual part-of-speech tags as input data, and examine extensions to the basic model. We dis- cuss errors made by the system, compare the sys- tem to previous models, and discuss upper bounds, lower bounds, and stability for this task. 1 Introduction The task of inducing hierarchical syntactic structure from observed yields alone has received a great deal of attention (Carroll and Charniak, 1992; Pereira and Schabes, 1992; Brill, 1993; Stolcke and Omohun- dro, 1994). Researchers have explored this problem for a variety of reasons: to argue empirically against the poverty of the stimulus (Clark, 2001), to use in- duction systems as a first stage in constructing large treebanks (van Zaanen, 2000), or to build better lan- guage models (Baker, 1979; Chen, 1995). In previous work, we presented a conditional model over trees which gave the best published re- sults for unsupervised parsing of the ATIS corpus (Klein and Manning, 2001b). However, it suffered from several drawbacks, primarily stemming from the conditional model used for induction. Here, we improve on that model in several ways. First, we construct a generative model which utilizes the same features. Then, we extend the model to allow mul- tiple constituent types and multiple prior distribu- tions over trees. The new model gives a 13% reduc- tion in parsing error on WSJ sentence experiments, including a positive qualitative shift in error types. Additionally, it produces much more stable results, does not require heavy smoothing, and exhibits a re- liable correspondence between the maximized ob- jective and parsing accuracy. It is also much faster, not requiring a fitting phase for each iteration. Klein and Manning (2001b) and Clark (2001) take treebank part-of-speech sequences as input. We fol- lowed this for most experiments, but in section 4.3, we use distributionally induced tags as input. Perfor- mance with induced tags is somewhat reduced, but still gives better performance than previous models. 2 Previous Work Early work on grammar induction emphasized heu- ristic structure search, where the primary induction is done by incrementally adding new productions to an initially empty grammar (Olivier, 1968; Wolff, 1988). In the early 1990s, attempts were made to do grammar induction by parameter search, where the broad structure of the grammar is fixed in advance and only parameters are induced (Lari and Young, 1990; Carroll and Charniak, 1992).1 However, this appeared unpromising and most recent work has re- turned to using structure search. Note …

Content truncated to 500 words