Context-free reordering, finite-state translation

Human Language Technologies: The 2010 Annual Conference of the North American Chapter of the ACL, pages 858–866, Los Angeles, California, June 2010. c⃝2010 Association for Computational Linguistics Context-free reordering, finite-state translation Chris Dyer and Philip Resnik UMIACS Laboratory for Computational Linguistics and Information Processing Department of Linguistics University of Maryland, College Park, MD 20742, USA redpony, resnik AT umd.edu Abstract We describe a class of translation model in which a set of input variants encoded as a context-free forest is translated using a finite- state translation model. The forest structure of the input is well-suited to representing word order alternatives, making it straightforward to model translation as a two step process: (1) tree-based source reordering and (2) phrase transduction. By treating the reordering pro- cess as a latent variable in a probabilistic trans- lation model, we can learn a long-range source reordering model without example reordered sentences, which are problematic to construct. The resulting model has state-of-the-art trans- lation performance, uses linguistically moti- vated features to effectively model long range reordering, and is significantly smaller than a comparable hierarchical phrase-based transla- tion model. 1 Introduction Translation models based on synchronous context- free grammars (SCFGs) have become widespread in recent years (Wu, 1997; Chiang, 2007). Compared to phrase-based models, which can be represented as finite-state transducers (FSTs, Kumar et al. (2006)), one important benefit that SCFG models have is the ability to process long range reordering patterns in space and time that is polynomial in the length of the displacement, whereas an FST must generally explore a number of states that is exponential in this length.1 As one would expect, for language 1Our interest here is the reordering made possible by varying the arrangement of the translation units, not the local word order differences captured inside memorized phrase pairs. pairs with substantial structural differences (and thus requiring long-range reordering during translation), SCFG models have come to outperform the best FST models (Zollmann et al., 2008). In this paper, we explore a new way to take advan- tage of the computational benefits of CFGs during translation. Rather than using a single SCFG to both reorder and translate a source sentence into the target language, we break the translation process into a two step pipeline where (1) the source language is re- ordered into a target-like order, with alternatives en- coded in a context-free forest, and (2) the reordered source is transduced into the target language using an FST that represents phrasal correspondences. While multi-step decompositions of the transla- tion problem have been proposed before (Kumar et al., 2006), they are less practical with the rise of SCFG models, since the context-free languages are not closed under intersection (Hopcroft and Ullman, 1979). However, the CFLs are closed under intersec- tion with regular languages. By restricting ourselves to a finite-state phrase transducer and representing reorderings of the source in a context-free forest, ex- act inference over the composition of the two models is possible. The paper proceeds as follows. We first ex- plore reordering …

Content truncated to 500 words