Constituency to Dependency Translation with Forests

Proceedings of the 48th Annual Meeting of the Association for Computational Linguistics, pages 1433–1442, Uppsala, Sweden, 11-16 July 2010. c⃝2010 Association for Computational Linguistics Constituency to Dependency Translation with Forests Haitao Mi and Qun Liu Key Laboratory of Intelligent Information Processing Institute of Computing Technology Chinese Academy of Sciences P.O. Box 2704, Beijing 100190, China {htmi,liuqun}@ict.ac.cn Abstract Tree-to-string systems (and their forest- based extensions) have gained steady pop- ularity thanks to their simplicity and effi- ciency, but there is a major limitation: they are unable to guarantee the grammatical- ity of the output, which is explicitly mod- eled in string-to-tree systems via target- side syntax. We thus propose to com- bine the advantages of both, and present a novel constituency-to-dependency trans- lation model, which uses constituency forests on the source side to direct the translation, and dependency trees on the target side (as a language model) to en- sure grammaticality. Medium-scale exper- iments show an absolute and statistically significant improvement of +0.7 BLEU points over a state-of-the-art forest-based tree-to-string system even with fewer rules. This is also the first time that a tree- to-tree model can surpass tree-to-string counterparts. 1 Introduction Linguistically syntax-based statistical machine translation models have made promising progress in recent years. By incorporating the syntactic an- notations of parse trees from both or either side(s) of the bitext, they are believed better than phrase- based counterparts in reorderings. Depending on the type of input, these models can be broadly di- vided into two categories (see Table 1): the string- based systems whose input is a string to be simul- taneously parsed and translated by a synchronous grammar, and the tree-based systems whose input is already a parse tree to be directly converted into a target tree or string. When we also take into ac- count the type of output (tree or string), the tree- based systems can be divided into tree-to-string and tree-to-tree efforts. tree on examples (partial) fast gram. BLEU source Liu06, Huang06 + - + target Galley06, Shen08 - + + both Ding05, Liu09 + + - both our work + + + Table 1: A classification and comparison of lin- guistically syntax-based SMT systems, where gram. denotes grammaticality of the output. On one hand, tree-to-string systems (Liu et al., 2006; Huang et al., 2006) have gained significant popularity, especially after incorporating packed forests (Mi et al., 2008; Mi and Huang, 2008; Liu et al., 2009; Zhang et al., 2009). Compared with their string-based counterparts, tree-based systems are much faster in decoding (linear time vs. cu- bic time, see (Huang et al., 2006)), do not re- quire a binary-branching grammar as in string- based models (Zhang et al., 2006; Huang et al., 2009), and can have separate grammars for pars- ing and translation (Huang et al., 2006). However, they have a major limitation that they do not have a principled mechanism to guarantee grammatical- ity on the target side, since there is no linguistic tree structure of the output. On the other hand, string-to-tree systems …

Content truncated to 500 words