Bidirectional Decoding for Statistical Machine Translation

Bidirectional Decoding for Statistical Machine Translation Taro WATANABE †‡ and Eiichiro SUMITA † {taro.watanabe, eiichiro.sumita}@atr.co.jp † ATR Spoken Language Translation Research Laboratories ‡ Department of Information Science 2-2-2 Hikaridai Seika-cho, Kyoto University Soraku-gun, Kyoto 619-0288 JAPAN Sakyo-ku, Kyoto 606-8501, JAPAN Abstract This paper describes the right-to-left decoding method, which translates an input string by gen- erating in right-to-left direction. In addition, pre- sented is the bidirectional decoding method, that can take both of the advantages of left-to-right and right-to-left decoding method by generating output in both ways and by merging hypothesized partial outputs of two directions. The experimental results on Japanese and English translation showed that the right-to-left was better for Englith-to-Japanese translation, while the left-to-right was suitable for Japanese-to-English translation. It was also ob- served that the bidirectional method was better for English-to-Japanese translation. 1 Introduction The statistical approach to machine translation re- gards the machine translation problem as the maxi- mum likelihood solution of a translation target text given a translation source text. According to the Bayes Rule, the problem is transformed into the noisy channel model paradigm, where the transla- tion is the maximum a posteriori solution of a dis- tribution for a channel target text given a channel source text and a prior distribution for the channel source text (Brown et al., 1993). Although there exists efficient algorithms to es- timate the parameters for the statistical machine translation (SMT), one of the problems of SMT is the search algorithms for the translation given a se- quence of words. There exists stack decoding al- gorithm (Berger et al., 1996), A* search algorithm (Och et al., 2001; Wang and Waibel, 1997) and dynamic-programming algorithms (Tillmann and Ney, 2000; Garcia-Varea and Casacuberta, 2001), and all translate a given input string word-by-word and render the translation in left-to-right, with prun- ing technologies assuming almost linearly aligned translation source and target texts. The algorithms proposed above cannot deal with drastically differ- ent word correspondence, such as Japanese and En- glish translation, where Japanese is SOV while SVO in English. Germann et al. (2001) suggested greedy method and integer programming decoding, though the first method suffer from the similar problem as described above and the second is impractical for the real-world application. This paper presents two decoding methods, one is the right-to-left decoding based on the left-to- right beam search algorithm, which generates out- puts from the end of a sentence. The second one is the bidirectional decoding method which decodes in both of the left-to-right and right-to-left directions and merges the two hypothesized partial sentences into one. The experimental results of Japanese and English translation indicated that the right-to-left decoding was better for English-to-Japanese trans- lation, while the left-to-right decoding was better for Japanese-to-English decoding. The above re- sults could be justified by the structural difference of Japanese and English, where English takes the prefix structure that places emphasis at the begin- ning of a sentence, hence prefers left-to-right de- coding. On the other hand, Japanese takes postfix structure, setting attention …

Content truncated to 500 words