A Systematic Comparison of Phrase Table Pruning Techniques

Richard Zens, Daisy Stanton, Peng XuEMNLP 2012

TL;DR

This paper introduces a novel, theoretically grounded entropy-based criterion for pruning phrase tables in statistical machine translation (SMT). By systematically comparing it with existing methods, the authors demonstrate that their approach significantly reduces phrase table size while maintaining translation quality, offering substantial savings in storage and processing.

What Problem Does This Paper Address?

Statistical machine translation (SMT) systems, especially those trained on massive parallel corpora, suffer from extremely large phrase tables. These tables, which store translation probabilities for phrase pairs, consume vast computational resources for storage and processing, leading to long experiment cycles and hindering deployment on resource-constrained devices. While various pruning techniques exist, many lack a solid theoretical foundation and rely on ad-hoc heuristics. This paper aims to address this by providing a systematic comparison of existing methods and introducing a new, theoretically sound pruning criterion that is both efficient and effective.

Methods

The paper categorizes existing phrase table pruning methods into two main types:

  • Absolute Pruning: These methods consider the statistics of individual phrase pairs (f, ē) independently. Examples include:
  • Count-based pruning: Discards pairs with observation counts below a threshold.
  • Probability-based pruning: Discards pairs with a probability p(ē|f) below a threshold.
  • Relative Pruning: These methods consider the context of other phrases for a given source phrase. Examples include:
  • Threshold pruning: Discards phrases that are significantly worse than the best translation for a source phrase.
  • Histogram pruning: Keeps a fixed number (K) of the most probable target phrases for each source phrase.
  • Significance pruning (Fisher's exact test): Tests if a phrase pair co-occurs more frequently than expected by chance, using a contingency table and p-values.

The core contribution is the Entropy-based Pruning criterion. This method is inspired by language model pruning techniques and is based on minimizing the conditional Kullback-Leibler divergence between the original and pruned model. The criterion quantifies the "redundancy" of a phrase pair by its contribution to the relative entropy. Phrase pairs with a contribution below a threshold are pruned. The authors also address the issue of compositional phrases, where a translation can be formed by combining shorter phrases, and propose a method to handle non-compositional phrases.

Datasets

The experiments were conducted on publicly available WMT (Workshop on Statistical Machine Translation) shared translation task data for four language pairs:

  • German-English
  • Czech-English
  • Spanish-English
  • French-English

These language pairs represent a range of training corpus sizes, as detailed in Table 3. The evaluation was performed on the WMT'07 news commentary blind set.

Key Insights and Ideas

  • Theoretical Foundation Matters: Many existing pruning methods rely on ad-hoc heuristics. The paper argues for a principled approach grounded in information theory, leading to more reliable and effective pruning.
  • Redundancy vs. Quality: The proposed entropy-based pruning focuses on removing redundant phrases (those whose removal minimally impacts the overall translation model distribution) rather than directly assessing translation quality. This is a key differentiator.
  • Compositionality is Key: The paper highlights that most phrases in a phrase table are compositional, meaning they can be formed by combining smaller phrases. This understanding is crucial for effective pruning and for modeling the pruned system.
  • Efficiency is Achievable: The entropy-based criterion is designed to be computationally feasible, allowing for efficient pruning without requiring extensive re-computation.

Key Results

  • Entropy-based pruning consistently outperforms other methods across all tested language pairs and translation directions in terms of translation quality (measured by BLEU score) for a given phrase table size.
  • Significant Savings: Entropy-based pruning achieves consistently high savings, retaining only 85-95% of the phrase table without losing more than one BLEU point. This is a substantial improvement over count-based or significance-based pruning, which typically retain 70-90%.
  • Half the Size: In many cases, the entropy-based method allows for cutting the required phrase table size in half compared to count or significance-based pruning while achieving the same BLEU score.
  • Probability-based pruning is poor: This method performs poorly, especially when pruning large portions of the table, likely because it ignores the frequency of the source phrase.
  • Length-based pruning is suboptimal: Compared to phrase table pruning methods, simply reducing the maximum phrase length is less effective.

Limitations and Future Work

  • Approximation in Computation: The paper acknowledges a minor approximation made in the computation of the entropy criterion, where phrase pairs are assumed to affect relative entropy independently. A more detailed analysis of this effect is left for future work.
  • Ignoring Other Models: The current entropy pruning criterion primarily considers the p(ē|f) model. Future work could incorporate other models like p(f|ē), lexical models, and language models, as well as distortion costs, to potentially yield even better pruning estimates.
  • Hierarchical SMT: The authors suggest that the entropy pruning criterion could be applied to hierarchical machine translation systems, where it might lead to even larger reductions in phrase table size due to the greater number of entries.
  • Non-compositional Phrases: While the paper addresses non-compositional phrases, further investigation into their handling and the impact of the constant pc value is suggested.

Summary updated

BibTeX
@inproceedings{zens2012systematic,
  author = {Richard Zens and Daisy Stanton and Peng Xu},
  title = {{A Systematic Comparison of Phrase Table Pruning Techniques}},
  booktitle = {Conference on Empirical Methods in Natural Language Processing},
  year = {2012},
}
Figure