Generalized Stack Decoding Algorithms for Statistical Machine Translation

Proceedings of the Workshop on Statistical Machine Translation, pages 64–71, New York City, June 2006. c⃝2006 Association for Computational Linguistics Generalized Stack Decoding Algorithms for Statistical Machine Translation∗ Daniel Ortiz Mart´ınez Inst. Tecnol´ogico de Inform´atica Univ. Polit´ecnica de Valencia 46071 Valencia, Spain dortiz@iti.upv.es Ismael Garc´ıa Varea Dpto. de Informatica Univ. de Castilla-La Mancha 02071 Albacete, Spain ivarea@info-ab.uclm.es Francisco Casacuberta Nolla Dpto. de Sist Inf. y Comp. Univ. Polit´ec. de Valencia 46071 Valencia, Spain fcn@dsic.upv.es Abstract In this paper we propose a generalization of the Stack-based decoding paradigm for Statistical Machine Translation. The well known single and multi-stack decoding algorithms defined in the literature have been integrated within a new formalism which also defines a new family of stack- based decoders. These decoders allows a tradeoff to be made between the ad- vantages of using only one or multiple stacks. The key point of the new formal- ism consists in parameterizeing the num- ber of stacks to be used during the de- coding process, and providing an efficient method to decide in which stack each par- tial hypothesis generated is to be inserted- during the search process. Experimental results are also reported for a search algo- rithm for phrase-based statistical transla- tion models. 1 Introduction The translation process can be formulated from a statistical point of view as follows: A source lan- guage string f J 1 = f1 . . . fJ is to be translated into a target language string eI 1 = e1 . . . eI. Every tar- get string is regarded as a possible translation for the source language string with maximum a-posteriori probability Pr(eI 1|f J 1 ). According to Bayes’ theo- rem, the target string ˆeI 1 that maximizes1 the product ∗This work has been partially supported by the Spanish project TIC2003-08681-C02-02, the Agencia Valenciana de Ciencia y Tecnolog´ıa under contract GRUPOS03/031, the Gen- eralitat Valenciana, and the project HERMES (Vicerrectorado de Investigaci´on - UCLM-05/06) 1Note that the expression should also be maximized by I; however, for the sake of simplicity we suppose that it is known. of both the target language model Pr(eI 1) and the string translation model Pr(f J 1 |eI 1) must be chosen. The equation that models this process is: ˆeI 1 = arg max eI 1 {Pr(eI 1) · Pr(f J 1 |eI 1)} (1) The search/decoding problem in SMT consists in solving the maximization problem stated in Eq. (1). In the literature, we can find different techniques to deal with this problem, ranging from heuristic and fast (as greedy decoders) to optimal and very slow decoding algorithms (Germann et al., 2001). Also, under certain circumstances, stack-based decoders can obtain optimal solutions. Many works (Berger et al., 1996; Wang and Waibel, 1998; Germann et al., 2001; Och et al., 2001; Ort´ız et al., 2003) have adopted different types of stack-based algorithms to solve the global search optimization problem for statistical machine trans- lation. All these works follow two main different approaches according to the number of stacks used …

Content truncated to 500 words