When to Finish? Optimal Beam Search for Neural Text Generation (modulo beam size)

Proceedings of the 2017 Conference on Empirical Methods in Natural Language Processing, pages 2134–2139 Copenhagen, Denmark, September 7–11, 2017. c⃝2017 Association for Computational Linguistics When to Finish? Optimal Beam Search for Neural Text Generation (modulo beam size) Liang Huang and Kai Zhao† and Mingbo Ma School of Electrical Engineering and Computer Science Oregon State University Corvallis, Oregon, USA {liang.huang.sh, kzhao.hf, cosmmb}@gmail.com Abstract In neural text generation such as neural machine translation, summarization, and image captioning, beam search is widely used to improve the output text quality. However, in the neural generation set- ting, hypotheses can finish in different steps, which makes it difficult to decide when to end beam search to ensure op- timality. We propose a provably optimal beam search algorithm that will always re- turn the optimal-score complete hypothe- sis (modulo beam size), and finish as soon as the optimality is established (finishing no later than the baseline). To counter neural generation’s tendency for shorter hypotheses, we also introduce a bounded length reward mechanism which allows a modified version of our beam search al- gorithm to remain optimal. Experiments on neural machine translation demonstrate that our principled beam search algorithm leads to improvement in BLEU score over previously proposed alternatives. 1 Introduction In recent years, neural text generation using re- current networks have witnessed rapid progress, quickly becoming the state-of-the-art paradigms in machine translation (Kalchbrenner and Blun- som, 2013; Sutskever et al., 2014; Bahdanau et al., 2014), summarization (Rush et al., 2015; Ranzato et al., 2016), and image captioning (Vinyals et al., 2015; Xu et al., 2015). In the decoder of neu- ral generation, beam search is widely employed to boost the output text quality, often leading to sub- stantial improvement over greedy search (equiva- lent to beam size 1) in metrics such as BLEU or † Current address: Google Inc., New York, NY, USA. ROUGE; for example, Ranzato et al. (2016) re- ported +2.2 BLEU (on single reference) in trans- lation and +3.5 ROUGE-2 in summarization, both using a beam of 10. Our own experiments on ma- chine translation (see Sec. 5) show +4.2 BLEU (on four references) using a beam of 5. However, unlike traditional beam search in phrase-based MT or shift-reduce parsing where all hypotheses finish in the same number of steps, here in neural generation, hypotheses can finish in vastly different numbers of steps. Once you find a completed hypothesis (by generating the </s> sym- bol), there are still other active hypotheses in the beam that can continue to grow, which might lead to better scores. Therefore when can you end the beam search? How (and when) can you guarantee that the returned hypothesis has the optimal score modulo beam size? There have not been satisfying answers to these questions, and existing beam search strategies are heuristic methods that do not guarantee optimality. For example, the widely influential RNNsearch (Bahdanau et al., 2014) employs a “shrinking beam” method: once a completed hypothesis is found, beam size shrinks by 1, and beam search would finish …

Content truncated to 500 words