A Hierarchical Pitman-Yor Process HMM for Unsupervised Part of Speech Induction

Phil Blunsom, Trevor CohnACL 2011 · OpenReview

Abstract

In this work, we address the problem of unsupervised part-of-speech (PoS) induction by bringing together several strands of research into a single model. We develop a novel hidden Markov model incorporating sophisticated smoothing using a hierarchical Pitman-Yor process prior, providing an elegant and principled means of incorporating lexical characteristics. Central to our approach is a new type-based sampling algorithm for hierarchical Pitman-Yor models in which we track fractional table counts. In an empirical evaluation, we show that our model consistently out-performs the current state-of-the-art across 10 languages.

Introduction

Unsupervised part-of-speech (PoS) induction—the task of automatically clustering words into syntactic categories without labeled data—remains a fundamental challenge in natural language processing. While supervised tagging is highly accurate for high-resource languages, unsupervised methods are crucial for low-resource languages and for modeling human language acquisition. Previous research in this area has faced three primary hurdles: inadequate smoothing techniques that fail to capture the power-law nature of language, the neglect of sub-word morphological cues, and inefficient inference algorithms that often converge on local optima.

This paper introduces the PYP-HMM, a Bayesian Hidden Markov Model that addresses these limitations by leveraging hierarchical Pitman-Yor Process (PYP) priors and a novel type-based sampling strategy.

The PYP-HMM Framework

The core of the proposed approach is a trigram HMM where transition and emission distributions are governed by a Hierarchical Pitman-Yor Process. Unlike standard Dirichlet priors, the PYP naturally models the power-law distribution characteristic of natural language, providing a more principled "rich-get-richer" effect.

The graphical model representation of the PYP-HMM, illustrating the hierarchical dependencies and plate notation for documents and word types.

The model employs a sophisticated backoff hierarchy for smoothing: Trigram $\rightarrow$ Bigram $\rightarrow$ Unigram $\rightarrow$ Uniform. This allows the model to share statistical strength across different contexts effectively. By using a non-parametric prior, the model can adjust its complexity based on the available data, mirroring the structural properties of human language.

Morphology and Type-Based Inference

To capture morphological signals, the authors extend the model (HMM+LM) by embedding a character-level bigram model within the emission distribution. This enables the model to learn that words with similar suffixes (e.g., "-ing", "-ed") likely share the same syntactic category, a feature particularly beneficial for morphologically rich languages.

Inference is performed using a novel type-based Markov Chain Monte Carlo (MCMC) sampler. Traditional token-based samplers update one word at a time, which can be slow and prone to getting stuck in local optima. By contrast, the "1HMM" sampler updates all instances of a specific word type (e.g., every occurrence of "the") to the same tag simultaneously. To make this computationally feasible within a hierarchical model, the authors introduced an approximation method using fractional "expected table counts."

Key Results and Evaluation

The model was evaluated on the English Penn Treebank (WSJ) and the CoNLL-X shared task datasets, covering 10 diverse languages including Arabic, Bulgarian, and Swedish. The PYP-HMM consistently outperformed previous state-of-the-art systems across the board.

  • English (WSJ): Achieved a Many-to-One (M-1) accuracy of 77.5%, surpassing the previous best of 76.1%.
  • Multilingual Robustness: The model set new benchmarks for all 10 languages. In Danish, for example, it reached 76.2% accuracy compared to the previous best of 66.7%.
Comparison of the induced tag distributions against the gold standard. The 1HMM and 1HMM-LM models closely track the gold distribution, significantly outperforming the MKCLS baseline.

As shown in the distribution analysis, the 1HMM variants match the frequency characteristics of gold-standard tags much more closely than traditional clustering methods like MKCLS. The inclusion of character-level modeling (HMM+LM) provided massive boosts in accuracy for morphologically rich languages like Arabic (+5%) and Spanish (+4%).

Conclusion

By combining hierarchical Bayesian smoothing with character-level modeling and efficient type-based inference, the PYP-HMM sets a new standard for unsupervised PoS induction. The success of this model across 10 different languages highlights the universality of power-law priors and morphological cues in syntactic discovery. Future work may explore relaxing the "one-tag-per-type" constraint to better handle lexical ambiguity while maintaining the efficiency of the sampling algorithm.

Summary updated

Abstract

In this work we address the problem of unsupervised part-of-speech induction by bringing together several strands of research into a single model. We develop a novel hidden Markov model incorporating sophisticated smoothing using a hierarchical Pitman-Yor processes prior, providing an elegant and principled means of incorporating lexical characteristics. Central to our approach is a new type-based sampling algorithm for hierarchical Pitman-Yor models in which we track fractional table counts. In an empirical evaluation we show that our model consistently out-performs the current state-of-the-art across 10 languages.
BibTeX
@inproceedings{blunsom2011hierarchical,
  author = {Phil Blunsom and Trevor Cohn},
  title = {{A Hierarchical Pitman-Yor Process HMM for Unsupervised Part of Speech Induction}},
  booktitle = {Annual Meeting of the Association for Computational Linguistics},
  year = {2011},
  url = {https://openreview.net/forum?id=ByVUm3edWr},
}
Figure