A Syntactified Direct Translation Model with Linear-time Decoding

Proceedings of the 2009 Conference on Empirical Methods in Natural Language Processing, pages 1182–1191, Singapore, 6-7 August 2009. c⃝2009 ACL and AFNLP A Syntactified Direct Translation Model with Linear-time Decoding Hany Hassan Cairo TDC IBM Cairo, Egypt hanyh@eg.ibm.com Khalil Sima’an Language and Computation University of Amsterdam Amsterdam, The Netherlands k.simaan@uva.nl Andy Way School of Computing Dublin City University Dublin, Ireland away@computing.dcu.ie Abstract Recent syntactic extensions of statisti- cal translation models work with a syn- chronous context-free or tree-substitution grammar extracted from an automatically parsed parallel corpus. The decoders ac- companying these extensions typically ex- ceed quadratic time complexity. This paper extends the Direct Transla- tion Model 2 (DTM2) with syntax while maintaining linear-time decoding. We employ a linear-time parsing algorithm based on an eager, incremental interpre- tation of Combinatory Categorial Gram- mar (CCG). As every input word is pro- cessed, the local parsing decisions resolve ambiguity eagerly, by selecting a single supertag–operator pair for extending the dependency parse incrementally. Along- side translation features extracted from the derived parse tree, we explore syn- tactic features extracted from the incre- mental derivation process. Our empiri- cal experiments show that our model sig- nificantly outperforms the state-of-the art DTM2 system. 1 Introduction Syntactic structure is gradually showing itself to constitute a promising enrichment of state-of-the- art Statistical Machine Translation (SMT) models. However, it would appear that the decoding algo- rithms are bearing the brunt of this improvement in terms of time and space complexity. Most recent extensions work with a synchronous context-free or tree-substitution grammar extracted from an au- tomatically parsed parallel corpus. While attrac- tive in many ways, the decoders that are needed for these types of grammars usually have time and space complexities that are far beyond linear. Leaving pruning aside, there is a genuine ques- tion as to whether syntactic structure necessarily implies more complex decoding algorithms. This paper shows that this need not necessarily be the case. In this paper we extend the Direct Translation Model (DTM2) (Ittycheriah and Roukos, 2007) with target language syntax while maintaining linear-time decoding. With this extension we make three novel contributions to SMT. Our first contribution is to define a linear-time syntactic parser that works as incrementally as standard SMT decoders (Tillmann and Ney, 2003; Koehn, 2004a). At every word position in the target lan- guage string, this parser spans at most a single parse-state to augment the translation states in the decoder. The parse state summarizes previ- ous parsing decisions and imposes constraints on the set of valid future extensions such that a well- formed sequence of parse states unambiguously defines a dependency structure. This approach is based on an incremental interpretation of the mechanisms of Combinatory Categorial Grammar (CCG) (Steedman, 2000). Our second contribution lies in extending the DMT2 model with a novel set of syntactically- oriented feature functions. Crucially, these feature functions concern the derived (partial) dependency structure as well as local aspects of the derivation process, including such information as the CCG lexical categories (supertag), the CCG operators and …

Content truncated to 500 words