Lateen EM: Unsupervised Training with Multiple Objectives, Applied to Dependency Grammar Induction

Proceedings of the 2011 Conference on Empirical Methods in Natural Language Processing, pages 1269–1280, Edinburgh, Scotland, UK, July 27–31, 2011. c⃝2011 Association for Computational Linguistics Lateen EM: Unsupervised Training with Multiple Objectives, Applied to Dependency Grammar Induction Valentin I. Spitkovsky Computer Science Department Stanford University and Google Inc. valentin@cs.stanford.edu Hiyan Alshawi Google Inc. Mountain View, CA, 94043, USA hiyan@google.com Daniel Jurafsky Departments of Linguistics and Computer Science Stanford University, Stanford, CA, 94305, USA jurafsky@stanford.edu Abstract We present new training methods that aim to mitigate local optima and slow convergence in unsupervised training by using additional im- perfect objectives. In its simplest form, lateen EM alternates between the two objectives of ordinary “soft” and “hard” expectation max- imization (EM) algorithms. Switching objec- tives when stuck can help escape local optima. We find that applying a single such alternation already yields state-of-the-art results for En- glish dependency grammar induction. More elaborate lateen strategies track both objec- tives, with each validating the moves proposed by the other. Disagreements can signal earlier opportunities to switch or terminate, saving it- erations. De-emphasizing fixed points in these ways eliminates some guesswork from tuning EM. An evaluation against a suite of unsu- pervised dependency parsing tasks, for a vari- ety of languages, showed that lateen strategies significantly speed up training of both EM al- gorithms, and improve accuracy for hard EM. 1 Introduction Expectation maximization (EM) algorithms (Demp- ster et al., 1977) play important roles in learning latent linguistic structure. Unsupervised techniques from this family excel at core natural language pro- cessing (NLP) tasks, including segmentation, align- ment, tagging and parsing. Typical implementations specify a probabilistic framework, pick an initial model instance, and iteratively improve parameters using EM. A key guarantee is that subsequent model instances are no worse than the previous, according to training data likelihood in the given framework. Another attractive feature that helped make EM instrumental (Meng, 2007) is its initial efficiency: Training tends to begin with large steps in a param- eter space, sometimes bypassing many local optima at once. After a modest number of such iterations, however, EM lands close to an attractor. Next, its convergence rate necessarily suffers: Disproportion- ately many (and ever-smaller) steps are needed to finally approach this fixed point, which is almost in- variably a local optimum. Deciding when to termi- nate EM often involves guesswork; and finding ways out of local optima requires trial and error. We pro- pose several strategies that address both limitations. Unsupervised objectives are, at best, loosely cor- related with extrinsic performance (Pereira and Sch- abes, 1992; Merialdo, 1994; Liang and Klein, 2008, inter alia). This fact justifies (occasionally) devi- ating from a prescribed training course. For exam- ple, since multiple equi-plausible objectives are usu- ally available, a learner could cycle through them, optimizing alternatives when the primary objective function gets stuck; or, instead of trying to escape, it could aim to avoid local optima in the first place, by halting search early if an improvement to one objec- tive would come at …

Content truncated to 500 words