Forest-based Translation Rule Extraction

Proceedings of the 2008 Conference on Empirical Methods in Natural Language Processing, pages 206–214, Honolulu, October 2008. c⃝2008 Association for Computational Linguistics Forest-based Translation Rule Extraction Haitao Mi1 1Key Lab. of Intelligent Information Processing Institute of Computing Technology Chinese Academy of Sciences P.O. Box 2704, Beijing 100190, China htmi@ict.ac.cn Liang Huang2,1 2Dept. of Computer & Information Science University of Pennsylvania 3330 Walnut St., Levine Hall Philadelphia, PA 19104, USA lhuang3@cis.upenn.edu Abstract Translation rule extraction is a fundamental problem in machine translation, especially for linguistically syntax-based systems that need parse trees from either or both sides of the bi- text. The current dominant practice only uses 1-best trees, which adversely affects the rule set quality due to parsing errors. So we pro- pose a novel approach which extracts rules from a packed forest that compactly encodes exponentially many parses. Experiments show that this method improves translation quality by over 1 BLEU point on a state-of-the-art tree-to-string system, and is 0.5 points better than (and twice as fast as) extracting on 30- best parses. When combined with our previous work on forest-based decoding, it achieves a 2.5 BLEU points improvement over the base- line, and even outperforms the hierarchical system of Hiero by 0.7 points. 1 Introduction Automatic extraction of translation rules is a funda- mental problem in statistical machine translation, es- pecially for many syntax-based models where trans- lation rules directly encode linguistic knowledge. Typically, these models extract rules using parse trees from both or either side(s) of the bitext. The former case, with trees on both sides, is often called tree-to-tree models; while the latter case, with trees on either source or target side, include both tree- to-string and string-to-tree models (see Table 1). Leveraging from structural and linguistic informa- tion from parse trees, these models are believed to be better than their phrase-based counterparts in source target examples (partial) tree-to-tree Ding and Palmer (2005) tree-to-string Liu et al. (2006); Huang et al. (2006) string-to-tree Galley et al. (2006) string-to-string Chiang (2005) Table 1: A classification of syntax-based MT. The first three use linguistic syntax, while the last one only formal syntax. Our experiments cover the second type using a packed forest in place of the tree for rule-extraction. handling non-local reorderings, and have achieved promising translation results.1 However, these systems suffer from a major limi- tation, that the rule extractor only uses 1-best parse tree(s), which adversely affects the rule set quality due to parsing errors. To make things worse, mod- ern statistical parsers are often trained on domains quite different from those used in MT. By contrast, formally syntax-based models (Chiang, 2005) do not rely on parse trees, yet usually perform better than these linguistically sophisticated counterparts. To alleviate this problem, an obvious idea is to extract rules from k-best parses instead. However, a k-best list, with its limited scope, has too few vari- ations and too many redundancies (Huang, 2008). This situation worsens with longer sentences as the number of possible parses grows exponentially with the sentence …

Content truncated to 500 words