TL;DR
This paper investigates why standard Expectation-Maximization (EM) algorithms struggle to produce accurate Part-of-Speech (POS) taggers from unlabeled text. The authors find that EM's tendency to create uniform hidden state distributions, unlike the skewed nature of real POS tags, is a key issue. They propose and evaluate Bayesian approaches (Gibbs Sampling and Variational Bayes) and a simpler EM modification (reducing hidden states) that significantly improve POS tagging accuracy.
What Problem Does This Paper Address?
Unsupervised learning aims to extract structure from data without explicit labels. A fundamental task in this area is Part-of-Speech (POS) tagging, where the goal is to assign grammatical categories (like noun, verb, adjective) to words in a sentence. While Hidden Markov Models (HMMs) are a common framework for this, training them using the standard Expectation-Maximization (EM) algorithm on unlabeled data often yields poor results. This paper seeks to understand why EM fails in this context and explore alternative methods to achieve better unsupervised POS tagging. The core challenge is that EM, by optimizing the likelihood of the observed data, tends to create a "flat" distribution of hidden states, meaning each state is used roughly equally. This contrasts sharply with the real-world distribution of POS tags, where a few tags (like nouns and verbs) are extremely common, and many others are rare.
Methods
The paper compares several methods for estimating HMMs for POS tagging:
- Expectation-Maximization (EM): The standard, likelihood-based approach. The authors implement this using the Forward-Backward algorithm.
- Bayesian Estimation (Gibbs Sampling - GS and Variational Bayes - VB): These methods incorporate prior beliefs about the model parameters. The authors use Dirichlet priors, which are conjugate to multinomials and naturally encourage sparsity (i.e., favoring skewed distributions).
- Gibbs Sampling (GS): A Markov Chain Monte Carlo (MCMC) method that samples from the posterior distribution.
- Variational Bayes (VB): An approximation method that finds a simpler, factorized distribution that is close to the true posterior. The authors adapt VB for HMMs, showing it's computationally similar to EM.
- EM with Reduced Hidden States: A simpler modification where EM is run with a significantly smaller number of hidden states, forcing them to be more densely populated.
Datasets
The experiments were conducted using the Penn Treebank (PTB) Wall Street Journal corpus. This corpus is used for both training the HMMs and for evaluation, with the gold-standard POS tags serving as the ground truth. No new benchmarks were introduced.
Key Insights and Ideas
- EM's "Flatness" Problem: The primary reason EM struggles is its tendency to assign roughly equal numbers of word tokens to each hidden state. This "flat" distribution is fundamentally at odds with the highly skewed, Zipfian distribution of actual POS tags in natural language.
- Bayesian Priors as a Solution: By using Dirichlet priors in Bayesian methods (GS and VB), the authors can bias the estimation towards more skewed distributions, mimicking the natural distribution of POS tags. This significantly improves performance.
- Variational Bayes Efficiency: VB is shown to be computationally efficient, converging much faster than Gibbs Sampling for this task.
- Reducing States as a Simple Fix: Surprisingly, simply reducing the number of hidden states in EM can dramatically improve 1-to-1 accuracy. This forces states to be more specialized, even if it means missing rare POS tags.
- High Variance and Slow Convergence: All tested estimators (EM, VB, GS) exhibit significant variance across different random initializations and require many more iterations than typically assumed to reach optimal performance.
Key Results
- EM Performance: EM performs competitively on "many-to-1" accuracy (where multiple hidden states can map to one POS tag) and Variation of Information, but poorly on "1-to-1" accuracy (where each hidden state ideally maps to a unique POS tag).
- Bayesian Improvement: VB with appropriate Dirichlet priors (e.g., $\alpha_x = 0.1$) significantly boosts 1-to-1 accuracy, reaching up to 47% (compared to EM's ~40%).
- Reduced States Improvement: EM with a reduced number of hidden states (e.g., 25 states) achieves performance comparable to the best VB models on 1-to-1 accuracy and VI, while being faster.
- Convergence: Optimal performance for all methods is often achieved only after several hundred iterations, with significant accuracy gains observed even after 100 iterations.
- Variance: All estimators show considerable variance, necessitating multiple runs for reliable evaluation.
Limitations and Future Work
- Computational Cost: Running multiple estimators for thousands of iterations is computationally intensive. The authors note that exploring a wider range of prior parameters for VB and GS was limited by resources.
- Ad Hoc Nature of State Reduction: While effective, reducing the number of states in EM is somewhat ad hoc and might lead to missing rare POS tags.
- Future Work: The authors suggest exploring more sophisticated ways to improve accuracy, such as using distributional clustering to group similar HMM states after initial EM inference. They also point to the potential of other Bayesian priors, like "entropic priors," to encode linguistic knowledge. The idea of Bayesian priors determining the number of states, as seen in infinite HMMs, is also highlighted as a promising direction.
Summary updated