Sampling-Based Approximations to Minimum B ayes Risk Decoding for Neural Machine Translation (2022)

Abstract: In NMT we search for the mode of the model distribution to form predictions. The mode and other high-probability translations found by beam search have been shown to often be inadequate in a number of ways. This prevents improving translation quality through better search, as these idiosyncratic translations end up selected by the decoding algorithm, a problem known as the beam search curse. Recently, an approximation to minimum Bayes risk (MBR) decoding has been proposed as an alternative decision rule that would likely not suffer from the same problems. We analyse this approximation and establish that it has no equivalent to the beam search curse. We then design approximations that decouple the cost of exploration from the cost of robust estimation of expected utility. This allows for much larger hypothesis spaces, which we show to be beneficial. We also show that mode-seeking strategies can aid in constructing compact sets of promising hypotheses and that MBR is effective in identifying good translations in them. We conduct experiments on three language pairs varying in amounts of resources available: English into and from German, Romanian, and Nepali.

## introduction nmt systems @xcite are trained to predict a conditional probability distribution over translation candidates of any given source sentence. after training, choosing a translation for a given input requires a decision rule: a criterion to elect a 'preferred' translation. map decoding, the most common decision rule in nmt, seeks the most probable translation under the model (i.e., the mode of the distribution). 1 code is available at github.com/roxot/mbr-nmt. map decoding and its approximations such as beam search @xcite have been under scrutiny. @xcite show that the true mode is oftentimes inadequately short or empty. better approximate search is known to hurt quality @xcite @xcite , a problem known as the beam search curse. the success of beam search depends on search biases introduced by hyperparameters such as beam size and length normalisation, which are tuned not to correlate with the objective of map decoding, but rather to strike a compromise between modeseeking search and properties of reasonable translations. despite its success, a number of problems have been observed: length bias @xcite , word frequency bias @xcite , susceptibility to copy noise @xcite , and hallucination under domain shift @xcite @xcite . eikema and @xcite argue that the inadequacy of the mode in nmt is a reasonable consequence of the translation space being combinatorial and unbounded. they show that, while distri-butions predicted by nmt do reproduce various statistics of observed data, they tend to spread probability mass almost uniformly over a large space of translation candidates. this makes their precise ranking in terms of probability mass a fragile criterion for prediction. while some of these candidates are possibly inadequate (e.g., the empty sequence), most of them are similar to one another and exhibit appreciable structural similarity to reference translations. to make better use of the statistics predicted by nmt models, eikema and aziz (2020) recommend mbr decoding @xcite , a decision rule that seeks the translation candidate which maximises an external notion of utility (e.g., an mt evaluation metric) in expectation under the model distribution. while mbr decoding promises robustness to idiosyncratic translations, it remains intractable, much like map decoding. eikema and @xcite propose an approximation based on monte carlo (mc) sampling, which although tractable in principle, requires a prohibitive number of assessments of the utility function. in this work, we first analyse the procedure by eikema and @xcite and establish that it does not suffer from a counterpart to the beam search curse. that is, better search does not hurt translation quality. their approximation is, however, computationally expensive, requiring a number of assessments of the utility function that is quadratic in sample size. we propose algorithms that scale linearly, allowing us to explore large hypothesis spaces, and considerably improve upon existing approximations to mbr with less computation. finally, we find that mode-seeking strategies such nucleus sampling and beam search can still aid mbr decoding by constructing compact sets of high expected utility hypotheses, relying on mbr to filter idiosyncratic translations that may be present. ## nmt and decision rules nmt employs neural networks (nns) to predict a conditional probability distribution y |θ, x over translation candidates of any given source sentence x. the sample space y is the set of all sequences of known target-language symbols (e.g., sub-word units). nmt factorises the distribution as a chain of random draws from categorical distributions after training, and for a given input, choosing a translation requires a decision rule to map from a distribution over translation candidates to a single 'preferred' translation. the most common decision rule in nmt is map decoding, which outputs the mode of the conditional distribution. despite the widespread intuition that map decoding is an obvious choice, maximum likelihood estimation (mle) is oblivious to our desire to form predictions. ## coarse-to-fine mbr decoding a big disadvantage of mbr n-by-n is that it requires n 2 assessments of the utility function. if u is an upperbound on the time necessary to assess the utility function once, then mbr n-by-n runs in time o(n 2 ×u ). for a complex utility function, this can grow expensive even for a modest hypothesis space. as nmt distributions have been shown to be high entropy @xcite , the quadratic cost prevents us from sufficiently exploring the space of translations. therefore, we investigate and propose more flexible algorithms. an important property of sampling-based mbr decoding is that mc estimation of expected utility, equation (4), and approximation of the hypothesis space in equation (5) really are two independent approximations. tying the two is no more than a design choice that must be reconsidered. we start by obtaining n translation candidates from the model, which will form the hypothesis space h(x). then, we use any number @xmath2. 3 we call this version mbr n-by-s , which takes time o(n × s × u ). compared to mbr n-by-n , this variant is able to scale to much larger hypothesis spaces h(x). in practice, however, robust mc estimation for the utility of interest may still require s that is too large for the n we are interested in. an idea that we explore in this work is to make use of a proxy utility that correlates with the target src convercent erhielt @xmath047 millionen angehoben wurde. ref convercent raised @xmath147 million. figure 2 : motivation for coarse-to-fine mbr. we sort 300 candidates sampled from the model along the x-axis from best to worst according to a robust mc estimate (using 1,000 samples) of expected beer under the model. left: feasible mc estimates (5 samples) of each candidate's expected beer. right: robust and inexpensive mc estimates (100 samples) of expected utility w.r.t. a simpler metric (skip-bigram f1). as estimates are stochastic, we perform 100 repetitions and plot @xmath3. we can see that the robust estimates (right) correlate fairly well with the expensive ranking we intend to approximate (x-axis), despite of the simpler utility. as we can afford more evaluations of the proxy utility, we obtain estimates of reduced variance, which leads to safer pruning. ht (x) := top-t @xmath4; x, s) . upper-bounding the complexity of the proxy utility by u proxy , the target utility by u target , using s samples for mc estimation in the coarse step (6b) and l in the fine step (6a), the complexity of this algorithm is o(n × s × u proxy + t × l × u target ). mbr c2f decouples robust mc estimation (large l) from exploration (large n ) and the cost of exploration from the cost of the target utility. as illustrated in figure 2 , we can find proxy utilities that correlate reasonably well with our target utility and are able to give us a rough-but usefulordering of the hypothesis space. rather than using a proxy utility, we could use the target utility itself in the coarse-step provided we pick a small s. this, however, most likely leads to too high variability in the ranking, as shown in figure 2 (left). ## data, systems and utilities we perform experiments on three language pairs with varying amount of resources for training: en-glish into and from german, romanian and nepali. for german-english (de-en) we use all available wmt'18 @xcite news data except for paracrawl, resulting in 5.9 million sentence pairs. we train a transformer base model @xcite until convergence and average the last 10 epoch checkpoints to obtain our final model. we test our models on newstest2018. for romanian-english (ro-en) we use all available wmt'16 @xcite news data amounting to 565k sentence pairs. we train a transformer base model until convergence and pick the best epoch checkpoint according to the validation loss. we test our models on newstest2016. finally, for nepali-english (ne-en) we use the data setup by @xcite . we apply the pre-processing step of removing duplicates as in eikema and @xcite . this results in 235k sentence pairs. we test our models on the flores test set, which is of a widely different domain than the training data. we mimick the training setup and models used in @xcite . in all models we disable label smoothing, as this has been found to negatively impact model fit, which would compromise the performance of mbr (eikema and aziz, 2020). for computational efficiency, we opt for nonneural evaluation metrics for use as utility function in mbr. beer @xcite is a non-neural trained metric that has shown good correlation with human judgements in previous wmt metrics shared tasks @xcite @xcite . in experiments shown in ## related work in recent nmt literature mbr has started being explored either in combination with map decoding or replacing it altogether. @xcite adapt lattice minimum bayes risk decoding @xcite on smt translation lattices to be incorporated in left-to-right beam search decoding in nmt, thereby proposing a hybrid decoding scheme. they adapt lattice mbr to work on par-tial hypotheses and perform beam search to find translations that are both high probability under the nmt model and have high expected utility under the smt model. @xcite also combine beam search with mbr decoding to find low risk hypotheses, after which they re-rank all hypotheses with mbr again. they report having to restrict the number of hypotheses as not to degrade the effectiveness of mbr re-ranking, a finding that is likely due to biased estimation of expected utility, as in our work we find that increasing the number of hypotheses always improves translation quality. @xcite explore the quality of k-best lists obtained from beam search in nmt models and find that while map is not a good criterion for ranking the resulting hypotheses, re-ranking using mbr with beer as a utility leads to improvements on top of standard beam search decoding (with a small beam size), in terms of both bleu scores as well as human evaluation scores. @xcite approach decoding from a voting theory perspective and derive a decoding strategy similar to mbr. they explore a range of utility functions, achieving similar bleu scores to beam search, but showing improvements in terms of length, diversity and human judgement. all of the above works make use of beam search to provide both the hypothesis space as well as to make a biased estimate of expected utility. eikema and aziz (2020) are the first work in nmt that propose to use sampling from the model to both make unbiased estimates of expected utility, the importance of which we confirm in experiments, and to form the hypothesis space. the authors only explore mbr n-by-n , however, and never explore hypothesis spaces larger than @xmath5. we show that it is beneficial to scale mbr to much larger hypothesis spaces and that it can be beneficial to construct them using mode-seeking strategies. @xcite study the properties of the sampling-based algorithm proposed in eikema and @xcite and explore hypothesis spaces up to a size of @xmath6. they find that mbr decoding outputs exhibit a similar but smaller bias towards short translations and frequent tokens compared to beam search, but do observe that this is dependent on the choice of utility function. they further find that mbr decoding mitigates spurious copying and hallucinations under domain shift. similar to our work, they find that mbr decoding scales well with larger hypothesis spaces and better estimation of expected utility. @xcite explore the use of large hypothesis spaces and a range of utilities, including neural utilities, on the mbr n-by-n approximation. they find that using bleurt as utility leads to significantly better translations in a human evaluation, while producing considerably lower probability translations. we provide a more extensive overview of historical approximations to the mbr objective as well as an overview of alternatives for tackling the inadequacy of the mode in appendix a. ## conclusion we have shown mbr to be a robust decision rule for nmt that can find high quality translations. in particular, we have found that mbr, under reasonable hyperparameter choices, generally leads to improved translation quality with more computation (i.e., searching a larger search space and/or using more samples for more accurate mc estimation). big challenges in decoding with mbr are constructing the hypothesis space and keeping computational cost of estimating expected utility tractable. we have proposed effective strategies for both, by exploring more efficient ways of forming the hypothesis space and proposing an approximation to mbr that is linear in the size of this hypothesis space. our coarse-to-fine mbr procedure is able to considerably reduce the number of calls to the utility function without compromising translation quality. we have shown that sampling-based mbr in general can outperform beam search on all the language pairs we explored and can continue to improve with better and more accurate search. we believe sampling-based mbr to be a promising, albeit still more expensive, alternative to beam search decoding. unlike beam search, where it is not obvious how to further improve translation quality, sampling-based mbr is likely to benefit from improvements of different aspects of the algorithm. we believe fruitful avenues of research to be among i) clever algorithms for constructing hypothesis spaces, ii) more robust estimates of expected utility using fewer samples, iii) use of modern neural utilities and iv) improving the modelling capacity of nmt systems. we hope that this work motivates researchers and practitioners to make more conscious considerations of the choice of decision rule and that it paves the way for use of tractable sampling-based mbr decoding in nmt.