Is MAP Decoding All You Need? The Inadequacy of the Mode in Neural Machine Translation (2020)

Abstract: Recent studies have revealed a number of pathologies of neural machine translation (NMT) systems. Hypotheses explaining these mostly suggest there is something fundamentally wrong with NMT as a model or its training algorithm, maximum likelihood estimation (MLE). Most of this evidence was gathered using maximum a posteriori (MAP) decoding, a decision rule aimed at identifying the highest-scoring translation, i.e. the mode. We argue that the evidence corroborates the inadequacy of MAP decoding more than casts doubt on the model and its training algorithm. In this work, we show that translation distributions do reproduce various statistics of the data well, but that beam search strays from such statistics. We show that some of the known pathologies and biases of NMT are due to MAP decoding and not to NMT’s statistical assumptions nor MLE. In particular, we show that the most likely translations under the model accumulate so little probability mass that the mode can be considered essentially arbitrary. We therefore advocate for the use of decision rules that take into account the translation distribution holistically. We show that an approximation to minimum Bayes risk decoding gives competitive results confirming that NMT models do capture important aspects of translation well in expectation.

## introduction recent findings in neural machine translation (nmt) suggest that modern translation systems have some serious flaws. this is based on observations such as: i) translations produced via beam search typically under-estimate sequence length @xcite , the length bias; ii) translation quality generally deteriorates with better approximate search @xcite @xcite , the beam search curse; iii) the true most likely translation under the model (i.e., the mode of the distribution) is empty in many cases @xcite and a general negative correlation exists between likelihood and quality beyond a certain likelihood value @xcite , we call this the inadequacy of the mode problem. a number of hypotheses have been formulated to explain these observations. they mostly suggest there is something fundamentally wrong with nmt as a model (i.e., its factorisation as a product of locally normalised distributions) or its most popular training algorithm (i.e., regularised maximum likelihood estimation, mle for short). these explanations make an unspoken assumption, namely, that identifying the mode of the distribution, also referred to as maximum a posteriori (map) decoding @xcite , is in some sense the obvious decision rule for predictions. while this assumption makes intuitive sense and works well in unstructured classification problems, it is less justified in nmt, where oftentimes the most likely translations together account for very little probability mass, a claim we shall defend conceptually and provide evidence for in experiments. unless the translation distribution is extremely peaked about the mode for every plausible input, criticising the model in terms of properties of its mode can at best say something about the adequacy of map decoding. unfortunately, as previous research has pointed out, this is seldom the case @xcite . thus, pathologies about the mode cannot be unambiguously ascribed to nmt as a model nor to mle, and inadequacies about the mode cannot rule out the possibility that the model captures important aspects of translation well in expectation. in this work, we criticise nmt models as probability distributions estimated via mle in various settings: varying language pairs, amount of training data, and test domain. we observe that the induced probability distributions represent statistics of the data well in expectation, and that some length and lexical biases are introduced by approximate map decoding. we demonstrate that beam search outputs are rare events, particularly so when test data stray from the training domain. the empty string, shown to often be the true mode @xcite , too is an infrequent event. finally, we show that samples obtained by following the model's own generative story are of reasonable quality, which suggests we should base decisions on statistics gathered from the distribution holistically. one such decision rule is minimum bayes risk (mbr) decoding @xcite . we show that an approximation to mbr performs rather well, especially so when models are more uncertain. to summarise: we argue that i) map decoding is not well-suited as a decision rule for mle-trained nmt; we also show that ii) pathologies and biases observed in nmt are not necessarily inherent to nmt as a model or its training objective, rather, map decoding is at least partially responsible for many of these pathologies and biases; finally, we demonstrate that iii) a straight-forward approximation to a sampling-based decision rule known as minimum bayes risk decoding gives good results, showing promise for research into decision rules that take into account the distribution holistically. ## observed pathologies in nmt many studies have found that nmt suffers from a length bias: nmt underestimates length which hurts the adequacy of translations. @xcite already demonstrate that nmt systematically degrades in performance for longer sequences. @xcite identify the same bias in a chat suggestion task and argue that sequence to sequence models underestimate the margin between correct and incorrect sequences due to local normalisation. later studies have also confirmed the existence of this bias in nmt @xcite @xcite . notably, all these studies employ beam search decoding. in fact, some studies link the length bias to the beam search curse: the observation that large beam sizes hurt performance in nmt @xcite . @xcite already note that larger beam sizes exacerbate the length bias. later studies have confirmed this connection @xcite @xcite . @xcite attribute both problems to local normalisation which they claim introduces label bias @xcite to nmt. @xcite show that likelihood negatively correlates with translation length. these findings suggest that the mode might suffer from length bias, likely thereby failing to sufficiently account for adequacy. in fact, @xcite show that oftentimes the true mode is the empty sequence. the connection with the length bias is not the only reason for the beam search curse. @xcite find that the presence of copies in the training data cause the model to assign too much probability mass to copies of the input, and that with larger beam sizes this copying behaviour becomes more frequent. @xcite show that translations obtained with larger beam sizes often consist of an unlikely prefix with an almost deterministic suffix and are of lower quality. in open-ended generation, @xcite correlate model likelihood with human judgements for a fixed sequence length, thus eliminating any possible length bias issues. they find that likelihood generally correlates positively with human judgements, up until an inflection point, after which the correlation becomes negative. an observation also made in translation with bleu rather than human judgements @xcite . we call this general failure of the mode to represent good translations in nmt the inadequacy of the mode problem. ## nmt and its many biases mt systems are trained on sentence pairs drawn from a parallel corpus. each pair consists of a sequence x in the source language and a sequence y in the target language. most nmt models are conditional models @xcite @xcite , foot_1 that is, only the target sentence is given random treatment. target words are drawn in sequence from a product of locally normalised categorical distributions without markov assumptions: y j |θ, x, @xmath0, @xmath1; θ)). at each step, a neural network f (•; θ) maps from the source sequence x and the prefix sequence @xmath2. these models are typically trained via regularised maximum likelihood estimation, mle for short, where we search for the parameter θ mle that assigns maximum (regularised) likelihood to a dataset of observations d. a local optimum of the mle objective can be found by stochastic gradient-based optimisation @xcite . for a trained model with parameters θ mle and a given input x, a translation is predicted by searching for the mode of the distribution: the sequence y that maximises log p(y|x, θ mle ). this is a decision rule also known as maximum a posteriori (map) decoding @xcite . 2 exact map decoding is intractable in nmt, and the beam search algorithm @xcite is employed as a viable approximation. it has been said that due to certain design decisions nmt suffers from a number of biases. we review those biases here and then discuss in section 4 one bias that has received very little attention and which, we argue, underlies many biases in nmt and explains some of the pathologies discussed in section 2. exposure bias. mle parameters are estimated conditioned on observations sampled from the training data. clearly, those are not available at test time, when we search through the learnt distribution. this mismatch between training and test, known as exposure bias @xcite , has been linked to many of the pathologies of nmt and motivated modifications or alternatives to mle aimed at exposing the model to its own predictions during training @xcite @xcite @xcite . while exposure bias has been a point of critique mostly against mle, it has only been studied in the context of approximate map decoding. the use of map decoding and its approximations shifts the distribution of the generated translations away from data statistics (something we provide evidence for in later sections), thereby exacerbating exposure bias. ## biased statistics and the inadequacy of the mode in most nmt research, criticisms of the model are based on observations about the mode, or an approximation to it obtained using beam search. the mode, however, is not an unbiased summary of the probability distribution that the model learnt. that is, properties of the mode say little about properties of the learnt distribution (e.g., a short mode does not imply the model underestimates average sequence length). map decoding algorithms and their approximations bias the statistics by which we criticise nmt. they restrict our observations about the model to a single or a handful of outcomes which on their own can be rather rare. to gain insight about the model as a distribution, it seems more natural to use all of the information available to us, namely, all samples we can afford to collect, and search for frequent patterns in these samples. evidence found that way better represents the model and its beliefs. on top of that, the sample space of nmt is high-dimensional and highly structured. nmt models must distribute probability mass over a massive sample space (effectively unbounded). while most outcomes ought to be assigned negligible mass, for the total mass sums to 1, the outcomes with non-negligible mass might still be too many. the mode might only account for a tiny portion of the probability mass, and can actually be extremely unlikely under the learnt distribution. using the mode for predictions makes intuitive sense in unstructured problems, where probability distributions are likely very peaked, and in models trained with large margin methods @xcite , since those optimise a decision boundary directly. with probability distributions that are very spread out, and where the mode represents only a tiny bit of probability mass, targeting at the mode for predictions is much less obvious, an argument that we shall reinforce with experimental results throughout this analysis. 3 at the core of our analysis is the concept of an unbiased sample from the model, which we obtain by ancestral sampling: iteratively sampling from distributions of the form cat(f (x, @xmath3; θ)), each time extending the generated prefix @xmath4, until the end-of-sequence symbol is generated. by drawing from the model's probability distribution, unlike what happens in map decoding, we are imitating the model's training procedure. only we replace samples from the data by samples from the model, thus shedding light onto the model's fit. that is, if these samples do not reproduce statistics of the data, we have an instance of poor fit. 4 crucially, ancestral sampling is not a pathfinding algorithm, thus the non-admissible heuristic search bias it not a concern. ancestral sampling is not a decision rule either, thus returning a single sample as a prediction is not expected to outperform map decoding (or any other rule). samples can be used to diagnose model fit, as we do in section 6, and to approximate decision rules, as we do in section 7.4. in sum, we argue that map decoding is a source of various problems and that it biases conclusions about nmt. next, we provide empirical evidence for these claims. ## data & system we train our systems on german-english (de-en), sinhala-english (si-en), and nepali-english (ne-en), in both directions. for german-english we use all available wmt'18 @xcite parallel data, except for paracrawl, amounting to about 5.9 million sentence pairs, and train a transformer base model @xcite . for sinhala and nepali, for which very little parallel data are available, we mimic the data and system setup of @xcite . as we found that the data contained many duplicate sentence pairs, we removed duplicates, but left in those where only one side (source or target) of the data is duplicate to allow for paraphrases. for all language pairs, we do keep a portion of the training data (6, 000 sentence pairs) separate as held-out data for the analysis. in this process we also removed any sentence that corresponded exactly to either the source or target side of a held-out sentence from the training data. to analyse performance outside the training domain, we use wmt's newstest2018 for german-english, and the flores datasets collected by @xcite for the low-resource pairs. our analysis is focused on mle-trained nmt systems. however, as transformers are commonly trained with label smoothing (ls) @xcite , we do additionally report automatic quality assessments of beam search outputs on ls-trained systems. ## assessing the fit of mle-trained nmt we investigate the fit of the nmt models of section 5 on a held-out portion of the training data. this allows us to criticise mle without confounders such as domain shift. we will turn to data in the test domain (newstest2018, flores) in section 7. we compare unbiased samples from the model to goldstandard references and analyse statistics of several aspects of the data. if the mle solution is good, we would expect statistics of sampled data to closely match statistics of observed data. we obtain statistics from reference translations, ancestral samples, and beam search outputs and model them using hierarchical bayesian models. for each type of statistic, we formulate a joint model over these three groups and inspect the posterior distribution over the parameters of the analysis model. we also include statistics extracted from the training data in our analysis, and model the three test groups as a function of posterior inferences based on training data statistics. our methodology follows that advocated by @xcite and blei (2014). in particular, we formulate separate hierarchical models to inspect length, lexical, and word order statistics: sequence length, unigram and bigram counts, and skip-bigram counts, respectively. 5 in appendix a, we describe in detail all analysis models, inference procedures, and predictive checks that confirm their fit. for length statistics, we look at the expected posterior poisson rate for each group, each rate can be interpreted as that group's average sequence length. ideally, the expected poisson rates of predicted translations are close to those of gold-standard references. figure 1 (top row) shows the inferred posterior distributions for all language pairs. we observe that samples generated by nmt capture length statistics reasonably well, overlapping a fair amount with the reference group. in almost all cases we observe that beam search outputs stray away from data statistics, usually resulting in shorter translations. for unigrams, bigrams, and skip-bigrams, we compare the posterior agreement with training data of each group (this is formalised in terms of a scalar concentration parameter whose posterior we can plot). higher values indicate a closer resemblance to training data statistics. for each statistic, the posterior distribution for gold-standard references gives an indication of ideal values of this agreement variable. figure 1 (rows 2-4) show all posterior distributions. in most cases the gold-standard references agree most with the training data, as expected, followed by samples from the model, followed by beam search outputs. for nearly all statistics and language pairs beam search outputs show least agreement with the training data, even when samples from the model show similar agreement as references do. whereas samples from the model do sometimes show less similarity than references, in most cases they are similar and thus lexical and word order statistics are captured reasonably well by the nmt model. beam search on the other hand again strays from training data statistics, compared to samples from the model. ## examining the translation distribution the nmt models of section 5 specify complex distributions over an unbounded space of translations. here we examine properties of these distributions by inspecting translations in a large set of unbiased samples. to gain further insight we also analyse our models in the test domain (newstest2018, flores). ## related work some of our observations have been made in previous work. @xcite observe that unigram statistics of beam search stray from those of the data, while random samples do a better job at reproducing them. @xcite find that beam search outputs have disproportionately high token probabilities compared to natural language under a sequence to sequence model. our analysis is more extensive, we include richer statistics about the data, more language pairs, and vary the amount of training resources, leading to new insights about mle-trained nmt and the merits of mode-seeking predictions. ott et al. (2018) also observe that nmt learns flat distributions, they analyse a high-resource english-french system trained on 35.5 million sentence pairs from wmt'14 and find that after drawing 10, 000 samples from the wmt'14 validation set less than 25% of the probability space has been explored. our analysis shows that even though nmt distributions do not reveal clear winners, they do emphasise translations that share statistics with the reference, which motivates us to look into mbr. mbr decoding is old news in machine translation @xcite , but it has received little attention in nmt. previous approximations to mbr in nmt employ beam search to define the support and to evaluate expected utility (with probabilities renormalised to sum to 1 in the beam), these studies report the need for very large beams @xcite @xcite . they claim the inability to directly score better translations higher is a 8 map decoding is in fact mbr with a very strict utility function which evaluates to 1 if a translation exactly matches the reference, and 0 otherwise. as a community, we acknowledge by means of our evaluation strategies (manual or automatic) that exact matching is inadequate for translation, unlike many unstructured classification problems, admits multiple solutions. 9 even though one can alter bleu such that it is defined at the sentence level (for example, by adding a small positive constant to n-gram counts), this "smoothing" in effect biases bleu's sufficient statistics. unbiased statistics are the key to mbr, thus we opt for a metric that is already defined at the sentence level. the only instance that we are aware of where unbiased samples from an nmt model support a decision rule is the concurrent work by @xcite . the authors make the same observation that we make in section 7.3, namely that an oracle selection from a small set of samples of an nmt model shows great potential, greatly outperforming beam search. motivated by this observation, the authors propose a reranking model that learns to rank sampled translations according to their oracle bleu. using the trained model to re-rank a set of 100 samples from the nmt model they find strong improvements over beam search of up to 3 bleu points, again showing the potential of sampling-based decision rules. ## conclusion in this work, we discuss the inadequacy of the mode in nmt and question the appropriateness of map decoding. we show that for such a high dimensional problem as nmt, the probability distributions obtained with mle are spread out over many translations, and that the mode often does not represent any significant amount of probability mass under the learnt distribution. we therefore argue that map decoding is not suitable as a decision rule for nmt systems. whereas beam search performs well in practice, it suffers from biases of its own (i.e., non-admissible heuristic search bias), it shifts statistics away from those of the data (i.e., exposure bias and other lexical and length biases), and in the limit of perfect search it falls victim to the inadequacy of the mode. instead, we advocate for research into decision rules that take into account the probability distribution more holistically. using ancestral sampling we can explore the learnt distribution in an unbiased way and devise sampling-based decision rules. ancestral sampling does not suffer from non-admissibility, and, if the model fit is good, there is no distribution shift either. we further argue that criticisms about properties of the mode of an nmt system are not representative of the probability distributions obtained from mle training. while this form of criticism is perfectly reasonable where approximations to map decoding are the only viable alternative, there are scenarios where we ought to criticise models as probability distributions. for example, where we seek to correlate an observed pathology with a design decision, such as factorisation, or training algorithm. in fact, we argue that many of the observed pathologies and biases of nmt are at least partially due to the use of (approximate) map decoding, rather than inherent to the model or its training objective. even though nmt models spread mass over many translations, we find samples to be of decent quality and contain translations that outperform beam search outputs even for small sample sizes, further motivating the use of sampling-based decision rules. we show that an approximation to one such decision rule, mbr decoding, shows competitive results. this confirms that while the set of likely translations under the model is large, the translations in it share many statistics that correlate well with the reference. mle-trained nmt models admit probabilistic interpretation and an advantage of the probabilistic framework is that a lot of methodology is already in place when it comes to model criticism as well as making predictions. we therefore advocate for criticising nmt models as probability distributions and making predictions using decision rules that take into account the distributions holistically. we hope that our work paves the way for research into scalable sampling-based decision rules and motivates researchers to assess model improvements to mle-trained nmt systems from a probabilistic perspective. we do collapsed inference for each dirichlet-multinomial (as we are not interested in assessing θ g or φ g ), and infer posteriors approximately using svi with gamma approximate posterior distributions. to confirm the fit of the analysis model, we compare posterior predictive samples to the observed data in terms of absolute frequency errors of unigrams and bigrams as well as ranking correlation.