A Weighted Finite State Transducer Implementation of the Alignment Template Model for Statistical Machine Translation

A Weighted Finite State Transducer Implementation of the Alignment Template Model for Statistical Machine Translation Shankar Kumar and William Byrne Center for Language and Speech Processing, Johns Hopkins University, 3400 North Charles Street, Baltimore, MD, 21218, USA � skumar,byrne � @jhu.edu Abstract We present a derivation of the alignment tem- plate model for statistical machine translation and an implementation of the model using weighted finite state transducers. The approach we describe allows us to implement each con- stituent distribution of the model as a weighted finite state transducer or acceptor. We show that bitext word alignment and translation un- der the model can be performed with standard FSM operations involving these transducers. One of the benefits of using this framework is that it obviates the need to develop special- ized search procedures, even for the generation of lattices or N-Best lists of bitext word align- ments and translation hypotheses. We evaluate the implementation of the model on the French- to-English Hansards task and report alignment and translation performance. 1 Introduction The Alignment Template Translation Model (ATTM) (Och et al., 1999) has emerged as a promising modeling framework for statistical machine translation. The ATTM attempts to overcome the deficiencies of word-to-word translation models (Brown et al., 1993) through the use of phrasal translations. The overall model is based on a two-level alignment between the source and the target sentence: a phrase-level alignment between source and target phrases and a word-level alignment between words in these phrase pairs. The goal of this paper is to reformulate the ATTM so that the operations we intend to perform under a sta- tistical translation model, namely bitext word alignment and translation, can be implementation using standard weighted finite state transducer (WFST) operations. Our main motivation for a WFST modeling framework lies in the resulting simplicity of alignment and translation processes compared to dynamic programming or �� de- coders. The WFST implementation allows us to use stan- dard optimized algorithms available from an off-the-shelf FSM toolkit (Mohri et al., 1997). This avoids the need to develop specialized search procedures, even for the gen- TEMPLATE SEQUENCE MODEL PERMUTATION MODEL PHRASE PHRASAL TRANSLATION MODEL TARGET LANGUAGE MODEL v2 v3 1 v SOURCE SEGMENTATION MODEL u z TARGET LANGUAGE SENTENCE SENTENCE SOURCE LANGUAGE source language phrases alignment templates target language phrases f f f f f f 2 3 4 5 6 f7 v2 v1 v3 z z 1 2 3 u u 1 2 e1 e2 1 e4 e5 e6 e e e 3e 3 7 8 9 a a a 2 3 1 Figure 1: ATTM Architecture. eration of lattices or N-best lists of bitext word alignment or translation hypotheses. Weighted Finite State Transducers for Statistical Ma- chine Translation (SMT) have been proposed in the literature to implement word-to-word translation mod- els (Knight and Al-Onaizan, 1998) or to perform trans- lation in an application domain such as the call routing task (Bangalore and Ricardi, 2001). One of the objec- tives of these approaches has been to provide …

Content truncated to 500 words