If beam search is the answer, what was the question?

Proceedings of the 2020 Conference on Empirical Methods in Natural Language Processing, pages 2173–2185, November 16–20, 2020. c⃝2020 Association for Computational Linguistics 2173 If Beam Search is the Answer, What was the Question? Clara Meister Ryan Cotterell , Tim Vieira ETH Z¨urich University of Cambridge Johns Hopkins University clara.meister@inf.ethz.ch tim.vieira@gmail.com ryan.cotterell@inf.ethz.ch Abstract Quite surprisingly, exact maximum a posteri- ori (MAP) decoding of neural language gen- erators frequently leads to low-quality results (Stahlberg and Byrne, 2019). Rather, most state-of-the-art results on language generation tasks are attained using beam search despite its overwhelmingly high search error rate. This implies that the MAP objective alone does not express the properties we desire in text, which merits the question: if beam search is the an- swer, what was the question? We frame beam search as the exact solution to a different de- coding objective in order to gain insights into why high probability under a model alone may not indicate adequacy. We find that beam search enforces uniform information density in text, a property motivated by cognitive sci- ence. We suggest a set of decoding objec- tives that explicitly enforce this property and find that exact decoding with these objectives alleviates the problems encountered when de- coding poorly calibrated language generation models. Additionally, we analyze the text pro- duced using various decoding strategies and see that, in our neural machine translation ex- periments, the extent to which this property is adhered to strongly correlates with BLEU. Our code is publicly available at https:// github.com/rycolab/uid-decoding. 1 Introduction As a simple search heuristic, beam search has been used to decode models developed by the NLP community for decades. Indeed, it is notewor- thy that beam search is one of the few NLP al- gorithms that has stood the test of time: It has remained a cornerstone of NLP systems since the 1970s (Reddy, 1977). As such, it became the nat- ural choice for decoding neural probabilistic text generators—whose design makes evaluating the full search space impossible (Kalchbrenner and Blunsom, 2013; Sutskever et al., 2014; Vinyals and Le, 2015; Yin et al., 2016). While there is no formal guarantee that beam search will return— Figure 1: Average std. deviation σ of surprisals (per sentence) and corpus BLEU for translations generated using exact search over the MAP objective with a greedy regularizer (Eq. (11)) with varying degrees of λ. References for beam search (k = 5 and k = 100) are included. Sub-graph shows the explicit relationship between BLEU and σ. λ and σ axes are log-scaled. or even approximate—the highest-scoring candi- date under a model, it has repeatedly proven its merit in practice (Serban et al., 2017; Edunov et al., 2018; Yang et al., 2019) and, thus, has largely been tolerated—even embraced—as NLP’s go-to search heuristic. However, in the context of neural ma- chine translation (NMT), a shocking empirical find- ing has emerged: Using beam search to decode sentences from neural text generators almost invari- ably leads to better text than using exact search (or beam search …

Content truncated to 500 words