A comparison of Bayesian estimators for unsupervised Hidden Markov Model POS taggers

Jianfeng Gao, Mark JohnsonEMNLP 2008 · OpenReview

Abstract

There is growing interest in applying Bayesian techniques to NLP problems. There are a number of different estimators for Bayesian models, and it is useful to know what kinds of tasks each does well on. This paper compares a variety of different Bayesian estimators for Hidden Markov Model POS taggers with various numbers of hidden states on data sets of different sizes. Recent papers have given contradictory results when comparing Bayesian estimators to Expectation Maximization (EM) for unsupervised HMM POS tagging, and we show that the difference in reported results is largely due to differences in the size of the training data and the number of states in the HMM. We investigate a variety of samplers for HMMs, including some that these earlier papers did not study. We find that all of Gibbs samplers do well with small data sets and few states, and that Variational Bayes does well on large data sets and is competitive with the Gibbs samplers. In terms of times of convergence, we find that Variational Bayes was the fastest of all the estimators, especially on large data sets, and that explicit Gibbs sampler (both pointwise and sentence-blocked) were generally faster than their collapsed counterparts on large data sets.

Introduction

In the world of Natural Language Processing (NLP), unsupervised Part-of-Speech (POS) tagging—learning to categorize words without labeled training data—is a classic challenge. For years, the standard tool was Expectation Maximization (EM), but EM is notorious for getting stuck in local optima.

Recently, Bayesian methods emerged as a promising alternative because they allow researchers to incorporate "priors"—mathematical preferences for certain types of models (e.g., preferring that a word usually belongs to only one POS tag). However, previous literature has been contradictory: some studies suggested Bayesian methods were slow and underperformed EM, while others found them significantly superior. This study resolves these discrepancies by systematically varying data size and model parameters.

Methodology

The study compares several estimators for Hidden Markov Models (HMMs):

  1. Expectation Maximization (EM): The frequentist baseline using the Inside-Outside algorithm.
  2. Variational Bayes (VB): A fast approximation of the Bayesian posterior that minimizes "Variational Free Energy."
  3. Gibbs Samplers (MCMC): A 2x2 matrix of samplers was tested:
  4. Pointwise vs. Blocked: Pointwise resamples one word at a time ($O(nm)$ complexity), while Blocked resamples an entire sentence at once ($O(nm^2)$).
  5. Explicit vs. Collapsed: Explicit samplers track model parameters ($\theta, \phi$), while Collapsed samplers integrate them out to focus solely on hidden tags.

Experimental Setup

The study utilizes the Penn Treebank (Wall Street Journal) corpus, categorized into three sizes to test scalability:

  • All: The full ~1.1 million words.
  • 120K: A medium-sized subset.
  • 24K: A small subset.

Two different tag sets were evaluated: the full 50-state Penn Treebank set and a reduced 17-state set.

Key Results and Discussion

Data Size and Accuracy

The contradictions in previous research were largely due to scale. Bayesian methods and their priors are incredibly powerful on small datasets where EM struggles. On large datasets, the "signal" in the data overwhelms the prior, making EM much more competitive. As shown in the accuracy results below, Bayesian estimators outperformed EM by a wide margin on the 24K word dataset.

Table 5: Average greedy 1-to-1 accuracy across different estimators and data sizes. Bayesian methods show a clear advantage on smaller (24K) datasets.

Convergence and Speed

Variational Bayes consistently converged faster than any other estimator, especially on large datasets, while remaining competitive in accuracy with the more computationally expensive Gibbs samplers.

Furthermore, the study challenges the "Collapsed Efficiency Myth." While collapsed samplers are often preferred for reducing variance, explicit samplers were found to be faster for large-scale HMMs. Explicit samplers avoid the massive computational overhead of re-calculating probabilities on the fly for every word. Convergence behavior is further detailed in the following plots, where blocked samplers eventually overtake pointwise samplers in finding higher-probability solutions.

Figure 2: Comparison of convergence speed. The top graph shows negative log posterior probability over time; the bottom shows accuracy.

Conclusion

The "winner" in unsupervised POS tagging depends heavily on the size of the training data and model complexity. Bayesian methods are essential for small-data regimes, while Variational Bayes offers the best balance of speed and performance for large-scale applications. Future work may explore hybrid samplers that combine the early speed of pointwise sampling with the long-term stability of blocked sampling.

Summary updated

Abstract

There is growing interest in applying Bayesian techniques to NLP problems. There are a number of different estimators for Bayesian models, and it is useful to know what kinds of tasks each does well on. This paper compares a variety of different Bayesian estimators for Hidden Markov Model POS taggers with various numbers of hidden states on data sets of different sizes. Recent papers have given contradictory results when comparing Bayesian estimators to Expectation Maximization (EM) for unsupervised HMM POS tagging, and we show that the difference in reported results is largely due to differences in the size of the training data and the number of states in the HMM. We invesigate a variety of samplers for HMMs, including some that these earlier papers did not study. We find that all of Gibbs samplers do well with small data sets and few states, and that Variational Bayes does well on large data sets and is competitive with the Gibbs samplers. In terms of times of convergence, we find that Variational Bayes was the fastest of all the estimators, especially on large data sets, and that explicit Gibbs sampler (both pointwise and sentence-blocked) were generally faster than their collapsed counterparts on large data sets.
BibTeX
@inproceedings{gao2008comparison,
  author = {Jianfeng Gao and Mark Johnson},
  title = {{A comparison of Bayesian estimators for unsupervised Hidden Markov Model POS taggers}},
  booktitle = {Conference on Empirical Methods in Natural Language Processing},
  year = {2008},
  url = {https://openreview.net/forum?id=B1ZRuGMOZB},
}
Figure