Fast Consensus Decoding over Translation Forests

Proceedings of the 47th Annual Meeting of the ACL and the 4th IJCNLP of the AFNLP, pages 567–575, Suntec, Singapore, 2-7 August 2009. c⃝2009 ACL and AFNLP Fast Consensus Decoding over Translation Forests John DeNero David Chiang and Kevin Knight Computer Science Division Information Sciences Institute University of California, Berkeley University of Southern California denero@cs.berkeley.edu {chiang, knight}@isi.edu Abstract The minimum Bayes risk (MBR) decoding ob- jective improves BLEU scores for machine trans- lation output relative to the standard Viterbi ob- jective of maximizing model score. However, MBR targeting BLEU is prohibitively slow to op- timize over k-best lists for large k. In this pa- per, we introduce and analyze an alternative to MBR that is equally effective at improving per- formance, yet is asymptotically faster — running 80 times faster than MBR in experiments with 1000-best lists. Furthermore, our fast decoding procedure can select output sentences based on distributions over entire forests of translations, in addition to k-best lists. We evaluate our proce- dure on translation forests from two large-scale, state-of-the-art hierarchical machine translation systems. Our forest-based decoding objective consistently outperforms k-best list MBR, giving improvements of up to 1.0 BLEU. 1 Introduction In statistical machine translation, output transla- tions are evaluated by their similarity to human reference translations, where similarity is most of- ten measured by BLEU (Papineni et al., 2002). A decoding objective specifies how to derive final translations from a system’s underlying statistical model. The Bayes optimal decoding objective is to minimize risk based on the similarity measure used for evaluation. The corresponding minimum Bayes risk (MBR) procedure maximizes the ex- pected similarity score of a system’s translations relative to the model’s distribution over possible translations (Kumar and Byrne, 2004). Unfortu- nately, with a non-linear similarity measure like BLEU, we must resort to approximating the ex- pected loss using a k-best list, which accounts for only a tiny fraction of a model’s full posterior dis- tribution. In this paper, we introduce a variant of the MBR decoding procedure that applies effi- ciently to translation forests. Instead of maximiz- ing expected similarity, we express similarity in terms of features of sentences, and choose transla- tions that are similar to expected feature values. Our exposition begins with algorithms over k- best lists. A na¨ıve algorithm for finding MBR translations computes the similarity between every pair of k sentences, entailing O(k2) comparisons. We show that if the similarity measure is linear in features of a sentence, then computing expected similarity for all k sentences requires only k sim- ilarity evaluations. Specific instances of this gen- eral algorithm have recently been proposed for two linear similarity measures (Tromble et al., 2008; Zhang and Gildea, 2008). However, the sentence similarity measures we want to optimize in MT are not linear functions, and so this fast algorithm for MBR does not ap- ply. For this reason, we propose a new objective that retains the benefits of MBR, but can be op- timized efficiently, even for non-linear similarity measures. In experiments using BLEU over …

Content truncated to 500 words