An Algorithmic Framework for Solving the Decoding Problem in Statistical Machine Translation

An Algorithmic Framework for the Decoding Problem in Statistical Machine Translation Raghavendra Udupa U Tanveer A Faruquie IBM India Research Lab Block-1A, IIT, Hauz Khas New Delhi - 110 016 India {uraghave, ftanveer}@in.ibm.com Hemanta K Maji Dept. of Computer Science and Engineering, IIT Kanpur Kanpur - 208 016 India, hkmaji@iitk.ac.in Abstract The decoding problem in Statistical Ma- chine Translation (SMT) is a computation- ally hard combinatorial optimization prob- lem. In this paper, we propose a new al- gorithmic framework for solving the decod- ing problem and demonstrate its utility. In the new algorithmic framework, the decod- ing problem can be solved both exactly and approximately. The key idea behind the framework is the modeling of the decod- ing problem as one that involves alternat- ing maximization of two relatively simpler subproblems. We show how the subprob- lems can be solved efficiently and how their solutions can be combined to arrive at a so- lution for the decoding problem. A fam- ily of provably fast decoding algorithms can be derived from the basic techniques under- lying the framework and we present a few illustrations. Our first algorithm is a prov- ably linear time search algorithm. We use this algorithm as a subroutine in the other algorithms. We believe that decoding algo- rithms derived from our framework can be of practical significance. 1 Introduction Decoding is one of the three fundamental prob- lems in classical SMT (translation model and language model being the other two) as pro- posed by IBM in the early 1990’s (Brown et al., 1993). In the decoding problem we are given the language and translation models and a source language sentence and are asked to find the most probable translation for the sentence. De- coding is a discrete optimization problem whose search space is prohibitively large. The chal- lenge is, therefore, in devising a scheme to ef- ficiently search the solution space for the solu- tion. Decoding is known to belong to a class of com- putational problems popularly known as NP- hard problems (Knight, 1999). NP-hard prob- lems are known to be computationally hard and have eluded polynomial time algorithms (Garey and Johnson, 1979). The first algorithms for the decoding problem were based on what is known among the speech recognition commu- nity as stack-based search (Jelinek, 1969). The original IBM solution to the decoding prob- lem employed a restricted stack-based search (Berger et al., 1996). This idea was further ex- plored by Wang and Waibel (Wang and Waibel, 1997) who developed a faster stack-based search algorithm. In perhaps the first work on the computational complexity of Decoding, Kevin Knight showed that the problem is closely re- lated to the more famous Traveling Salesman problem (TSP). Independently, Christoph Till- man adapted the Held-Karp dynamic program- ming algorithm for TSP (Held and Karp, 1962) to Decoding (Tillman, 2001). The original Held- Karp algorithm for TSP is an exponential time dynamic programming algorithm and Tillman’s adaptation to Decoding has a prohibitive com- plexity of O �l3m22m� ≈ O �m52m� …

Content truncated to 500 words