Online EM for Unsupervised Models

Percy Liang, Dan KleinNAACL 2009 · OpenReview

Abstract

The Expectation-Maximization (EM) algorithm is a cornerstone of unsupervised induction, yet it often suffers from slow convergence and susceptibility to poor local optima. This paper evaluates online variants of EM, specifically Stepwise EM (sEM), across four diverse NLP tasks: part-of-speech tagging, document classification, word segmentation, and word alignment. We demonstrate that sEM not only provides significant speedups (up to 10x) but also frequently discovers superior solutions compared to traditional batch EM.

Introduction

Unsupervised learning from raw text typically relies on the EM algorithm to maximize the likelihood of observed data. However, standard "batch" EM updates parameters only after a complete pass through the dataset, which is computationally inefficient for large-scale data. Moreover, the non-convex nature of the EM objective often leads to linguistically suboptimal local maxima. This work investigates whether online updates can mitigate these issues by providing faster convergence and better exploration of the parameter space.

Methodology

We compare three primary algorithms:

  1. Batch EM: The standard baseline that updates parameters once per full iteration.
  2. Incremental EM (iEM): Updates parameters after each example by maintaining sufficient statistics for the entire dataset. While theoretically sound, its memory requirements scale linearly with the number of examples, limiting its practical use.
  3. Stepwise EM (sEM): An online variant that updates parameters after each mini-batch by interpolating new statistics with existing ones using a decaying stepsize $\eta_k = (k+2)^{-\alpha}$. sEM is memory-efficient and introduces stochasticity that helps escape local optima.

Additionally, we propose a penalized unigram model for word segmentation and a fast implementation for sEM that leverages sparse updates.

Experimental Setup

The algorithms were evaluated on:

  • Part-of-Speech (POS) Tagging: Bigram HMM on the Penn Treebank WSJ corpus.
  • Document Classification: Bag-of-words model on the 20 Newsgroups dataset.
  • Word Segmentation: Penalized unigram model on English (Bernstein-Ratner) and Chinese (Academia Sinica) corpora.
  • Word Alignment: IBM Model 1 on English-French Hansards.

Results and Discussion

Our experiments reveal that sEM consistently outperforms batch EM in terms of convergence speed and often in final accuracy.

Speed and Accuracy Gains

sEM achieved convergence 2x to 10x faster than batch EM across all evaluated tasks. The most significant improvement was observed in POS tagging, where sEM reached 65.4% accuracy in just two iterations, whereas batch EM required 100 iterations to reach only 57.3%.

Performance of sEM vs Batch EM on POS tagging. sEM_l shows a rapid increase in accuracy compared to the slow progression of Batch EM.

Clustering vs. Structural Tasks

A key insight is the performance difference between "clustering" tasks (POS tagging, document classification) and "structural" tasks (segmentation, alignment). sEM provides massive gains in clustering tasks where the model learns associations with latent labels. In contrast, structural tasks, which are more constrained by combinatorial properties, see more modest improvements.

Final results after convergence across all tasks. The table highlights the accuracy and log-likelihood improvements of sEM_l over Batch EM.

Hyperparameter Sensitivity

The effectiveness of sEM depends on the mini-batch size ($m$) and the stepsize power ($\alpha$). We found that these can be effectively tuned by maximizing training data likelihood, eliminating the need for labeled validation data.

Conclusion

Stepwise EM is a powerful alternative to batch EM for unsupervised NLP. Its ability to provide rapid convergence and find better local optima makes it particularly suitable for large-scale clustering-based induction tasks. Future work will explore theoretical explanations for the performance gap between clustering and structural tasks and investigate hybrid online-batch approaches.

Summary updated

Abstract

The (batch) EM algorithm plays an important role in unsupervised induction, but it sometimes suffers from slow convergence. In this paper, we show that online variants (1) provide significant speedups and (2) can even find better solutions than those found by batch EM. We support these findings on four unsupervised tasks: part-of-speech tagging, document classification, word segmentation, and word alignment.
BibTeX
@inproceedings{liang2009online,
  author = {Percy Liang and Dan Klein},
  title = {{Online EM for Unsupervised Models}},
  booktitle = {Conference of the North American Chapter of the Association for Computational Linguistics},
  year = {2009},
  url = {https://openreview.net/forum?id=SybWLX-uWH},
}
Figure