



\section{
\label{advanced-ruletables.tex}
Efficient Phrase and Rule Storage}


\subsection{
\label{advanced-ruletables.texntoc1}\label{advanced-ruletables.texBinaryPhraseTable}Binary Phrase Tables with On-demand Loading}


For larger tasks the phrase tables usually become huge, typically too large to fit into memory. Therefore, Moses supports a binary phrase table with on-demand loading, i.e. only the part of the phrase table that is required to translate a sentence is loaded into memory.



There are currently 3 binary formats to do this: 

\begin{compactitem}
\item OnDisk phrase-table. Works with SCFG models and phrase-based models.

\item <del>Binary phrase-table. Works with phrase-based models only.</del>

\item Compact phrase-table. Works with phrase-based models only (may be extended in the near future). Small and fast. Described below.

\end{compactitem}

\subsubsection*{
\label{advanced-ruletables.texntoc2}On-Disk Phrase table}


This phrase-table can be used for both phrase-based models and hierarchical models. (It can be used for fully syntax models too, but is likely to be very slow).



You first need to convert the rule table into a binary prefix format. This is done with the command {\tt CreateOnDiskPt}:






\begin{SaveVerbatim}{myverb}
CreateOnDiskPt [#source factors] [#target factors] [#scores] [ttable-limit]  \  
[index of p(e|f) (usually 2)] [input text pt] [output directory]
\end{SaveVerbatim}
\begin{shaded}
\small
\UseVerbatim{myverb}
\end{shaded}

e.g. 

\begin{SaveVerbatim}{myverb}
~/CreateOnDiskPt 1 1 4 100 2 phrase-table.1.gz phrase-table.1.folder
\end{SaveVerbatim}
\begin{shaded}
\small
\UseVerbatim{myverb}
\end{shaded}

This will create a directory, {\tt phrase-table.1.folder}, with the following files:

\begin{SaveVerbatim}{myverb}
Misc.dat
Source.dat
TargetColl.dat
TargetInd.dat
Vocab.dat
\end{SaveVerbatim}
\begin{shaded}
\small
\UseVerbatim{myverb}
\end{shaded}

The configuration file {\tt moses.ini} should also be changed so that the binary files is used instead of the text file. You should change it from:

\begin{SaveVerbatim}{myverb}
[feature]
PhraseDictionaryMemory path=phrase-table.1.gz ....
\end{SaveVerbatim}
\begin{shaded}
\small
\UseVerbatim{myverb}
\end{shaded}

to 

\begin{SaveVerbatim}{myverb}
[feature]
PhraseDictionaryOnDisk path=phrase-table.1.folder ....
\end{SaveVerbatim}
\begin{shaded}
\small
\UseVerbatim{myverb}
\end{shaded}

\subsection{
\label{advanced-ruletables.texntoc3}\label{advanced-ruletables.texCompactPhraseTable}Compact Phrase Table}


A compact phrase table implementation is available that is around 6 to 7 times smaller and than the original binary phrase table. It can be used in-memory and for on-demand loading. Like the original phrase table, this can only be used for phrase-based models. If you use this or the compact lexical reordering table below, please cite:






\begin{compactitem}
\item Marcin Junczys-Dowmunt: {\bf Phrasal Rank-Encoding: Exploiting Phrase Redundancy and Translational Relations for Phrase Table Compression\footnote{\sf http://ufal.mff.cuni.cz/pbml/98/art-junczys-dowmunt.pdf}}, Proceedings of the Machine Translation Marathon 2012, The Prague Bulletin of Mathematical Linguistics, vol. 98, pp. 63-74, 2012. 

\end{compactitem}

Download the CMPH library from {\sf http://sourceforge.net/projects/cmph/} and install according to the included instructions. Make sure the installation target directory contains an "include" and a "lib" directory. Next you need to recompile Moses with






\begin{SaveVerbatim}{myverb}
./bjam --with-cmph=/path/to/cmph
\end{SaveVerbatim}
\begin{shaded}
\small
\UseVerbatim{myverb}
\end{shaded}

Now, you can convert the standard ASCII phrase tables into the compact format. {\bf Phrase tables are required to be sorted as above. For a maximal compression effect, it is advised to generate a phrase table with phrase-internal word alignment} (this is the default). If you want to compress a phrase table without alignment information, rather use {\tt -encoding None} (see advanced options below). It is possible to use the default encoding (PREnc) without alignment information, but it will take much longer. For now, there may be problems to compact phrase tables on 32-bit systems since virtual memory usage quickly exceeds the 3 GB barrier.   



Here is an example (standard phrase table phrase-table, with 4 scores) which produces a single file {\tt phrase-table.minphr}:






\begin{SaveVerbatim}{myverb}
mosesdecoder/bin/processPhraseTableMin -in phrase-table.gz -out phrase-table -nscores 4 -threads 4
\end{SaveVerbatim}
\begin{shaded}
\scriptsize
\UseVerbatim{myverb}
\end{shaded}

In the Moses config file, specify the WHOLE file name of the phrase table:

\begin{SaveVerbatim}{myverb}
[feature]
PhraseDictionaryCompact path=phrase-table.minphr ...
\end{SaveVerbatim}
\begin{shaded}
\small
\UseVerbatim{myverb}
\end{shaded}

\noindent \ovalbox{\parbox{155mm}{{\bf Options}:

\begin{compactitem}
\item {\tt -in  string}         -{}- input table file name

\item {\tt -out string}         -{}- prefix of binary table file

\item {\tt -nscores int}        -{}- number of score components in phrase table

\item {\tt -no-alignment-info}  -{}- do not include alignment info in the binary phrase table

\item {\tt -threads int}        -{}- number of threads used for conversion

\item {\tt -T string}           -{}- path to custom temporary directory

\end{compactitem}}}

As for the original phrase table, the option {\tt -no-alignment-info} omits phrase internal alignment information in the phrase table and should also be used if you provide a phrase table without alignment information in the phrase table. Also if no alignment data is given in the phrase table you should use {\tt -encoding None} (see below), since the default compression method assumes that alignment information is present.  



Since compression is quite processor-heavy, it is advised to use the {\tt -threads} option to increase speed. 



{\bf Advanced options}: Default settings should be fine for most of your needs, but the size of the phrase table can be tuned to your specific needs with the help of the advanced options.



\noindent \ovalbox{\parbox{155mm}{{\bf Options}:

\begin{compactitem}
\item {\tt -encoding string}  -{}- encoding type: PREnc REnc None (default PREnc)

\item {\tt -rankscore int}    -{}- score index of P(t$|$s) (default 2)

\item {\tt -maxrank int}      -{}- maximum rank for PREnc (default 100)

\item {\tt -landmark int}     -{}- use landmark phrase every 2\^n source phrases (default 10)

\item {\tt -fingerprint int}  -{}- number of bits used for source phrase fingerprints (default 16)

\item {\tt -join-scores}      -{}- single set of Huffman codes for score components

\item {\tt -quantize int}     -{}- maximum number of scores per score component

\item {\tt -no-warnings}      -{}- suppress warnings about missing alignment data

\end{compactitem}}}

{\bf Encoding methods}: There are two encoding types that can be used on-top the standard compression methods, Phrasal Rank-Encoding ({\tt PREnc}) and word-based Rank Encoding ({\tt REnc}). PREnc (see Junczys-Dowmunt (MT Marathon 2012)\footnote{\sf http://ufal.mff.cuni.cz/pbml/98/art-junczys-dowmunt.pdf} for details) is used by default and requires a phrase table with phrase-internal alignment to reach its full potential. {\tt PREnc} can also work without explicit alignment information, but encoding is slower and the resulting file will be bigger, but smaller than without {\tt PREnc}. The tool will warn you about every line that misses alignment information if you use {\tt PREnc} or {\tt REnc}. These warnings can be suppressed with {\tt -no-warnings}. If you use {\tt PREnc} with non-standard scores you should specify which score type is used for sorting with {\tt -rankscore int}. By default this is P(t$|$s) which in the standard phrase table is the third score (index 2).



Basically with PREnc around, there is no reason to use {\tt REnc} unless you really want to. It requires the lexical translation table {\tt lex.f2e} to be present in the same directory as the text version phrase table. If no alignment information is available it falls back to None (See Junczys-Dowmunt (EAMT 2012)\footnote{\sf http://hltshare.fbk.eu/EAMT2012/html/Papers/57.pdf} for details on {\tt REnc} and {\tt None}).



{\tt None} is the fasted encoding method, but produces the biggest files. Concerning translation speed, there is virtually no difference between the  encoding methods when the phrase tables are later used with Moses, but smaller files result in lesser memory-usage, especially if the phrase tables are loaded entirely in-memory.



{\bf Indexing options}: The properties of the source phrase index can be modified with the {\tt -landmark} and {\tt -fingerprint} options, changing these options can affect file size and translation quality, so do it carefully. Junczys-Dowmunt (TSD 2012)\footnote{\sf http://www.staff.amu.edu.pl/\textasciitilde{}junczys/dokuwiki/lib/exe/fetch.php?cache=\&media=wiki:mjd2012tsd1.pdf} contains a discussion of these values and their effects.  



{\bf Scores and quantization}: You can reduce the file size even more by using score quantization. E.g. with {\tt -quantize 1000000}, a phrase table is generated that uses at most one million different scores for each score type. Be careful, low values will affect translation quality. By default, each score type is encoded with an own set of Huffman codes, with the {\tt -join-scores} option only one set is used. If this option is combined with {\tt -quantize N}, the summed number of different scores for all scores types will not exceed {\tt N}. 



{\bf In-memory loading}: You can start Moses with the option {\tt -minphr-memory} to load the compact phrase table directly into memory at start up. Without this option, on-demand loading is used by default.



\subsection{
\label{advanced-ruletables.texntoc4}\label{advanced-ruletables.texCompactReorderingTable}Compact Lexical Reordering Table}


The compact lexical reordering table produces files about 12 to 15 times smaller than the original Moses binary implementation. As for the compact phrase table you need to install CMPH and link against it. {\bf Reordering tables must be sorted in the same way as the phrase tables above.} The command below produces a single file {\tt reordering-table.minlexr}. 






\begin{SaveVerbatim}{myverb}
mosesdecoder/bin/processLexicalTableMin -in reordering-table.gz -out reordering-table -threads 4
\end{SaveVerbatim}
\begin{shaded}
\scriptsize
\UseVerbatim{myverb}
\end{shaded}

If you include the prefix in the Moses config file, the compact reordering table will be recognized and loaded automatically. You can start Moses with the option {\tt -minlexr-memory} to load the compact lexical reordering table directly into memory at start up.



{\bf Options:} See the compact phrase table above for a description of available common options. 



\subsection{
\label{advanced-ruletables.texntoc5}Pruning the Translation Table}


The translation table contains all phrase pairs found in the parallel corpus, which includes a lot of noise. To reduce the noise, recent work by Johnson et al. has suggested to prune out unlikely phrase pairs. For more detail, please refer to the paper:



H. Johnson, J. Martin, G. Foster and R. Kuhn. (2007) '''Improving Translation
Quality by Discarding Most of the Phrasetable'''. In Proceedings of the 2007
Joint Conference on Empirical Methods in Natural Language Processing and
Computational Natural Language Learning (EMNLP-CoNLL), pp. 967-975.



\subsubsection*{
\label{advanced-ruletables.texntoc6}Build Instructions}


Moses includes a re-implementation of this method in the directory {\tt contrib/sigtest-filter}. You first need to build it from the source files.



This implementation relies on Joy Zhang's. The source code can be download from github\footnote{\sf https://github.com/moses-smt/salm}. Joy's original code is here\footnote{\sf http://projectile.sv.cmu.edu/research/public/tools/salm/salm.htm\#update}.

\begin{compactenum}\item download and extract the SALM source release.

\item in {\tt SALM/Distribution/Linux} type: {\tt make}

\item enter the directory {\tt contrib/sigtest-filter} in the main Moses distribution directory

\item type make {\tt SALMDIR=/path/to/SALM}

\end{compactenum}
\subsubsection*{
\label{advanced-ruletables.texntoc7}Usage Instructions}


Using the {\tt SALM/Bin/Linux/Index/IndexSA.O32}, create a suffix array index of the source and target sides of your training bitext ({\tt SOURCE}, {\tt TARGET}).

\begin{SaveVerbatim}{myverb}
% SALM/Bin/Linux/Index/IndexSA.O32 TARGET
% SALM/Bin/Linux/Index/IndexSA.O32 SOURCE
\end{SaveVerbatim}
\begin{shaded}
\small
\UseVerbatim{myverb}
\end{shaded}

Prune the phrase table:

\begin{SaveVerbatim}{myverb}
% cat phrase-table | ./filter-pt -e TARGET -f SOURCE -l FILTER-VALUE > phrase-table.pruned
\end{SaveVerbatim}
\begin{shaded}
\scriptsize
\UseVerbatim{myverb}
\end{shaded}

{\tt FILTER-VALUE} is the -log prob threshold described in Johnson et al. (2007)'s paper.  It may be either {\tt 'a+e'}, {\tt 'a-e'}, or a positive real value. Run with no options to see more use-cases. A good setting is {\tt -l a+e -n 30}, which also keeps only the top 30 phrase translations for each source phrase, based on p(e$|$f).



If you filter an hierarchical model, add the switch {\tt -h}.



\subsubsection*{
\label{advanced-ruletables.texntoc8}Using the EMS}


To use this method in {\tt experiment.perl}, you will have to add two settings in the {\tt TRAINING} section:






\begin{SaveVerbatim}{myverb}
salm-index = /path/to/project/salm/Bin/Linux/Index/IndexSA.O64
sigtest-filter = "-l a+e -n 50"
\end{SaveVerbatim}
\begin{shaded}
\small
\UseVerbatim{myverb}
\end{shaded}

The setting {\tt salm-index} points to the binary to build the suffix array, and {\tt sigtest-filter} contains the options for filtering (excluding {\tt -e}, {\tt -f}, {\tt -h}). EMS detects automatically, if you filter a phrase-based or hierarchical model and if a reordering model is used.



\subsection{
\label{advanced-ruletables.texntoc9}Pruning the Phrase Table based on Relative Entropy}


While the pruning method in Johnson et al. (2007)\footnote{\sf http://www.aclweb.org/anthology/D/D07/D07-1103.pdf} is designed to remove spurious phrase pairs due to noisy data, it is also possible to remove phrase pairs that are redundant. That is, phrase pairs that can be composed by smaller phrase pairs in the model with similar probabilities. For more detail please refer to the following papers:



Ling, W., Gra�a, J., Trancoso, I., and Black, A. (2012). Entropy-based Pruning for Phrase-based
Machine Translation. In Proceedings of the 2012
Joint Conference on Empirical Methods in Natural Language Processing and
Computational Natural Language Learning (EMNLP-CoNLL), pp. 962-971.



Zens, R., Stanton, D., Xu, P. (2012). A Systematic Comparison of Phrase Table Pruning Technique. 
In Proceedings of the 2012 Joint Conference on Empirical Methods in Natural Language Processing and
Computational Natural Language Learning (EMNLP-CoNLL), pp. 972-983.



The code from Ling et al. (2012)'s paper is available at {\tt contrib/relent-filter}.



{\bf Update} The code in contrib/relent-filter no longer works with the current version of Moses. To compile it, use an older version of Moses with this command:

\begin{SaveVerbatim}{myverb}
git checkout RELEASE-0.91
\end{SaveVerbatim}
\begin{shaded}
\small
\UseVerbatim{myverb}
\end{shaded}

\subsubsection*{
\label{advanced-ruletables.texntoc10}Build Instructions}


The binaries for Relative Entropy-based Pruning are built automatically with Moses. However, this implementation also calculates the significance scores (Johnson et al., 2007)\footnote{\sf http://www.aclweb.org/anthology/D/D07/D07-1103.pdf}, using a slightly modified version of the code by Chris Dyer, which is in {\tt contrib/relent-filter/sigtest-filter}. This must be built using the same procedure:






\begin{compactenum}\item Download and build SALM available here\footnote{\sf http://projectile.sv.cmu.edu/research/public/tools/salm/salm.htm\#update}

\item Run "make {\tt SALMDIR=/path/to/SALM}" in "{\tt contrib/relent-filter/sigtest-filter}" to create the executable filter-pt

\end{compactenum}
\subsubsection*{
\label{advanced-ruletables.texntoc11}Usage Instructions}


Checklist of required files (I will use $<$varname$>$ to refer to these vars):

\begin{compactenum}\item s\_train - source training file

\item t\_train - target training file

\item moses\_ini - path to the Moses configuration file ( after tuning )

\item pruning\_binaries - path to the relent pruning binaries ( should be "{\tt bin}" if no changes were made )

\item pruning\_scripts - path to the relent pruning scripts ( should be "{\tt contrib/relent-filter/scripts}" if no changes were made )

\item sigbin - path to the sigtest filter binaries ( should be "{\tt contrib/relent-filter/sigtest-filter}" if no changes were made )

\item output\_dir - path to write the output

\end{compactenum}
Build suffix arrays for the source and target parallel training data






\begin{SaveVerbatim}{myverb}
% SALM/Bin/Linux/Index/IndexSA.O32 <s_train>
% SALM/Bin/Linux/Index/IndexSA.O32 <t_train>
\end{SaveVerbatim}
\begin{shaded}
\small
\UseVerbatim{myverb}
\end{shaded}

Calculate phrase pair scores by running:






\begin{SaveVerbatim}{myverb}
% perl <pruning_scripts>/calcPruningScores.pl -moses_ini <moses_ini> \
-training_s <s_train> -training_t <t_train> \
-prune_bin <pruning_binaries> -prune_scripts <pruning_scripts> \
-moses_scripts <path_to_moses>/scripts/training/ \
-workdir <output_dir> -dec_size 10000
\end{SaveVerbatim}
\begin{shaded}
\small
\UseVerbatim{myverb}
\end{shaded}

This will create the following files in the $<$output\_dir$>$/scores/ dir:






\begin{compactenum}\item count.txt - counts of the phrase pairs for N(s,t) N(s,*) and N(*,t)

\item divergence.txt - negative log of the divergence of the phrase pair

\item empirical.txt - empirical distribution of the phrase pairs N(s,t)/N(*,*)

\item rel\_ent.txt - relative entropy of the phrase pairs

\item significance.txt - significance of the phrase pairs

\end{compactenum}
You can use any one of these files for pruning and also combine these scores using  the script {\tt $<$pruning\_scripts$>$/interpolateScores.pl}.



To actually prune a phrase table, run {\tt $<$pruning\_scripts$>$/prunePT.pl}, this will prune phrase pairs based on the score file that is used. This script will prune the phrase pairs with lower scores first.



For instance, to prune 30\% of the phrase table using relative entropy run:

\begin{SaveVerbatim}{myverb}
% perl <pruning_scripts>/prunePT.pl -table <phrase_table_file> \
-scores <output_dir>/scores/rel_ent.txt -percentage 70 > <pruned_phrase_table_file>
\end{SaveVerbatim}
\begin{shaded}
\small
\UseVerbatim{myverb}
\end{shaded}

You can also prune by threshold

\begin{SaveVerbatim}{myverb}
% perl <pruning_scripts>/prunePT.pl -table <phrase_table_file> \
-scores <output_dir>/scores/rel_ent.txt -threshold 0.1 > <pruned_phrase_table_file>
\end{SaveVerbatim}
\begin{shaded}
\small
\UseVerbatim{myverb}
\end{shaded}

The same must be done for the reordering table by replacing {\tt $<$phrase\_table\_file$>$} with the {\tt $<$reord\_table\_file$>$}

\begin{SaveVerbatim}{myverb}
% perl <pruning_scripts>/prunePT.pl -table <reord_table_file> \
-scores <output_dir>/scores/rel_ent.txt -percentage 70 > <pruned_reord_table_file>
\end{SaveVerbatim}
\begin{shaded}
\small
\UseVerbatim{myverb}
\end{shaded}

\subsubsection*{
\label{advanced-ruletables.texntoc12}Parallelization }


The script {\tt $<$pruning\_scripts$>$/calcPruningScores.pl} requires the forced decoding of the whole set of phrase pairs in the phrase table, so unless it is used for a small corpora, it usually requires large amounts of time to process.
Thus, we recommend users to run multiple instances of {\tt $<$pruning\_scripts$>$/calcPruningScores.pl} in parallel to process different parts of the phrase table.



To do this, run:






\begin{SaveVerbatim}{myverb}
% perl <pruning_scripts>/calcPruningScores.pl -moses_ini <moses_ini> \
-training_s <s_train> -training_t <t_train> \
-prune_bin <pruning_binaries> -prune_scripts <pruning_scripts> \
-moses_scripts <path_to_moses>/scripts/training/ \
-workdir <output_dir> -dec_size 10000 -start 0 -end 100000
\end{SaveVerbatim}
\begin{shaded}
\small
\UseVerbatim{myverb}
\end{shaded}

The {\tt -start} and {\tt -end} options tell the script to only calculate the results for phrase pairs between 0 and 99999.



Thus, an example of a shell script to run for the whole phrase table would be:






\begin{SaveVerbatim}{myverb}
size=`wc <phrase_table_file> | gawk '{print $1}'`
phrases_per_process=100000

for i in $(seq 0 $phrases_per_process $size)
do
end=`expr $i + $phrases_per_process`
perl <pruning_scripts>/calcPruningScores.pl -moses_ini <moses_ini> \
-training_s <s_train> -training_t <t_train> \
-prune_bin <pruning_binaries> -prune_scripts <pruning_scripts> \
-moses_scripts <path_to_moses>/scripts/training/ 
-workdir <output_dir>.$i-$end -dec_size 10000 -start $i -end $end
done
\end{SaveVerbatim}
\begin{shaded}
\small
\UseVerbatim{myverb}
\end{shaded}

After all processes finish, simply join the partial score files together in the same order.



\subsection{
\label{advanced-ruletables.texntoc13}Pruning Rules based on Low Scores}


Rules can be also removed simply because some of their scores are too low. This can be done at the time of the phrase table creation. 






\begin{SaveVerbatim}{myverb}
train-model.perl [...]  \ 
-score-options="-MinScore FIELD1:THRESHOLD2[,FIELD2:THRESHOLD2[,FIELD3:THRESHOLD3]]"
\end{SaveVerbatim}
\begin{shaded}
\small
\UseVerbatim{myverb}
\end{shaded}

where {\tt FIELDn} is the position of the score (typically 2 for the direct phrase probability p(e$|$f), or 0 for the indirect phrase probability p(f$|$e)) and {\tt THRESHOLD} the maximum probability allowed. A good setting is {\tt 2:0.0001}, which removes all rules, where the direct phrase translation probability is below 0.0001.



In EMS, this can be specified in the {\tt TRAINING:score-settings} setting, for instance

\begin{SaveVerbatim}{myverb}
score-settings = "--MinScore 2:0.0001"
\end{SaveVerbatim}
\begin{shaded}
\small
\UseVerbatim{myverb}
\end{shaded}










\begin{center}\textit{\small Subsection last  modified on March 11, 2015, at 05:39 PM}\end{center}
