Complexity of Finding the BLEU-optimal Hypothesis in a Confusion Network

Proceedings of the 2008 Conference on Empirical Methods in Natural Language Processing, pages 839–847, Honolulu, October 2008. c⃝2008 Association for Computational Linguistics Complexity of finding the BLEU-optimal hypothesis in a confusion network Gregor Leusch and Evgeny Matusov and Hermann Ney RWTH Aachen University, Germany {leusch,matusov,ney}@cs.rwth-aachen.de Abstract Confusion networks are a simple representa- tion of multiple speech recognition or transla- tion hypotheses in a machine translation sys- tem. A typical operation on a confusion net- work is to find the path which minimizes or maximizes a certain evaluation metric. In this article, we show that this problem is gener- ally NP-hard for the popular BLEU metric, as well as for smaller variants of BLEU. This also holds for more complex representations like generic word graphs. In addition, we give an efficient polynomial-time algorithm to cal- culate unigram BLEU on confusion networks, but show that even small generalizations of this data structure render the problem to be NP-hard again. Since finding the optimal solution is thus not always feasible, we introduce an approximat- ing algorithm based on a multi-stack decoder, which finds a (not necessarily optimal) solu- tion for n-gram BLEU in polynomial time. 1 Introduction In machine translation (MT), confusion networks (CNs) are commonly used to represent alternative versions of sentences. Typical applications include translation of different speech recognition hypothe- ses (Bertoldi et al., 2007) or system combination (Fiscus, 1997; Matusov et al., 2006). A typical operation on a given CN is to find the path which minimizes or maximizes a certain eval- uation metric. This operation can be used in ap- plications like Minimum Error Rate Training (Och, 2003), or optimizing system combination as de- scribed by Hillard et al. (2007). Whereas this is easily achievable for simple metrics like the Word Error Rate (WER) as described by Mohri and Riley (2002), current research in MT uses more sophisti- cated measures, like the BLEU score (Papineni et al., 2001). Zens and Ney (2005) first described this task on general word graphs, and sketched a com- plete algorithm for calculating the maximum BLEU score in a word graph. While they do not give an estimate on the complexity of their algorithm, they note that already a simpler algorithm for calculating the Position independent Error Rate (PER) has an exponential worst-case complexity. The same can be expected for their BLEU algorithm. Dreyer et al (2007) examined a special class of word graphs, namely those that denote constrained reorderings of single sentences. These word graphs have some properties which simplify the calculation; for exam- ple, no edge is labeled with the empty word, and all paths have the same length and end in the same node. Even then, their decoder does not optimize the true BLEU score, but an approximate version which uses a language-model-like unmodified pre- cision. We give a very short introduction to CNs and the BLEU score in Section 2. In Section 3 we show that finding the best BLEU score is an NP-hard problem, even for a simplified variant …

Content truncated to 500 words