Synchronous Binarization for Machine Translation

Proceedings of the Human Language Technology Conference of the North American Chapter of the ACL, pages 256–263, New York, June 2006. c⃝2006 Association for Computational Linguistics Synchronous Binarization for Machine Translation Hao Zhang Computer Science Department University of Rochester Rochester, NY 14627 zhanghao@cs.rochester.edu Liang Huang Dept. of Computer & Information Science University of Pennsylvania Philadelphia, PA 19104 lhuang3@cis.upenn.edu Daniel Gildea Computer Science Department University of Rochester Rochester, NY 14627 gildea@cs.rochester.edu Kevin Knight Information Sciences Institute University of Southern California Marina del Rey, CA 90292 knight@isi.edu Abstract Systems based on synchronous grammars and tree transducers promise to improve the quality of statistical machine transla- tion output, but are often very computa- tionally intensive. The complexity is ex- ponential in the size of individual gram- mar rules due to arbitrary re-orderings be- tween the two languages, and rules ex- tracted from parallel corpora can be quite large. We devise a linear-time algorithm for factoring syntactic re-orderings by bi- narizing synchronous rules when possible and show that the resulting rule set signif- icantly improves the speed and accuracy of a state-of-the-art syntax-based machine translation system. 1 Introduction Several recent syntax-based models for machine translation (Chiang, 2005; Galley et al., 2004) can be seen as instances of the general framework of synchronous grammars and tree transducers. In this framework, both alignment (synchronous parsing) and decoding can be thought of as parsing problems, whose complexity is in general exponential in the number of nonterminals on the right hand side of a grammar rule. To alleviate this problem, we investi- gate bilingual binarization to factor the synchronous grammar to a smaller branching factor, although it is not guaranteed to be successful for any synchronous rule with arbitrary permutation. In particular: • We develop a technique called synchronous bi- narization and devise a fast binarization algo- rithm such that the resulting rule set allows ef- ficient algorithms for both synchronous parsing and decoding with integrated n-gram language models. • We examine the effect of this binarization method on end-to-end machine translation quality, compared to a more typical baseline method. • We examine cases of non-binarizable rules in a large, empirically-derived rule set, and we in- vestigate the effect on translation quality when excluding such rules. Melamed (2003) discusses binarization of multi- text grammars on a theoretical level, showing the importance and difficulty of binarization for efficient synchronous parsing. One way around this diffi- culty is to stipulate that all rules must be binary from the outset, as in inversion-transduction gram- mar (ITG) (Wu, 1997) and the binary synchronous context-free grammar (SCFG) employed by the Hi- ero system (Chiang, 2005) to model the hierarchical phrases. In contrast, the rule extraction method of Galley et al. (2004) aims to incorporate more syn- tactic information by providing parse trees for the target language and extracting tree transducer rules that apply to the parses. This approach results in rules with many nonterminals, making good bina- rization techniques critical. Suppose we have the following SCFG, where su- perscripts indicate reorderings (formal definitions …

Content truncated to 500 words