Search algorithms for statistical machine translation based on dynamic programming and pruning techniques

SEARCH ALGORITHMS FOR STATISTICAL MACHINE TRANSLATION BASED ON DYNAMIC PROGRAMMING AND PRUNING TECHNIQUES Ismael Garc´ıa-Varea � , Francisco Casacuberta � � Departamento de Inform´atica Universidad de Castilla-La Mancha 02071 Albacete, SPAIN ivarea@info-ab.uclm.es � Instituto Tecnol´ogico de Inform´atica Departamento de Sistemas Inform´aticos y Computaci´on Universidad Polit´ecnica de Valencia 46071 Valencia, SPAIN fcn@iti.upv.es Abstract The increasing interest in the statistical approach to Machine Translation is due to the development of effective algorithms for training the probabilistic models proposed so far. However, one of the open problems with statistical machine translation is the design of efficient algorithms for translating a given input string. For some interesting models, only (good) approximate solutions can be found. Recently, a dynamic programming-like algorithm for the IBM-Model 2 has been proposed which is based on an iterative process of refinement solutions. A new dynamic programming-like algorithm is proposed here to deal with more complex IBM models (models 3 to 5). The computational cost of the algorithm is reduced by using an alignment-based pruning technique. Experimental results with the so-called “Tourist Task” are also presented. Keywords Statistical Machine Translation, Search Algorithms, Pruning Techniques Introduction The goal of the translation process of statistical machine translation (SMT) can be formulated as follows: given a source language string �� �� � � � � � � � , search for the target language string  � �  � � � �   that maximize   �� argmax      �  � � � � (1) In our case, the source language is Spanish and the target language is English. According to Bayes’ decision rule, we have to choose the target string that maximizes the product of the target language model   � and the string transla- tion model   �� �  ! � . The equation that models this pro- cess is:   �"� argmax #  $     � %   � � �   � '& (2) Many existing systems for SMT (Niessen et al., 1998; Wang and Waibel, 1997) make use of a special way of struc- turing the string translation model as proposed by (Brown et al., 1993): The correspondence between the words in the source and the target string is described by alignments that assign one target word position to each source word posi- tion. One of the open problems with SMT is the design of efficient algorithms for searching the translation of a given input string, that is to solve the global search maximization problem. Interesting translation models were proposed in (Brown et al., 1993). However, the corresponding search algorithms for the IBM-Model 1 to IBM-Model 5 in (Brown et al., 1993) are based on a certain type of the () algorithm (Brown et al., 1990) or on the stack decoding approach (Al-Onaizan et al., 1999; Wang and Waibel, 1997). There are also dynamic-programming-based search al- gorithms such as (Tillmann et al., 1997a; Tillmann et al., 1997b) for the first-order …

Content truncated to 500 words