Consistency of a Recurrent Language Model With Respect to Incomplete Decoding (2020)

Abstract: Despite strong performance on a variety of tasks, neural sequence models trained with maximum likelihood have been shown to exhibit issues such as length bias and degenerate repetition. We study the related issue of receiving infinite-length sequences from a recurrent language model when using common decoding algorithms. To analyze this issue, we first define inconsistency of a decoding algorithm, meaning that the algorithm can yield an infinite-length sequence that has zero probability under the model. We prove that commonly used incomplete decoding algorithms – greedy search, beam search, top-k sampling, and nucleus 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 variants of top-k and nucleus sampling, and a self-terminating recurrent language model. Empirical results show that inconsistency occurs in practice, and that the proposed methods prevent inconsistency.

## introduction neural sequence models trained with maximum likelihood estimation (mle) have become a standard approach to modeling sequences in a variety of natural language applications such as machine translation @xcite , dialogue modeling @xcite , and language modeling @xcite . despite this success, mletrained neural sequence models have been shown to exhibit issues such as length bias @xcite and degenerate repetition @xcite . these issues are suspected to be related to the maximum 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 @xcite . this has prompted the development of alternative decoding methods @xcite and training objectives @xcite . in this paper, we formalize and study this discrepancy between the model and the decoding algorithm. we begin by formally defining recurrent neural language models, a family that encompasses neural models used in practice, such as recurrent neural networks @xcite @xcite , and transformers @xcite . next, we formally define a decoding algorithm -a function that induces a distribution over sequences given a recurrent language 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 algorithm may return improbable, infinite-length sequences. our main finding is that a sequence which receives zero probability under a recurrent language model's distribution can receive nonzero probability under the distribution induced by a decoding algorithm. this occurs when the recurrent language model always ranks the sequence termination token outside of the set of tokens considered at each decoding step, yielding an infinite-length, zero probability sequence. this holds whenever the decoding algorithm is incomplete, in the sense that the algorithm excludes tokens from consideration at each step of decoding, which is the case for common methods such as greedy search, beam search, top-k sampling @xcite , and nucleus sampling @xcite . we formalize our main finding using the notion of consistency @xcite -whether a distribution assigns probability mass only to finite sequences -and prove that a consistent recurrent language model paired with an incomplete decoding algorithm can induce an inconsistent sequence distribution. based on the insight that inconsistency occurs due to the behavior of the termination token under incomplete decoding, we develop two methods for addressing inconsistency. first, we propose consistent sampling methods which guarantee that the termination token is not excluded from selection during decoding. second, we introduce a self-terminating recurrent language model which ensures that the termination token is eventually ranked above all others, guaranteeing consistency under incomplete decoding. to empirically measure inconsistency, we decode sequences from trained recurrent language models and measure the proportion of sequences with lengths far exceeding the maximum training sequence length. our experiments on the wikitext2 dataset @xcite suggest that inconsistency occurs in practice when using incomplete decoding methods, while the proposed consistent sampling methods and self-terminating model parameterization prevent inconsistency and maintain language modeling quality. the theoretical analysis reveals defects of existing decoding algorithms, providing a way to develop future models, inference procedures, and learning algorithms. we present methods related to sampling and model parameterization, but there are more directions for future investigation; we close with directions related to sequence-level learning. ## background we begin our discussion by establishing background definitions. first, we define a sequence which is the main object of our investigation. definition 2.1 (sequence). a sequence y is an ordered collection of items from a predefined finite vocabulary v . a sequence of finite length always ends with a special token @xmath0. each model we consider generates a sequence conditioned on context information, such as a prefix in sentence completion. to consider this, we define a context distribution. definition 2.2 (context distribution). a context distribution p(c) is a probability distribution defined over a set c. an element @xmath1. ## fixing the inconsistency in this section, we consider two ways to prevent inconsistency arising from incomplete decoding algorithms. first, we introduce consistent versions of top-k and nucleus sampling. second, we introduce the self-terminating recurrent language model, which is consistent when paired with any of the decoding algorithms considered in this paper. ## empirical validation the theoretical results rely on the existence of a model that results in inconsistency; it remains to be shown that inconsistency with respect to incomplete decoding occurs with recurrent language models encountered in practice. moreover, while the proposed methods carry theoretical guarantees in terms of consistency, we must check whether they retain language modeling quality. to do so, we perform experiments using a sequence completion task. in each experiment, we use the beginning of a sequence as context, then decode continuations from a trained recurrent lm and measure the proportion of non-terminated sequences in order to approximately measure inconsistency. the first experiment ( §5.1) shows that inconsistency occurs in practice, and the second experiment ( §5.2) shows the effectiveness of the proposed approaches. our third experiment ( §5.3) shows that inconsistency also occurs frequently in gpt-2, a large-scale transformer language model. 4 sequence completion. we evaluate recurrent language models on a sequence completion task, which has previously been used to evaluate the effectiveness of sequence models, e.g., sutskever et al. (2011); graves (2013 2019 ). sequence completion is a general setting for studying the behavior of language models, encompassing machine translation @xcite , story generation @xcite , and dialogue modeling @xcite . the task consists of decoding a continuation ŷ ∼ f(p θ , c) given a length-k prefix @xmath2, . . . , c k ), resulting in a completion (c 1 , . . . , c k , ŷ1 . . . , ŷt ). dataset. our first two experiments use wikitext2 @xcite , which consists of paragraphs from english wikipedia, since it has frequently been used to evaluate language models @xcite @xcite . we consider both word and bpe foot_2 tokenization. we split each paragraph into sentences using spacy foot_3 . we split each sequence, using the first k tokens as a context and the remaining tokens as a continuation. to ensure that each sequence contains a prefix, we prepend padding tokens to make it length k. special bos and eos tokens are inserted at the beginning and end of each sequence. we use @xmath3. ## future directions the methods we proposed in this paper resolve inconsistency by changing the decoding algorithm or model parameterization. another approach is to address inconsistency in the learning phase. one interesting direction is to investigate whether the lack of decoding in maximum likelihood learning is a cause of inconsistency. maximum likelihood learning fits the model p θ using the data distribution, whereas a decoded sequence from the trained model follows the distribution q f induced by a decoding algorithm. sequence-level learning, however, uses a decoding algorithm during training (e.g., ranzato et al. ( 2016 )), which we hypothesize can result in a good sequence generator that is consistent with respect to incomplete decoding. ## conclusion we extended the notion of consistency of a recurrent language model put forward by @xcite to incorporate a decoding algorithm, and used it to analyze the discrepancy between a model and the distribution induced by a decoding algorithm. we proved that incomplete decoding is inconsistent, and proposed two methods to prevent this: consistent decoding and the self-terminating recurrent language model. using a sequence completion task, we confirmed that empirical inconsistency occurs in practice, and that each method prevents inconsistency while maintaining the quality of generated sequences. we suspect the absence of decoding in maximum likelihood estimation as a cause behind this inconsistency, and suggest investigating sequence-level learning as an alternative.