Incremental Hypothesis Alignment for Building Confusion Networks with Application to Machine Translation System Combination

Proceedings of the Third Workshop on Statistical Machine Translation, pages 183–186, Columbus, Ohio, USA, June 2008. c⃝2008 Association for Computational Linguistics Incremental Hypothesis Alignment for Building Confusion Networks with Application to Machine Translation System Combination Antti-Veikko I. Rosti and Bing Zhang and Spyros Matsoukas and Richard Schwartz BBN Technologies, 10 Moulton Street, Cambridge, MA 02138 � arosti,bzhang,smatsouk,schwartz � @bbn.com Abstract Confusion network decoding has been the most successful approach in combining out- puts from multiple machine translation (MT) systems in the recent DARPA GALE and NIST Open MT evaluations. Due to the vary- ing word order between outputs from differ- ent MT systems, the hypothesis alignment presents the biggest challenge in confusion network decoding. This paper describes an incremental alignment method to build confu- sion networks based on the translation edit rate (TER) algorithm. This new algorithm yields significant BLEU score improvements over other recent alignment methods on the GALE test sets and was used in BBN’s submission to the WMT08 shared translation task. 1 Introduction Confusion network decoding has been applied in combining outputs from multiple machine transla- tion systems. The earliest approach in (Bangalore et al., 2001) used edit distance based multiple string alignment (MSA) (Durbin et al., 1988) to build the confusion networks. The recent approaches used pair-wise alignment algorithms based on symmetric alignments from a HMM alignment model (Matusov et al., 2006) or edit distance alignments allowing shifts (Rosti et al., 2007). The alignment method described in this paper extends the latter by incre- mentally aligning the hypotheses as in MSA but also allowing shifts as in the TER alignment. The confusion networks are built around a “skele- ton” hypothesis. The skeleton hypothesis defines the word order of the decoding output. Usually, the 1-best hypotheses from each system are considered as possible skeletons. Using the pair-wise hypoth- esis alignment, the confusion networks are built in two steps. First, all hypotheses are aligned against the skeleton independently. Second, the confusion networks are created from the union of these align- ments. The incremental hypothesis alignment algo- rithm combines these two steps. All words from the previously aligned hypotheses are available, even if not present in the skeleton hypothesis, when align- ing the following hypotheses. As in (Rosti et al., 2007), confusion networks built around all skeletons are joined into a lattice which is expanded and re- scored with language models. System weights and language model weights are tuned to optimize the quality of the decoding output on a development set. This paper is organized as follows. The incre- mental TER alignment algorithm is described in Section 2. Experimental evaluation comparing the incremental and pair-wise alignment methods are presented in Section 3 along with results on the WMT08 Europarl test sets. Conclusions and future work are presented in Section 4. 2 Incremental TER Alignment The incremental hypothesis alignment is based on an extension of the TER algorithm (Snover et al., 2006). The extension allows using a confusion net- work as the reference. First, the algorithm finds the minimum edit …

Content truncated to 500 words