Towards Decoding as Continuous Optimisation in Neural Machine Translation

Cong Duy Vu Hoang, Gholamreza Haffari, Trevor Cohn

Abstract

Neural Machine Translation (NMT) typically relies on discrete heuristic search methods like beam search for decoding. This paper proposes a paradigm shift, treating decoding as a continuous optimization problem. By relaxing the discrete word selection into a probability simplex and employing gradient-based optimization—specifically Exponentiated Gradient (EG)—the authors enable decoding in complex, non-sequential models such as bidirectional ensembles. Results demonstrate that this continuous approach not only converges effectively but also outperforms standard beam search in various translation tasks.

The Challenge of Discrete Decoding

In NMT, "decoding" is the process of finding the most likely target sentence given a source sentence. Traditionally, this is a discrete search problem over an astronomical number of possible sentences. To manage this complexity, researchers have relied on heuristics like greedy search or beam search.

However, these methods have a major flaw: they require a strict left-to-right generation order. This constraint makes it nearly impossible to use "global" information or to combine models that work in different directions (e.g., a model that reads left-to-right and one that reads right-to-left). Standard search is also non-Markovian, meaning it cannot easily use dynamic programming to find the true global optimum. This research aims to break the "left-to-right" cage by turning decoding into a continuous calculus problem.

Methods: Continuous Relaxation and Optimization

The core innovation is Continuous Relaxation. Instead of forcing the model to pick a single "one-hot" word at each position, the authors allow the model to maintain a "soft" distribution (a vector on a probability simplex) over the entire vocabulary.

  1. Relaxation: The discrete optimization problem is transformed into a continuous one where the objective is to minimize the negative log-probability of the sequence.
  2. Optimization Algorithms: The authors compared Stochastic Gradient Descent (SGD) with Exponentiated Gradient (EG). EG proved superior, as its multiplicative updates are naturally suited to the geometry of probability distributions (ensuring values stay between 0 and 1 and sum to 1).
  3. Extended Models: This framework allows for decoding using Bidirectional Ensembles (intersecting a left-to-right model with a right-to-left model) and Bilingual Ensembles. These models have no natural start-to-finish order, making traditional beam search inapplicable.

Key Results and Convergence

Convergence of continuous cost (CCost), discrete cost (DCost), and BLEU score over iterations for various initialization strategies.

The optimization process shows clear convergence in both cost and BLEU scores. The authors found that initialization is critical: because the optimization landscape is non-convex, starting from a random or uniform distribution leads to poor results. Initializing with a quick greedy or beam search provides a "warm start" that the continuous optimizer then refines.

On the BTEC Chinese-English task, the bidirectional ensemble using EG decoding achieved 39.13 BLEU, a significant jump over the standard beam search baseline of 38.02. On the massive WMT German-English task, the method improved BLEU from 26.69 (beam search) to 27.34 (bidirectional EG).

Validating the Relaxation

A critical finding of this work is the validity of the continuous approximation. One might worry that optimizing a "soft" distribution wouldn't translate to the final discrete sentence. However, the authors found that the continuous cost and the final discrete (rounded) cost are almost identical in most cases.

Correlation between continuous cost (CCost) and discrete cost (DCost), validating the continuous relaxation approach.

Limitations and Future Work

While powerful, the method has limitations:

  • Speed: Decoding takes about 3.1 seconds per sentence—slower than beam search, though manageable for high-quality document translation.
  • Fixed Length: The current formulation assumes a fixed maximum length for the translation.
  • Local Optima: The algorithm can still get stuck in local minima if not initialized well.

Future directions include incorporating more complex global constraints, such as "word coverage" (ensuring every source word is translated) and "fertility," which are traditionally difficult to implement in standard NMT decoding.

Summary updated

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.
BibTeX
@inproceedings{hoang2017towards,
  author = {Cong Duy Vu Hoang and Gholamreza Haffari and Trevor Cohn},
  title = {{Towards Decoding as Continuous Optimisation in Neural Machine Translation}},
  booktitle = {Conference on Empirical Methods in Natural Language Processing},
  year = {2017},
  doi = {10.18653/v1/d17-1014},
}
Figure