\documentclass[11pt]{article}
\usepackage{fullpage}
\usepackage{times}
\usepackage{latexsym}
\usepackage{epsf}
\usepackage{graphicx}
\usepackage{version}
 
\newcommand{\versionnumber}{5.40.01}
\includeversion{internal-version} 
\excludeversion{open-version} 

%\includeversion{open-version} 
%\excludeversion{internal-version} 

\begin{document}   

\title{IRST Language Modeling Toolkit \\ Version \versionnumber\\USER MANUAL}
			         
\author{M. Federico, N. Bertoldi, M. Cettolo\\FBK-irst, Trento, Italy}			       
\date{\today}
 
\maketitle
%% INTRODUCTION %%%%
\section{Introduction}

\begin{internal-version}
This manual illustrates the functionalities of  the IRST Language  Modeling (LM)  toolkit. It  should  
put you quickly  in  the condition of:
\begin{itemize}
\item extracting the dictionary from a corpus
\item extracting n-gram statistics from it
\item estimating n-gram LMs using different smoothing criteria
\item estimating and handling gigantic LMs
\item adapting a LM on specific application data
\item saving a  LM into a compact binary file
\item querying a LM through a command or script
\end{itemize}

\noindent
Among  state-of-the-art  $n$-gram  smoothing  techniques,  the  IRST LM toolkit (internal version) features LM  very efficient 
data structures to handle very large LMs and adaptation  methods which  can  be effective when limited task-related 
data are available. 
\end{internal-version}

The IRST Language Modeling Toolkit
\begin{internal-version}
(internal version)
\end{internal-version}
features algorithms and data structures suitable to estimate, 
store, and access very  large LMs.  Our software has been integrated into a popular open source 
SMT decoder  called {\tt Moses}\footnote{http://www.statmt.org/moses/}, and is compatible with LMs
created with other tools, such as the SRILM Tooolkit\footnote{http://www.speech.sri.com/projects/srilm}


\paragraph{Acknowledgments.}Users of this toolkit  might cite in their publications:
\begin{quote}
M. Federico,  N. Bertoldi,  M. Cettolo, {\em IRSTLM: an Open Source Toolkit for Handling Large Scale Language Models}, Proceedings of Interspeech, Brisbane, Australia, 2008.
\end{quote}

\noindent
References to introductory material on $n$-gram LMs are given in the appendix. 

%% GETTING STARTED %%%%

\section{Getting started}
\paragraph{Environment Settings}
Commands and scripts described in this manual are installed under the directories {\tt bin}
(and architecture-dependent subdirectories).
We assume that directory bin is included in your  {\tt PATH} environment variable.
You need also to set the environment variable {\tt IRSTLM} to the
path of this package. Data sets used in the examples can be 
found in the {\tt example} directory.

\paragraph{Examples}
\noindent
The  directory {\tt example} contains 
two English  text files, namely {\tt train.gz} and {\tt test}, which   we    will   use   to   estimate   
and    evaluate   our   LM, respectively.  In particular, LM evaluation computes both the perplexity and the 
out-of-vocabulary rate of the test set. Notice that both file are tokenized and contain 
one  sentence per line and sentence boundary symbols. Given a text file, 
sentence boundary symbols can be added in each line with the  script {\tt add-start-end.sh}:
\begin{verbatim}
$> add-start-end.sh < your-text-file 
\end{verbatim}


\begin{internal-version}
\paragraph{Training our first LM}
\noindent
We  are now ready to estimate a  3-gram (trigram)  LM by  running the command:

\begin{verbatim}
$> tlm -tr="gunzip -c train.gz" -n=3 -lm=wb -te=test
\end{verbatim}
\noindent
which produces the output:
\begin{verbatim}
n=49984 LP=301734.5406 PP= 418.4772517 OOVRate=0.05007602433
\end{verbatim}
\noindent
The output shows the number of  words in the test set, the LM log-probability, the LM perplexity  
and the out-of-vocabulary rate  of the test set.

\noindent
If you need  to train and test different language  models on the same data, a  more efficient 
way to  proceed is to first  create an $n$-gram table of the training data:
\begin{verbatim}
$> ngt -i="gunzip -c train.gz" -n=3 -o=train.www -b=yes
\end{verbatim}
\noindent
The command {\tt ngt} reads an  input text file, creates an  $n$-gram table of specified size ({\tt -n=3}), and 
saves it in binary format ({\tt -b=yes}) into a specified output file.

Now,  the  LM can  be  estimated and evaluation more quickly:
\begin{verbatim}
$> tlm -tr=train.www -n=3 -lm=wb -te=test
\end{verbatim}

\noindent
Once  estimated, a  LM can  be also saved in the standard ARPA text format:
\begin{verbatim}
$> tlm -tr=train.www -n=3 -lm=wb  -o=train.lm
\end{verbatim}

\noindent
(Remark: the  binary format formerly used by the IRST speech recognizer is still available, through the option
{\tt -oasr <filename>}, but is no more supported.)
\end{internal-version}

\begin{internal-version}
\section{More on ngt}
Given a text corpus we can compute its dictionary and word frequencies
with the command:

\begin{verbatim}
$> dict -i="gunzip -c train.gz" -o=train.dict -f=yes
\end{verbatim}


For speech recognition applications, it  can be often the case that we
want to limit the LM dictionary  only to the top frequent, let us say,
10K words. We can obtain such a list by:
\begin{small}
\begin{verbatim}
$> (echo dict; sort -rn +1 train.dict | cut -d" " -f1 | head -10000) > top10k
\end{verbatim}
\end{small}

\noindent
{\bf Notice}: the list will also include the start/end-sentence symbols. 

\noindent
A new  $n$-gram table for the  limited dictionary can  be computed with {\tt ngt} by specifying 
the sub-dictionary:
\begin{verbatim}
$> ngt -i=train.www -sd=top10k -n=3 -o=train.10k.www -b=yes
\end{verbatim}
The command  will replace  all words outside  top10K with  the special
out-of-vocabulary symbol {\tt \_unk\_}.

An other useful feature of ngt is the merging of two $n$-gram tables. Assume that we have 
split our training corpus into files  {\tt text-a} and file {\tt text-b} and have computed $n$-gram 
tables for both files, we can merge them with the option {\tt -aug}:
\begin{verbatim}
$> ngt -i=text-a.www -aug=text-b.www -n=3 -o=text.www -b=yes
\end{verbatim}
\end{internal-version}

%% MORE ON TLM %%%%
\begin{internal-version}
\section{More on tlm}
Language models have to  cope with out-of-vocabulary words, that is internally represented
with the word class  {\tt \_unk\_}.  In order  to
compare perplexity of LMs having  different vocabulary size it is better
to define  a conventional dictionary  size, or dictionary  upper bound
size,  trough the  parameter  ({\tt -dub}).  In  the  following example,  we
compare the perplexity of the full vocabulary LM against the perplexity of the
LM estimated over the more frequent 10K-words. In our comparison, we assume a dictionary 
upper bound of one million words.

\begin{verbatim}
$>tlm -tr=train.10k.www -n=3 -lm=wb -te=test -dub=1000000
  n=49984 LP=342099.6668 PP= 938.4067352 OOVRate=0.07648447503

$>tlm -tr=train.www -n=3 -lm=wb -te=test -dub=1000000
  n=49984 LP=336276.7867 PP= 835.2145141 OOVRate=0.05007602433
\end{verbatim}

\noindent
The  large  difference  in  perplexity  between the two LMs is   explained  by  the 
significantly higher  OOV rate of the 10K-word LM.

\noindent
N-gram LMs generally apply frequency smoothing techniques, and combine
smoothed frequencies according to  two main schemes: interpolation and
back-off.  For  historical reasons, this  toolkit assumes interpolation
as default.  The back-off  scheme is computationally more costly but
often provides better performance. It  can be activated with the option
{\tt -bo=yes}, e.g.:

\begin{verbatim}
$>tlm -tr=train.10k.www -n=3 -lm=wb -te=test -dub=1000000 -bo=yes
  n=49984 LP=337219.7008 PP= 851.1198162 OOVRate=0.07648447503
\end{verbatim}
This toolkit implements several frequency smoothing methods, which are
specified  by  the  parameter  {\tt -lm}.  Two  methods  are  particularly
recommended:
\begin{itemize}
\item [a)] {\bf Modified shift-beta}, also known as  "improved kneser-ney smoothing".  
This smoothing scheme gives top performance when training data is not 
very sparse but is more time and memory consuming during the estimation phase: 

\begin{verbatim}
$>tlm -tr=train.www -n=3 -lm=msb -te=test -dub=1000000 -bo=yes
  n=49984 LP=321877.3436 PP= 626.1610125 OOVRate=0.05007602433
\end{verbatim}

\item [b)] {\bf Witten Bell smoothing}. This is an excellent smoothing
   method which works well in every data condition and is much less time and memory consuming:

\begin{verbatim}
$> tlm -tr=train.www -n=3 -lm=wb -te=test -dub=1000000  -bo=yes
  n=49984 LP=331577.2305 PP= 760.2652481 OOVRate=0.05007602433
\end{verbatim}

\item [c)] {\bf Shift-beta smoothing}. This smoothing method is a simpler and cheaper version
of the Modified shift-beta method and works sometimes better than Witten-Bell method: 

\begin{verbatim}
$> tlm -tr=train.www -n=3 -lm=sb -te=test -dub=1000000  -bo=yes
  n=49984 LP=334724.5032 PP= 809.6750442 OVVRate=0.05007602433
\end{verbatim}

Moreover, the non linear smoothing parameter $\beta$ can be specified with the option {\tt -beta}:
\begin{verbatim}
$> tlm -tr=train.www -n=3 -lm=sb -beta=0.001 -te=test -dub=1000000  -bo=yes
  n=49984 LP=449339.8282 PP= 8019.836058 OVVRate=0.05007602433
\end{verbatim}
This could be helpful in case we need to uses language models with very limited frequency smoothing.

\end{itemize}
\subsection*{Limited Vocabulary}
\noindent
Using an  n-gram table  with a fixed  or limited  dictionary  will cause
some performance  degradation, as LM smoothing  statistics will result
slightly distorted. A  valid alternative is to estimate  the LM on the
full dictionary of the training corpus and to use a limited dictionary
just when  saving the  LM on a  file.  This  can be achieved  with the
option {\tt -d} (or {\tt -dictionary}):
\begin{verbatim}
$> tlm -tr=train.www -n=3 -lm=msb -bo=y -te=test -o=train.lm -d=top10k
\end{verbatim}
\end{internal-version}

%% LM ADAPTATION %%%%
\begin{internal-version}
\section{LM Adaptation}
Language model adaptation can be  applied when little training data is given for the 
task at hand, but much more data from other less related sources is available.  {\tt tlm} supports two adaptation methods.

\subsection{Minimum Discriminative Information Adaptation}
MDI adaptation  is used  when domain related  data is very  little but
enough to  estimate a  unigram LM.  Basically,  the n-gram probs  of a
general  purpose (background)  LM are  scaled so  that they  match the
target unigram distribution.
	
\noindent	 
Relevant parameters:
\begin{itemize}
\item {\tt -ar=value}: the adaptation {\tt rate},  a real number ranging 
 from 0 (=no adaptation) to 1(=strong adaptation).

\item {\tt -ad=file}: the  adaptation file,  either a text  or a
  unigram table.

\item {\tt -ao=y}: open vocabulary mode, which  must be set if the adaptation file
 might contain new words to be added to the basic dictionary.
\end{itemize}

\noindent
As an example, we apply MDI adaptation on the "adapt" file:
\begin{small}
\begin{verbatim}
$> tlm -tr=train.www -lm=wb -n=3 -te=test -dub=1000000 -ad=adapt -ar=0.8 -ao=yes
   n=49984 LP=308472.2281 PP= 478.8653332 OOVRate=0.02664852753
\end{verbatim}
\end{small}

\noindent
\paragraph{Important:}  modified shift-beta  smoothing  cannot  be applied  in  open
vocabulary mode  ({\tt -ao=yes}).  If  this is the  case, you  should either
change  smoothing method  or simply  add  the adaptation  text to  the
background LM (use {\tt -aug} parameter  of {\tt ngt}). This solution should in
general provide better performance.
\begin{small}
\begin{verbatim}
$> ngt -i=train.www -aug=adapt -o=train-adapt.www -n=3 -b=yes
$> tlm -tr=train-adapt.www -lm=msb -n=3 -te=test -dub=1000000 -ad=adapt -ar=0.8
  n=49984 LP=274018.328 PP= 240.3559234 OOVRate=0.02664852753
\end{verbatim}
\end{small}

\subsection{Mixture Adaptation}

\noindent
Mixture adaptation  is useful  when you have  enough training  data to
estimate a  bigram or  trigram LM and  you also have  data collections
from other domains.

\noindent
Relevant parameters:
\begin{itemize}
\item {\tt-lm=mix} : specifies mixture smoothing method
\item {\tt -slmi=<filename>}: specifies filename with information about LMs to combine.
\end{itemize}

\noindent
In the example directory, the file {\tt sublmi} contains the following lines:
\begin{verbatim}
2
slm=msb  -str=adapt -sp=0
slm=msb -str=train.www -sp=0
\end{verbatim}

\noindent
This means  that we use train a  mixture model on the  {\tt adapt} data set and
combine it  with the train data. For each data  set the desired
smoothing method is specified  (disregard the parameter {\tt -sp}). The file
used for adaptation is the one in FIRST position.

\begin{verbatim}
$> tlm -tr=train.www -lm=mix -slmi=sublm -n=3 -te=test -dub=1000000
  n=49984 LP=276121.2776 PP= 250.684028 OOVRate=0.02664852753
\end{verbatim}

\noindent
{\bf Important}: for  computational reasons it  is expected that  the $n$-gram
table  specified by {\tt -tr}  contains AT  LEAST the  $n$-grams of  the last
table specified in the slmi file, i.e. {\tt train.www} in  the example.
Faster computations are achieved by putting the largest dataset as the
last sub-model in the list and the union of all data sets as training
file.

\noindent
It is  also IMPORTANT  that a  large {\tt -dub} value  is specified  so that
probabilities  of  sub-LMs  can  be  correctly  computed  in  case  of
out-of-vocabulary words.
\end{internal-version}

%% ESTIMATING GIGANTIC LMs %%%%
\section{Estimating Gigantic LMs}
\label{sec:giganticLM}
LM estimation starts with the collection of n-grams and their frequency counters. Then, 
smoothing parameters are estimated for each n-gram level; infrequent n-grams are
possibly pruned and, finally, a LM file is created containing n-grams with probabilities and 
back-off weights.  This procedure can be very demanding in terms of memory and
time if it applied on huge corpora.   We provide here a way to split LM training  into smaller and independent steps, that can be easily distributed among independent processes. The  
procedure relies on a training scripts that makes little use of computer RAM and implements 
the  Witten-Bell smoothing method in an exact way.  

\noindent
Before starting, let us create a working directory under {\tt examples}, as many files will be created:

\begin{verbatim}
$> mkdir stat
\end{verbatim}

The script to generate the LM is:

\begin{verbatim}
> build-lm.sh -i "gunzip -c train.gz" -n 3  -o train.ilm.gz -k 5
\end{verbatim}
where the available options are:

\begin{verbatim}
-i    Input training file e.g. 'gunzip -c train.gz'
-o    Output gzipped LM, e.g. lm.gz
-k    Number of splits (default 5)
-n    Order of language model (default 3)
-t    Directory for temporary files (default ./stat)
-p    Prune singleton n-grams (default false)
-s    Smoothing: witten-bell (default), kneser-ney, improved-kneser-ney 
-b    Include sentence boundary n-grams (optional)
-d    Define subdictionary for n-grams (optional)
-v    Verbose
\end{verbatim}

\noindent
The script splits the estimation procedure into 5 distinct jobs, that are explained in
the following section. There are other options that can be used. We recommend for instance to use pruning of singletons to get smaller LM files. 
Notice that {\tt build-lm.sh} produces a LM file {\tt train.ilm.gz} that is NOT in the final ARPA format, but in
an intermediate format called {\tt iARPA}, that is recognized by the {\tt compile-lm} 
command and by the Moses SMT decoder running with IRSTLM. 
To convert the file into the standard ARPA format you can use the command:

\begin{verbatim}
> compile-lm train.ilm.gz --text yes train.lm 
\end{verbatim}
this will create the proper ARPA file {\tt lm-final}.
To create a gzipped file you might also use:
\begin{verbatim}
> compile-lm train.ilm.gz --text yes /dev/stdout | gzip -c > train.lm.gz
\end{verbatim}


\noindent
In the following sections, we will talk about LM file formats, compiling your LM into a 
more compact and efficient binary format, and about querying your LM.

\subsection{Estimating a LM with a Partial Dictionary}

We can extract the corpus dictionary  sorted by frequency with the command:
\begin{verbatim}
$> dict -i="gunzip -c train.gz" -o=dict -f=y -sort=no
\end{verbatim}

A sub-dictionary can be defined by just taking words occurring at least 5 times:
\begin{verbatim}
$> (echo DICTIONARY; tail +2 dict | awk '{if ($2>=5) print}') > sdict
\end{verbatim}

\noindent
The LM can be restricted to the defined sub-dictionary with the 
command {\tt build-lm.sh} by using the option {\tt -d}: 
\begin{verbatim}
> build-lm.sh -i "gunzip -c train.gz" -n 3  -o sublm.gz -k 5 -p -d sdict 
\end{verbatim}

\noindent
Notice that, all words outside the sub-dictionary will be mapped to the {\tt <unk>}
class, the probability of which will be directly estimated from the corpus statistics.
A preferable alternative to this approach is to estimate a large LM and then to filter
it according to a list of words (see Filtering a LM).

%%%% LM FORMATS %%%%%%%%%%%

\section{LM File Formats}
This toolkit supports three output format of LMs. These formats have the
purpose of permitting  the use of LMs by  external programs.  External
programs could in principle estimate the LM from an $n$-gram table before
using it, but this would take much more time and memory! So the best thing
to do is to first  estimate the LM, and then compile it into a binary format   
that is more compact and that can be quickly loaded and queried by the 
external program.


\subsection{ARPA Format}
This format was  introduced in DARPA ASR evaluations  to exchange LMs.
ARPA format  is also  supported by the  SRI LM  Toolkit. It is  a text
format which is rather costly in terms of memory. There is no limit to
the size $n$ of $n$-grams.

\subsection{qARPA Format}
This extends the ARPA format by including codebooks that quantize 
probabilities and back-off weights of each $n$-gram level. This format
is created through the command {\tt quantize-lm}.

\subsection{iARPA Format}
This is an intermediate ARPA format in the sense that each entry of the file
does not contain in the first position the full $n$-gram probability, but just its
smoothed frequency, i.e.:\\
\noindent
{\tt ...\\
f(z|x y) x y z bow(x y)\\
...
}

\noindent
This format is nevertheless properly managed by the {\tt compile-lm} command
in order to generate a binary version or a correct ARPA version.


\subsection{Binary Formats}
Both ARPA and qARPA formats can be converted into a binary format 
that allows for space savings on disk and a much quickers upload of
the LM file.  Binary versions can be created with the command 
{\tt compile-lm}, that produces files with  headers {\tt blmt} or {\tt Qblmt}.

%%%% LM QUANTIZATION & COMPILATION %%%%%
\section{LM Pruning}
Large LMs files can be pruned in a smart way by means of the command 
{\tt prune-lm} that removes $n$-grams for which resorting to the back-off 
results in a small loss. The syntax is as follows:
\begin{verbatim}
> prune-lm --threshold=1e-6,1e-6  train.lm.gz  train.plm
\end{verbatim}
Thresholds for each n-gram level, up from 2-grams, are based on empirical 
evidence. Threshold zero results in no pruning. If less thresholds are specified,
the right most is applied to the higher levels. Hence, in the above example we
could have just specified one threshold, namely {\tt --threshold=1e-6}. 
The effect of pruning is shown in the following messages of {\tt prune-lm}:

\begin{verbatim}
1-grams: reading 15059 entries
2-grams: reading 142684 entries
3-grams: reading 293685 entries
done
OOV code is 15058
OOV code is 15058
pruning LM with thresholds: 
 1e-06 1e-06
savetxt: train.lm.plm
save: 15059 1-grams
save: 135967 2-grams
save: 185127 3-grams
\end{verbatim}

The saved LM table {\tt train.plm}  contains about 5\% less bigrams, and 37\%  
less trigrams!
Notice that the output of prune-lm is an ARPA LM file, while the input can be 
either an ARPA or binary LM. Notice that quantization must be eventually 
performed after pruning! In order to measure the loss in accuracy introduced
by pruning, perplexity of the resulting LM can per computed (see below).

\section{LM Quantization}
A language model file in ARPA  format, created with the IRST LM toolkit or
with other tools, can be quantized and stored in a compact data structure, 
called language model table.  Quantization can be performed by the command:

\begin{verbatim}
$> quantize-lm  train.lm train.qlm
\end{verbatim}

\noindent
which  generates   the  quantized  version  {\tt train.qlm} that  encodes all probabilities and back-off 
weights in 8 bits. The  output is a  modified ARPA format, called qARPA. Notice that quantized
LMs reduce memory consumptions at the cost of some loss in performance. Moreover, probabilities
of quantized LMs are not supposed to be properly normalized!

\section{LM Compilation}
LMs in ARPA, iARPA, and qARPA format can be stored in a compact binary table through the command:

\begin{verbatim}
$> compile-lm train.lm tran.blm
\end{verbatim}

\noindent
which generates the binary file {\tt train.blm} that can be quickly loaded in memory.  If the LM
is really very large, {\tt compile-lm} can avoid to create the binary LM directly in memory through the 
option {\tt -memmap 1}, which exploits the {\em Memory Mapping} mechanism in order to work as 
much as possible on disk rather than in RAM. \\

\begin{verbatim}
$> compile-lm --memmap 1 train.lm tran.blm
\end{verbatim}

\noindent
This option clearly pays a fee  in terms of speed, but  is often the only way to proceed. It is also recommended 
that the hard disk for the LM storage belongs to the computer on which the compilation is performed.

\noindent
Notice that most of the functionalities of {\tt compile-lm} (see below) apply to binary and quantized models. 

\noindent
It is possible to change the standard directory ("/tmp") used for temporary computation through the parameter "--tmpdir".
\begin{verbatim}
$> compile-lm --tmodir=<mytmpdir> train.lm tran.blm
\end{verbatim}
For huge LMs the emporary files created for compilaion can dramatically grows. In the case the system tmp directory can be too small for such LM, hence it is mandatory to set a new directory to avoid a "disk full" system error.


\section{Filtering a LM}
A large LM can be filtered according to a word list through the command:

\begin{verbatim}
$> compile-lm  train.lm -d list filtered.lm
\end{verbatim}
The resulting LM will only contain n-grams inside the provided list of words,
with the exception of the 1-gram level, which by default is preserved identical
to the original LM. This behavior can be changed by setting the option 
{\tt --keepunigrams no}.  LM filtering can be useful once very large LMs can
be specialized in advance to work on a particular portion of language.
\noindent
If the original LM is in binary format and is very large, {\tt compile-lm} can avoid to load it in memory,
through the memory mapping option {\tt -memmap 1}.







%%%% LM INTERFACE %%%%%%%%%
\section{LM Interface}
LMs are useful when they can be queried through another application in order to compute 
perplexity scores or n-gram probabilities. IRSTLM provides two possible interfaces: 
\begin{itemize}
\item at the command level, through  {\tt compile-lm}
\item at the c++ library level, mainly through methods of the class {\tt lmtable}
\end{itemize}

\noindent
In the following, we will only focus on the command level interface. Details about
the c++ library interface will be provided in a future version of this manual.  

\subsection{Perplexity Computation}
\begin{internal-version}
Assume we have estimated and saved the following LM:

\begin{verbatim}
$> tlm -tr=train.www -n=3 -lm=wb -te=test -o=train.lm -ps=no
 n=49984 LP=308057.0419 PP= 474.9041687 OOVRate=0.05007602433
\end{verbatim}
\end{internal-version}

\noindent
To compute the perplexity directly from the LM on disk, we can use the command:

\begin{verbatim}
$> compile-lm train.lm  --eval=test
   Nw=49984 PP=1064.40 PPwp=589.50 Nbo=39847 Noov=2503 OOV=5.01%
\end{verbatim}
Notice that {\tt PPwp} reports the contribution of OOV words to the perplexity. Each OOV word is indeed penalized by dividing the
LM probability of the {\tt unk} word by  the quantity


\centerline{{\tt DictionaryUpperBound} - {\tt SizeOfDictionary}}

\noindent
The OOV penalty can be modify by changing the {\tt DictionaryUpperBound} with the parameter {\tt --dub} (whose default value is set to $10^7$). \\

\noindent
The perplexity of the pruned LM can be computed with the command:
\begin{verbatim}
compile-lm train.plm --eval test --dub 10000000
Nw=49984 PP=1019.57 PPwp=564.67 Nbo=42671 Noov=2503 OOV=5.01%
\end{verbatim}
Interestingly, a slightly better value is obtained which could be explained by the 
fact that pruning has removed many unfrequent trigrams and has redistributed 
their probabilities over more frequent bigrams.

\begin{internal-version}
\noindent
Notice that {\tt PPwp} reports the perplexity with a fixed dictionary upper-bound of 10 million words. Indeed:
\begin{verbatim}
> tlm -tr=train.www -n=3 -lm=wb -te=test -o=train.lm -ps=no -dub=10000000 
 n=49984 LP=348396.8634 PP= 1064.401259 OOVRate=0.05007602433
\end{verbatim}
\end{internal-version}
\bigskip
\noindent
Again, if the LM is in binary format and is very large, {\tt compile-lm} can avoid to load it in memory,
through the memory mapping option {\tt -memmap 1}.

\subsection{Probability Computations}
We can compute as well log-probabilities word-by-word  from standard input with the command:

\begin{verbatim}
$> compile-lm train.lm --score yes < test

> </s>  1 p= NULL
> </s> <s>      1 p= NULL
> </s> <s> <unk>        1 p= -6.130331e+00 bo= 2
> <s> <unk> of  1 p= -3.530050e+00 bo= 2
> <unk> of the  1 p= -1.250671e+00 bo= 1
> of the senate 1 p= -8.805695e+00 bo= 0
> the senate (  1 p= -6.150410e+00 bo= 2
> senate ( <unk>   1 p= -5.547798e+00 bo= 2
....
....
\end{verbatim}

\noindent
the commands reports the currently observed n-gram, 
including {\tt\_unk\_} words, a dummy
constant frequency 1, the log-probability of the n-gram, and the 
number of back-offs performed by the LM.  

\noindent
Finally, tracing information with the {\tt --eval }  option are shown by setting 
debug levels from 1 to 4 ({\tt --debug}):
\begin{itemize}
\item [1] reports the back-off level for each word
\item [2] adds the log-prob 
\item [3] adds the back-off weight
\item [4] check if probabilities sum up to 1.
\end{itemize}

%%%% LM INTERPOLATION %%%%%%%%%
\section{LM Interpolation}
We provide a convenient tool to estimate mixtures of LMs that have been already 
created in one of the available formats.  The tool permits to estimate interpolation
weights through the EM algorithm, to compute the perplexity, and to query the interpolated
LM. Interpolated LMs are simply defined by a configuration file in the following format:
\begin{verbatim}
3
0.3 lm-file1
0.3 lm-file2
0.4 lm-file3
\end{verbatim}

\noindent
The first number indicates the number of LMs to be interpolated, then each LM is specified
by its weight and its file (either in ARPA or binary format). Notice that you can interpolate
LMs with different orders!\\

\noindent
Given an initial configuration file {\tt lmlist.start} (with arbitrary weights), new weights can be estimated
through Expectation-Maximization on some text sample {\tt text-file} by running the command:
[lm-list-file.out]
\begin{verbatim}
> interpolate-lm lmlist.start --learn text-file  lmlist.final
\end{verbatim}
New weights will be written in the updated configuration file {\tt lmlist.final}. The full list of options is: 
\begin{verbatim}
--learn text-file   learn optimal interpolation for text-file
--order n           order of n-grams used in --learn (optional)
--eval text-file    compute perplexity on text-file
--dub dict-size     dictionary upper bound (default 10^7)
--score [yes|no]    compute log-probs of n-grams from stdin
--debug [1-3]       verbose output for --eval option (see compile-lm)
--memmap 1          use memory map to read a binary LM
\end{verbatim}
 
\noindent
Interpolated LMs can be queried through the option {\tt --score}, similarly to {\tt compile-lm}. 

\bigskip
\noindent
If there are binary LMs in the list,  {\tt interpolate-lm} can avoid to load them in memory through the memory 
mapping option {\tt -memmap 1}.

 
%%%% PARALLEL COMPUTATION %%%%%%%%%
\section{Parallel Computation}
This package provides facilities to build a gigantic LM in parallel in order to reduce computation time.
The script implementing this feature is based on the {\tt SUN Grid Engine} software\footnote{http://www.sun.com/software/gridware}.

\noindent
To apply the parallel computation run the following script (instead of {\tt build-lm.sh}):

\begin{verbatim}
> build-lm-qsub.sh -i "gunzip -c train.gz" -n 3  -o train.ilm.gz -k 5
\end{verbatim}
Besides the options of {\tt build-lm.sh}, parameters for the SGE manager can be provided through the following one:

\begin{verbatim}
   -q      parameters for qsub, e.g. "-q <queue>", "-l <resources>"
\end{verbatim}

\noindent
The script performs the same {\em split-and merge} policy described in Section~\ref{sec:giganticLM}, but some computation is performed in parallel (instead of sequentially) distributing the tasks on several machines.


\appendix


\section{Reference Material}
The following books contain basic introductions to statistical language modeling:
\begin{itemize}
\item {\em Spoken Dialogues with Computers}, by Renato DeMori, chapter 7.
\item {\em Speech  and Language Processing},  by Dan  Jurafsky and  Jim Martin, chapter 6.
\item {\em Foundations   of  Statistical   Natural  Language   Processing},  by C. Manning and H. Schuetze.
\item {\em Statistical Methods for Speech Recognition}, by Frederick Jelinek.
\item {\em Spoken Language Processing}, by Huang, Acero and Hon.
\end{itemize}

\begin{internal-version}
The following papers describe the IRST LM toolkit:
\begin{itemize}

\item Efficient data structures to handle huge language models:
\begin{quote}
Marcello Federico and Mauro Cettolo, {\em Efficient Handling of N-gram Language Models for Statistical Machine Translation}, In Proc. of the Second Workshop on Statistical Machine Translation, pp. 88--95, ACL, Prague, Czech Republic, 2007.
\end{quote}

\item Language Model quantization:
\begin{quote}
Marcello Federico and Nicola Bertoldi, {\em How Many Bits Are Needed To Store Probabilities for Phrase-Based Translation?}, In Proc. of the Workshop on Statistical Machine Translation. pp. 94-101, NAACL, New York City, NY, 2006. 
\end{quote}


\item Language Model adaptation with mixtures:
\begin{quote}
Marcello Federico and Nicola Bertoldi, {\em Broadcast news LM adaptation over time}, Computer Speech and Language. 18(4): pp. 417-435, October, 2004.
\end{quote}
\item Language Model adaptation with MDI:
\begin{quote}
Marcello Federico, {\em Efficient LM Adaptation through MDI Estimation}. In Proc. of Eurospeech, Budapest, Hungary, 1999.
\end{quote}
\end{itemize}
\end{internal-version}

\section{Release Notes}

\subsection{Version 3.2}
\begin{itemize}
\item Quantization of probabilities
\item Efficient run-time data structure for LM querying 
\item Dismissal of MT output format
\end{itemize}

\subsection{Version 4.2}
\begin{itemize}
\item Distinction between open source and internal Irstlm tools
\item More memory efficient versions of binarization and quantization commands
\item Memory mapping of run-time LM
\item Scripts and data structures for the estimation and handling of gigantic LMs 
\item Integration of IRSTLM into Moses Decoder
\end{itemize}

\subsection{Version 5.00}
\begin{itemize}
\item Fixed bug in the documentation 
\item General script {\tt build-lm.sh} for the estimation of large LMs.
\item Management of iARPA file format.
\item Bug fixes
\item Estimation of LM over a partial dictionary.
\end{itemize}


\subsection{Version 5.04}
\begin{itemize}
\begin{internal-version}
\item Extended documentation with ShiftBeta smoothing. 
\item Smoothing parameter of ShiftBeta can be set manually.
\item Robust handling for smoothing parameters of ModifiedShiftBeta.
\item Fixed probability checks in TLM.
\end{internal-version}
\item Parallel estimation of gigantic LM through SGE
\item Better management of sub dictionary with build-lm.sh   
\item Minor bug fixes
\end{itemize}

\subsection{Version 5.05}
\begin{itemize}
\item (Optional) computation of OOV penalty in terms of single OOV word instead of OOV class
\item Extended use of OOV penalty to the standard input LM scores of compile-lm. 
\item Minor bug fixes
\end{itemize}

\subsection{Version 5.10}
\begin{itemize}
\item Extended ngt to compute statistics for approximated Kneser-Ney smoothing
\item New implementation of approximated Kneser-Ney smoothing method
\item Minor bug fixes
\item More to be added here ....
\end{itemize}

\subsection{Version 5.20}
\begin{itemize}
\item Improved tracing of back-offs
\item Added command prune-lm  (thanks to Fabio Brugnara)
\item Extended lprob function to supply back-off weight/level information
\item Improved back-off handling of OOV words with quantized LM
\item Added more debug modalities to compile-lm
\item Fixed minor bugs in regression tests
\item Updated documentation
\end{itemize}

\subsection{Version 5.21}
\begin{itemize}
\item Addition of interpolate-lm 
\item Added LM filtering to compile-lm
\item Improved regression tests
\item Integration of interpolated LMs in Moses
\item Extended tests on compilers and platforms
\item Improved documentation with website
\end{itemize}

\subsection{Version 5.22}
\begin{itemize}
\item Use of AutoConf/AutoMake toolkit compilation and installation
\end{itemize}

\subsection{Version 5.30}
\begin{itemize}
\item Support for a safe management of LMs with a total amount of $n$-grams larger than 250 million
\item Use of a new parameter to specify a directory for temporary computation because the default ("/tmp") could be too small
\item Improved a safer method of concatenation of gzipped sub lms
\item Improved management of log files
\end{itemize}

\subsection{Version 5.40}
\begin{itemize}
\item Merging of internal-only tlm code into the public version
\item Updated documentation into the public version
\item Included documentation into the public version
\end{itemize}



\end{document}
