A Decoder for Syntax-based Statistical MT

A Decoder for Syntax-based Statistical MT Kenji Yamada and Kevin Knight Information Sciences Institute University of Southern California 4676 Admiralty Way, Suite 1001 Marina del Rey, CA 90292 � kyamada,knight � @isi.edu Abstract This paper describes a decoding algorithm for a syntax-based translation model (Ya- mada and Knight, 2001). The model has been extended to incorporate phrasal translations as presented here. In con- trast to a conventional word-to-word sta- tistical model, a decoder for the syntax- based model builds up an English parse tree given a sentence in a foreign lan- guage. As the model size becomes huge in a practical setting, and the decoder consid- ers multiple syntactic structures for each word alignment, several pruning tech- niques are necessary. We tested our de- coder in a Chinese-to-English translation system, and obtained better results than IBM Model 4. We also discuss issues con- cerning the relation between this decoder and a language model. 1 Introduction A statistical machine translation system based on the noisy channel model consists of three components: a language model (LM), a translation model (TM), and a decoder. For a system which translates from a foreign language � to English � , the LM gives a prior probability P ��� and the TM gives a chan- nel translation probability P ��� � � . These models are automatically trained using monolingual (for the LM) and bilingual (for the TM) corpora. A decoder then finds the best English sentence given a foreign sentence that maximizes P �� � � � , which also maxi- mizes P ��� �� �� � according to Bayes’ rule. A different decoder is needed for different choices of LM and TM. Since P ��� and P �� � � � are not sim- ple probability tables but are parameterized models, a decoder must conduct a search over the space de- fined by the models. For the IBM models defined by a pioneering paper (Brown et al., 1993), a de- coding algorithm based on a left-to-right search was described in (Berger et al., 1996). Recently (Ya- mada and Knight, 2001) introduced a syntax-based TM which utilized syntactic structure in the chan- nel input, and showed that it could outperform the IBM model in alignment quality. In contrast to the IBM models, which are word-to-word models, the syntax-based model works on a syntactic parse tree, so the decoder builds up an English parse tree  given a sentence  in a foreign language. This pa- per describes an algorithm for such a decoder, and reports experimental results. Other statistical machine translation systems such as (Wu, 1997) and (Alshawi et al., 2000) also pro- duce a tree  given a sentence  . Their models are based on mechanisms that generate two languages at the same time, so an English tree  is obtained as a subproduct of parsing  . However, their use of the LM is not mathematically motivated, since their models do not decompose into P ��� � � and ��� unlike the …

Content truncated to 500 words