Abstract
Standard MCMC methods for unsupervised NLP tasks, such as Gibbs sampling, often suffer from slow mixing and entrapment in local optima. This is primarily due to the "token-based" nature of updates, which fail to account for the strong coupling between identical word types across a corpus. We present Type-Based MCMC, a sampling framework that performs joint updates on all occurrences of a specific type. By leveraging the exchangeability of sufficient statistics, this method achieves significantly higher likelihoods and improved accuracy across tasks including POS induction, word segmentation, and grammar induction.
Introduction
Unsupervised learning in NLP—inducing structures like part-of-speech tags or syntactic trees from raw text—is a search for global optima in a complex, multimodal likelihood landscape. Traditional approaches like Expectation-Maximization (EM) or standard Gibbs samplers are inherently local. They process data at the level of individual tokens or sentences.
The Problem: Token-Based Coupling
The fundamental issue is parameter coupling. In Bayesian models with Dirichlet priors, a "rich-gets-richer" effect occurs: if a word like "bank" is predominantly labeled as a Noun in the current state of the model, the probability of a token-based sampler changing any single instance to a Verb is negligible. To escape such a local optimum, the model would need to change many instances of "bank" simultaneously—a move that token-based samplers are statistically unlikely to make.
Proposed Method: Type-Based Sampling
To address this, the authors propose Type-Based MCMC. Instead of updating a single latent variable at a time, the sampler identifies a "type block"—a set of variables across the entire corpus that share the same influence on the model's sufficient statistics.
As illustrated in the figure above, while token-based and sentence-based methods update contiguous or single units, type-based sampling targets specific categories of variables (e.g., all instances of a specific word or boundary type) regardless of their position in the text.
Technical Innovations
The framework relies on several key technical insights:
- Binary Representation: Latent structures are mapped to binary variables $b_s$. For multi-state models like HMMs, a "random binary slice" technique is used to reduce the problem to binary choices.
- Non-Conflicting Sites: To ensure tractability, the sampler groups variables that are "non-conflicting." This means the choice made at one site in the block does not alter the set of valid choices at another.
- The Exchangeability Trick: Because the model's joint probability depends only on the total counts (sufficient statistics), the probability of a configuration within a type block depends only on the number of variables set to 1 ($m$), not their specific locations. This allows the sampler to first draw $m$ from a distribution and then distribute the values uniformly, enabling massive joint updates with minimal computational overhead.
Experimental Evaluation
The effectiveness of Type-Based MCMC was tested on three diverse tasks:
- Part-of-Speech (POS) Induction: Using a 45-state HMM on the Wall Street Journal (WSJ) corpus.
- Word Segmentation: Using a Unigram Segmentation Model (USM) on the CHILDES database.
- Grammar Induction: Using a Probabilistic Tree-Substitution Grammar (PTSG) on the WSJ treebank.
Across all models, the type-based sampler consistently reached higher log-likelihoods than its token-based counterparts. Notably, in word segmentation, the type-based sampler converged almost immediately, whereas the token-based sampler required multiple passes over the data to escape initial local optima.
Conclusion
Type-Based MCMC provides "model-driven mobility," allowing samplers to make large, coordinated jumps in the state space. By moving beyond the limitations of token-based updates, this framework offers a robust solution for unsupervised NLP, showing particular strength in its independence from initialization and its ability to find higher-quality global solutions.
Summary updated