Scaling Phrase-Based Statistical Machine Translation to Larger Corpora and Longer Phrases

Proceedings of the 43rd Annual Meeting of the ACL, pages 255–262, Ann Arbor, June 2005. c⃝2005 Association for Computational Linguistics Scaling Phrase-Based Statistical Machine Translation to Larger Corpora and Longer Phrases Chris Callison-Burch Colin Bannard University of Edinburgh 2 Buccleuch Place Edinburgh EH8 9LW {chris,colin}@linearb.co.uk Josh Schroeder Linear B Ltd. 39 B Cumberland Street Edinburgh EH3 6RA josh@linearb.co.uk Abstract In this paper we describe a novel data structure for phrase-based statistical ma- chine translation which allows for the re- trieval of arbitrarily long phrases while si- multaneously using less memory than is required by current decoder implementa- tions. We detail the computational com- plexity and average retrieval times for looking up phrase translations in our suf- fix array-based data structure. We show how sampling can be used to reduce the retrieval time by orders of magnitude with no loss in translation quality. 1 Introduction Statistical machine translation (SMT) has an advan- tage over many other statistical natural language processing applications in that training data is reg- ularly produced by other human activity. For some language pairs very large sets of training data are now available. The publications of the European Union and United Nations provide gigbytes of data between various language pairs which can be eas- ily mined using a web crawler. The Linguistics Data Consortium provides an excellent set of off the shelf Arabic-English and Chinese-English paral- lel corpora for the annual NIST machine translation evaluation exercises. The size of the NIST training data presents a prob- lem for phrase-based statistical machine translation. Decoders such as Pharaoh (Koehn, 2004) primarily use lookup tables for the storage of phrases and their translations. Since retrieving longer segments of hu- man translated text generally leads to better trans- lation quality, participants in the evaluation exer- cise try to maximize the length of phrases that are stored in lookup tables. The combination of large corpora and long phrases means that the table size can quickly become unwieldy. A number of groups in the 2004 evaluation exer- cise indicated problems dealing with the data. Cop- ing strategies included limiting the length of phrases to something small, not using the entire training data set, computing phrases probabilities on disk, and fil- tering the phrase table down to a manageable size after the testing set was distributed. We present a data structure that is easily capable of handling the largest data sets currently available, and show that it can be scaled to much larger data sets. In this paper we: • Motivate the problem with storing enumerated phrases in a table by examining the memory re- quirements of the method for the NIST data set • Detail the advantages of using long phrases in SMT, and examine their potential coverage • Describe a suffix array-based data structure which allows for the retrieval of translations of arbitrarily long phrases, and show that it re- quires far less memory than a table • Calculate the computational complexity and average time for retrieving phrases and show how this can …

Content truncated to 500 words