Better Synchronous Binarization for Machine Translation

Proceedings of the 2009 Conference on Empirical Methods in Natural Language Processing, pages 362–370, Singapore, 6-7 August 2009. c⃝2009 ACL and AFNLP Better Synchronous Binarization for Machine Translation Tong Xiao*, Mu Li+, Dongdong Zhang+, Jingbo Zhu*, Ming Zhou+ *Natural Language Processing Lab Northeastern University Shenyang, China, 110004 xiaotong@mail.neu.edu.cn zhujingbo@mail.neu.edu.cn +Microsoft Research Asia Sigma Center Beijing, China, 100080 muli@microsoft.com dozhang@microsoft.com mingzhou@microsoft.com Abstract Binarization of Synchronous Context Free Grammars (SCFG) is essential for achieving polynomial time complexity of decoding for SCFG parsing based machine translation sys- tems. In this paper, we first investigate the excess edge competition issue caused by a left- heavy binary SCFG derived with the method of Zhang et al. (2006). Then we propose a new binarization method to mitigate the problem by exploring other alternative equivalent bi- nary SCFGs. We present an algorithm that ite- ratively improves the resulting binary SCFG, and empirically show that our method can im- prove a string-to-tree statistical machine trans- lations system based on the synchronous bina- rization method in Zhang et al. (2006) on the NIST machine translation evaluation tasks. 1 Introduction Recently Statistical Machine Translation (SMT) systems based on Synchronous Context Free Grammar (SCFG) have been extensively investi- gated (Chiang, 2005; Galley et al., 2004; Galley et al., 2006) and have achieved state-of-the-art performance. In these systems, machine transla- tion decoding is cast as a synchronous parsing task. Because general SCFG parsing is an NP- hard problem (Satta and Peserico, 2005), practic- al SMT decoders based on SCFG parsing re- quires an equivalent binary SCFG that is directly learned from training data to achieve polynomial time complexity using the CKY algorithm (Ka- sami, 1965; Younger, 1967) borrowed from CFG parsing techniques. Zhang et al. (2006) proposed synchronous binarization, a principled method to binarize an SCFG in such a way that both the source-side and target-side virtual non-terminals have contiguous spans. This property of syn- chronous binarization guarantees the polynomial time complexity of SCFG parsers even when an n-gram language model is integrated, which has been proved to be one of the keys to the success of a string-to-tree syntax-based SMT system. However, as shown by Chiang (2007), SCFG- based decoding with an integrated n-gram lan- guage model still has a time complexity of 𝛩(𝑚3 𝑃��� 4(𝑚���−1)), where m is the source sentence length, and 𝑃��� is the vocabulary size of the lan- guage model. Although it is not exponential in theory, the actual complexity can still be very high in practice. Here is an example extracted from real data. Given the following SCFG rule: VP → VB NP 会 JJR , VB NP will be JJR we can obtain a set of equivalent binary rules using the synchronous binarization method (Zhang et al., 2006) as follows: VP → V1 JJR , V1 JJR V1 → VB V2 , VB V2 V2 → NP 会 , NP will be This binarization is shown with the solid lines as binarization (a) in Figure 1. We can see that bi- narization (a) requires that …

Content truncated to 500 words