Hierarchical Phrase-Based Translation with Suffix Arrays

Proceedings of the 2007 Joint Conference on Empirical Methods in Natural Language Processing and Computational Natural Language Learning, pp. 976–985, Prague, June 2007. c⃝2007 Association for Computational Linguistics Hierarchical Phrase-Based Translation with Suffix Arrays Adam Lopez Computer Science Department Institute for Advanced Computer Studies University of Maryland College Park, MD 20742 USA alopez@cs.umd.edu Abstract A major engineering challenge in statistical machine translation systems is the efficient representation of extremely large translation rulesets. In phrase-based models, this prob- lem can be addressed by storing the training data in memory and using a suffix array as an efficient index to quickly lookup and ex- tract rules on the fly. Hierarchical phrase- based translation introduces the added wrin- kle of source phrases with gaps. Lookup algorithms used for contiguous phrases no longer apply and the best approximate pat- tern matching algorithms are much too slow, taking several minutes per sentence. We describe new lookup algorithms for hierar- chical phrase-based translation that reduce the empirical computation time by nearly two orders of magnitude, making on-the-fly lookup feasible for source phrases with gaps. 1 Introduction Current statistical machine translation systems rely on very large rule sets. In phrase-based systems, rules are extracted from parallel corpora containing tens or hundreds of millions of words. This can re- sult in millions of rules using even the most conser- vative extraction heuristics. Efficient algorithms for rule storage and access are necessary for practical decoding algorithms. They are crucial to keeping up with the ever-increasing size of parallel corpora, as well as the introduction of new data sources such as web-mined and comparable corpora. Until recently, most approaches to this problem involved substantial tradeoffs. The common prac- tice of test set filtering renders systems impracti- cal for all but batch processing. Tight restrictions on phrase length curtail the power of phrase-based models. However, some promising engineering so- lutions are emerging. Zens and Ney (2007) use a disk-based prefix tree, enabling efficient access to phrase tables much too large to fit in main memory. An alternative approach introduced independently by both Callison-Burch et al. (2005) and Zhang and Vogel (2005) is to store the training data itself in memory, and use a suffix array as an efficient in- dex to look up, extract, and score phrase pairs on the fly. We believe that the latter approach has several important applications (§7). So far, these techniques have focused on phrase- based models using contiguous phrases (Koehn et al., 2003; Och and Ney, 2004). Some recent models permit discontiguous phrases (Chiang, 2007; Quirk et al., 2005; Simard et al., 2005). Of particular in- terest to us is the hierarchical phrase-based model of Chiang (2007), which has been shown to be supe- rior to phrase-based models. The ruleset extracted by this model is a superset of the ruleset in an equiv- alent phrase-based model, and it is an order of mag- nitude larger. This makes efficient rule representa- tion even more critical. We tackle the problem using the online rule extraction method of …

Content truncated to 500 words