Streaming for large scale NLP: Language Modeling

Amit Goyal, Hal Daumé Iii, Suresh Venkatasubramanian

Abstract: Amit Goyal, Hal Daumé III, Suresh Venkatasubramanian. Proceedings of Human Language Technologies: The 2009 Annual Conference of the North American Chapter of the Association for Computational Linguistics.

2009.

Introduction

In the late 2000s, Natural Language Processing (NLP) faced a significant scaling challenge. Improving Statistical Machine Translation (SMT) required training language models (LMs) on trillions of words, leading to hundreds of millions of unique n-grams. The conventional workflow created a "catch-22": to produce a compact, efficient model, researchers first had to build a massive, unpruned model and then delete infrequent sequences. This initial stage required high-performance computing clusters with massive RAM, often exceeding 20GB, making large-scale NLP inaccessible to many researchers.

This paper introduces a memory-efficient streaming algorithm that allows for the construction of large-scale LMs on a single desktop. By estimating n-gram frequencies in a single pass, the authors reduced memory requirements to less than 3GB while maintaining translation performance comparable to cluster-built models.

Methodology: The Streaming Approach

The researchers adapted a deterministic streaming algorithm to the NLP domain. Instead of storing every n-gram encountered, the algorithm processes the data stream in "epochs."

  1. Counting: The system maintains a dynamic list of n-grams and their observed frequencies.
  2. Pruning (Cleaning House): At the end of each epoch, the algorithm deletes any n-gram whose maximum possible true frequency falls below a predefined threshold.
  3. Mathematical Guarantees: The algorithm provides a "no-false-negative" guarantee, ensuring that any n-gram appearing frequently in the total dataset is preserved in the final output. While it may include some infrequent "false positives" or slightly underestimate counts, these errors are mathematically bounded by the parameter $\epsilon$.

This streaming approach is fundamentally "bottom-up," keeping only what matters during the ingestion process, rather than the traditional "top-down" method of building a full model and then shrinking it.

Experimental Setup and Datasets

The study utilized two primary English text sources:

  • Europarl (EP): Standard proceedings from the European Parliament.
  • Gigaword (EAN): A massive 1.1-billion-word collection comprising Europarl text plus news feeds from Agence France Press and the New York Times.

The researchers integrated these stream counts into the Moses SMT decoder using a recursive feature score to handle back-off scenarios where long sequences are not found.

Key Results

Translation Quality and Efficiency

The streaming models were compared against "exact" models and traditional pruning methods. On the EAN corpus, an exact 5-gram model achieved a BLEU score of 28.73 but required 20.5 GB of RAM. In contrast, the streaming version achieved a statistically comparable BLEU score (approximately 27.98) while utilizing only 2.8 GB of RAM. This shift moves the bottleneck of large-scale NLP from hardware availability to algorithmic efficiency.

Performance of the streaming model across different error bounds (epsilon).

Intrinsic Accuracy

The algorithm proved highly effective at identifying the most important data. For the top 100,000 most frequent 5-grams, the streaming algorithm achieved 99.4% accuracy in identifying correct sequences compared to exact counts. As shown in the data, accuracy remains high for the most frequent items, which are the most critical for model performance.

Intrinsic accuracy and correlation (rho) for the top K n-grams.

Discussion and Future Work

While the method is highly effective for 4-gram and 5-gram models, the authors noted diminishing returns for higher-order n-grams (7-grams or 9-grams). This is attributed to the drop in "recall"—the likelihood of finding these extremely long sequences in test data—as $n$ increases.

Future research directions include developing more sophisticated ways to convert stream counts into smoothed probability distributions (such as Kneser-Ney smoothing) directly within the streaming framework. Additionally, this streaming paradigm could be applied to other large-scale NLP tasks, such as noun-clustering or analogy detection, where relative frequency is a primary metric.

Summary updated

BibTeX
@inproceedings{goyal2009streaming,
  author = {Amit Goyal and Hal Daumé III and Suresh Venkatasubramanian},
  title = {{Streaming for large scale NLP: Language Modeling}},
  booktitle = {Conference of the North American Chapter of the Association for Computational Linguistics},
  year = {2009},
  url = {https://openreview.net/forum?id=HJWCqQZuZH},
}
Figure