Efficient Minimum Bayes Risk Decoding using Low-Rank Matrix Completion Algorithms

• URL: http://arxiv.org/abs/2406.02832v1
• Date: Wed, 5 Jun 2024 00:54:03 GMT
• Title: Efficient Minimum Bayes Risk Decoding using Low-Rank Matrix Completion Algorithms
• Authors: Firas Trabelsi, David Vilar, Mara Finkelstein, Markus Freitag,
• Abstract summary: We formulate Minimum Bayes Risk (MBR) decoding as a matrix completion problem. We exploit this by only computing a random subset of the scores and efficiently recover the missing entries in the matrix. Our experimental results on machine translation tasks demonstrate that the proposed method requires 1/16 utility metric computations.
• Score: 19.543681023903456
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Minimum Bayes Risk (MBR) decoding is a powerful decoding strategy widely used for text generation tasks, but its quadratic computational complexity limits its practical application. This paper presents a novel approach for approximating MBR decoding using matrix completion techniques, focusing on the task of machine translation. We formulate MBR decoding as a matrix completion problem, where the utility metric scores between candidate hypotheses and pseudo-reference translations form a low-rank matrix. First, we empirically show that the scores matrices indeed have a low-rank structure. Then, we exploit this by only computing a random subset of the scores and efficiently recover the missing entries in the matrix by applying the Alternating Least Squares (ALS) algorithm, thereby enabling a fast approximation of the MBR decoding process. Our experimental results on machine translation tasks demonstrate that the proposed method requires 1/16 utility metric computations compared to vanilla MBR decoding while achieving equal translation quality measured by COMET22 on the WMT22 dataset (en<>de and en<>ru). We also benchmark our method against other approximation methods and we show gains in quality when comparing to them.

Related papers

• Centroid-Based Efficient Minimum Bayes Risk Decoding [38.04403087991526]
  Minimum Bayes risk (MBR) decoding achieved state-of-the-art translation performance by using COMET. MBR decoding requires quadratic time since it computes the expected score between a translation hypothesis and all reference translations. Our method clusters the reference translations in the feature space, and then calculates the score using the centroids of each cluster.
  arXiv  Detail & Related papers  (2024-02-17T05:15:12Z)
• Linear-time Minimum Bayes Risk Decoding with Reference Aggregation [52.1701152610258]
  Minimum Bayes Risk (MBR) decoding is a text generation technique that has been shown to improve the quality of machine translations. It requires the pairwise calculation of a utility metric, which has quadratic complexity. We propose to approximate pairwise metric scores with scores calculated against aggregated reference representations.
  arXiv  Detail & Related papers  (2024-02-06T18:59:30Z)
• Hyperparameter-Free Approach for Faster Minimum Bayes Risk Decoding [5.639904484784127]
  Minimum Bayes-Risk (MBR) decoding is a powerful alternative to beam search decoding for a wide range of text generation tasks. MBR requires a huge amount of time for inference to compute the objective. Confidence-based pruning (CBP) has recently been proposed to reduce the inference time in machine translation tasks.
  arXiv  Detail & Related papers  (2024-01-05T11:02:08Z)
• Faster Minimum Bayes Risk Decoding with Confidence-based Pruning [8.709382540743391]
  We describe an algorithm for Minimum Bayes risk (MBR) decoding which gradually grows the number of samples used to estimate the utility. Our method requires fewer samples and drastically reduces the number of calls to the utility function compared to standard MBR. We demonstrate the effectiveness of our approach in experiments on three language pairs, using chrF++ and COMET as utility/evaluation metrics.
  arXiv  Detail & Related papers  (2023-11-25T03:38:14Z)
• Spectral Entry-wise Matrix Estimation for Low-Rank Reinforcement Learning [53.445068584013896]
  We study matrix estimation problems arising in reinforcement learning (RL) with low-rank structure. In low-rank bandits, the matrix to be recovered specifies the expected arm rewards, and for low-rank Markov Decision Processes (MDPs), it may for example characterize the transition kernel of the MDP. We show that simple spectral-based matrix estimation approaches efficiently recover the singular subspaces of the matrix and exhibit nearly-minimal entry-wise error.
  arXiv  Detail & Related papers  (2023-10-10T17:06:41Z)
• Learning the Positions in CountSketch [49.57951567374372]
  We consider sketching algorithms which first compress data by multiplication with a random sketch matrix, and then apply the sketch to quickly solve an optimization problem. In this work, we propose the first learning-based algorithms that also optimize the locations of the non-zero entries.
  arXiv  Detail & Related papers  (2023-06-11T07:28:35Z)
• Machine Learning-Aided Efficient Decoding of Reed-Muller Subcodes [59.55193427277134]
  Reed-Muller (RM) codes achieve the capacity of general binary-input memoryless symmetric channels. RM codes only admit limited sets of rates. Efficient decoders are available for RM codes at finite lengths.
  arXiv  Detail & Related papers  (2023-01-16T04:11:14Z)
• Asymmetric Scalable Cross-modal Hashing [51.309905690367835]
  Cross-modal hashing is a successful method to solve large-scale multimedia retrieval issue. We propose a novel Asymmetric Scalable Cross-Modal Hashing (ASCMH) to address these issues. Our ASCMH outperforms the state-of-the-art cross-modal hashing methods in terms of accuracy and efficiency.
  arXiv  Detail & Related papers  (2022-07-26T04:38:47Z)
• Rapid Person Re-Identification via Sub-space Consistency Regularization [51.76876061721556]
  Person Re-Identification (ReID) matches pedestrians across disjoint cameras. Existing ReID methods adopting real-value feature descriptors have achieved high accuracy, but they are low in efficiency due to the slow Euclidean distance computation. We propose a novel Sub-space Consistency Regularization (SCR) algorithm that can speed up the ReID procedure by 0.25$ times.
  arXiv  Detail & Related papers  (2022-07-13T02:44:05Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.