Machine Translation Decoding beyond Beam Search

Proceedings of the 2021 Conference on Empirical Methods in Natural Language Processing, pages 8410–8434 November 7–11, 2021. c⃝2021 Association for Computational Linguistics 8410 Machine Translation Decoding beyond Beam Search Rémi Leblond DeepMind Jean-Baptiste Alayrac DeepMind Laurent Sifre DeepMind Miruna Pislar DeepMind Jean-Baptiste Lespiau DeepMind Ioannis Antonoglou DeepMind Karen Simonyan DeepMind Oriol Vinyals DeepMind Abstract Beam search is the go-to method for decod- ing auto-regressive machine translation mod- els. While it yields consistent improvements in terms of BLEU, it is only concerned with find- ing outputs with high model likelihood, and is thus agnostic to whatever end metric or score practitioners care about. Our aim is to es- tablish whether beam search can be replaced by a more powerful metric-driven search tech- nique. To this end, we explore numerous de- coding algorithms, including some which rely on a value function parameterised by a neu- ral network, and report results on a variety of metrics. Notably, we introduce a Monte- Carlo Tree Search (MCTS) based method and showcase its competitiveness. We provide a blueprint for how to use MCTS fruitfully in language applications, which opens promising future directions. We find that which algo- rithm is best heavily depends on the character- istics of the goal metric; we believe that our extensive experiments and analysis will inform further research in this area. 1 Introduction Sequence to sequence model decoding remains something of a paradox. The most widely adopted training method for these models is maximum like- lihood estimation (MLE), which aims at maximis- ing the probability of the ground truth outputs pro- vided in the training datasets. Consequently, decod- ing from MLE-trained models is done by trying to find the output to which the model assigns maxi- mum likelihood. Unfortunately, as models usually predict tokens one by one, exact search is not fea- sible in the general case and practitioners resort to heuristic mechanisms instead. The most popular of these heuristics is beam search (Reddy, 1977), which maintains several hy- potheses in parallel and is guaranteed to find a more likely output than the more basic greedy decoding. This approach has some obvious flaws: for one, it is completely agnostic to the actual metrics (or scores) practitioners actually want to optimise. Even more crucially, in most cases beam search fails at the one thing it is supposed to do: find- ing the optimal output sequence (w.r.t the model), as shown by Stahlberg and Byrne (2019). Also alarming are the findings of Welleck et al. (2020), proving that traditional search mechanisms can yield infinite-length outputs, to which the model assigns zero probability. Finally, the use of likeli- hood as a training objective has a spectacular side- effect: it causes trained models to have an inordi- nate fondness for empty outputs. By using exact search on the output likelihood in machine trans- lation, Stahlberg and Byrne (2019) show that in more than half of cases the highest scoring output according to the model is the empty sentence! All told, we rely on models placing a …

Content truncated to 500 words