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:
- 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.
- 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.
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.
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