Unsupervised Induction of Tree Substitution Grammars for Dependency Parsing

Proceedings of the 2010 Conference on Empirical Methods in Natural Language Processing, pages 1204–1213, MIT, Massachusetts, USA, 9-11 October 2010. c⃝2010 Association for Computational Linguistics Unsupervised Induction of Tree Substitution Grammars for Dependency Parsing Phil Blunsom Computing Laboratory University of Oxford Phil.Blunsom@comlab.ox.ac.uk Trevor Cohn Department of Computer Science University of Sheffield T.Cohn@dcs.shef.ac.uk Abstract Inducing a grammar directly from text is one of the oldest and most challenging tasks in Computational Linguistics. Significant progress has been made for inducing depen- dency grammars, however the models em- ployed are overly simplistic, particularly in comparison to supervised parsing models. In this paper we present an approach to depen- dency grammar induction using tree substi- tution grammar which is capable of learn- ing large dependency fragments and thereby better modelling the text. We define a hi- erarchical non-parametric Pitman-Yor Process prior which biases towards a small grammar with simple productions. This approach sig- nificantly improves the state-of-the-art, when measured by head attachment accuracy. 1 Introduction Grammar induction is a central problem in Compu- tational Linguistics, the aim of which is to induce linguistic structures from an unannotated text cor- pus. Despite considerable research effort this un- supervised problem remains largely unsolved, par- ticularly for traditional phrase-structure parsing ap- proaches (Clark, 2001; Klein and Manning, 2002). Phrase-structure parser induction is made difficult due to two types of ambiguity: the constituent struc- ture and the constituent labels. In particular the con- stituent labels are highly ambiguous, firstly we don’t know a priori how many there are, and secondly la- bels that appear high in a tree (e.g., an S category for a clause) rely on the correct inference of all the latent labels below them. However recent work on the induction of dependency grammars has proved more fruitful (Klein and Manning, 2004). Depen- dency grammars (Mel′ˇcuk, 1988) should be easier to induce from text compared to phrase-structure gram- mars because the set of labels (heads) are directly observed as the words in the sentence. Approaches to unsupervised grammar induction, both for phrase-structure and dependency grammars, have typically used very simplistic models (Clark, 2001; Klein and Manning, 2004), especially in com- parison to supervised parsing models (Collins, 2003; Clark and Curran, 2004; McDonald, 2006). Sim- ple models are attractive for grammar induction be- cause they have a limited capacity to overfit, how- ever they are incapable of modelling many known linguistic phenomena. We posit that more complex grammars could be used to better model the unsuper- vised task, provided that active measures are taken to prevent overfitting. In this paper we present an approach to dependency grammar induction using a tree-substitution grammar (TSG) with a Bayesian non-parametric prior. This allows the model to learn large dependency fragments to best describe the text, with the prior biasing the model towards fewer and smaller grammar productions. We adopt the split-head construction (Eisner, 2000; Johnson, 2007) to map dependency parses to context free grammar (CFG) derivations, over which we apply a model of TSG induction (Cohn et al., 2009). The …

Content truncated to 500 words