Centroid-Based Efficient Minimum B ayes Risk Decoding (2024)

Abstract: Minimum Bayes risk (MBR) decoding achieved state-of-the-art translation performance by using COMET, a neural metric that has a high correlation with human evaluation.However, MBR decoding requires quadratic time since it computes the expected score between a translation hypothesis and all reference translations.We propose centroid-based MBR (CBMBR) decoding to improve the speed of MBR decoding.Our method clusters the reference translations in the feature space, and then calculates the score using the centroids of each cluster.The experimental results show that our CBMBR not only improved the decoding speed of the expected score calculation 5.7 times, but also outperformed vanilla MBR decoding in translation quality by up to 0.5 COMET in the WMT’22 En \leftrightarrow Ja, En \leftrightarrow De, En \leftrightarrow Zh, and WMT’23 En \leftrightarrow Ja translation tasks.

## introduction minimum bayes risk (mbr) decoding achieves robust and high-quality translation by selecting the output sentence that maximizes the expected metric score computed from the set of translation hypotheses @xcite @xcite . recently, neural evaluation metrics that have a high correlation with human evaluation have been proposed @xcite @xcite , and mbr decoding using such neural metrics has achieved state-of-the-art translation performance in human evaluation compared with conventional maximum-a-posteriori (map) decoding using beam search @xcite . however, because of its formulation, typical mbr decoding that regards the hypothesis set as a pseudo-reference set requires the computational time of o(n 2 ) when n translation hypotheses are 1 https://github.com/naist-nlp/mbrs given. in recent work, the number of hypotheses n exceeded 1,000 candidates @xcite , which makes the quadratic order of computational time a challenge for mbr decoding, particularly when expensive neural metrics are used. several pruning methods have been proposed @xcite to improve the decoding speed. these approaches require the careful selection of a proxy metric @xcite , or it is difficult to take advantage of computational parallelism because hypotheses are pruned iteratively @xcite . given that expensive neural metrics, e.g., comet or bleurt, are trained to output high scores when a hypothesis sentence and reference translation are semantically similar, we hypothesize that the distance between sentence vectors of similar sentences in the feature space of their models is close. we leverage sentence similarity to improve the decoding speed of comet-mbr by clustering sentence vectors of the translation candidates into k ≪ n clusters as shown in figure 1 . then, we calculate the comet scores using k centroid vectors of their clusters, instead of using n sentence vectors. in experiments, our proposed method not only achieved a speed-up of 5.7 times in the calculation of the expected score but also an improvement in the comet score of up to 0.5% compared with naive mbr decoding in the wmt'22 en↔ja, en↔de, en↔zh, and wmt'23 en↔ja transla-tion tasks. let x and y be the spaces of possible source sentences and target sentences, respectively. map decoding generates the target sentence y * @xmath0, where θ denotes the parameter of the translation model that calculates the likelihood of an output sentence y given an input sentence @xmath1. because it is infeasible to calculate probabilities for all possible @xmath2, beam search is typically used to obtain the solution. by contrast, mbr decoding determines the output sentence y * @xmath3: comet-mbr comet is an evaluation metric of translation quality that achieves a high correlation with human evaluation. the comet model consists of the xlm-roberta (xlm-r)-based sentence encoder @xcite and the output layer, and is trained to predict direct assessment scores @xcite . it first encodes the source sentence @xmath4, hypothesis sentence @xmath5, and reference sentence ŷ ∈ y into their d-dimensional sentence vectors independently. then the comet score is computed from the triplet of sentence vectors in the output layer. let f : x ∪ @xmath6: r d × r d × r @xmath7. the comet score is computed using s(f (x), f (h), f (ŷ)). mbr decoding with comet (comet-mbr) replaces the utility u in equation 2 with the comet score: ## proposed method our proposed centroid-based mbr (cbmbr) approximates the expected utility using the centroids of similar sentence vectors. cbmbr decodes by computing the expected utility according to the following procedures: sentence encoding, clustering, and calculating the expected utility. encoding first, we compute the sentence vector of the source f (x) ∈ r d , the hypotheses clustering next, we cluster the sentence vectors of the pseudo-references into k ≪ n clusters and obtain the centroid vectors of each cluster @xmath8. here, we employ kmeans++ @xcite to prevent the centroids from being biased. kmeans++ selects the initial centroids so that the distances between each pair of centroids are farther according to the weights calculated from the distances between vectors. we describe the details of the algorithm in appendix c.1. then, we cluster the vectors {f (ŷ i )} | ŷ| @xmath9. specifically, we calculate the following steps iteratively: 1) assign a vector to its nearest neighbor centroid and 2) update the centroid using the vectors assigned to its cluster. expected utility finally, we calculate the expected utility by replacing pseudo-reference vectors f (ŷ) ∈ r d with centroids @xmath10: and the time complexity of cbmbr is o(n ), which is equivalent to @xcite and @xcite . our proposed method approximates the expected utility using centroid representations, which implicitly assumes that the score function s is approximately linear. specifically, when @xmath11, we approximate the expected utility ## experiments setup we conducted translation experiments with two settings; one used diversified translation candidates and the other simulated a more realistic scenario, multi-system translation. we evaluated the translation quality using the comet score, which is the same as the utility function of mbr decoding used in our experiments. for comparison, we also performed translation candidate reranking using a quality estimation model cometkiwi @xcite ) (qe) 2 , mbr decoding with confidence-based pruning (prunembr) @xcite , and evaluated the quality upper bound (oracle), which selects the hypothesis with the best score according to comet using reference translations. we also compared cbmbr without kmeans++, where we randomly selected the initial centroids from the sample set (w/o kmeans++). we used comet-22 @xcite for the evaluation metric and utility function. in mbr decoding, we treat the hypothesis set as the pseudo-reference set, i.e., ŷ := h. we set the number of centroids to @xmath12. the details of our setup are shown in appendix d. ## conclusion in this paper, we proposed cbmbr, which improved the speed of mbr decoding by clustering the sentence vectors of similar sentences and computing the score using the centroid representations of each cluster. our cbmbr achieved a 5.7 times speed-up in the expected score calculation and an improvement in comet of up to 0.5% compared with vanilla mbr decoding in the wmt'22 en↔ja, en↔de, en↔zh, and wmt'23 en↔ja translation tasks. for future work, we will apply our method to other evaluation metrics, including both neural and non-neural metrics.