Inducing Compact but Accurate Tree-Substitution Grammars

Human Language Technologies: The 2009 Annual Conference of the North American Chapter of the ACL, pages 548–556, Boulder, Colorado, June 2009. c⃝2009 Association for Computational Linguistics Inducing Compact but Accurate Tree-Substitution Grammars Trevor Cohn and Sharon Goldwater and Phil Blunsom School of Informatics University of Edinburgh 10 Crichton Street, Edinburgh EH8 9AB Scotland, United Kingdom {tcohn,sgwater,pblunsom}@inf.ed.ac.uk Abstract Tree substitution grammars (TSGs) are a com- pelling alternative to context-free grammars for modelling syntax. However, many popu- lar techniques for estimating weighted TSGs (under the moniker of Data Oriented Parsing) suffer from the problems of inconsistency and over-fitting. We present a theoretically princi- pled model which solves these problems us- ing a Bayesian non-parametric formulation. Our model learns compact and simple gram- mars, uncovering latent linguistic structures (e.g., verb subcategorisation), and in doing so far out-performs a standard PCFG. 1 Introduction Many successful models of syntax are based on Probabilistic Context Free Grammars (PCFGs) (e.g., Collins (1999)). However, directly learning a PCFG from a treebank results in poor parsing perfor- mance, due largely to the unrealistic independence assumptions imposed by the context-free assump- tion. Considerable effort is required to coax good results from a PCFG, in the form of grammar en- gineering, feature selection and clever smoothing (Collins, 1999; Charniak, 2000; Charniak and John- son, 2005; Johnson, 1998). This effort must be re- peated when moving to different languages, gram- mar formalisms or treebanks. We propose that much of this hand-coded knowledge can be obtained auto- matically as an emergent property of the treebanked data, thereby reducing the need for human input in crafting the grammar. We present a model for automatically learning a Probabilistic Tree Substitution Grammar (PTSG), an extension to the PCFG in which non-terminals can rewrite as entire tree fragments (elementary trees), not just immediate children. These large frag- ments can be used to encode non-local context, such as head-lexicalisation and verb sub-categorisation. Since no annotated data is available providing TSG derivations we must induce the PTSG productions and their probabilities in an unsupervised way from an ordinary treebank. This is the same problem ad- dressed by Data Oriented Parsing (DOP, Bod et al. (2003)), a method which uses as productions all sub- trees of the training corpus. However, many of the DOP estimation methods have serious shortcomings (Johnson, 2002), namely inconsistency for DOP1 (Bod, 2003) and overfitting of the maximum like- lihood estimate (Prescher et al., 2004). In this paper we develop an alternative means of learning a PTSG from a treebanked corpus, with the twin objectives of a) finding a grammar which ac- curately models the data and b) keeping the gram- mar as simple as possible, with few, compact, ele- mentary trees. This is achieved using a prior to en- courage sparsity and simplicity in a Bayesian non- parametric formulation. The framework allows us to perform inference over an infinite space of gram- mar productions in an elegant and efficient manner. The net result is a grammar which only uses the in- creased context afforded by …

Content truncated to 500 words