Computational Complexity of Statistical Machine Translation

Computational Complexity of Statistical Machine Translation Raghavendra Udupa U. IBM India Research Lab New Delhi India uraghave@in.ibm.com Hemanta K. Maji Dept. of Computer Science University of Illinois at Urbana-Champaigne hemanta.maji@gmail.com Abstract In this paper we study a set of prob- lems that are of considerable importance to Statistical Machine Translation (SMT) but which have not been addressed satis- factorily by the SMT research community. Over the last decade, a variety of SMT algorithms have been built and empiri- cally tested whereas little is known about the computational complexity of some of the fundamental problems of SMT. Our work aims at providing useful insights into the the computational complexity of those problems. We prove that while IBM Mod- els 1-2 are conceptually and computation- ally simple, computations involving the higher (and more useful) models are hard. Since it is unlikely that there exists a poly- nomial time solution for any of these hard problems (unless P = NP and P#P = P), our results highlight and justify the need for developing polynomial time ap- proximations for these computations. We also discuss some practical ways of deal- ing with complexity. 1 Introduction Statistical Machine Translation is a data driven machine translation technique which uses proba- bilistic models of natural language for automatic translation (Brown et al., 1993), (Al-Onaizan et al., 1999). The parameters of the models are estimated by iterative maximum-likelihood train- ing on a large parallel corpus of natural language texts using the EM algorithm (Brown et al., 1993). The models are then used to decode, i.e. trans- late texts from the source language to the target language 1 (Tillman, 2001), (Wang, 1997), (Ger- mann et al., 2003), (Udupa et al., 2004). The models are independent of the language pair and therefore, can be used to build a translation sys- tem for any language pair as long as a parallel corpus of texts is available for training. Increas- ingly, parallel corpora are becoming available for many language pairs and SMT systems have been built for French-English, German-English, Arabic-English, Chinese-English, Hindi-English and other language pairs (Brown et al., 1993), (Al- Onaizan et al., 1999), (Udupa, 2004). In SMT, every English sentence e is considered as a translation of a given French sentence f with probability Pr (f|e). Therefore, the problem of translating f can be viewed as a problem of finding the most probable translation of f: e∗ = argmax e Pr(e|f) = argmax e Pr(f|e)P(e). (1) The probability distributions Pr(f|e) and Pr(e) are known as translation model and lan- guage model respectively. In the classic work on SMT, Brown and his colleagues at IBM introduced the notion of alignment between a sentence f and its translation e and used it in the development of translation models (Brown et al., 1993). An align- ment between f = f1 . . . fm and e = e1 . . . el is a many-to-one mapping a : {1, . . . , m} → {0, . . . , l}. Thus, an alignment …

Content truncated to 500 words