Abstract
We propose a novel decoding approach for neural machine translation (NMT) based on continuous optimisation. We convert decoding - basically a discrete optimization problem - into a continuous optimization problem. The resulting constrained continuous optimisation problem is then tackled using gradient-based methods. Our powerful decoding framework enables decoding intractable models such as the intersection of left-to-right and right-to-left (bidirectional) as well as source-to-target and target-to-source (bilingual) NMT models. Our empirical results show that our decoding framework is effective, and leads to substantial improvements in translations generated from the intersected models where the typical greedy or beam search is not feasible. We also compare our framework against reranking, and analyse its advantages and disadvantages.
Introduction: The Problem with Discrete Search
In standard Neural Machine Translation (NMT), translations are typically generated using greedy or beam search. While effective, these methods are fundamentally "local": they select words sequentially from left to right. This approach suffers from two major limitations:
- Lack of Future Context: The decoder cannot account for future words when making current decisions, which can lead to suboptimal translations or dead ends.
- Incompatibility with Global Models: Combining disparate models, such as a Left-to-Right (L2R) model with a Right-to-Left (R2L) model, is nearly impossible with beam search because the models do not share a common generation order.
Finding the absolute best translation in the entire space of possible sentences is NP-hard. This research reimagines decoding as a continuous optimization problem, allowing for "global" inference that considers the entire sentence simultaneously and facilitates the combination of diverse models.
Methodology: Continuous Relaxation
The core innovation of this framework is the use of continuous relaxation to transform the discrete search space into a differentiable one.
From Discrete to Continuous
Instead of forcing the decoder to choose a single "one-hot" word vector at each position, the authors allow the model to maintain a distribution (a point on the probability simplex) over the entire vocabulary. This relaxation enables the use of gradient-based optimization algorithms.
Optimization Algorithms
The authors compared two primary approaches:
- Stochastic Gradient Descent (SGD): A standard method that requires a softmax transformation to maintain valid probability distributions.
- Exponentiated Gradient (EG): An algorithm specifically designed for simplex constraints. EG proved to be faster and more effective, converging in roughly 50 iterations compared to 150 for SGD.
Global Ensembles
Because the optimization considers all word positions at once, it can easily define objective functions that intersect different models:
- Bidirectional Ensemble: Combines L2R and R2L models to leverage both past and future context.
- Bilingual Ensemble: Combines Source-to-Target and Target-to-Source models, ensuring the translation is "back-translatable."
Key Insights
Initialization is Critical
Due to the non-convex nature of the optimization landscape, starting from a uniform distribution (a "blank slate") yields poor results. The most effective strategy is to initialize the optimization with the output of a standard beam search, which provides a strong starting point for further refinement.
The Validity of Relaxation
A critical finding is that the continuous cost (the relaxed objective being optimized) and the discrete cost (the actual sentence probability) are highly correlated. This validates the approach: by optimizing the "soft" version of the problem, the model effectively minimizes the true discrete cost.
Key Results and Performance
The proposed method was evaluated on BTEC (Chinese-English), IWSLT 2015 (German-English), and WMT 2016 (German-English) datasets.
- BLEU Score Gains: The continuous decoding framework consistently outperformed greedy and beam search baselines. On the WMT German-English task, the bidirectional ensemble achieved a BLEU score of 27.34, compared to 26.69 for standard beam search.
- Effective Model Intersection: The framework successfully combined models that are traditionally intractable to use together, such as the bilingual ensemble (S2T + T2S), providing a complementary signal that improves translation quality.
- Beyond Reranking: Unlike standard reranking, which is limited to a fixed K-best list, this optimization approach can explore the search space more fluidly to find superior translations.
Limitations and Future Work
Despite its success, the method faces a significant hurdle in computational speed. While standard beam search takes approximately 0.11 seconds per sentence, the relaxed EG decoding requires about 3.1 seconds, primarily due to the cost of calculating gradients through the NMT model. Additionally, the current formulation requires a fixed maximum length for the translation before optimization begins.
Future research may focus on integrating more complex constraints directly into the objective function, such as word coverage (ensuring all source words are translated) or fertility (controlling the number of target words per source word).
Summary updated