Adjoining Tree-to-String Translation

Proceedings of the 49th Annual Meeting of the Association for Computational Linguistics, pages 1278–1287, Portland, Oregon, June 19-24, 2011. c⃝2011 Association for Computational Linguistics Adjoining Tree-to-String Translation Yang Liu, Qun Liu, and Yajuan L¨u Key Laboratory of Intelligent Information Processing Institute of Computing Technology Chinese Academy of Sciences P.O. Box 2704, Beijing 100190, China {yliu,liuqun,lvyajuan}@ict.ac.cn Abstract We introduce synchronous tree adjoining grammars (TAG) into tree-to-string transla- tion, which converts a source tree to a target string. Without reconstructing TAG deriva- tions explicitly, our rule extraction algo- rithm directly learns tree-to-string rules from aligned Treebank-style trees. As tree-to-string translation casts decoding as a tree parsing problem rather than parsing, the decoder still runs fast when adjoining is included. Less than 2 times slower, the adjoining tree-to- string system improves translation quality by +0.7 BLEU over the baseline system only al- lowing for tree substitution on NIST Chinese- English test sets. 1 Introduction Syntax-based translation models, which exploit hi- erarchical structures of natural languages to guide machine translation, have become increasingly pop- ular in recent years. So far, most of them have been based on synchronous context-free grammars (CFG) (Chiang, 2007), tree substitution grammars (TSG) (Eisner, 2003; Galley et al., 2006; Liu et al., 2006; Huang et al., 2006; Zhang et al., 2008), and inversion transduction grammars (ITG) (Wu, 1997; Xiong et al., 2006). Although these for- malisms present simple and precise mechanisms for describing the basic recursive structure of sentences, they are not powerful enough to model some impor- tant features of natural language syntax. For ex- ample, Chiang (2006) points out that the transla- tion of languages that can stack an unbounded num- ber of clauses in an “inside-out” way (Wu, 1997) provably goes beyond the expressive power of syn- chronous CFG and TSG. Therefore, it is necessary to find ways to take advantage of more powerful syn- chronous grammars to improve machine translation. Synchronous tree adjoining grammars (TAG) (Shieber and Schabes, 1990) are a good candidate. As a formal tree rewriting system, TAG (Joshi et al., 1975; Joshi, 1985) provides a larger domain of lo- cality than CFG to state linguistic dependencies that are far apart since the formalism treats trees as basic building blocks. As a mildly context-sensitive gram- mar, TAG is conjectured to be powerful enough to model natural languages. Synchronous TAG gener- alizes TAG by allowing the construction of a pair of trees using the TAG operations of substitution and adjoining on tree pairs. The idea of using syn- chronous TAG in machine translation has been pur- sued by several researchers (Abeille et al., 1990; Prigent, 1994; Dras, 1999), but only recently in its probabilistic form (Nesson et al., 2006; De- Neefe and Knight, 2009). Shieber (2007) argues that probabilistic synchronous TAG possesses appealing properties such as expressivity and trainability for building a machine translation system. However, one major challenge for applying syn- chronous TAG to machine translation is computa- tional complexity. While TAG requires O(n6) time for monolingual parsing, synchronous TAG requires O(n12) for bilingual …

Content truncated to 500 words