Binarized Forest to String Translation

Proceedings of the 49th Annual Meeting of the Association for Computational Linguistics, pages 835–845, Portland, Oregon, June 19-24, 2011. c⃝2011 Association for Computational Linguistics Binarized Forest to String Translation Hao Zhang Google Research haozhang@google.com Licheng Fang Computer Science Department University of Rochester lfang@cs.rochester.edu Peng Xu Google Research xp@google.com Xiaoyun Wu Google Research xiaoyunwu@google.com Abstract Tree-to-string translation is syntax-aware and efficient but sensitive to parsing errors. Forest- to-string translation approaches mitigate the risk of propagating parser errors into transla- tion errors by considering a forest of alterna- tive trees, as generated by a source language parser. We propose an alternative approach to generating forests that is based on combining sub-trees within the first best parse through binarization. Provably, our binarization for- est can cover any non-consitituent phrases in a sentence but maintains the desirable prop- erty that for each span there is at most one nonterminal so that the grammar constant for decoding is relatively small. For the purpose of reducing search errors, we apply the syn- chronous binarization technique to forest-to- string decoding. Combining the two tech- niques, we show that using a fast shift-reduce parser we can achieve significant quality gains in NIST 2008 English-to-Chinese track (1.3 BLEU points over a phrase-based system, 0.8 BLEU points over a hierarchical phrase-based system). Consistent and significant gains are also shown in WMT 2010 in the English to German, French, Spanish and Czech tracks. 1 Introduction In recent years, researchers have explored a wide spectrum of approaches to incorporate syntax and structure into machine translation models. The uni- fying framework for these models is synchronous grammars (Chiang, 2005) or tree transducers (Graehl and Knight, 2004). Depending on whether or not monolingual parsing is carried out on the source side or the target side for inference, there are four general categories within the framework: • string-to-string (Chiang, 2005; Zollmann and Venugopal, 2006) • string-to-tree (Galley et al., 2006; Shen et al., 2008) • tree-to-string (Lin, 2004; Quirk et al., 2005; Liu et al., 2006; Huang et al., 2006; Mi et al., 2008) • tree-to-tree (Eisner, 2003; Zhang et al., 2008) In terms of search, the string-to-x models explore all possible source parses and map them to the target side, while the tree-to-x models search over the sub- space of structures of the source side constrained by an input tree or trees. Hence, tree-to-x mod- els are more constrained but more efficient. Mod- els such as Huang et al. (2006) can match multi- level tree fragments on the source side which means larger contexts are taken into account for transla- tion (Poutsma, 2000), which is a modeling advan- tage. To balance efficiency and accuracy, forest-to- string models (Mi et al., 2008; Mi and Huang, 2008) use a compact representation of exponentially many trees to improve tree-to-string models. Tradition- ally, such forests are obtained through hyper-edge pruning in the k-best search space of a monolin- gual parser (Huang, 2008). The pruning parameters that control the size of forests are normally hand- tuned. Such forests encode …

Content truncated to 500 words