Annealing Structural Bias in Multilingual Weighted Grammar Induction

Proceedings of the 21st International Conference on Computational Linguistics and 44th Annual Meeting of the ACL, pages 569–576, Sydney, July 2006. c⃝2006 Association for Computational Linguistics Annealing Structural Bias in Multilingual Weighted Grammar Induction∗ Noah A. Smith and Jason Eisner Department of Computer Science / Center for Language and Speech Processing Johns Hopkins University, Baltimore, MD 21218 USA {nasmith,jason}@cs.jhu.edu Abstract We first show how a structural locality bias can improve the accuracy of state-of-the-art dependency grammar induction models trained by EM from unannotated examples (Klein and Manning, 2004). Next, by annealing the free parame- ter that controls this bias, we achieve further improvements. We then describe an alternative kind of structural bias, to- ward “broken” hypotheses consisting of partial structures over segmented sentences, and show a similar pattern of im- provement. We relate this approach to contrastive estimation (Smith and Eisner, 2005a), apply the latter to grammar in- duction in six languages, and show that our new approach improves accuracy by 1–17% (absolute) over CE (and 8–30% over EM), achieving to our knowledge the best results on this task to date. Our method, structural annealing, is a gen- eral technique with broad applicability to hidden-structure discovery problems. 1 Introduction Inducing a weighted context-free grammar from flat text is a hard problem. A common start- ing point for weighted grammar induction is the Expectation-Maximization (EM) algorithm (Dempster et al., 1977; Baker, 1979). EM’s mediocre performance (Table 1) reflects two prob- lems. First, it seeks to maximize likelihood, but a grammar that makes the training data likely does not necessarily assign a linguistically defensible syntactic structure. Second, the likelihood surface is not globally concave, and learners such as the EM algorithm can get trapped on local maxima (Charniak, 1993). We seek here to capitalize on the intuition that, at least early in learning, the learner should search primarily for string-local structure, because most structure is local.1 By penalizing dependencies be- tween two words that are farther apart in the string, we obtain consistent improvements in accuracy of the learned model (§3). We then explore how gradually changing δ over time affects learning (§4): we start out with a ∗This work was supported by a Fannie and John Hertz Foundation fellowship to the first author and NSF ITR grant IIS-0313193 to the second author. The views expressed are not necessarily endorsed by the sponsors. We thank three anonymous COLING-ACL reviewers for comments. 1To be concrete, in the corpora tested here, 95% of de- pendency links cover ≤ 4 words (English, Bulgarian, Por- tuguese), ≤ 5 words (German, Turkish), ≤ 6 words (Man- darin). model selection among values of λ and Θ(0) worst unsup. sup. oracle German 19.8 19.8 54.4 54.4 English 21.8 41.6 41.6 42.0 Bulgarian 24.7 44.6 45.6 45.6 Mandarin 31.8 37.2 50.0 50.0 Turkish 32.1 41.2 48.0 51.4 Portuguese 35.4 37.4 42.3 43.0 Table 1: Baseline performance of EM-trained dependency parsing models: F1 on non-$ attachments in test data, with various model selection conditions (3 initializers × 6 smooth- ing values). …

Content truncated to 500 words