Decoding Algorithm in Statistical Machine Translation

Decoding Algorithm in Statistical Machine Translation Ye-Yi Wang and Alex Waibel Language Technology Institute School of Computer Science Carnegie Mellon University 5000 Forbes Avenue Pittsburgh, PA 15213, USA {yyw, waibel}@cs, cmu. edu Abstract Decoding algorithm is a crucial part in sta- tistical machine translation. We describe a stack decoding algorithm in this paper. We present the hypothesis scoring method and the heuristics used in our algorithm. We report several techniques deployed to improve the performance of the decoder. We also introduce a simplified model to moderate the sparse data problem and to speed up the decoding process. We evalu- ate and compare these techniques/models in our statistical machine translation sys- tem. 1 Introduction 1.1 Statistical Machine Translation Statistical machine translation is based on a channel model. Given a sentence T in one language (Ger- man) to be translated into another language (En- glish), it considers T as the target of a communi- cation channel, and its translation S as the source of the channel. Hence the machine translation task becomes to recover the source from the target. Ba- sically every English sentence is a possible source for a German target sentence. If we assign a probability P(S I T) to each pair of sentences (S, T), then the problem of translation is to find the source S for a given target T, such that P(S [ T) is the maximum. According to Bayes rule, P(S IT) = P(S)P(T I S) P(T) (1) Since the denominator is independent of S, we have -- arg maxP(S)P(T I S) (2) S Therefore a statistical machine translation system must deal with the following three problems: • Modeling Problem: How to depict the process of generating a sentence in a source language, and the process used by a channel to generate a target sentence upon receiving a source sen- tence? The former is the problem of language modeling, and the later is the problem of trans- lation modeling. They provide a framework for calculating P(S) and P(W I S) in (2). • Learning Problem: Given a statistical language model P(S) and a statistical translation model P(T I S), how to estimate the parameters in these models from a bilingual corpus of sen- tences? • Decoding Problem: With a fully specified (framework and parameters) language and translation model, given a target sentence T, how to efficiently search for the source sentence that satisfies (2). The modeling and learning issues have been dis- cussed in (Brown et ah, 1993), where ngram model was used for language modeling, and five different translation models were introduced for the transla- tion process. We briefly introduce the model 2 here, for which we built our decoder. In model 2, upon receiving a source English sen- tence e = el,. • -, el, the channel generates a German sentence g = gl, • • ", g,n at the target end in the fol- lowing way: 1. With a distribution P(m I e), randomly choose the length m of the German translation g. …

Content truncated to 500 words