Consistency of a Recurrent Language Model With Respect to Incomplete Decoding

Proceedings of the 2020 Conference on Empirical Methods in Natural Language Processing, pages 5553–5568, November 16–20, 2020. c⃝2020 Association for Computational Linguistics 5553 Consistency of a Recurrent Language Model With Respect to Incomplete Decoding Sean Welleck1∗ Ilia Kulikov1∗ Jaedeok Kim2† Richard Yuanzhe Pang1 Kyunghyun Cho1,3 1 New York University 2 Samsung Research 3 CIFAR Associate Fellow Abstract Despite strong performance on a variety of tasks, neural sequence models trained with maximum likelihood have been shown to ex- hibit issues such as length bias and degener- ate repetition. We study the related issue of receiving infinite-length sequences from a re- current language model when using common decoding algorithms. To analyze this issue, we first define inconsistency of a decoding algo- rithm, meaning that the algorithm can yield an infinite-length sequence that has zero probabil- ity under the model. We prove that commonly used incomplete decoding algorithms – greedy search, beam search, top-k sampling, and nu- cleus sampling – are inconsistent, despite the fact that recurrent language models are trained to produce sequences of finite length. Based on these insights, we propose two remedies which address inconsistency: consistent vari- ants of top-k and nucleus sampling, and a self- terminating recurrent language model. Empir- ical results show that inconsistency occurs in practice, and that the proposed methods pre- vent inconsistency. 1 Introduction Neural sequence models trained with maximum likelihood estimation (MLE) have become a stan- dard approach to modeling sequences in a variety of natural language applications such as machine translation (Bahdanau et al., 2015), dialogue mod- eling (Vinyals et al., 2015), and language modeling (Radford et al., 2019). Despite this success, MLE- trained neural sequence models have been shown to exhibit issues such as length bias (Sountsov and Sarawagi, 2016; Stahlberg and Byrne, 2019) and degenerate repetition (Holtzman et al., 2019). ∗Equal contribution. Correspondence to: Sean Welleck wellecks@nyu.edu. †Work done at New York University. These issues are suspected to be related to the max- imum likelihood objective’s local normalization, which results in a discrepancy between the learned model’s distribution and the distribution induced by the decoding algorithm used to generate sequences (Lafferty et al., 2001; Andor et al., 2016). This has prompted the development of alternative decoding methods (Wu et al., 2016; Holtzman et al., 2019) and training objectives (Murray and Chiang, 2018; Welleck et al., 2019). In this paper, we formalize and study this discrepancy between the model and the decoding algorithm. We begin by formally defining recurrent neu- ral language models, a family that encompasses neural models used in practice, such as recurrent neural networks (Elman, 1990; Cho et al., 2014; Hochreiter and Schmidhuber, 1997), and transform- ers (Vaswani et al., 2017). Next, we formally define a decoding algorithm – a function that induces a distribution over sequences given a recurrent lan- guage model and a context distribution – which is used to obtain probable sequences from a model. In this paper, we show that the distribution induced by a decoding algorithm can contradict this intended use; instead, the decoding …

Content truncated to 500 words