Abstract
Unsupervised learning of linguistic structure is a difficult problem. A common approach is to define a generative model and maximize the probability of the hidden structure given the observed data. Typically, this is done using maximum-likelihood estimation (MLE) of the model parameters. We show using part-of-speech tagging that a fully Bayesian approach can greatly improve performance. Rather than estimating a single set of parameters, the Bayesian approach integrates over all possible parameter values. This difference ensures that the learned structure will have high probability over a range of possible parameters, and permits the use of priors favoring the sparse distributions that are typical of natural language. Our model has the structure of a standard trigram HMM, yet its accuracy is closer to that of a state-of-the-art discriminative model (Smith and Eisner, 2005), up to 14 percentage points better than MLE. We find improvements both when training from data alone, and using a tagging dictionary.
Introduction
Unsupervised part-of-speech (POS) tagging—the task of assigning grammatical categories to words without labeled training data—is a cornerstone challenge in computational linguistics. Traditionally, this problem is approached using Hidden Markov Models (HMMs) trained via Maximum Likelihood Estimation (MLE), typically implemented through the Expectation-Maximization (EM) algorithm. However, MLE is notoriously brittle. It seeks a single point estimate for model parameters that maximizes the likelihood of the observed data, often leading to overfitting or "degenerate" solutions that fail to capture the inherent sparsity of natural language.
Methodology: From Point Estimation to Integration
This work proposes a shift from finding the "best" parameters to a fully Bayesian framework. Instead of estimating fixed parameters $\theta$ (transition and emission probabilities), the model treats $\theta$ as a random variable and integrates it out. The objective is to find the tag sequence $t$ that maximizes the posterior probability $P(t|w)$:
$$P(t|w) = \int P(t|w, \theta)P(\theta|w)d\theta$$
Sparsity and Priors
A key advantage of the Bayesian approach is its ability to incorporate priors that favor sparsity. Human language is naturally sparse: most words belong to only one or two POS categories, and most tags follow only a small subset of other tags. By using symmetric Dirichlet distributions with hyperparameters $\beta < 1$, the model encourages sparse distributions without the numerical instability often seen in MLE-based sparse models.
Inference via Gibbs Sampling
Because the required integral is analytically intractable, the authors employ Gibbs sampling. This Markov Chain Monte Carlo (MCMC) method iteratively samples the tag for each word based on the current state of all other tags. To find the Maximum A Posteriori (MAP) assignment, simulated annealing (tempering) is used, gradually lowering a temperature parameter to encourage convergence to a high-probability state. Additionally, hyperparameters are inferred directly from the data using the Metropolis-Hastings algorithm, reducing the need for manual tuning.
Experimental Results
The model was evaluated on the Wall Street Journal (WSJ) corpus across various sizes and levels of dictionary knowledge. The performance gains were substantial. On a 24,000-word corpus with a full tagging dictionary, the standard MLE HMM achieved 74.5% accuracy, while the Bayesian HMM (BHMM) reached 86.8%—a 12.3 percentage point improvement.
Qualitative Analysis and Clustering
Beyond raw accuracy, the BHMM demonstrates superior performance in dictionary-free clustering. The authors utilize Variation of Information (VI) to measure the overlap between discovered clusters and true linguistic categories. As illustrated in the confusion matrices, the BHMM produces much cleaner, more distinct alignments with ground-truth tags compared to the noisy results of the MLE HMM.
Limitations and Future Work
While the BHMM offers significant performance gains, it comes with increased computational costs. Gibbs sampling is notably slower than the EM algorithm. Furthermore, in completely unsupervised settings, the model may occasionally produce "junk" clusters—groupings of rare words that lack a true linguistic category. Future research could explore more sophisticated, non-uniform priors to further refine the model's ability to capture natural language distributions.
Conclusion
The success of the BHMM demonstrates that a simple, well-understood model like the trigram HMM can achieve near state-of-the-art performance when paired with a robust Bayesian learning framework. By integrating over parameter uncertainty and leveraging sparsity-inducing priors, the Bayesian approach overcomes the primary limitations of MLE in unsupervised linguistic tasks. While computationally more intensive than EM, the significant gains in accuracy and robustness make it a compelling alternative for learning linguistic structure.
Summary updated