Phylogenetic Grammar Induction

Proceedings of the 48th Annual Meeting of the Association for Computational Linguistics, pages 1288–1297, Uppsala, Sweden, 11-16 July 2010. c⃝2010 Association for Computational Linguistics Phylogenetic Grammar Induction Taylor Berg-Kirkpatrick and Computer Science DivisionDan Klein University of California, Berkeley {tberg, klein}@cs.berkeley.edu Abstract We present an approach to multilin- gual grammar induction that exploits a phylogeny-structured model of parameter drift. Our method does not require any translated texts or token-level alignments. Instead, the phylogenetic prior couples languages at a parameter level. Joint in- duction in the multilingual model substan- tially outperforms independent learning, with larger gains both from more articu- lated phylogenies and as well as from in- creasing numbers of languages. Across eight languages, the multilingual approach gives error reductions over the standard monolingual DMV averaging 21.1% and reaching as high as 39%. 1 Introduction Learning multiple languages together should be easier than learning them separately. For exam- ple, in the domain of syntactic parsing, a range of recent work has exploited the mutual constraint between two languages’ parses of the same bi- text (Kuhn, 2004; Burkett and Klein, 2008; Kuz- man et al., 2009; Smith and Eisner, 2009; Sny- der et al., 2009a). Moreover, Snyder et al. (2009b) in the context of unsupervised part-of-speech in- duction (and Bouchard-Cˆot´e et al. (2007) in the context of phonology) show that extending be- yond two languages can provide increasing ben- efit. However, multitexts are only available for limited languages and domains. In this work, we consider unsupervised grammar induction without bitexts or multitexts. Without translation exam- ples, multilingual constraints cannot be exploited at the sentence token level. Rather, we capture multilingual constraints at a parameter level, us- ing a phylogeny-structured prior to tie together the various individual languages’ learning problems. Our joint, hierarchical prior couples model param- eters for different languages in a way that respects knowledge about how the languages evolved. Aspects of this work are closely related to Co- hen and Smith (2009) and Bouchard-Cˆot´e et al. (2007). Cohen and Smith (2009) present a model for jointly learning English and Chinese depen- dency grammars without bitexts. In their work, structurally constrained covariance in a logistic normal prior is used to couple parameters between the two languages. Our work, though also differ- ent in technical approach, differs most centrally in the extension to multiple languages and the use of a phylogeny. Bouchard-Cˆot´e et al. (2007) consid- ers an entirely different problem, phonological re- construction, but shares with this work both the use of a phylogenetic structure as well as the use of log-linear parameterization of local model com- ponents. Our work differs from theirs primarily in the task (syntax vs. phonology) and the vari- ables governed by the phylogeny: in our model it is the grammar parameters that drift (in the prior) rather than individual word forms (in the likeli- hood model). Specifically, we consider dependency induction in the DMV model of Klein and Manning (2004). Our data is a collection of standard dependency data sets in eight languages: English, Dutch, Dan- …

Content truncated to 500 words