A Maximum Entropy/Minimum Divergence Translation Model

George F. FosterACL 2000 · OpenReview

Abstract

I present empirical comparisons between a linear combination of standard statistical language and translation models and an equivalent Maximum Entropy/Minimum Divergence (MEMD) model, using several different methods for automatic feature selection. The MEMD model significantly outperforms the standard model in test corpus perplexity, even though it has far fewer parameters.

Introduction

In the late 1990s, Statistical Machine Translation (SMT) was primarily built upon the "noisy-channel" framework. This approach uses Bayes' rule to decompose the probability of a translation $p(t|s)$ into a language model $p(t)$ and a translation model $p(s|t)$. While mathematically sound, this decomposition necessitates a complex search through the target vocabulary during decoding. Furthermore, these components are typically combined via linear interpolation—a simple weighted average. This paper argues that linear combination is a "weak" integration method that averages the strengths of components rather than allowing them to complement each other. The goal is to model $p(t|s)$ directly using a more robust framework.

Methods

The proposed solution is a Maximum Entropy (ME) framework, specifically a Minimum Divergence (MEMD) model. Instead of the noisy channel, the model employs a chain-rule expansion to predict the next word $w$ based on the history $h$ and the source sentence $s$: $p(w|h, s)$.

The MEMD model integrates a "reference distribution" (a standard trigram language model) with "feature functions" representing bilingual word pairs. Given the millions of possible pairs, three feature selection methods were evaluated:

  1. Mutual Information (MI): A standard statistical association measure.
  2. MEMD Gains: An iterative approach selecting features that maximize model likelihood.
  3. IBM1 Gains: A novel, computationally efficient heuristic that estimates a feature's value based on its contribution within a standard IBM Model 1 translation model.
Comparison of feature selection methods: test corpus perplexity vs. number of features.

As shown in the figure above, the IBM1 Gains method is particularly effective, often outperforming the more complex MEMD gains at lower feature counts.

Experimental Setup

Experiments were conducted using the Canadian Hansard corpus, containing official transcripts from the Canadian Parliament in English and French. The training set comprised approximately 1.6 million sentence pairs (~30 million tokens), with English as the source and French as the target.

Results and Discussion

The core advantage of the ME framework is that it essentially multiplies predictive scores from different sources. This allows a single confident source to heavily influence the outcome, unlike the smoothing effect of linear interpolation.

The performance was measured using perplexity (ppx), where lower values indicate higher model certainty. The MEMD model demonstrated extreme parameter efficiency: with only 30,000 features, it outperformed a linear model using 35 million parameters.

Summary of perplexity (ppx) results for baseline and MEMD models.

As summarized in the table, the best linear combination (3G+IBM1) reached a perplexity of 43.6. In contrast, the MEMD model with 30,000 features achieved a perplexity of 23.2, representing a 46.9% reduction. Qualitatively, the MEMD and IBM1 gain methods selected more intuitive translation pairs (e.g., government/gouvernement) compared to Mutual Information, which often prioritized punctuation or frequent but less meaningful pairings.

Conclusion

While the MEMD model offers significant performance gains and parameter efficiency, it comes with a high computational cost; training a 30,000-feature model took roughly six days on contemporary hardware. Additionally, the current framework lacks "hidden" variables like word alignments, which are vital for complex translation tasks. Future work should explore integrating MEMD models directly into full-scale SMT decoding systems to overcome current search space bottlenecks.

Summary updated

Abstract

I present empirical comparisons between a linear combination of standard statistical language and translation models and an equivalent Maximum Entropy/Minimum Divergence (MEMD) model, using several different methods for automatic feature selection. The MEMD model significantly outperforms the standard model in test corpus perplexity, even though it has far fewer parameters.
BibTeX
@inproceedings{foster2000maximum,
  author = {George F. Foster},
  title = {{A Maximum Entropy/Minimum Divergence Translation Model}},
  booktitle = {Annual Meeting of the Association for Computational Linguistics},
  year = {2000},
  url = {https://openreview.net/forum?id=r1Z-solu-S},
}
Figure