A non-contiguous Tree Sequence Alignment-based Model for Statistical Machine Translation

Proceedings of the 47th Annual Meeting of the ACL and the 4th IJCNLP of the AFNLP, pages 914–922, Suntec, Singapore, 2-7 August 2009. c⃝2009 ACL and AFNLP A non-contiguous Tree Sequence Alignment-based Model for Statistical Machine Translation Jun Sun1,2 Min Zhang1 Chew Lim Tan2 1 Institute for Infocomm Research 2School of Computing, National University of Singapore sunjun@comp.nus.edu.sg mzhang@i2r.a-star.edu.sg tancl@comp.nus.edu.sg Abstract The tree sequence based translation model al- lows the violation of syntactic boundaries in a rule to capture non-syntactic phrases, where a tree sequence is a contiguous sequence of sub- trees. This paper goes further to present a trans- lation model based on non-contiguous tree se- quence alignment, where a non-contiguous tree sequence is a sequence of sub-trees and gaps. Compared with the contiguous tree sequence- based model, the proposed model can well han- dle non-contiguous phrases with any large gaps by means of non-contiguous tree sequence alignment. An algorithm targeting the non- contiguous constituent decoding is also proposed. Experimental results on the NIST MT-05 Chi- nese-English translation task show that the pro- posed model statistically significantly outper- forms the baseline systems. 1 Introduction Current research in statistical machine translation (SMT) mostly settles itself in the domain of either phrase-based or syntax-based. Between them, the phrase-based approach (Marcu and Wong, 2002; Koehn et al, 2003; Och and Ney, 2004) allows lo- cal reordering and contiguous phrase translation. However, it is hard for phrase-based models to learn global reorderings and to deal with non- contiguous phrases. To address this issue, many syntax-based approaches (Yamada and Knight, 2001; Eisner, 2003; Gildea, 2003; Ding and Palmer, 2005; Quirk et al, 2005; Zhang et al, 2007, 2008a; Bod, 2007; Liu et al, 2006, 2007; Hearne and Way, 2003) tend to integrate more syntactic information to enhance the non-contiguous phrase modeling. In general, most of them achieve this goal by intro- ducing syntactic non-terminals as translational equivalent placeholders in both source and target sides. Nevertheless, the generated rules are strictly required to be derived from the contiguous transla- tional equivalences (Galley et al, 2006; Marcu et al, 2006; Zhang et al, 2007, 2008a, 2008b; Liu et al, 2006, 2007). Among them, Zhang et al. (2008a) acquire the non-contiguous phrasal rules from the contiguous tree sequence pairs1, and find them use- less via real syntax-based translation systems. However, Wellington et al. (2006) statistically re- port that discontinuities are very useful for transla- tional equivalence analysis using binary branching structures under word alignment and parse tree constraints. Bod (2007) also finds that discontinues phrasal rules make significant improvement in lin- guistically motivated STSG-based translation model. The above observations are conflicting to each other. In our opinion, the non-contiguous phrasal rules themselves may not play a trivial role, as reported in Zhang et al. (2008a). We believe that the effectiveness of non-contiguous phrasal rules highly depends on how to extract and utilize them. To verify the above assumption, suppose there is only one tree pair in the training data with its alignment information illustrated as Fig. 1(a) 2. …

Content truncated to 500 words