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

Student Name : Valentin Spitkovsky
Advisor : Daniel Jurafsky
Research Areas: Artificial Intelligence
We present new training methods that aim to mitigate local optima and slow convergence in unsupervised training by using additional imperfect objectives. In its simplest form, lateen EM alternates between the two objectives of ordinary “soft” and “hard” expectation maximization (EM) algorithms. Switching objectives when stuck can help escape local optima. We find that applying a single such alternation already yields state-of-the-art results for English dependency grammar induction. More elaborate lateen strategies track both objectives, with each validating the moves proposed by the other. Disagreements can signal earlier opportunities to switch or terminate, saving iterations. De-emphasizing fixed points in these ways eliminates some guesswork from tuning EM. An evaluation against a suite of unsupervised dependency parsing tasks, for a variety of languages, showed that lateen strategies significantly speed up training of both EM algorithms, and improve accuracy for hard EM.

Born in Odessa, USSR, Valentin became a Hertz Fellow in 1999, having graduated from MIT with an SB in mathematics and a minor in psychology. In his first year as a Fellow, Val completed an SB in computer science and engineering, an SB in economics, and an MEng in electrical engineering and computer science—his research in computational biology culminated in 2000 in a master’s thesis: A Fast Genomic Dictionary.

In the summer of 2000 Valentin left MIT and pulled a brief stint at a Silicon Valley start-up that went belly up in the .com bust, early in 2001. Val then joined Google Inc. and worked on various aspects of its advertising system, scalable spam-fighting, and statistical machine translation. While serving as a Software Engineer he earned an MS in Statistics from Stanford University. As of 2008, Val is pursuing a PhD, applying Machine Learning techniques to problems of Natural Language Processing.

A medal at the International Olympiad in Informatics crowned Valentin’s high school career. His five years at MIT led to statistical algorithms for gene recognition and annotation, hastening the already accelerated pace of the Human Genome Project. While in industry, Val continued to make forays onto the world stage, as a core member of several small, dedicated teams, delivering (i) arguably the most profitable and targeted advertising system the world had seen; (ii) an automated anti-spam system widely regarded as best in the world; and (iii) a machine translation engine that consistently outshined all competition at international evaluations organized by NIST.

Valentin’s new research tackles unsupervised grammar induction. He hopes to develop high quality, efficient algorithms for automatic machine learning of language and grammar models from very large quantities of raw text. Successful solutions would find immediate applications in machine translation and information retrieval; less obvious uses would likely arise in the contexts of other language technologies as well.