Online EM for Unsupervised Models

Human Language Technologies: The 2009 Annual Conference of the North American Chapter of the ACL, pages 611–619, Boulder, Colorado, June 2009. c⃝2009 Association for Computational Linguistics Online EM for Unsupervised Models Percy Liang Dan Klein Computer Science Division, EECS Department University of California at Berkeley Berkeley, CA 94720 {pliang,klein}@cs.berkeley.edu Abstract The (batch) EM algorithm plays an important role in unsupervised induction, but it some- times suffers from slow convergence. In this paper, we show that online variants (1) provide significant speedups and (2) can even find bet- ter solutions than those found by batch EM. We support these findings on four unsuper- vised tasks: part-of-speech tagging, document classification, word segmentation, and word alignment. 1 Introduction In unsupervised NLP tasks such as tagging, parsing, and alignment, one wishes to induce latent linguistic structures from raw text. Probabilistic modeling has emerged as a dominant paradigm for these problems, and the EM algorithm has been a driving force for learning models in a simple and intuitive manner. However, on some tasks, EM can converge slowly. For instance, on unsupervised part-of- speech tagging, EM requires over 100 iterations to reach its peak performance on the Wall-Street Jour- nal (Johnson, 2007). The slowness of EM is mainly due to its batch nature: Parameters are updated only once after each pass through the data. When param- eter estimates are still rough or if there is high redun- dancy in the data, computing statistics on the entire dataset just to make one update can be wasteful. In this paper, we investigate two flavors of on- line EM—incremental EM (Neal and Hinton, 1998) and stepwise EM (Sato and Ishii, 2000; Capp´e and Moulines, 2009), both of which involve updating pa- rameters after each example or after a mini-batch (subset) of examples. Online algorithms have the potential to speed up learning by making updates more frequently. However, these updates can be seen as noisy approximations to the full batch up- date, and this noise can in fact impede learning. This tradeoff between speed and stability is famil- iar to online algorithms for convex supervised learn- ing problems—e.g., Perceptron, MIRA, stochastic gradient, etc. Unsupervised learning raises two ad- ditional issues: (1) Since the EM objective is non- convex, we often get convergence to different local optima of varying quality; and (2) we evaluate on accuracy metrics which are at best loosely correlated with the EM likelihood objective (Liang and Klein, 2008). We will see that these issues can lead to sur- prising results. In Section 4, we present a thorough investigation of online EM, mostly focusing on stepwise EM since it dominates incremental EM. For stepwise EM, we find that choosing a good stepsize and mini-batch size is important but can fortunately be done ade- quately without supervision. With a proper choice, stepwise EM reaches the same performance as batch EM, but much more quickly. Moreover, it can even surpass the performance of batch EM. Our results are particularly striking on part-of-speech tagging: Batch EM crawls to an accuracy of …

Content truncated to 500 words