Large-Scale Discriminative Training for Statistical Machine Translation Using Held-Out Line Search

Jeffrey Flanigan, Chris Dyer, Jaime G. CarbonellNAACL 2013 · OpenReview

Abstract

We introduce a new large-scale discriminative learning algorithm for machine translation that is capable of learning parameters in models with extremely sparse features. To ensure their reliable estimation and to prevent overfitting, we use a two-phase learning algorithm. First, the contribution of individual sparse features is estimated using large amounts of parallel data. Second, a small development corpus is used to determine the relative contributions of the sparse features and standard dense features. Not only does this two-phase learning approach prevent overfitting, the second pass optimizes corpus-level BLEU of the Viterbi translation of the decoder. We demonstrate significant improvements using sparse rule indicator features in three different translation tasks. To our knowledge, this is the first large-scale discriminative training algorithm capable of showing improvements over the MERT baseline with only rule indicator features in addition to the standard MERT features.

Introduction

Statistical Machine Translation (SMT) systems traditionally rely on a small set of "dense" features, such as language model probabilities or word penalties. These parameters are typically optimized on a small development set using algorithms like Minimum Error Rate Training (MERT). However, there is a growing desire to incorporate millions of "sparse" features—specifically, rule indicator features that track the usage of specific translation rules.

Integrating millions of features presents two primary challenges: overfitting and poor scaling. Overfitting occurs when translation rules are extracted from a training corpus and their weights are tuned on that same data, leading to poor generalization. Scaling issues arise because frequent dense features dominate the loss function, causing gradients to oscillate and preventing the learning of rare sparse features.

Tuning on training data leads to significant overfitting, as shown by the drop in BLEU when moving from Train1000 to Dev1000 for the In1000 tuning set.

The Held-Out Line Search (HOLS) Algorithm

To address these challenges, we propose the Held-Out Line Search (HOLS) algorithm. HOLS is a two-phase batch optimizer:

  1. Gradient Calculation: The algorithm decodes a large portion of the training data to compute a gradient using a differentiable surrogate loss function—a smoothed, sentence-level approximation of BLEU.
  2. Line Search: Instead of a standard gradient step, HOLS performs a line search along the gradient direction using MERT on a separate, high-quality held-out development set.

Two critical techniques enable HOLS to scale effectively:

  • Grammar and Language Model Folds: The training data is split into $n$-folds. When decoding a fold to calculate the gradient, the system uses models built only from the remaining folds, preventing the model from "memorizing" the training data.
  • Gradient Conditioning: To stabilize optimization, each feature's gradient component is divided by its frequency in the $n$-best lists. This prevents frequent rules from causing oscillations and allows the model to learn from rare rules.

Experimental Results

We evaluated HOLS across three translation tasks: Chinese-English (Zh-En), Arabic-English (Ar-En), and Malagasy-English (Mg-En).

In the Chinese-English task, HOLS achieved a significant improvement of +1.1 BLEU over the MERT baseline. Ablation studies confirmed that both data folds and gradient conditioning are essential; removing either component reduced performance to near-baseline levels.

Comparison of HOLS configurations against the MERT baseline, highlighting the necessity of data folds and gradient conditioning for performance gains.

Similar gains were observed across other language pairs, with improvements of +0.6 to +0.9 BLEU for Arabic-English and +0.7 BLEU for the lower-resource Malagasy-English task. Notably, HOLS is computationally efficient, completing a 2-pass run on the large Zh-En dataset in approximately 40 hours using parallelization.

Conclusion

HOLS demonstrates that large-scale discriminative training can successfully incorporate millions of sparse features to improve translation quality. By separating gradient calculation from line search and employing cross-validation folds, the algorithm avoids the pitfalls of overfitting and optimization instability. Future work will explore richer linguistic feature sets to further leverage the scaling capabilities of this approach.

Summary updated

Abstract

We introduce a new large-scale discriminative learning algorithm for machine translation that is capable of learning parameters in models with extremely sparse features. To ensure their reliable estimation and to prevent overfitting, we use a two-phase learning algorithm. First, the contribution of individual sparse features is estimated using large amounts of parallel data. Second, a small development corpus is used to determine the relative contributions of the sparse features and standard dense features. Not only does this two-phase learning approach prevent overfitting, the second pass optimizes corpus-level BLEU of the Viterbi translation of the decoder. We demonstrate significant improvements using sparse rule indicator features in three different translation tasks. To our knowledge, this is the first large-scale discriminative training algorithm capable of showing improvements over the MERT baseline with only rule indicator features in addition to the standard MERT features.
BibTeX
@inproceedings{flanigan2013large,
  author = {Jeffrey Flanigan and Chris Dyer and Jaime G. Carbonell},
  title = {{Large-Scale Discriminative Training for Statistical Machine Translation Using Held-Out Line Search}},
  booktitle = {Conference of the North American Chapter of the Association for Computational Linguistics},
  year = {2013},
  url = {https://openreview.net/forum?id=Skb8iXbuWH},
}
Figure