Efficient retrieval of tree translation examples for Syntax-Based Machine Translation

Proceedings of the 2011 Conference on Empirical Methods in Natural Language Processing, pages 508–518, Edinburgh, Scotland, UK, July 27–31, 2011. c⃝2011 Association for Computational Linguistics Efficient retrieval of tree translation examples for Syntax-Based Machine Translation Fabien Cromieres Graduate School of Informatics Kyoto University Kyoto, Japan fabien@nlp.kuee.kyoto-u.ac.jp Sadao Kurohashi Graduate School of Informatics Kyoto University Kyoto, Japan kuro@i.kyoto-u.ac.jp Abstract We propose an algorithm allowing to effi- ciently retrieve example treelets in a parsed tree database in order to allow on-the-fly ex- traction of syntactic translation rules. We also propose improvements of this algorithm al- lowing several kinds of flexible matchings. 1 Introduction The popular Example-Based (EBMT) and Statistical Machine Translation (SMT) paradigms make use of the translation examples provided by a parallel bilin- gual corpus to produce new translations. Most of these translation systems process the example data in a similar way: The parallel sentences are first word-aligned. Then, translation rules are extracted from these aligned sentences. Finally, the transla- tion rules are used in a decoding step to translate sentences. We use the term translation rule in a very broad sense here, as it may refer to substring pairs as in (Koehn et al., 2003), synchronous grammar rules as in (Chiang, 2007) or treelet pairs as in (Quirk et al., 2005; Nakazawa and Kurohashi, 2008). As the size of bilingual corpus grow larger, the number of translation rules to be stored can easily become unmanageable. As a solution to this prob- lem in the context of phrase-based Machine Transla- tion, (Callison-Burch et al., 2005) proposed to pre- align the example corpora, but delay the rule extrac- tion to the decoding stage. They showed that using Suffix Arrays, it was possible to efficiently retrieve all sentences containing substrings of the sentence to be translated, and thus extract the needed trans- lation rules on-the-fly. (Lopez, 2007) proposed an extension of this method for retrieving discontinu- ous substrings, making it suitable for systems such as (Chiang, 2007). In this paper, we propose a method to apply the same idea to Syntax-Based SMT and EBMT (Quirk et al., 2005; Mi et al., 2008; Nakazawa and Kuro- hashi, 2008). Since Syntax-Based systems usually work with the parse trees of the source-side sen- tences, we will need to be able to retrieve effi- ciently examples trees from fragments (treelets) of the parse tree of the sentence we want to translate. We will also propose extensions of this method al- lowing more flexible matchings. 2 Overview of the method 2.1 Treelet retrieval We first formalize the setting of this chapter by pro- viding some definitions. Definition 2.1 (Treelets). A treelet is a connected subgraph of a tree. A treelet T1 is a subtreelet of an- other treelet T2 if T1 is itself a connected subgraph of T2. We note |T| the number of nodes in a treelet. If |T| = 1, T is called an elementary treelet. A lin- ear treelet is a treelet whose nodes have at most 1 child. A subtree rooted at node n …

Content truncated to 500 words