Efficient Decoding for Statistical Machine Translation with a Fully Expanded WFST Model

Efficient Decoding for Statistical Machine Translation with a Fully Expanded WFST Model Hajime Tsukada NTT Communication Science Labs. 2-4 Hikaridai Seika-cho Soraku-gun Kyoto 619-0237 Japan tsukada@cslab.kecl.ntt.co.jp Masaaki Nagata NTT Cyber Space Labs. 1-1 Hikari-no-Oka Yokosuka-shi Kanagawa 239-0847 Japan nagata.masaaki@lab.ntt.co.jp Abstract This paper proposes a novel method to compile sta- tistical models for machine translation to achieve efficient decoding. In our method, each statistical submodel is represented by a weighted finite-state transducer (WFST), and all of the submodels are ex- panded into a composition model beforehand. Fur- thermore, the ambiguity of the composition model is reduced by the statistics of hypotheses while de- coding. The experimental results show that the pro- posed model representation drastically improves the efficiency of decoding compared to the dynamic composition of the submodels, which corresponds to conventional approaches. 1 Introduction Recently, research on statistical machine translation has grown along with the increase in computational power as well as the amount of bilingual corpora. The basic idea of modeling machine translation was proposed by Brown et al. (1993), who assumed that machine translation can be modeled on noisy chan- nels. The source language is encoded from a target language by a noisy channel, and translation is per- formed as a decoding process from source language to target language. Knight (1999) showed that the translation prob- lem defined by Brown et al. (1993) is NP- complete. Therefore, with this model it is al- most impossible to search for optimal solutions in the decoding process. Several studies have pro- posed methods for searching suboptimal solutions. Berger et al. (1996) and Och et al. (2001) pro- posed such depth-first search methods as stack de- coders. Wand and Waibel (1997) and Tillmann and Ney (2003) proposed breadth-first search methods, i.e. beam search. Germann (2001) and Watanabe and Sumita (2003) proposed greedy type decoding methods. In all of these search algorithms, better representation of the statistical model in systems can improve the search efficiency. For model representation, a search method based on weighted finite-state transducer (WFST) (Mohri et al., 2002) has achieved great success in the speech recognition field. The basic idea is that each statis- tical model is represented by a WFST and they are composed beforehand; the composed model is op- timized by WFST operations such as determiniza- tion and minimization. This fully expanded model permits efficient searches. Our motivation is to ap- ply this approach to machine translation. However, WFST optimization operations such as determiniza- tion are nearly impossible to apply to WFSTs in ma- chine translation because they are much more am- biguous than speech recognition. To reduce the am- biguity, we propose a WFST optimization method that considers the statistics of hypotheses while de- coding. Some approaches have applied WFST to sta- tistical machine translation. Knight and Al- Onaizan (1998) proposed the representation of IBM model 3 with WFSTs; Bangalore and Ric- cardi (2001) studied WFST models in call-routing tasks, and Kumar and Byrne (2003) modeled phrase-based translation by WFSTs. All of these studies mainly focused on …

Content truncated to 500 words