Probabilistic Inference for Machine Translation

Phil Blunsom, Miles OsborneEMNLP 2008 · OpenReview

Abstract: We advance the state-of-the-art for discriminatively trained machine translation systems by presenting novel probabilistic inference and search methods for synchronous grammars. By approximating the intractable space of all candidate translations produced by intersecting an ngram language model with a synchronous grammar, we are able to train and decode models incorporating millions of sparse, heterogeneous features. Further, we demonstrate the power of the discriminative training paradigm by extracting structured syntactic features, and achieving increases in translation performance.

Introduction

This research represents a pivotal moment in the evolution of Statistical Machine Translation (SMT), addressing a significant bottleneck in training probabilistic models. While Synchronous Context-Free Grammars (SCFG) are highly effective at handling structural differences between languages, such as reordering, they face a major hurdle in discriminative training.

To train a probabilistic model effectively, one must calculate a partition function ($Z$)—a normalization factor representing the sum over every possible translation the model could produce. When a Language Model (LM) is integrated with an SCFG, the search space expands to $O(n^3 |T|^{4(m-1)})$, making exact calculation of $Z$ computationally impossible. This paper introduces a mathematically sound probabilistic framework that keeps the LM in the loop during training.

Methods: Sampling and Approximation

The authors propose a log-linear model where translation is treated as a latent variable over derivations. The core innovation lies in two technical advancements:

  1. Monte-Carlo Partition Function Approximation: Instead of summing over the infinite space of all translations, the system approximates $Z$ by sampling a large, representative subset of derivations.
  2. Top-down Recursive Sampling: Unlike standard "cube pruning" (a beam search variant) which can bias the model toward a narrow cluster of "good" translations, the authors utilize a top-down recursive sampling algorithm. This builds a "packed chart" of derivations that includes both high- and low-probability examples. This global view allows the model to learn contrastive features—effectively learning what not to do.
Visualization of the derivation process and the resulting packed chart used for sampling candidate translations.

Syntactic Features as Suggestions

A key contribution of this work is the treatment of source-side syntax. Rather than forcing the grammar to adhere strictly to linguistic rules—which often results in translation failures when parsers are noisy—the authors treat syntax as sparse features.

By encoding syntax as features (over 4 million in total), the system learns to favor translations that respect syntactic structure without being strictly forbidden from breaking rules if the data suggests a better alternative. This makes the system robust to parser errors; the model can simply assign a low weight to a specific syntactic feature rather than failing to produce a translation entirely.

Example of syntactic feature extraction and the multi-step derivation process for a Chinese-to-English translation task.

Experimental Results

The model was evaluated on the IWSLT 2005 Chinese-to-English translation task, utilizing approximately 40,000 sentence pairs from the travel domain. The results demonstrated the power of this discriminative approach:

  • Language Model Integration: Incorporating the LM into the discriminative training regime led to a massive performance jump, increasing the BLEU score from 32.6 to 40.6 on the development set.
  • Syntactic Gains: The addition of 4.2 million syntactic features provided a further statistically significant boost, reaching 45.3 BLEU on the test set.
  • Scalability: The inference method successfully handled a model with a total of 7.1 million features, a landmark achievement for the time.

Conclusion and Future Work

The research demonstrates that sampling-based approximations ($Z^{sam}$) consistently outperform beam-search-based ones ($Z^{cb}$) by providing a broader distribution of the translation space. While computationally expensive, this probabilistic approach proves more stable across different versions of the BLEU metric than traditional Minimum Error Rate Training (MERT).

Future work remains to determine how these millions of sparse features scale to larger, more diverse datasets beyond the travel domain, and to further optimize the efficiency of the MCMC methods used for sampling.

Summary updated

Abstract

We advance the state-of-the-art for discriminatively trained machine translation systems by presenting novel probabilistic inference and search methods for synchronous grammars. By approximating the intractable space of all candidate translations produced by intersecting an ngram language model with a synchronous grammar, we are able to train and decode models incorporating millions of sparse, heterogeneous features. Further, we demonstrate the power of the discriminative training paradigm by extracting structured syntactic features, and achieving increases in translation performance.
BibTeX
@inproceedings{blunsom2008probabilistic,
  author = {Phil Blunsom and Miles Osborne},
  title = {{Probabilistic Inference for Machine Translation}},
  booktitle = {Conference on Empirical Methods in Natural Language Processing},
  year = {2008},
  url = {https://openreview.net/forum?id=rJNQmMGdWH},
}
Figure