Download Statistical Machine Translation System User Manual and Code Guide

4.2. Decoder
115
We proceed through these hypothesis stacks, going through each hypothesis in the stack,
deriving new hypotheses for this hypothesis and placing them into the appropriate stack (see
figure below for an illustration). After a new hypothesis is placed into a stack, the stack may
have to be pruned by threshold or histogram pruning, if it has become too large. In the end,
the best hypothesis of the ones that cover all foreign words is the final state of the best translation. We can read off the English words of the translation by following the back links in each
hypothesis.
4.2.5
Future Cost Estimation
Recall that for excluding hypotheses from the beam we do not only have to consider the cost so
far, but also an estimate of the future cost. While it is possible to calculate the cheapest possible
future cost for each hypothesis, this is computationally so expensive that it would defeat the
purpose of the beam search.
The future cost is tied to the foreign words that are not yet translated. In the framework
of the phrase-based model, not only may single words be translated individually, but also
consecutive sequences of words as a phrase.
Each such translation operation carries a translation cost, language model costs, and a distortion cost. For our future cost estimate we consider only translation and language model
costs. The language model cost is usually calculated by a trigram language model. However,
we do not know the preceding English words for a translation operation. Therefore, we approximate this cost by computing the language model score for the generated English words
alone. That means, if only one English word is generated, we take its unigram probability. If
two words are generated, we take the unigram probability of the first word and the bigram
probability of the second word, and so on.
For a sequence of foreign words multiple overlapping translation options exist. We just
described how we calculate the cost for each translation option. The cheapest way to translate
the sequence of foreign words includes the cheapest translation options. We approximate the
cost for a path through translation options by the product of the cost for each option.
To illustrate this concept, refer to the figure below. The translation options cover different
consecutive foreign words and carry an estimated cost cij . The cost of the shaded path through