Smoothed Bloom Filter Language Models: Tera-Scale LMs on the Cheap

David Talbot, Miles OsborneEMNLP 2007

TL;DR

This paper introduces a novel framework for building highly compressed language models (LMs) using Bloom filters, drastically reducing memory requirements for statistical machine translation (SMT) systems. By leveraging the probabilistic nature of Bloom filters and clever statistical approximations, they achieve competitive translation performance with significantly less memory than traditional LMs.

What Problem Does This Paper Address?

Statistical Machine Translation (SMT) systems heavily rely on language models (LMs) to predict the probability of word sequences in the target language. Standard n-gram LMs, while effective, suffer from an exponential increase in size as the 'n' in n-gram increases. For instance, a 5-gram model on a large corpus can involve billions of parameters. This massive memory footprint makes it challenging to deploy these models efficiently, especially on resource-constrained devices, as they ideally need to reside in memory for fast lookups. The paper addresses this by proposing a method to create LMs that are orders of magnitude smaller while maintaining acceptable performance.

Methods

The core of the paper's contribution lies in using Bloom filters (BFs) as a space-efficient, randomized data structure to store n-gram statistics. Instead of storing exact counts, they use a "log-frequency Bloom filter" that quantizes counts logarithmically. This allows them to represent a vast number of n-grams with a much smaller bit array.

Key techniques include:

  • Log-Frequency Bloom Filter: Counts are transformed using qc(x) = 1 + [log_b(c(x))], where c(x) is the raw count and b is the logarithm base. This quantizes counts, with lower counts being more granularly represented.
  • Composite Events for Training: To store the quantized counts, they train the BF with composite events: an n-gram appended with a counter j from 1 up to its quantized count qc(x).
  • On-the-Fly Probability Estimation: At test time, they query the BF for an n-gram. If all bits are set, they increment a counter and re-query. This process stops when a zero bit is encountered, providing an upper bound on the quantized count.
  • Expected Value Approximation: The original frequency is approximated using the expected value formula E[c(x)|qc(x) = j] = (-1 + b^j) / 2.
  • Proxy Items: To further reduce memory, they use "proxy items." For example, the presence of an n-gram with a count of at least 1 implies the existence of a singleton suffix count of at least 1, so the suffix count doesn't need to be explicitly stored.
  • Monotonicity and Upper Bounds: They leverage the one-sided error of BFs (never underestimating) and inequalities between n-gram statistics (e.g., c(w1, ..., wn) <= min(c(w1, ..., wn-1), c(w2, ..., wn))) to reduce the probability of querying for non-existent (negative) events, thereby improving accuracy.

Datasets

  • Europarl Corpus (French-English): Used for training parallel data and language modeling.
  • Gigaword Corpus: Mentioned as an example of a large corpus with a high number of n-grams.

Key Insights and Ideas

  • Bloom filters are surprisingly effective for LMs: Despite their probabilistic nature and potential for false positives, BFs can be adapted to store n-gram statistics with dramatic space savings.
  • Logarithmic quantization is key: It allows for efficient representation of the Zipfian distribution of n-gram frequencies, where most n-grams occur rarely.
  • Leveraging one-sided error is crucial: The fact that BFs never produce false negatives (they only err by saying an item is present when it's not) is a significant advantage that can be exploited with statistical bounds.
  • Proxy items and statistical bounds reduce redundancy and error: By intelligently using related statistics and inequalities, the memory footprint can be further reduced, and the accuracy of the derived probabilities can be improved.
  • MSE as a predictor for translation quality: The Mean Squared Error between the log-probabilities assigned by the BF-LM and the baseline LM appears to be a good indicator of translation performance, potentially allowing for faster optimization without full SMT decoding.

Key Results

  • Significant Memory Reduction: BF-LMs achieved substantial memory savings. For example, a 5-gram model that would be 924MB in SRILM (gzip compressed) could be represented by a BF-LM using only 50MB. This translates to a reduction of a factor of 16-24 compared to plain models and 4-7 compared to gzip-compressed models.
  • Competitive Translation Performance: Despite the memory reduction, the BF-LMs performed consistently close to their baseline SRILM counterparts. For instance, MER-optimized 3-gram BF-LMs achieved BLEU scores around 28.33-29.31, very close to the SRILM baseline of 28.54.
  • Faster Convergence with Coarser Quantization: Models using coarser quantization bases (e.g., base 3) reached their optimal translation performance with less memory compared to finer-grained schemes (e.g., base 1.1).
  • Upper bounds improve performance: Applying statistical bounds to reduce the probability of querying for non-existent events improved translation performance, especially when memory was limited.

Limitations and Future Work

  • Translation Speed: BF-LMs were 2-5 times slower than their SRILM counterparts, although this is still considered acceptable for many applications.
  • False Positives: The inherent false positive rate of Bloom filters means that probabilities can be overestimated. While the paper shows this can be managed, it's a fundamental trade-off.
  • Future Work: The authors are currently implementing Kneser-Ney smoothing within their framework, suggesting it can be extended to other smoothing techniques. They also hope to establish the Bloom filter as a practical alternative to traditional data structures in computational linguistics.

Summary updated

BibTeX
@inproceedings{talbot2007smoothed,
  author = {David Talbot and Miles Osborne},
  title = {{Smoothed Bloom Filter Language Models: Tera-Scale LMs on the Cheap}},
  booktitle = {Conference on Empirical Methods in Natural Language Processing},
  year = {2007},
}
Figure