Compressed Nonparametric Language Modelling

Ehsan Shareghi, Gholamreza Haffari, Trevor Cohn

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.
Compressed Suffix Tree (CST) representation using Suffix Array (SA) and Burrows-Wheeler Transform (BWT).

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.

Relationship between backward-search on the CST and interpolation/sampling on the HPYP.

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

Abstract

Hierarchical Pitman-Yor Process priors are compelling for learning language models, outperforming point-estimate based methods. However, these models remain unpopular due to computational and statistical inference issues, such as memory and time usage, as well as poor mixing of sampler. In this work we propose a novel framework which represents the HPYP model compactly using compressed suffix trees. Then, we develop an efficient approximate inference scheme in this framework that has a much lower memory footprint compared to full HPYP and is fast in the inference time. The experimental results illustrate that our model can be built on significantly larger datasets compared to previous HPYP models, while being several orders of magnitudes smaller, fast for training and inference, and outperforming the perplexity of the state-of-the-art Modified Kneser-Ney count-based LM smoothing by up to 15%.
BibTeX
@inproceedings{shareghi2017compressed,
  author = {Ehsan Shareghi and Gholamreza Haffari and Trevor Cohn},
  title = {{Compressed Nonparametric Language Modelling}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2017},
  doi = {10.24963/ijcai.2017/376},
}
Figure