Computing Lattice BLEU Oracle Scores for Machine Translation

Proceedings of the 13th Conference of the European Chapter of the Association for Computational Linguistics, pages 120–129, Avignon, France, April 23 - 27 2012. c⃝2012 Association for Computational Linguistics Computing Lattice BLEU Oracle Scores for Machine Translation Artem Sokolov Guillaume Wisniewski LIMSI-CNRS & Univ. Paris Sud BP-133, 91 403 Orsay, France {firstname.lastname}@limsi.fr Franc¸ois Yvon Abstract The search space of Phrase-Based Statisti- cal Machine Translation (PBSMT) systems can be represented under the form of a di- rected acyclic graph (lattice). The quality of this search space can thus be evaluated by computing the best achievable hypoth- esis in the lattice, the so-called oracle hy- pothesis. For common SMT metrics, this problem is however NP-hard and can only be solved using heuristics. In this work, we present two new methods for efficiently computing BLEU oracles on lattices: the first one is based on a linear approximation of the corpus BLEU score and is solved us- ing the FST formalism; the second one re- lies on integer linear programming formu- lation and is solved directly and using the Lagrangian relaxation framework. These new decoders are positively evaluated and compared with several alternatives from the literature for three language pairs, using lat- tices produced by two PBSMT systems. 1 Introduction The search space of Phrase-Based Statistical Ma- chine Translation (PBSMT) systems has the form of a very large directed acyclic graph. In several softwares, an approximation of this search space can be outputted, either as a n-best list contain- ing the n top hypotheses found by the decoder, or as a phrase or word graph (lattice) which com- pactly encodes those hypotheses that have sur- vived search space pruning. Lattices usually con- tain much more hypotheses than n-best lists and better approximate the search space. Exploring the PBSMT search space is one of the few means to perform diagnostic analysis and to better understand the behavior of the system (Turchi et al., 2008; Auli et al., 2009). Useful diagnostics are, for instance, provided by look- ing at the best (oracle) hypotheses contained in the search space, i.e, those hypotheses that have the highest quality score with respect to one or several references. Such oracle hypotheses can be used for failure analysis and to better under- stand the bottlenecks of existing translation sys- tems (Wisniewski et al., 2010). Indeed, the in- ability to faithfully reproduce reference transla- tions can have many causes, such as scantiness of the translation table, insufficient expressiveness of reordering models, inadequate scoring func- tion, non-literal references, over-pruned lattices, etc. Oracle decoding has several other applica- tions: for instance, in (Liang et al., 2006; Chi- ang et al., 2008) it is used as a work-around to the problem of non-reachability of the reference in discriminative training of MT systems. Lattice reranking (Li and Khudanpur, 2009), a promising way to improve MT systems, also relies on oracle decoding to build the training data for a reranking algorithm. For sentence level metrics, finding oracle hy- potheses in n-best lists is a simple issue; how- …

Content truncated to 500 words