Annealing Techniques For Unsupervised Statistical Language Learning

Noah A. Smith, Jason EisnerACL 2004 · OpenReview

Abstract

Exploiting unannotated natural language data is hard largely because unsupervised parameter estimation is hard. We describe deterministic annealing (Rose et al., 1990) as an appealing alternative to the Expectation-Maximization algorithm (Dempster et al., 1977). Seeking to avoid search error, DA begins by globally maximizing an easy concave function and maintains a local maximum as it gradually morphs the function into the desired non-concave likelihood function. Applying DA to parsing and tagging models is shown to be straightforward; significant improvements over EM are shown on a part-of-speech tagging task. We describe a variant, skewed DA, which can incorporate a good initializer when it is available, and show significant improvements over EM on a grammar induction task.

Introduction

In unsupervised language learning, the primary challenge lies in estimating model parameters from unlabeled data. The standard approach utilizes the Expectation-Maximization (EM) algorithm, a "hill-climbing" method that iteratively improves likelihood. However, EM is highly sensitive to its starting point. In natural language processing (NLP), likelihood functions are frequently "riddled with suboptimal local maxima"—small peaks that trap the algorithm and prevent it from reaching the global maximum. Furthermore, maximizing likelihood does not always correlate perfectly with achieving the highest task accuracy. This research seeks a search method that is less sensitive to initial conditions and more likely to find high-quality, globally optimal solutions.

Methodology

The authors propose Deterministic Annealing (DA), a technique inspired by statistical physics, as a robust alternative to EM. DA introduces a parameter $\beta$ (analogous to inverse temperature) to control the complexity of the objective function.

  • Gradated Difficulty: When $\beta$ is near 0, the objective function is concave and easy to solve, resulting in a uniform distribution over all possible hidden structures (like tags or trees). As $\beta$ is gradually increased toward 1, the function "morphs" into the standard, non-concave likelihood function.
  • "Riding the Maximum": By tracking the maximum as the function changes, DA effectively "rides" the global peak from the simple version of the problem to the complex one.
Learning curves for EM and DA showing the stepwise progression of the DA algorithm.

DA also acts as a form of regularization. By finding local maxima with higher Shannon entropy, it prevents the model from overcommitting to specific hidden sequences too early, leading to better generalization. For cases where a helpful prior bias is available, the authors introduce Skewed Deterministic Annealing (SDA). SDA modifies the E-step to interpolate between the model's current state and a "skew" distribution (the initializer) rather than a uniform one, allowing for a cautious exploration that respects prior knowledge.

Experimental Results

The methods were evaluated using the Wall Street Journal (WSJ) portion of the Penn Treebank for two primary tasks: Part-of-Speech (POS) tagging and Grammar Induction.

Part-of-Speech Tagging

On a trigram POS tagging task using approximately 1.1 million words for training, DA demonstrated superior performance over standard EM. Specifically, DA achieved a 10% reduction in tag error rate on training data and an 11% reduction on test data. As shown in the results table, DA's advantage is particularly pronounced in the accuracy of ambiguous test tags.

Comparative performance of EM and DA on the part-of-speech tagging task.

Grammar Induction

Using the Constituent-Context Model (CCM) on the WSJ-10 corpus, SDA significantly outperformed EM. In the improved "Model 2," SDA achieved an F-measure of 68.03%, compared to EM's 67.10%. Furthermore, SDA showed a significant reduction in "crossing brackets," a key measure of structural error. In jack-knifed trials, SDA exhibited much lower variance than EM, suggesting it is a more stable and reliable optimizer for complex grammar models.

Discussion and Conclusion

While DA and SDA offer significant improvements in accuracy and stability, they come with a higher computational cost. These methods require an outer loop to iterate over values of $\beta$, leading to significantly more E-steps (e.g., 1200 steps for DA vs. 279 for EM in the POS task). Additionally, the authors acknowledge the "likelihood gap": even if DA finds the global maximum of the likelihood function, that maximum might not perfectly correspond to the highest linguistic accuracy.

Future work may explore "quenching" (pushing $\beta$ beyond 1 to create a winner-take-all effect) and applying these techniques to broader domains such as machine translation or large-scale parsing. Despite the increased computational requirements, the ease of implementation for any model already using EM makes DA and SDA appealing tools for unsupervised NLP tasks.

Summary updated

Abstract

Exploiting unannotated natural language data is hard largely because unsupervised parameter estimation is hard. We describe deterministic annealing (Rose et al., 1990) as an appealing alternative to the Expectation-Maximization algorithm (Dempster et al., 1977). Seeking to avoid search error, DA begins by globally maximizing an easy concave function and maintains a local maximum as it gradually morphs the function into the desired non-concave likelihood function. Applying DA to parsing and tagging models is shown to be straightforward; significant improvements over EM are shown on a part-of-speech tagging task. We describe a variant, skewed DA, which can incorporate a good initializer when it is available, and show significant improvements over EM on a grammar induction task.
BibTeX
@inproceedings{smith2004annealing,
  author = {Noah A. Smith and Jason Eisner},
  title = {{Annealing Techniques For Unsupervised Statistical Language Learning}},
  booktitle = {Annual Meeting of the Association for Computational Linguistics},
  year = {2004},
  url = {https://openreview.net/forum?id=rkE-oix_-H},
}
Figure