Abstract: Hiroshi Noji, Daichi Mochihashi, Yusuke Miyao. Proceedings of the 2013 Conference on Empirical Methods in Natural Language Processing.
2013.
Introduction
Standard $n$-gram models are fundamental to natural language processing but suffer from "nearsightedness," focusing only on local context and ignoring the broader document topic. While integrating topic models like Latent Dirichlet Allocation (LDA) with $n$-grams seems intuitive, it introduces two significant challenges: the Sparsity Trap and the Local Minima Trap.
The Sparsity Trap occurs because dividing a corpus into $K$ topics reduces the available training data for each topic-specific $n$-gram model, making higher-order $n$-grams (e.g., 4-grams) unreliable. The Local Minima Trap arises from the deep hierarchies of the Pitman-Yor Process; standard word-by-word inference often fails to escape suboptimal configurations because small changes cannot shift the overall model structure.
Proposed Architectures
To address these issues, the authors introduce two novel architectures: the Hierarchical and Switching models.
The Hierarchical Model
This model utilizes a Doubly Hierarchical Pitman-Yor Process (DHPYP). It establishes a global $n$-gram model that serves as a prior for all topic-specific models. This structure allows individual topics to "borrow" statistical strength from a shared global pool, effectively mitigating data sparsity.
The Switching Model
The Switching model introduces a "topicality" variable ($\lambda_h$) for each context. It recognizes that language consists of both functional "glue" words (e.g., "in order to") and highly topical phrases (e.g., "support vectors"). By switching between a global model and a topic-specific model based on context, it prevents functional noise from polluting topic distributions.
Inference via Blocked Gibbs Sampling
A key innovation is the Blocked Gibbs Sampler. Unlike traditional samplers that reassign one word at a time, this algorithm identifies "blocks" of related $n$-grams within a suffix tree and moves them between topics simultaneously. This approach allows the model to navigate the complex probability space more efficiently and avoid local minima.
Evaluation and Results
The models were evaluated on the Brown Corpus, NIPS papers, and the British National Corpus (BNC).
- Performance: The Switching Model consistently outperformed baselines. On the NIPS dataset, it achieved a perplexity of 100.0, a significant improvement over the 117.2 achieved by a standard Hierarchical Pitman-Yor Language Model (HPYLM).
- Efficiency: The blocked sampler reached higher probability states significantly faster than token-based alternatives.
- Qualitative Analysis: The model successfully distinguished between functional contexts (low $\lambda_h$) and topical ones (high $\lambda_h$), leading to cleaner topic representations.
Conclusion
By combining hierarchical priors, context-aware switching, and efficient blocked sampling, this work enables Bayesian topic $n$-gram models to scale to higher orders and larger datasets. These improvements make the models more practical for real-world applications like speech recognition where both local syntax and global semantics are crucial.
Summary updated