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 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%.
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