Abstract This paper presents Compressed Nonparametric (CN) language modelling, a novel framework that integrates infinite-order Bayesian models with highly efficient compressed data structures. By mapping Hierarchical Pitman-Yor Process (HPYP) models onto Compressed Suffix Trees (CST), the proposed approach achieves a 15% improvement in perplexity over traditional smoothing techniques. Notably, the CN model reduces memory consumption by orders of magnitude compared to previous Bayesian implementations, enabling the processing of datasets up to 8GiB in size.
1. Introduction
Language models (LMs) are essential components in natural language processing, providing the probabilistic foundation for tasks such as machine translation and speech recognition. Traditionally, these models rely on $n$-gram counts combined with smoothing techniques, such as Kneser-Ney, to estimate probabilities for rare or unseen sequences. The Hierarchical Pitman-Yor Process (HPYP) offers a theoretically elegant Bayesian generalization of these methods, capable of capturing "infinite-order" dependencies by considering contexts of arbitrary length.
Despite their statistical advantages, HPYP models have historically been hindered by extreme memory requirements. The complex tree structures required to store these models grow linearly with the dataset size. Previous state-of-the-art implementations, such as the Sequence Memoizer, often hit memory limits with only a few million words. Furthermore, the Gibbs sampling processes used for training are computationally intensive and frequently suffer from poor mixing on large-scale data.
2. Methodology
The authors introduce the "Compressed HPYP" to address the dual challenges of memory bloat and computational inefficiency. This is achieved through three primary innovations:
- Compressed Suffix Trees (CST): Rather than employing standard pointer-based trees, the model utilizes a CST built upon a Compressed Suffix Array and the FM-Index. This structure allows the entire model to reside in a memory footprint roughly equivalent to the compressed source text.
- Branch Sampling at Test Time: To avoid the overhead of sampling a massive global tree during training, the authors shift the sampling process to the query phase. When calculating the probability of a specific word, the model samples only the relevant branch (context) on-the-fly.
- Range Shrinking and Forgetting: To maintain inference speed, the model limits the sampling range for internal parameters—specifically the "number of tables" in the Chinese Restaurant Process metaphor. Samples are "forgotten" immediately after a query to prevent memory accumulation during long-running inference tasks.
3. Experimental Setup
The CN model was evaluated across diverse linguistic contexts using the following datasets:
- Europarl v7: Multilingual corpora including Finnish (FI), Spanish (ES), German (DE), English (EN), and French (FR).
- English Common Crawl: Large-scale web data ranging from 125MiB to 8GiB. The 8GiB subset represents a 100-fold increase in scale over datasets typically used in prior HPYP research.
4. Results and Discussion
The integration of Bayesian nonparametrics with compressed structures yields significant performance gains. A key insight of this work is the structural synergy between Kneser-Ney smoothing and the HPYP; both rely on hierarchical counting mechanisms that can be efficiently mapped to a CST.
Key Results: * Perplexity: The CN model consistently outperformed Modified Kneser-Ney (MKN) by up to 15%. It also surpassed the Sequence Memoizer (SM), which often fails to converge on larger datasets due to global sampling inefficiencies. * Memory Efficiency: On a 250MiB dataset, the CN model required approximately 300MB of RAM, a stark contrast to the 16GB required by the Sequence Memoizer for a single set of samples. * Scalability and Speed: The model successfully processed 8GiB of text, a feat previously unattainable for HPYP models. Training was 40x to 67x faster than the SM, as the "training" phase is reduced to building the compressed index.
5. Conclusion
While the CN model offers superior perplexity and memory efficiency, it introduces higher test-time latency—averaging 24x slower than the Sequence Memoizer during queries due to on-the-fly sampling. Future work may address this by approximating computationally expensive generalized Stirling numbers or exploring continuous space adaptations of the HPYP. Nevertheless, this framework demonstrates that infinite-order Bayesian language modelling is viable at a massive scale when paired with modern compressed data structures.
Summary updated