A New String-to-Dependency Machine Translation Algorithm with a Target Dependency Language Model

Proceedings of ACL-08: HLT, pages 577–585, Columbus, Ohio, USA, June 2008. c⃝2008 Association for Computational Linguistics A New String-to-Dependency Machine Translation Algorithm with a Target Dependency Language Model Libin Shen BBN Technologies Cambridge, MA 02138, USA lshen@bbn.com Jinxi Xu BBN Technologies Cambridge, MA 02138, USA jxu@bbn.com Ralph Weischedel BBN Technologies Cambridge, MA 02138, USA weisched@bbn.com Abstract In this paper, we propose a novel string-to- dependency algorithm for statistical machine translation. With this new framework, we em- ploy a target dependency language model dur- ing decoding to exploit long distance word relations, which are unavailable with a tra- ditional n-gram language model. Our ex- periments show that the string-to-dependency decoder achieves 1.48 point improvement in BLEU and 2.53 point improvement in TER compared to a standard hierarchical string-to- string system on the NIST 04 Chinese-English evaluation set. 1 Introduction In recent years, hierarchical methods have been suc- cessfully applied to Statistical Machine Translation (Graehl and Knight, 2004; Chiang, 2005; Ding and Palmer, 2005; Quirk et al., 2005). In some language pairs, i.e. Chinese-to-English translation, state-of- the-art hierarchical systems show significant advan- tage over phrasal systems in MT accuracy. For ex- ample, Chiang (2007) showed that the Hiero system achieved about 1 to 3 point improvement in BLEU on the NIST 03/04/05 Chinese-English evaluation sets compared to a start-of-the-art phrasal system. Our work extends the hierarchical MT approach. We propose a string-to-dependency model for MT, which employs rules that represent the source side as strings and the target side as dependency struc- tures. We restrict the target side to the so called well- formed dependency structures, in order to cover a large set of non-constituent transfer rules (Marcu et al., 2006), and enable efficient decoding through dy- namic programming. We incorporate a dependency language model during decoding, in order to exploit long-distance word relations which are unavailable with a traditional n-gram language model on target strings. For comparison purposes, we replicated the Hiero decoder (Chiang, 2005) as our baseline. Our string- to-dependency decoder shows 1.48 point improve- ment in BLEU and 2.53 point improvement in TER on the NIST 04 Chinese-English MT evaluation set. In the rest of this section, we will briefly dis- cuss previous work on hierarchical MT and de- pendency representations, which motivated our re- search. In section 2, we introduce the model of string-to-dependency decoding. Section 3 illustrates of the use of dependency language models. In sec- tion 4, we describe the implementation details of our MT system. We discuss experimental results in sec- tion 5, compare to related work in section 6, and draw conclusions in section 7. 1.1 Hierarchical Machine Translation Graehl and Knight (2004) proposed the use of target- tree-to-source-string transducers (xRS) to model translation. In xRS rules, the right-hand-side(rhs) of the target side is a tree with non-terminals(NTs), while the rhs of the source side is a string with NTs. Galley et al. (2006) extended this string-to-tree model by using Context-Free parse trees to represent the target side. A tree could represent multi-level transfer …

Content truncated to 500 words