



\section{
\label{tutorial.tex}
Phrase-based Tutorial}


This tutorial describes the workings of the phrase-based decoder in Moses, using a simple model downloadable from the Moses website.



\subsection{
\label{tutorial.texntoc1}A Simple Translation Model}


Let us begin with a look at the toy phrase-based translation model that is 
available for download at {\sf http://www.statmt.org/moses/download/sample-models.tgz}. Unpack the tar ball and enter the directory {\tt sample-models/phrase-model}.



The model consists of two files:

\begin{compactitem}
\item {\tt phrase-table} the phrase translation table, and

\item {\tt moses.ini} the configuration file for the decoder.

\end{compactitem}

Let us look at the first line of the {\bf phrase translation table} (file {\tt phrase-table}):






\begin{SaveVerbatim}{myverb}
der ||| the ||| 0.3 ||| |||
\end{SaveVerbatim}
\begin{shaded}
\small
\UseVerbatim{myverb}
\end{shaded}

This entry means that the probality of translating the English word {\tt the} from the German {\tt der} is 0.3. Or in mathematical notation: p(the$|$der)=0.3. Note that these translation probabilities are in the inverse order due to the noisy channel model.



The translation tables are the main knowledge source for the machine translation decoder. The decoder consults these tables to figure out how to translate input in one language into output in another language.  



Being a phrase translation model, the translation tables do not only contain single word entries, but multi-word entries. These are called {\bf phrases}, but this concept means nothing more than an arbitrary sequence of words, with no sophisticated linguistic motivation.



Here is an example for a phrase translation entry in {\tt phrase-table}:






\begin{SaveVerbatim}{myverb}
das ist ||| this is ||| 0.8 ||| |||
\end{SaveVerbatim}
\begin{shaded}
\small
\UseVerbatim{myverb}
\end{shaded}

\subsection{
\label{tutorial.texntoc2}Running the Decoder}


Without further ado, let us run the decoder (it needs to be run from the {\tt sample-models} directory) :

\begin{SaveVerbatim}{myverb}
% echo 'das ist ein kleines haus' | moses -f phrase-model/moses.ini > out
Defined parameters (per moses.ini or switch):
config: phrase-model/moses.ini
input-factors: 0
lmodel-file: 8 0 3 lm/europarl.srilm.gz
mapping: T 0
n-best-list: nbest.txt 100
ttable-file: 0 0 0 1 phrase-model/phrase-table
ttable-limit: 10
weight-d: 1
weight-l: 1
weight-t: 1
weight-w: 0
Loading lexical distortion models...have 0 models
Start loading LanguageModel lm/europarl.srilm.gz : [0.000] seconds
Loading the LM will be faster if you build a binary file.
Reading lm/europarl.srilm.gz
----5---10---15---20---25---30---35---40---45---50---55---60---65---70---75---80---85---90---95--100
****************************************************************************************************
The ARPA file is missing <unk>.  Substituting log10 probability -100.000.
Finished loading LanguageModels : [2.000] seconds
Start loading PhraseTable phrase-model/phrase-table : [2.000] seconds
filePath: phrase-model/phrase-table
Finished loading phrase tables : [2.000] seconds
Start loading phrase table from phrase-model/phrase-table : [2.000] seconds
Reading phrase-model/phrase-table
----5---10---15---20---25---30---35---40---45---50---55---60---65---70---75---80---85---90---95--100
****************************************************************************************************
Finished loading phrase tables : [2.000] seconds
IO from STDOUT/STDIN
Created input-output object : [2.000] seconds
Translating line 0  in thread id 0
Translating: das ist ein kleines haus

Collecting options took 0.000 seconds
Search took 0.000 seconds
BEST TRANSLATION: this is a small house [11111]  [total=-28.923] <<0.000, -5.000, 0.000, -27.091, -1.833>>
Translation took 0.000 seconds
Finished translating

% cat out
this is a small house
\end{SaveVerbatim}
\begin{shaded}
\scriptsize
\UseVerbatim{myverb}
\end{shaded}

Here, the toy model managed to translate the German input sentence {\tt das ist ein kleines haus} into the English {\tt this is a small house}, which is a correct translation.



The decoder is controlled by the configuration file {\tt moses.ini}. The file used in the example above is displayed below.






\begin{SaveVerbatim}{myverb}
#########################
### MOSES CONFIG FILE ###
#########################

# input factors
[input-factors]
0

# mapping steps, either (T) translation or (G) generation
[mapping]
T 0

[feature]
KENLM name=LM factor=0 order=3 num-features=1 path=lm/europarl.srilm.gz
Distortion
WordPenalty
UnknownWordPenalty
PhraseDictionaryMemory input-factor=0 output-factor=0 path=phrase-model/phrase-table num-features=1 table-limit=10 

[weight]
WordPenalty0= 0
LM= 1
Distortion0= 1
PhraseDictionaryMemory0= 1

[n-best-list]
nbest.txt
100
\end{SaveVerbatim}
\begin{shaded}
\tiny
\UseVerbatim{myverb}
\end{shaded}

We will take a look at all the parameters that are specified here (and
then some) later. At this point, let us just note that the translation
model files and the language model file are specified here. In this
example, the file names are relative paths, but usually having full
paths is better, so that the decoder does not have to be run from a
specific directory.



We just ran the decoder on a single sentence provided on the command
line. Usually we want to translate more than one sentence. In this
case, the input sentences are stored in a file, one sentence per line.
This file is piped into the decoder and the output is piped into some
output file for further processing:






\begin{SaveVerbatim}{myverb}
% moses -f phrase-model/moses.ini < phrase-model/in > out
\end{SaveVerbatim}
\begin{shaded}
\small
\UseVerbatim{myverb}
\end{shaded}

\subsection{
\label{tutorial.texntoc3}Trace}


How the decoder works is described in detail in the background (Section \ref{statmt.tex}) section. But let us first develop an intuition by looking under the hood. There are two switches that force the decoder to reveal more about its inner workings: {\tt -report-segmentation} and {\tt -verbose}.



The trace option reveals which phrase translations were used in the
best translation found by the decoder. Running the decoder with the 
segmentation trace switch (short {\tt -t}) on the same example 






\begin{SaveVerbatim}{myverb}
echo 'das ist ein kleines haus' | moses -f phrase-model/moses.ini -t >out
\end{SaveVerbatim}
\begin{shaded}
\small
\UseVerbatim{myverb}
\end{shaded}

gives us the extended output






\begin{SaveVerbatim}{myverb}
% cat out
this is |0-1| a |2-2| small |3-3| house |4-4|
\end{SaveVerbatim}
\begin{shaded}
\small
\UseVerbatim{myverb}
\end{shaded}

Each generated English phrase is now annotated with additional
information:

\begin{compactitem}
\item {\tt this is} was generated from the German words 0-1, {\tt das ist},

\item {\tt a} was generated from the German word 2-2, {\tt ein}, 

\item {\tt small} was generated from the German word 3-3, {\tt kleines}, and

\item {\tt house} was generated from the German word 4-4, {\tt haus}.

\end{compactitem}

Note that the German sentence does not have to be translated in
sequence. Here an example, where the English output is reordered:






\begin{SaveVerbatim}{myverb}
echo 'ein haus ist das' | moses -f phrase-model/moses.ini -t -weight-overwrite "Distortion0= 0"
\end{SaveVerbatim}
\begin{shaded}
\scriptsize
\UseVerbatim{myverb}
\end{shaded}

The output of this command is:






\begin{SaveVerbatim}{myverb}
this |3-3| is |2-2| a |0-0| house |1-1|
\end{SaveVerbatim}
\begin{shaded}
\small
\UseVerbatim{myverb}
\end{shaded}

\subsection{
\label{tutorial.texntoc4}Verbose}


Now for the next switch, {\tt -verbose} (short {\tt -v}), that displays additional run time information. The verbosity of the decoder output exists in three levels. The default is 1. Moving on to {\tt -v 2} gives additional statistics for each translated sentences:






\begin{SaveVerbatim}{myverb}
% echo 'das ist ein kleines haus' | moses -f phrase-model/moses.ini -v 2
[...]
TRANSLATING(1): das ist ein kleines haus
Total translation options: 12
Total translation options pruned: 0
\end{SaveVerbatim}
\begin{shaded}
\small
\UseVerbatim{myverb}
\end{shaded}

A short summary on how many translations options were used for the translation of these sentences. 






\begin{SaveVerbatim}{myverb}
Stack sizes: 1, 10, 2, 0, 0, 0
Stack sizes: 1, 10, 27, 6, 0, 0
Stack sizes: 1, 10, 27, 47, 6, 0
Stack sizes: 1, 10, 27, 47, 24, 1
Stack sizes: 1, 10, 27, 47, 24, 3
Stack sizes: 1, 10, 27, 47, 24, 3
\end{SaveVerbatim}
\begin{shaded}
\small
\UseVerbatim{myverb}
\end{shaded}

The stack sizes after each iteration of the stack decoder. An iteration is the processing of all hypotheses on one stack: After the first iteration (processing the initial empty hypothesis), 10 hypothesis that cover one German word are placed on stack 1, and 2 hypotheses that cover two foreign words are placed on stack 2. Note how this relates to the 12 translation options.






\begin{SaveVerbatim}{myverb}
total hypotheses generated = 453
number recombined = 69
number pruned = 0
number discarded early = 272
\end{SaveVerbatim}
\begin{shaded}
\small
\UseVerbatim{myverb}
\end{shaded}

During the beam search a large number of hypotheses are generated (453). Many are discarded early because they are deemed to be too bad (272), or pruned at some later stage (0), and some are recombined (69). The remainder survives on the stacks.






\begin{SaveVerbatim}{myverb}
total source words = 5
words deleted = 0 ()
words inserted = 0 ()
\end{SaveVerbatim}
\begin{shaded}
\small
\UseVerbatim{myverb}
\end{shaded}

Some additional information on word deletion and insertion, two advanced options that are not activated by default.






\begin{SaveVerbatim}{myverb}
BEST TRANSLATION: this is a small house [11111]  [total=-28.923] <<0.000, -5.000, 0.000, -27.091, -1.833
Sentence Decoding Time: : [4.000] seconds
\end{SaveVerbatim}
\begin{shaded}
\scriptsize
\UseVerbatim{myverb}
\end{shaded}

And finally, the translated sentence, its coverage vector (all 5 bits for the 5 German input words are set), its overall log-probability score, and the breakdown of the score into language model, reordering model, word penalty and translation model components.



Also, the sentence decoding time is given.



The most verbose output {\tt -v 3} provides even more information. In fact, it is so much, that we could not possibly fit it in this tutorial. Run the following command and enjoy:






\begin{SaveVerbatim}{myverb}
% echo 'das ist ein kleines haus' | moses -f phrase-model/moses.ini -v 3
\end{SaveVerbatim}
\begin{shaded}
\small
\UseVerbatim{myverb}
\end{shaded}

Let us look together at some highlights. The overall translation score is made up from several components. The decoder reports these components, in our case:






\begin{SaveVerbatim}{myverb}
The score component vector looks like this:
0 distortion score
1 word penalty
2 unknown word penalty
3 3-gram LM score, factor-type=0, file=lm/europarl.srilm.gz
4 Translation score, file=phrase-table
\end{SaveVerbatim}
\begin{shaded}
\small
\UseVerbatim{myverb}
\end{shaded}

Before decoding, the phrase
translation table is consulted for possible phrase translations.
For some phrases, we find entries, for others we find nothing.
Here an excerpt:






\begin{SaveVerbatim}{myverb}
[das ; 0-0]
the , pC=-0.916, c=-5.789
this , pC=-2.303, c=-8.002
it , pC=-2.303, c=-8.076

[das ist ; 0-1]
it is , pC=-1.609, c=-10.207
this is , pC=-0.223, c=-10.291

[ist ; 1-1]
is , pC=0.000, c=-4.922
's , pC=0.000, c=-6.116
\end{SaveVerbatim}
\begin{shaded}
\small
\UseVerbatim{myverb}
\end{shaded}

The pair of numbers next to a phrase is the coverage, {\tt pC} denotes the log of the phrase translation probability, after {\tt c} the future cost estimate for the phrase is given.



Future cost is an estimate of how hard it is to translate different parts of the sentence. After looking up phrase translation probabilities, future costs are computed for all contigous spans over the sentence:






\begin{SaveVerbatim}{myverb}
future cost from 0 to 0 is -5.789
future cost from 0 to 1 is -10.207
future cost from 0 to 2 is -15.722
future cost from 0 to 3 is -25.443
future cost from 0 to 4 is -34.709
future cost from 1 to 1 is -4.922
future cost from 1 to 2 is -10.437
future cost from 1 to 3 is -20.158
future cost from 1 to 4 is -29.425
future cost from 2 to 2 is -5.515
future cost from 2 to 3 is -15.236
future cost from 2 to 4 is -24.502
future cost from 3 to 3 is -9.721
future cost from 3 to 4 is -18.987
future cost from 4 to 4 is -9.266
\end{SaveVerbatim}
\begin{shaded}
\small
\UseVerbatim{myverb}
\end{shaded}

Some parts of the sentence are easier to translate than others. For instance the estimate for translating the first two words (0-1: {\tt das ist}) is deemed to be cheaper (-10.207) than the last two (3-4: {\tt kleines haus}, -18.987). Again, the negative numbers are log-probabilities.



After all this preperation, we start to create partial translations by translating a phrase at a time. The first hypothesis is generated by translating the first German word as {\tt the}:






\begin{SaveVerbatim}{myverb}
creating hypothesis 1 from 0 ( <s> )
base score 0.000
covering 0-0: das
translated as: the
score -2.951 + future cost -29.425 = -32.375
unweighted feature scores: <<0.000, -1.000, 0.000, -2.034, -0.916>>
added hyp to stack, best on stack, now size 1
\end{SaveVerbatim}
\begin{shaded}
\small
\UseVerbatim{myverb}
\end{shaded}

Here, starting with the empty initial hypothesis 0, a new hypothesis ({\tt id}={\tt 1}) is created. Starting from zero cost (base score), translating the phrase {\tt das} into {\tt the} carries translation cost (-0.916), distortion or reordering cost (0), language model cost (-2.034), and word penalty (-1). Recall that the score component information is printed out earlier, so we are able to interpret the vector.



Overall, a weighted log-probability cost of -2.951 is accumulated. Together with the future cost estimate for the remaining part of the sentence (-29.425), this hypothesis is assigned a score of -32.375.



And so it continues, for a total of 453 created hypothesis. At the end, the best scoring final hypothesis is found and the hypothesis graph traversed backwards to retrieve the best translation:






\begin{SaveVerbatim}{myverb}
Best path: 417 <= 285 <= 163 <= 5 <= 0
\end{SaveVerbatim}
\begin{shaded}
\small
\UseVerbatim{myverb}
\end{shaded}

Confused enough yet? Before we get caught too much in the intricate details of the inner workings of the decoder, let us return to actually using it. Much of what has just been said will become much clearer after reading the background (Section \ref{statmt.tex}) information.



\subsection{
\label{tutorial.texntoc5}Tuning for Quality}


The key to good translation performance is having a good phrase translation table. But some tuning can be done with the decoder. The most important is the tuning of the model parameters.



The probability cost that is assigned to a translation is a product of probability costs of four models: 

\begin{compactitem}
\item phrase translation table,

\item language model,

\item reordering model, and

\item word penalty.

\end{compactitem}

Each of these models contributes information over one aspect of the characteristics of a good translation:

\begin{compactitem}
\item The {\bf phrase translation} table ensures that the English phrases and the German phrases are good translations of each other.

\item The {\bf language model} ensures that the output is fluent English.

\item The {\bf distortion model} allows for reordering of the input sentence, but at a cost: The more reordering, the more expensive is the translation.

\item The {\bf word penalty} ensures that the translations do not get too long or too short.

\end{compactitem}

Each of the components can be given a weight that sets its importance. Mathematically, the cost of translation is:


\begin{equation} p(e|f) = \phi(f|e)^{\text{weight}_\phi} \times \text{LM}^{\text{weight}_\text{LM}} \times D(e,f)^{\text{weight}_d} \times W(e)^{\text{weight}_\phi} \end{equation}



The probability p(e$|$f) of the English translation e given the foreign input f is broken up into four models, phrase translation phi(f$|$e), language model LM(e), distortion model D(e,f), and word penalty W(e) = exp(length(e)). Each of the four models is weighted by a weight. 



The weighting is provided to the decoder with the four parameters {\tt weight-t},  {\tt weight-l}, {\tt weight-d}, and {\tt weight-w}. The default setting for these weights is 1, 1, 1, and 0. These are also the values in the configuration file {\tt moses.ini}.



Setting these weights to the right values can improve translation quality. We already sneaked in one example above. When translating the German sentence {\tt ein haus ist das}, we set the distortion weight to 0 to get the right translation:






\begin{SaveVerbatim}{myverb}
% echo 'ein haus ist das' | moses -f phrase-model/moses.ini -d 0
this is a house
\end{SaveVerbatim}
\begin{shaded}
\small
\UseVerbatim{myverb}
\end{shaded}

With the default weights, the translation comes out wrong:






\begin{SaveVerbatim}{myverb}
% echo 'ein haus ist das' | moses -f phrase-model/moses.ini
a house is the
\end{SaveVerbatim}
\begin{shaded}
\small
\UseVerbatim{myverb}
\end{shaded}

What is the right weight setting depends on the corpus and the language pair. Ususally, a held out development set is used to optimize the parameter settings. The simplest method here is to try out with a large number of possible settings, and pick what works best. Good values for the weights for phrase translation table ({\tt weight-t}, short {\tt tm}), language model ({\tt weight-l}, short {\tt lm}), and
reordering model ({\tt weight-d}, short {\tt d}) are 0.1-1, good values for the word penalty ({\tt weight-w}, short {\tt w}) are -3-3. Negative values for the word penalty favor longer output, positive values favor shorter output.



\subsection{
\label{tutorial.texntoc6}Tuning for Speed}


Let us now look at some additional parameters that help to speed
up the decoder. Unfortunately higher speed usually comes at cost of
translation quality. The speed-ups are achieved by limiting the search
space of the decoder. By cutting out part of the search space, we may
not be able to find the best translation anymore.



\subsubsection*{
\label{tutorial.texntoc7}Translation Table Size}


One strategy to limit the search space is by reducing the number of 
translation options used for each input phrase, i.e. the number of
phrase translation table entries that are retrieved. While in the toy
example, the translation tables are very small, these can have
thousands of entries per phrase in a realistic scenario. If the
phrase translation table is learned from real data, it contains a lot
of noise. So, we are really interested only in the most probable ones
and would like to elimiate the others.



The are two ways to limit the translation table size: by a fixed
limit on how many translation options are retrieved for each input
phrase, and by a probability threshold, that specifies that the phrase
translation probability has to be above some value.



Compare the statistics and the translation output for our toy model, when no
translation table limit is used






\begin{SaveVerbatim}{myverb}
% echo 'das ist ein kleines haus' | moses -f phrase-model/moses.ini -ttable-limit 0 -v 2
[...]
Total translation options: 12
[...]
total hypotheses generated = 453
number recombined = 69
number pruned = 0
number discarded early = 272
[...]
BEST TRANSLATION: this is a small house [11111]  [total=-28.923]
\end{SaveVerbatim}
\begin{shaded}
\small
\UseVerbatim{myverb}
\end{shaded}

with the statistics and translation output, when a limit of 1 is used






\begin{SaveVerbatim}{myverb}
% echo 'das ist ein kleines haus' | moses -f phrase-model/moses.ini -ttable-limit 1 -v 2
[...]
Total translation options: 6
[...]
total hypotheses generated = 127
number recombined = 8
number pruned = 0
number discarded early = 61
[...]
BEST TRANSLATION: it is a small house [11111]  [total=-30.327]
\end{SaveVerbatim}
\begin{shaded}
\small
\UseVerbatim{myverb}
\end{shaded}

Reducing the number of translation options to only one per phrase, had a
number of effects: (1) Overall only 6 translation options instead of
12 translation options were collected. (2) The number of generated
hypothesis fell to 127 from 442, and no hypotheses were pruned out.
(3) The translation changed, and the output now has lower log-probability: -30.327 vs. -28.923.



\subsubsection*{
\label{tutorial.texntoc8}Hypothesis Stack Size (Beam)}


A different way to reduce the search is to reduce the size of
hypothesis stacks. For each number of foreign words translated, 
the decoder keeps a stack of the best (partial) translations. 
By reducing this stack size the search will be quicker, since less
hypotheses are kept at each stage, and therefore less hypotheses are
generated. 
This is explained in more detail on the Background (Section \ref{statmt.tex}) page.



From a user perspective, search speed is linear to the maximum stack
size. Compare the following system runs with stack size 1000, 100 (the
default), 10, and 1:






\begin{SaveVerbatim}{myverb}
% echo 'das ist ein kleines haus' | moses -f phrase-model/moses.ini -v 2 -s 1000
[...]
total hypotheses generated = 453
number recombined = 69
number pruned = 0
number discarded early = 272
[...]
BEST TRANSLATION: this is a small house [11111]  [total=-28.923]

% echo 'das ist ein kleines haus' | moses -f phrase-model/moses.ini -v 2 -s 100
[...]
total hypotheses generated = 453
number recombined = 69
number pruned = 0
number discarded early = 272
[...]
BEST TRANSLATION: this is a small house [11111]  [total=-28.923]

% echo 'das ist ein kleines haus' | moses -f phrase-model/moses.ini -v 2 -s 10
[...]
total hypotheses generated = 208
number recombined = 23
number pruned = 42
number discarded early = 103
[...]
BEST TRANSLATION: this is a small house [11111]  [total=-28.923]

% echo 'das ist ein kleines haus' | moses -f phrase-model/moses.ini -v 2 -s 1
[...]
total hypotheses generated = 29
number recombined = 0
number pruned = 4
number discarded early = 19
[...]
BEST TRANSLATION: this is a little house [11111]  [total=-30.991]
\end{SaveVerbatim}
\begin{shaded}
\small
\UseVerbatim{myverb}
\end{shaded}

Note that the number of hypothesis entered on stacks is getting smaller with the stack size: 453, 453, 208, and 29. 



As we have previously described with translation table pruning, we may also want to use the relative scores of hypothesis for pruning instead of a fixed limit. The two strategies are also called histogram pruning and threshold pruning.



Here some experiments to show the effects of different stack size limits and beam size limits.






\begin{SaveVerbatim}{myverb}
% echo 'das ist ein kleines haus' | moses -f phrase-model/moses.ini -v 2 -s 100 -b 0
[...]
total hypotheses generated = 1073
number recombined = 720
number pruned = 73
number discarded early = 0
[...]

% echo 'das ist ein kleines haus' | moses -f phrase-model/moses.ini -v 2 -s 1000 -b 0
[...]
total hypotheses generated = 1352
number recombined = 985
number pruned = 0
number discarded early = 0
[...]

% echo 'das ist ein kleines haus' | moses -f phrase-model/moses.ini -v 2 -s 1000 -b 0.1
[...]
total hypotheses generated = 45
number recombined = 3
number pruned = 0
number discarded early = 32
[...]
\end{SaveVerbatim}
\begin{shaded}
\small
\UseVerbatim{myverb}
\end{shaded}

In the second example no pruning takes place, which means an exhaustive search is performed. With small stack sizes or small thresholds we risk search errors, meaning the generation of translations that score worse than the best translation according
to the model.



In this toy example, a worse translation is only generated with a stack size of 1. Again, by worse translation, we mean worse scoring according to our model (-30.991 vs. -28.923). If it is actually a worse translation in terms of translation quality, is another question. However, the task of the decoder is to find the best scoring translation. If worse scoring translations are of better quality, then this is a problem of the model, and should be resolved by better modeling. 



\subsection{
\label{tutorial.texntoc9}Limit on Distortion (Reordering)}


The basic reordering model implemented in the decoder is fairly weak. Reordering cost is measured by the number of words skipped when foreign phrases are picked out of order.



Total reordering cost is computed by D(e,f) = - $\text{$\Sigma$}_\text{i}$ (d\_i) where d for each phrase i is defined as d = abs( last word position of previously translated phrase + 1 - first word position of newly translated phrase ).



This is illustrated by the following graph:









\begin{center}
\includegraphics[scale=1]{images/reordering-model.png}
\end{center}




This reordering model is suitable for local reorderings: they are 
discouraged, but may occur with sufficient support from the language 
model. But large-scale reorderings are often arbitrary and 
effect translation performance negatively.



By limiting reordering, we can not only speed up the decoder,
often translation performance is increased. Reordering can be
limited to a maximum number of words skipped (maximum d)
with the switch {\tt -distortion-limit}, or short {\tt -dl}.



Setting this parameter to 0 means monotone translation (no reordering).
If you want to allow unlimited reordering, use the value -1.







\begin{center}\textit{\small Subsection last  modified on June 21, 2014, at 08:16 PM}\end{center}
