Binarizing Syntax Trees to Improve Syntax-Based Machine Translation Accuracy

Proceedings of the 2007 Joint Conference on Empirical Methods in Natural Language Processing and Computational Natural Language Learning, pp. 746–754, Prague, June 2007. c⃝2007 Association for Computational Linguistics Binarizing Syntax Trees to Improve Syntax-Based Machine Translation Accuracy Wei Wang and Kevin Knight and Daniel Marcu Language Weaver, Inc. 4640 Admiralty Way, Suite 1210 Marina del Rey, CA, 90292 {wwang,kknight,dmarcu}@languageweaver.com Abstract We show that phrase structures in Penn Tree- bank style parses are not optimal for syntax- based machine translation. We exploit a se- ries of binarization methods to restructure the Penn Treebank style trees such that syn- tactified phrases smaller than Penn Treebank constituents can be acquired and exploited in translation. We find that by employing the EM algorithm for determining the binariza- tion of a parse tree among a set of alternative binarizations gives us the best translation re- sult. 1 Introduction Syntax-based translation models (Eisner, 2003; Gal- ley et al., 2006; Marcu et al., 2006) are usually built directly from Penn Treebank (PTB) (Marcus et al., 1993) style parse trees by composing treebank gram- mar rules. As a result, often no substructures corre- sponding to partial PTB constituents are extracted to form translation rules. Syntax translation models acquired by composing treebank grammar rules assume that long rewrites are not decomposable into smaller steps. This ef- fectively restricts the generalization power of the in- duced model. For example, suppose we have an xRs (Knight and Graehl, 2004) rule R1 in Figure 1 that translates the Chinese phrase RUSSIA MINISTER VIKTOR-CHERNOMYRDIN into an English NPB tree fragment yielding an English phrase. Also suppose that we want to translate a Chinese phrase VIKTOR-CHERNOMYRDIN AND HIS COLLEAGUE into English. What we desire is that if we have another rule R2 as shown in Figure 1, we could somehow compose it with R1 to obtain the desir- able translation. We unfortunately cannot do this because R1 and R2 are not further decomposable and their substructures cannot be re-used. The re- quirement that all translation rules have exactly one root node does not enable us to use the translation of VIKTOR-CHERNOMYRDIN in any other contexts than those seen in the training corpus. A solution to overcome this problem is to right- binarize the left-hand side (LHS) (or the English- side) tree of R1 such that we can decompose R1 into R3 and R4 by factoring NNP(viktor) NNP(chernomyrdin) out as R4 according to the word alignments; and left-binarize the LHS of R2 by introducing a new tree node that collapses the two NNP’s, so as to generalize this rule, getting rule R5 and rule R6. We also need to consistently syntact- ify the root labels of R4 and the new frontier label of R6 such that these two rules can be composed. Since labeling is not a concern of this paper, we sim- ply label new nodes with X-bar where X here is the parent label. With all these in place, we now can translate the foreign sentence by composing R6 and R4 in Figure …

Content truncated to 500 words