Epsilon Sampling Rocks: Investigating Sampling Strategies for Minimum B ayes Risk Decoding for Machine Translation (2023)

Abstract: Recent advances in machine translation (MT) have shown that Minimum Bayes Risk (MBR) decoding can be a powerful alternative to beam search decoding, especially when combined with neural-based utility functions. However, the performance of MBR decoding depends heavily on how and how many candidates are sampled from the model. In this paper, we explore how different sampling approaches for generating candidate lists for MBR decoding affect performance. We evaluate popular sampling approaches, such as ancestral, nucleus, and top-k sampling. Based on our insights into their limitations, we experiment with the recently proposed epsilon-sampling approach, which prunes away all tokens with a probability smaller than epsilon, ensuring that each token in a sample receives a fair probability mass. Through extensive human evaluations, we demonstrate that MBR decoding based on epsilon-sampling significantly outperforms not only beam search decoding, but also MBR decoding with all other tested sampling methods across four language pairs.

## introduction mbr decoding has recently gained attention in machine translation (mt) as a decision rule with the potential to overcome some of the biases of beam search decoding in nmt @xcite @xcite @xcite . while most prior work on mbr decoding for mt is based on k-best lists obtained via beam search, @xcite proposed to use an approximation of mbr decoding based on unbiased sampling to overcome the shortcomings of map decoding. they demonstrated that samples from the nmt model are faithful to the training data statistics, while beam search is not. @xcite al. (2022a figure 1 : sorted next token prediction probabilities for an example sentence from newstest2021 @xmath0. for simplicity, we plot only the top 30 tokens (out of 32k). the correct token is the second most likely token (with 19.3% probability). all but five tokens have a probability of less than 0.02. however, in aggregate, these low-probability tokens have 21.4% probability. in this work, we continue this exploration while focusing on the sampling approach used for generating the candidate lists for mbr decoding. we compare mbr decoding using bleurt on popular sampling approaches such as ancestral sampling, nucleus sampling, or k-best sampling and analyze their advantages and disadvantages. based on these insights, we explore mbr with the recentlyproposed epsilon-sampling @xcite approach, which instead of considering only tokens that fall within an aggregated probability mass (nucleus sampling) or a fixed amount of tokens (k-best sampling), prunes away all tokens with a probabil-ity smaller than epsilon. by doing so, it ensures that every token in each sample gets a decent amount of probability mass from the model. this is not always the case when sampling with nucleus or top-k sampling and the incorrect samples can hurt mbr decoding performance especially for long sequences. in addition, we also explore the relationship between the underlying sampling approach and the sampling's temperature. our contributions can be summarized as follows: ## experimental results to understand why epsilon sampling is the most suitable sampling approach for machine translation, we first investigate the limitations of the commonly used sampling approaches in section 4.1. we then explore different hyperparameter settings for all sampling approaches in section 4.2. since it is not feasible to run human assessment on all hyperparameter settings, we select a subset of the highest quality settings based on bleurt and conduct an expert-based human evaluation to assess the final quality of this subset in section 4.3. ## related work minimum bayes risk (mbr) decoding stems from statistical decision theory from the principal of maximisation of expected utility @xcite . mbr has been applied to parsing @xcite and speech recognition @xcite . the same idea was later applied to bilingual word alignment @xcite and machine translation @xcite . mbr was used to maximize overlap metrics such as bleu @xcite with statistical mt systems @xcite @xcite . after the advent of neural machine translation, most methods relied on beam search to approximate map decoding @xcite @xcite . mbr decoding has recently gained attention in mt as a decision rule with the potential to overcome some of the biases of map decoding in nmt @xcite @xcite . while most prior work on mbr decoding for mt is based on k-best lists obtained via beam search, @xcite proposed to use an approximation of mbr decoding based on unbiased sampling to overcome the shortcomings of map decoding. they demonstrated that samples from the nmt model are faithful to the training data statistics, while beam search is not. we adopt their sampling-based mbr decoding approximation in all our experiments. @xcite further explored mbr using neural-based utility functions. they demonstrated that neural-based utility function like bleurt and comet outperform lexical overlap metrics. further, @xcite found that alternatives to ancestral sampling could lead to improved performance of mbr-based decoding. @xcite found that, despite promising results with neural metrics in machine translation evaluation, mbr might exploit biases towards faulty translations with high scores that exist in these metrics (reward over-fitting). mbr has since been extensively in used in submissions to various machine and speech translation shared tasks with good results @xcite @xcite , showcasing its potential to improve translation quality. besides the approaches discussed in section 2.1, other sampling approaches that attempt to fix some of the issues with vanilla sampling have been proposed. for example, @xcite introduced the concept of typical sampling, which proposed pruning tokens whose probability deviates alot from model's (conditional) entropy (so potentially both high and low probability tokens), and show this reduces degenerate repetitions and improves generation quality. ## conclusion in this paper, we investigated the impact of different sampling approaches (ancestral, nucleus, topk, and epsilon sampling) during mbr decoding. we analysed the limitations of the traditional sampling approaches and proposed combining the recently proposed epsilon-sampling with mbr. finally, we conducted human evaluations on four language pairs, and showed that mbr decoding based on epsilon-sampling significantly outperforms not only beam search but also mbr decoding with all other tested sampling approaches. we believe that the results of this study are significant for several reasons. first, they demonstrate that epsilonsampling is a promising approach for improving the quality of mbr decoding. second, they provide insights into the relative performance of different sampling approaches, suggesting that epsilon sampling is a promising direction even outside of mbr decoding and for other non open-ended generation tasks. in future work, we plan to conduct further human assessment to investigate the impact of using a smaller candidate size on the performance of mbr decoding.