Mode recovery in neural autoregressive sequence modeling (2021)

Abstract: Despite its wide use, recent studies have revealed unexpected and undesirable properties of neural autoregressive sequence models trained with maximum likelihood, such as an unreasonably high affinity to short sequences after training and to infinitely long sequences at decoding time. We propose to study these phenomena by investigating how the modes, or local maxima, of a distribution are maintained throughout the full learning chain of the ground-truth, empirical, learned and decoding-induced distributions, via the newly proposed mode recovery cost . We design a tractable testbed where we build three types of ground-truth distributions: (1) an LSTM based structured distribution, (2) an unstructured distribution where probability of a sequence does not depend on its content, and (3) a product of these two which we call a semi-structured distribution. Our study reveals both expected and unexpected findings. First, starting with data collection, mode recovery cost strongly relies on the ground-truth distribution and is most costly with the semi-structured distribution. Second, after learning, mode recovery cost from the ground-truth distribution may increase or decrease compared to data collection, with the largest cost degradation occurring with the semi-structured ground-truth distribution. Finally, the ability of the decoding-induced distribution to recover modes from the learned distribution is highly impacted by the choices made earlier in the learning chain. We conclude that future research must consider the entire learning chain in order to fully understand the potentials and perils and to further improve neural autoregressive sequence models.

## introduction neural autoregressive sequence modeling has become the standard approach to modeling sequences in a variety of natural language processing applications @xcite @xcite . in this modeling paradigm, the probability of a sequence is decomposed into the product of the conditional probability of each token given the previous tokens. each conditional probability is modeled by a shared neural network, typically implemented as a recurrent neural network @xcite or a transformer @xcite . despite its success, recent studies have identified peculiarities in neural autoregressive sequence models. @xcite identify hallucinations in neural machine translation, in which a well-trained model suddenly generates a nonsense translation when a rare token is artificially introduced to a source sentence. @xcite observe that a vast portion of probability mass is concentrated on the empty sequence in neural machine translation, although the models they studied were never presented with empty sequences during training. @xcite report that large-scale language models often produce pathological sequences with many n-gram repetitions, at a rate which far exceeds that of the training data. @xcite show that neural language models can generate infinite-length sequences despite being trained on only finite sequences. a common theme underlying these findings is that well-trained models can assign unreasonably high probabilities to sequences that are dissimilar to any sequence from the training set. in particular, the modes of the model's distribution appear to be undesired, implying that the model failed to recover the modes of the empirical distribution, which we term mode recovery degradation. the situation is further complicated by the fact that we only approximate the model's modes with a decoding algorithm, so it is unclear whether the decoding algorithm, the model, or even the data collection is at fault. in this paper, we isolate and study mode recovery degradation by characterizing each stage of neural sequence modeling as inducing a new sequence distribution, then directly analyzing each distribution's modes. with this approach, we diagnose at what stage, and to what extent, sequences receive unreasonably high probabilities. to do so, we first define a learning chain that consists of the ground-truth distribution, the empirical distribution induced by data collection, the learned distribution, and the decoding-induced distribution. we then quantify the extent to which the most probable sequences under each distribution match the most probable sequences under the ground-truth distribution by defining a mode recovery cost, which measures how expensive it is for a later distribution to recover the most probable sequences of an earlier distribution in the chain. in summary, we find that mode recovery cost is non-trivial at each part of the neural autoregressive learning pipeline. the pattern of how mode recovery changes heavily depends on the properties of the ground-truth distribution. in particular, when the ground-truth distribution is parameterized as a product of highly structured distribution based on lstm neural network and unstructured distribution where the probability of every sequence is sampled independently from all the others, its modes are more costly to recover. furthermore, the ability of a decoding algorithm to recover modes is also dependent upon all choices made earlier in the chain including the underlying ground-truth distribution, even in the case of modes of the learned distribution. these observations make a meaningful step towards better understanding of mode degradation in neural autoregressive sequence modeling. ## neural autoregressive sequence modeling we consider the problem of modeling a distribution p * (s) over variable-length, discrete sequences s. formally, @xmath0, where @xmath1, 2, . . . , l}, σ is a finite set of tokens, and ω ⊂ l @xmath2. every sequence @xmath3. in neural autoregressive sequence modeling, we model the distribution p * (s) as p θ (s) = |s| @xmath4, with each conditional distribution parameterized by a shared neural network. ## mode recovery mode sets we define a k-mode set as a set of top-k sequences under a given distribution: ## why do we study mode recovery? the recent success of neural sequence modeling has operated on the assumption that we can find sequences that are reasonably similar to training sequences by fitting a neural autoregressive model to maximize the log-probabilities of the training sequences (maximum-likelihood learning) and searching for the most likely sequences under the trained model (maximum a posteriori inference). however, recent studies suggest that the most likely sequences may not resemble training sequences at all. for instance, the learning stage can yield a distribution p model which places high probability on empty @xcite or repetitive @xcite sequences, while the decoding stage can yield a distribution p f which places non-zero mass on infinite-length sequences @xcite . as a result, various workarounds have been proposed in the form of alternative learning or decoding algorithms @xcite @xcite @xcite @xcite @xcite . a particularly relevant work by @xcite argues that the modes of neural sequence models are inadequate and thus we must discard maximum-a-posteriori inference altogether. rather than advocating for a particular solution, we instead seek an understanding of why the conventional approach displays these peculiar behaviors. while we do not claim to provide a full explanation, the first step is developing a way of quantifying the problem, then localizing it. to this end, we develop the mode recovery cost and measure it along the learning chain p * p emp p model p f . this focus on modes departs from the conventional focus on evaluating the full distribution with a probabilistic divergence. ## a testbed for evaluating mode recovery it is intractable to measure mode recovery cost (eq. 4) on real-world datasets that are popular in neural sequence modeling, e.g. wikitext-103 @xcite given the exponential growth of the sequence space with sequence length. for example, the training part of wikitext-103 consists of 28k sequences with 3.5k tokens, each drawn from a vocabulary of 267k tokens. furthermore, these datasets do not provide access to the ground-truth distribution, which prevents us from computing any recovery cost involving p * . in order to allow exact computations of mode recovery cost, we design a controllable testbed. this testbed consists of (1) the ground-truth distribution, which permits explicit control over the structuredness, (2) the data collection step, which controls the complexity of the empirical distribution, (3) the learning step, which allows us to induce the learned distribution with neural autoregressive models, and (4) the decoding step, where the decoding algorithm induces the approximation of the learned distribution. in the rest of this section we describe each distribution in detail. we set the size of the sequence space of the testbed so that all computations are feasible. we limit the vocabulary size |σ| to 7 tokens and use a maximum sequence length l of 10 tokens. this results in a sequence space size |ω| of around 12 million sequences. ground-truth distribution. we define each ground-truth distribution as a product of two components: we implement p θ using a randomly initialized lstm neural network, with two layers and 512 lstm units in every layer. we build p(s; µ, σ) with µ = 0.0 and σ = 1.0. we build the ground-truth distribution to reflect some properties of real data. first, real data has strong statistical dependencies among the tokens within each sequence. we induce these dependencies by assuming that each sequence is produced from left to right by generating each token conditioned on the previously generated sub-sequences of tokens. we implement this procedure using the lstm neural network. second, there exist exceptional sequences in real data which receive high probability even though those sequences do not reflect statistical dependencies mentioned above. we build another distribution component in order to introduce exceptions in a way that there are no statistical dependencies in the given sequence. we use independent samples from a laplace distribution as unnormalized probabilities of every sequence from the sequence space ω. we thus ensure that there are no statistical dependencies among the tokens under this unstructured distribution. we thus construct the product of two distributions described above so that it exhibits structured and unstructured aspects of the generating process. the mixing coefficient α allows us to interpolate between the heavily structured to heavily unstructured ground-truth distributions. we call it semistructured when 0 < α < 1. empirical distribution. we create each empirical distribution p emp (eq. 2) by drawing samples with replacement from the ground-truth distribution. we sample a training multi-set and a validation multi-set, then form the empirical distribution with their union . we denote the size of the training dataset as n train , and set the size of the validation set to .05 × n train . learned distribution. we obtain each learned distribution p model by training an lstm model on the training dataset d train using maximum likelihood (eq. 1). we vary the complexity of the learned distribution using the number of lstm units of every layer of the lstm neural network from the set n model @xmath5, 512}. variable-length sequences are padded with a pad token in order to form equal-length batches of 5120 sequences. we use the adam optimizer (kingma and ba, 2014) with a learning rate of 10 -4 . we compute validation loss every 5×10 2 steps, and apply early stopping with a patience of 5 validation rounds based on increasing validation loss. we train the model for up to 2×10 4 steps. after training, the checkpoint with the lowest validation loss is selected to parameterize the learned distribution p model . decoding-induced distribution. we form decoding-induced distributions (eq. 3) using beam search and ancestral sampling. for beam search, we set n @xmath6. for ancestral sampling, we sample sequences and discard duplicates until a given number of unique sequences, n @xmath7, are obtained. randomness. to account for randomness that occurs when initializing the ground-truth distribution, sampling the empirical distribution, and using ancestral sampling during decoding, we run each configuration of the learning chain (i.e. groundtruth, empirical, learned, and decoding-induced distributions) with 10 different random seeds, and report the median and 25-th and 75-th quantiles, if available, of each evaluation metric. ## mode recovery in the learning chain we use our testbed to empirically study mode recovery degradation by measuring mode recovery cost in the data collection, learning, and decoding, stages of the learning chain. we use @xmath8. data collection: recovering ground-truth modes with the empirical distribution. we start by asking: does mode degradation happen during data collection? we fix n @xmath9. 1 using three configurations of ground-truth distributions. it shows that mode recovery cost grows as k increases. furthermore, we observe different patterns of mode recovery cost given each choice of the ground-truth distribution. we observe distinct patterns of mode recovery with either structured (α = 1.0) and unstructured (α = 0.0) ground-truth distributions. we found that the structured ground-truth distribution assigns higher probabilities to shorter sequences because of lstm neural network and autoregressive factorization. this implies that sequences which are sorted w.r.t. their probabilities are also sorted w.r.t. their lengths. because of this property the empirical distribution can recover modes from the structured ground-truth distribution almost perfectly for particular k. in the case of the unstructured groundtruth distribution mode recovery cost is lower compared to other cases. this ground-truth distribution has no statistical dependencies within modes which makes it less interesting to us due to the lack of similarity with real data. finally, in the case of the semi-structured groundtruth distribution (α = 0.3) the cost of recovering its modes grows increasingly as k increases. in other words, empirical distributions recover modes from ground-truth distributions less effectively when latter exhibit statistical dependencies as well as many exceptional sequence probabilities. now we focus on the influence of the training set size n train on mode recovery during data collection. we fix @xmath10, 5 × 10 5 , 10 6 , 5 × 10 6 , 10 7 }, shown in fig. 2 . mode recovery cost naturally decreases as we increase the number of training instances as seen on the right-most side of fig. 2 . the left-most side is more interesting to us because it corresponds to values of n train that reflect real world problems. for instance, in the case of n @xmath11. we thus conclude that mode recovery degradation happens already during data collection, and that parameterization of ground-truth distributions impacts mode recovery cost. learning: recovering modes with the learned distribution. the next stage in the chain is learning, p emp learning p model , in which we train a model using a training dataset with the expectation that the model will match the ground-truth distribution. our experiments center on the question: how does mode recovery degradation in the learning stage compare to that of the data collection stage? for instance, we anticipate that the learned model will have a mode recovery cost that is at least as bad as that of the empirical distribution. we measure the mode recovery cost reduction log-rate from empirical to learned distributions, log 3 shows the reduction log-rate as a function of k with fixed n @xmath12, for three different ground-truth distributions. we observe three different cases, with a clear dependency on what kind of data was used during learning. learning with data coming from the unstructured ground-truth distribution (α = 0.0) results in mode recovery cost reduction log-rate being close to zero. this implies that the underlying lstm model is able to memorize the unstructured data points coming from the empirical distribution, but it can not recover any other modes from the ground-truth distribution. with the structured ground-truth distribution (α = 1.0), we observe positive log-rate for some values of k. this means that the learned distribution is able to recover modes of the ground-truth distribution at a lower cost than the empirical distribution does. similarly to data collection stage, this largely happens due to the property of lstm to put high probabilities on short sequences. the learned distribution's ability in mode recovery goes above that of the empirical distribution when there is a match between the parameterization of models behind the ground-truth distribution and the learned distribution. in the case of the semi-structured ground-truth distribution (α = 0.3), the learned distribution has severe mode recovery degradation even with smaller values of k (left-most side of fig. 3 ). the model is unable to perfectly learn an underlying dataset which has a few statistical exceptions within it. in addition to our observations about recovering modes from ground-truth distributions, fig. 4 shows at what cost modes of each empirical distribution are recovered by the learned distribution as a function of n train . the learned distribution recovers modes of the empirical distribution with the highest cost when the latter was induced using the semi-structured ground-truth distribution. mode recovery cost of all empirical distributions naturally decreases as number of training instances n train becomes unrealistically high. we conjecture that the combination of sequences with statistical dependencies and sequences which do not share any statistical dependencies in the dataset makes the learned distribution struggling at mode recovery from both ground-truth and empirical distributions. we conclude that properties of ground-truth distributions have direct impacts on the ability of the learned distributions to recover modes from groundtruth and empirical distributions. learning struggles to capture all patterns from the underlying distributions when the latter exhibit exceptions in statistical dependencies within data points. decoding: recovering modes with the decodinginduced distribution. the final stage in the learning chain is decoding, p model decoding p f , in which we use a decoding algorithm f to obtain highly-probable sequences. we study both a deterministic decoding algorithm, implemented using beam search, and a stochastic decoding algorithm, implemented using ancestral sampling. our experiments are centered on two questions: (1) how do the choices made earlier in the learning chain affect the decoding behavior? and (2) how is this behavior affected by the choice of the decoding algorithm? we consider six different datasets that we train models on, each of which is a combination of the ground-truth distribution where α ∈ {0.0, 0.3, 1.0}, and the number of training points n @xmath13, 5 × 10 6 }. our previous analysis revealed each of those datasets leads to a substantially different ability of the learned distributions to recover modes from earlier distributions along the learning chain. we set n model hs to be equal to 512. our choice of decoding algorithms results in decoding-induced distributions with a limited support. hence the induced distribution p f often fails to recover modes of distributions from the earlier stage of the chain especially as k increases. as we described in sec. 3, we use the k-mode set overlap i k (• p f ) to examine the degree to which a given decoding algorithm f fails at mode recovery. first, we study how well the decoding algorithm recovers modes from the learned distribution. fig. 5 shows k-mode set overlap between learned and decoding-induced distributions using both beam search (left) and ancestral sampling (right). both algorithms fail increasingly more often as k increases. ancestral sampling fails substantially more often than beam search. this is expected given that ancestral sampling was not designed to find highly probable sequences, unlike beam search. both of these decoding algorithms fail to recover modes from the learned distribution most when the learned distribution was obtained using the semi-structured ground-truth distribution (α = 0.3), regardless of the size of the dataset. in other words, the choices made earlier along the learning chain impact the decoding-induced distribution's ability to recover modes from the learned distribution, regardless of which decoding algorithm was used. second, we investigate how the choice of the decoding algorithm influences the difference in how the decoding-induced distribution recovers modes of ground-truth and learned distributions. we thus look at the k-mode set overlap reduction from ground-truth to learned distributions (i k (p * α p f )-i k (p model p f )) for both beam search and ancestral sampling. the positive overlap reduction in fig. 6 means that the decoding algorithm fails more to recover modes from the learned distribution than from the ground-truth distribution. each decoding algorithm shows a different pattern of the overlap reduction. reduction is more or less flat and is close to zero for ancestral sampling regardless of the choice of the dataset. it is, however, different with beam search where we have three observations. first, the reduction overlap deviates from zero as k increases. second, with the semi-structured ground-truth distribution (α = 0.3) the overlap deviates most, which is then followed by the unstructured variant (α = 0.0). third, the number of training points n train leads to significant difference in the case of the semi-structured distribution. reduction overlap goes very negative with the smaller number of training instances, while the trend flips when we have ten times more data. we thereby conclude that the pattern of mode recovery degradation along the entire learning chain depends on the choice of the decoding algorithm. ## conclusion in this paper, we studied the propensity of neural autoregressive sequence models to assign high probabilities to sequences that differ from those in the ground-truth distribution. to measure this phenomenon, we defined mode recovery cost, which measures a distribution's ability to recover the highly probable sequences of another distribution. we developed a testbed for evaluating mode recovery cost throughout the entire learning chain. we provided evidence of non-trivial mode recovery cost within this testbed, and observed that the increase in the cost relies heavily on the structuredness of the ground-truth distribution. mode recovery from earlier distributions was more costly along the learning chain when the ground-truth distribution was constructed as a product of fullystructured and fully-unstructured distributions such that it reflects patterns in real data. mode recovery cost at each stage depended on all the choices made earlier at all the previous stages. the empirical distribution induced during data collection recovered modes from the ground-truth distribution imperfectly regardless of the dataset size. it was particularly high when we used the semi-structured ground-truth distribution. as expected, mode recovery cost was negatively correlated with a number of training instances. mode recovery after learning was directly affected by the choice of the ground-truth distribution as well. in general, the learned distribution failed to recover modes from the ground-truth distribution as well as the empirical distribution does. this trend flipped, however, when the learned distribution was parameterized identically to the ground-truth distribution. distributions induced during decoding recovered modes of learned distributions with sig-nificantly different costs depending on all choices made at previous stages of the learning chain. the choice of decoding algorithm was also found to influence patterns of mode recovery cost. based on these observations, we conclude that we have to use the entire learning chain to study mode recovery in neural autoregressive sequence modeling. future directions. we highlight three main directions of research based on our findings and conclusions. first, mode recovery along the learning chain must be studied in the context of real world problems. to do so, there is a need for future work on approximation schemes of mode recovery cost computable in real tasks. second, the relationship between the ground-truth and learned distributions may be changed to better match real-world cases, for instance by considering structured ground-truth distributions that are less similar to the learned model family, or unstructured components that are informed by sequence content. third, we have considered standard practices of neural autoregressive modeling while constructing the learning chain. extending the learning chain to study the effects of new approaches such as knowledge distillation @xcite or back translation @xcite is another fruitful direction for future research.