Abstract
Discriminative reordering models are essential for high-quality Statistical Machine Translation (SMT) but are notoriously difficult to train on large-scale datasets due to high computational and memory requirements. We present a novel approach that solves the dual problem of multinomial logistic regression (MLR) using a stochastic exponentiated gradient algorithm. This formulation allows for an efficient "data shrinking" technique where training examples are dynamically removed once they satisfy convergence criteria. Our experiments on the Arabic-English MultiUN corpus demonstrate that this method achieves a 4x speedup in training time and significant memory reduction without compromising translation accuracy.
Introduction
In Statistical Machine Translation (SMT), reordering models handle the structural differences between source and target languages—for instance, determining the correct placement of adjectives relative to nouns. While simple lexicalized models are common, discriminative models using rich contextual features provide superior performance. However, training these models on tens of millions of phrase pairs often leads to significant bottlenecks, including excessive training times and memory exhaustion (disk-swapping) that can stall the learning process.
Methodology
The core of our approach is the transition from the Primal Problem to the Dual Problem. In the primal formulation, we directly optimize classifier weights. In the dual formulation, we optimize Lagrange multipliers associated with each training example.
We employ a Stochastic Exponentiated Gradient (EG) algorithm to solve the dual MLR. The primary advantage of this dual approach is Data Shrinking. As training progresses, many examples reach their optimal dual variables and contribute little to further weight updates. By identifying and removing these "inactive" examples from the training set on the fly, we focus computational resources on the "hard" examples that are still being learned. This not only speeds up computation but also reduces the memory footprint as the active dataset size decreases.
Experimental Setup
We evaluated our model using the MultiUN corpus for Arabic-to-English translation. The training set consisted of over 47 million phrase pairs with approximately 670,000 unique features. Testing was conducted on the NIST MT06 and MT08 datasets to measure translation quality via BLEU scores and classification accuracy.
Results and Discussion
The dual approach significantly improves training efficiency. As shown in Figure 1, the percentage of active phrase pairs drops precipitously after only a few iterations. For a shrinking parameter of $\epsilon=0.1$, more than 99% of the training data is disregarded by the 13th iteration, allowing the model to focus on the most informative samples.
This reduction in active data translates directly to faster training times. As summarized in the table below, the Dual MLR with $\epsilon=0.1$ completed training in just 18 minutes, compared to 1 hour and 9 minutes for the Primal MLR—a nearly 4x speedup.
Crucially, this efficiency does not come at the cost of translation quality. The Dual MLR achieved BLEU scores of 31.36 on MT06 and 34.87 on MT08, which are statistically equivalent to the Primal MLR results and significantly better than baseline lexicalized models. However, the choice of the shrinking parameter $\epsilon$ is critical; setting it too high (e.g., 1.0) leads to excessive data loss and a higher error rate (21.13% vs ~17.9%).
Conclusion
By leveraging the dual formulation of MLR, we can train high-performance reordering models on massive datasets with a fraction of the time and memory required by traditional primal methods. This "shrinking" technique is a general-purpose optimization strategy applicable to various large-scale NLP classification tasks, providing a robust solution to the scalability challenges of discriminative learning.
Summary updated