Forest-Based Translation

Proceedings of ACL-08: HLT, pages 192–199, Columbus, Ohio, USA, June 2008. c⃝2008 Association for Computational Linguistics Forest-Based Translation Haitao Mi† Liang Huang‡ Qun Liu† †Key Lab. of Intelligent Information Processing ‡Department of Computer & Information Science Institute of Computing Technology University of Pennsylvania Chinese Academy of Sciences Levine Hall, 3330 Walnut Street P.O. Box 2704, Beijing 100190, China Philadelphia, PA 19104, USA {htmi,liuqun}@ict.ac.cn lhuang3@cis.upenn.edu Abstract Among syntax-based translation models, the tree-based approach, which takes as input a parse tree of the source sentence, is a promis- ing direction being faster and simpler than its string-based counterpart. However, current tree-based systems suffer from a major draw- back: they only use the 1-best parse to direct the translation, which potentially introduces translation mistakes due to parsing errors. We propose a forest-based approach that trans- lates a packed forest of exponentially many parses, which encodes many more alternatives than standard n-best lists. Large-scale exper- iments show an absolute improvement of 1.7 BLEU points over the 1-best baseline. This result is also 0.8 points higher than decoding with 30-best parses, and takes even less time. 1 Introduction Syntax-based machine translation has witnessed promising improvements in recent years. Depend- ing on the type of input, these efforts can be di- vided into two broad categories: the string-based systems whose input is a string to be simultane- ously parsed and translated by a synchronous gram- mar (Wu, 1997; Chiang, 2005; Galley et al., 2006), and the tree-based systems whose input is already a parse tree to be directly converted into a target tree or string (Lin, 2004; Ding and Palmer, 2005; Quirk et al., 2005; Liu et al., 2006; Huang et al., 2006). Compared with their string-based counterparts, tree- based systems offer some attractive features: they are much faster in decoding (linear time vs. cubic time, see (Huang et al., 2006)), do not require a binary-branching grammar as in string-based mod- els (Zhang et al., 2006), and can have separate gram- mars for parsing and translation, say, a context-free grammar for the former and a tree substitution gram- mar for the latter (Huang et al., 2006). However, de- spite these advantages, current tree-based systems suffer from a major drawback: they only use the 1- best parse tree to direct the translation, which po- tentially introduces translation mistakes due to pars- ing errors (Quirk and Corston-Oliver, 2006). This situation becomes worse with resource-poor source languages without enough Treebank data to train a high-accuracy parser. One obvious solution to this problem is to take as input k-best parses, instead of a single tree. This k- best list postpones some disambiguation to the de- coder, which may recover from parsing errors by getting a better translation from a non 1-best parse. However, a k-best list, with its limited scope, of- ten has too few variations and too many redundan- cies; for example, a 50-best list typically encodes a combination of 5 or 6 binary ambiguities (since 25 < 50 < 26), and many subtrees are repeated across different parses …

Content truncated to 500 words