Computing Optimal Alignments for the IBM-3 Translation Model

Proceedings of the Fourteenth Conference on Computational Natural Language Learning, pages 98–106, Uppsala, Sweden, 15-16 July 2010. c⃝2010 Association for Computational Linguistics Computing Optimal Alignments for the IBM-3 Translation Model Thomas Schoenemann Centre for Mathematical Sciences Lund University, Sweden Abstract Prior work on training the IBM-3 transla- tion model is based on suboptimal meth- ods for computing Viterbi alignments. In this paper, we present the first method guaranteed to produce globally optimal alignments. This not only results in im- proved alignments, it also gives us the op- portunity to evaluate the quality of stan- dard hillclimbing methods. Indeed, hill- climbing works reasonably well in prac- tice but still fails to find the global opti- mum for between 2% and 12% of all sen- tence pairs and the probabilities can be several tens of orders of magnitude away from the Viterbi alignment. By reformulating the alignment problem as an Integer Linear Program, we can use standard machinery from global opti- mization theory to compute the solutions. We use the well-known branch-and-cut method, but also show how it can be cus- tomized to the specific problem discussed in this paper. In fact, a large number of alignments can be excluded from the start without losing global optimality. 1 Introduction Brown et al. (1993) proposed to approach the problem of automatic natural language translation from a statistical viewpoint and introduced five probability models, known as IBM 1-5. Their models were single word based, where each source word could produce at most one target word. State-of-the-art statistical translation systems follow the phrase based approach, e.g. (Och and Ney, 2000; Marcu and Wong, 2002; Koehn, 2004; Chiang, 2007; Hoang et al., 2007), and hence al- low more general alignments. Yet, single word based models (Brown et al., 1993; Brown et al., 1995; Vogel et al., 1996) are still highly relevant: many phrase based systems extract phrases from the alignments found by training the single word based models, and those that train phrases directly usually underperform these systems (DeNero et al., 2006). Single word based models can be divided into two classes. On the one hand, models like IBM-1, IBM-2 and the HMM are computationally easy to handle: both marginals and Viterbi alignments can be computed by dynamic programming or even simpler techniques. On the other hand there are fertility based mod- els, including IBM 3-5 and Model 6. These mod- els have been shown to be of higher practical rel- evance than the members of the first class (Och and Ney, 2003) since they usually produce better alignments. At the same time, computing Viterbi alignments for these methods has been shown to be NP-hard (Udupa and Maji, 2006), and comput- ing marginals is no easier. The standard way to handle these models – as implemented in GIZA++ (Al-Onaizan et al., 1999; Och and Ney, 2003) – is to use a hillclimbing al- gorithm. Recently Udupa and Maji (2005) pro- posed an interesting approximation based on solv- ing sequences of exponentially large subproblems by means of …

Content truncated to 500 words