Entropy-based Pruning for Phrase-based Machine Translation

Wang Ling, João Graça, Isabel Trancoso, Alan W. BlackEMNLP 2012

Abstract

Phrase-based machine translation (PBMT) models often suffer from bloated phrase tables containing redundant entries, which increase memory usage and can lead to decoding search errors. This paper proposes a pruning method based on relative entropy that identifies and removes phrase pairs that can be accurately reconstructed from smaller, simpler components. Experiments on IWSLT and EUROPARL datasets demonstrate that this approach significantly reduces model size while maintaining or even improving translation quality.

Introduction

In Phrase-Based Machine Translation (PBMT), systems utilize "phrase pairs"—sequences of words—to capture linguistic context. Standard model construction involves extracting every possible phrase pair matching word alignments in a bilingual corpus, leading to massive, redundant phrase tables. For instance, if a model contains "the big red dog," it likely also contains "the big," "red dog," and "dog." If the translation of the longer phrase is merely the composition of its parts, retaining it consumes unnecessary memory and expands the search space, potentially leading to "search errors" where the decoder fails to find the optimal translation amidst the noise.

Methodology: Relative Entropy Pruning

The proposed pruning algorithm utilizes Relative Entropy (Kullback-Leibler divergence) to identify redundancy. The core idea is to distinguish between "Atomic" phrases (indivisible units) and "Composite" phrases (sequences that can be reconstructed from smaller units).

Illustration of phrase derivations used to identify redundant composite phrase pairs.

For each phrase pair, the algorithm performs a Redundancy Test: it asks how well the rest of the model can reconstruct the pair if it were deleted. Using a modified Viterbi decoder, the system finds the best "derivation" of a phrase using only other, typically smaller, phrases. If the reconstructed probability is close to the original, the relative entropy is low, indicating the phrase is redundant and safe to prune. Conversely, phrases that encode unique contextual information yield high relative entropy and are preserved. The authors explored two weighting schemes: a uniform distribution and a multinomial distribution (weighting by training frequency).

Experimental Setup and Results

The method was evaluated on two scales: the IWSLT 2010 (Chinese-English) dialogue task (~30k sentences) and the EUROPARL (Portuguese-English) task (~1.3M sentence pairs, 48.7M phrase table entries).

BLEU scores on the IWSLT task across different pruning levels for uniform and multinomial distributions.

On the IWSLT task, pruning the table to 85% of its original size actually increased the BLEU score from 15.68 to 15.82, supporting the hypothesis that removing noise reduces search errors. In the large-scale EUROPARL task, the model was compressed from 49 million pairs to 39 million (80% retention) with a negligible quality loss (28.99 BLEU vs. 29.18 baseline). The entropy-based approach consistently outperformed standard "Significance Pruning" baselines, particularly on smaller datasets.

Discussion and Future Work

A key insight is that "less is more": pruning can improve accuracy by cleaning the decoder's search path. The method naturally identifies useful context; for example, "in China" might be kept because "China" changes the translation of "in," whereas "John in" might be pruned if "John" provides no additional translation cues for "in."

However, the model currently struggles with "spurious" phrase pairs resulting from poor word alignments. Since these bad pairs often lack derivations, the entropy model incorrectly identifies them as "Atomic." Future work suggests a hybrid approach combining entropy-based pruning with significance pruning to address both redundancy and alignment noise simultaneously.

Summary updated

BibTeX
@inproceedings{ling2012entropy,
  author = {Wang Ling and João Graça and Isabel Trancoso and Alan W. Black},
  title = {{Entropy-based Pruning for Phrase-based Machine Translation}},
  booktitle = {Conference on Empirical Methods in Natural Language Processing},
  year = {2012},
}
Figure