Fast Translation Rule Matching for Syntax-based Statistical Machine Translation

Proceedings of the 2009 Conference on Empirical Methods in Natural Language Processing, pages 1037–1045, Singapore, 6-7 August 2009. c⃝2009 ACL and AFNLP Fast Translation Rule Matching for Syntax-based Statistical Machine Translation Hui Zhang1, 2 Min Zhang1 Haizhou Li1 Chew Lim Tan2 1Institute for Infocomm Research 2National University of Singapore zhangh1982@gmail.com {mzhang, hli}@i2r.a-star.edu.sg tancl@comp.nus.edu.sg Abstract In a linguistically-motivated syntax-based trans- lation system, the entire translation process is normally carried out in two steps, translation rule matching and target sentence decoding us- ing the matched rules. Both steps are very time- consuming due to the tremendous number of translation rules, the exhaustive search in trans- lation rule matching and the complex nature of the translation task itself. In this paper, we pro- pose a hyper-tree-based fast algorithm for trans- lation rule matching. Experimental results on the NIST MT-2003 Chinese-English translation task show that our algorithm is at least 19 times faster in rule matching and is able to help to save 57% of overall translation time over previ- ous methods when using large fragment transla- tion rules. 1 Introduction Recently linguistically-motivated syntax-based translation method has achieved great success in statistical machine translation (SMT) (Galley et al., 2004; Liu et al., 2006, 2007; Zhang et al., 2007, 2008a; Mi et al., 2008; Mi and Huang 2008; Zhang et al., 2009). It translates a source sentence to its target one in two steps by using structured translation rules. In the first step, which is called translation rule matching step, all the applicable1 translation rules are extracted from the entire rule set by matching the source parse tree/forest. The second step is to decode the source sentence into its target one using the extracted translation rules. Both of the two steps are very time-consuming due to the exponential number of translation rules and the complex nature of machine translation as 1 Given a source structure (either a parse tree or a parse forest), a translation rule is applicable if and only if the left hand side of the translation rule exactly matches a tree fragment of the given source structure. an NP-hard search problem (Knight, 1999). In the SMT research community, the second step has been well studied and many methods have been proposed to speed up the decoding process, such as node-based or span-based beam search with different pruning strategies (Liu et al., 2006; Zhang et al., 2008a, 2008b) and cube pruning (Huang and Chiang, 2007; Mi et al., 2008). How- ever, the first step attracts less attention. The pre- vious solution to this problem is to do exhaustive searching with heuristics on each tree/forest node or on each source span. This solution becomes computationally infeasible when it is applied to packed forests with loose pruning threshold or rule sets with large tree fragments of large rule height and width. This not only overloads the translation process but also compromises the translation per- formance since as shown in our experiments the large tree fragment rules are also very useful. To solve the above issue, …

Content truncated to 500 words