<commit_before>% TODO:
% * List the feature functions that we use in our decoder.

\documentclass[11pt]{article}
\usepackage{acl08}
\usepackage{times}
\usepackage{latexsym}
\usepackage{multirow}
\usepackage{clrscode}
\usepackage{amscd}
\usepackage{amsmath}
\usepackage{amssymb}
\usepackage{color}
\usepackage{epsfig}
\usepackage{float}
\usepackage{subfigure}
\usepackage{url}
\newcommand{\ignore}[1]{}



\title{Joshua: An Open Source Toolkit for Parsing-based Machine Translation}

\author{
<NAME>,\,\,\,
<NAME>,\,\,\, %add a footnote to mention that CCB is the project leader
<NAME>,$^\dagger$\,\,\,
<NAME>,$^+$\,\,\,
<NAME>,\,\,\, \\
{\bf <NAME>,$^\star$\,\,\,
<NAME>.\,G.\,Thornton,\,\,\,
<NAME>,\,\,\,
{\textnormal{ and}}\,\,\,<NAME>}\\
Center for Language and Speech Processing, Johns Hopkins University, Baltimore, MD\\
$\dagger$ Computational Linguistics and Information Processing Lab, University of Maryland, College Park, MD\\
$+$ Human Language Technology and Pattern Recognition group, RWTH Aachen University, Germany\\
$\star$ Natural Language Processing Lab, University of Minnesota, Minneapolis, MN }


\date{}

\begin{document}

\maketitle


\begin{abstract}
We describe \textbf{Joshua}, an open source toolkit for statistical machine translation.  Joshua implements all of the algorithms required for synchronous context free grammars (SCFGs): chart-parsing, $n$-gram language model integration, beam- and cube-pruning, and $k$-best extraction. The toolkit also implements suffix-array grammar extraction and minimum error rate training. It uses parallel and distributed computing techniques for scalability. We demonstrate that the toolkit achieves state of the art translation performance on the WMT09 French-English translation task.

\end{abstract}


\section{Introduction}
Large scale parsing-based statistical machine translation (e.g., \newcite{Chiang2007}, \newcite{Quirk2005}, \newcite{Galley2006}, and \newcite{Liu2006}) has made remarkable progress in the last few years.
However, most of the systems mentioned above employ tailor-made, dedicated software that is not open source.  This results in a high barrier to entry for other researchers, and makes experiments difficult to duplicate and compare.
In this paper, we describe \textbf{Joshua}, a general-purpose open source toolkit for parsing-based machine translation, serving the same role as Moses \cite{Moses} does for regular phrase-based machine translation.

Our toolkit is written in Java and implements all the essential algorithms described in \newcite{Chiang2007}: chart-parsing, $n$-gram language model integration, beam- and cube-pruning, and $k$-best extraction.  The toolkit also implements suffix-array grammar extraction \cite{Lopez2007} and minimum error rate training \cite{Och2003c}. Additionally, parallel and distributed computing techniques are exploited to make it scalable \cite{Li2008b}. We have also made great effort to ensure that our toolkit is easy to use and to extend.

The toolkit has been used to translate roughly a million sentences in a parallel corpus for large-scale discriminative training experiments \cite{Li2008}.
%The decoder has also been successfully used by other researchers. For example, \newcite{sg-boxing} have demonstrated that our decoder achieves performance competitive with Moses \cite{Moses}.
We hope the release of the toolkit will greatly contribute the progress of the syntax-based machine translation research.\footnote{The toolkit can be downloaded at \url{http://www.sourceforge.net/projects/joshua}, and the instructions in using the toolkit are at \url{http://cs.jhu.edu/~ccb/joshua}.}



\section{Joshua Toolkit}
When designing our toolkit,  we applied general principles of software engineering to achieve three major goals: \emph{extendibility}, \emph{end-to-end coherence}, and \emph{scalability}.

\textbf{Extendibility:} The Joshua code is organized into separate \emph{packages} for each major aspect of functionality. In this way it is clear which files contribute to a given functionality and researchers can focus on a single package without worrying about the rest of the system. Moreover, to minimize the problems of unintended interactions and unseen dependencies, which is common hinderance to extensibility in large projects, all extensible components are defined by Java \emph{interfaces}. Where there is a clear point of departure for research, a basic implementation of each interface is provided as an \emph{abstract class} to minimize the work necessary for new extensions.

\textbf{End-to-end Cohesion:} There are many components to a machine translation pipeline. One of the great difficulties with current MT pipelines is that these diverse components are often designed by separate groups and have different file format and interaction requirements. This leads to a large investment in scripts to convert formats and connect the different components, and often leads to untenable and non-portable projects as well as hindering repeatability of experiments.
To combat these issues, the Joshua toolkit integrates most critical components of the machine translation pipeline. Moreover, each component can be treated as a stand-alone tool and does not rely on the rest of the toolkit we provide.

\textbf{Scalability}: Our third design goal was to ensure that the decoder is scalable to large models and data sets. The parsing and pruning algorithms are carefully implemented with dynamic programming strategies, and efficient data structures are used to minimize overhead. Other techniques contributing to scalability includes suffix-array grammar extraction, parallel and distributed decoding, and bloom filter language models.

Below we give a short description about the main functions implemented in our Joshua toolkit.

\subsection{Training Corpus Sub-sampling}\label{subsampling} 

Rather than inducing a grammar from the full parallel training data, we made use of a method proposed by <NAME> (personal communication) to select the subset of the training data consisting of  sentences useful for inducing a grammar to translate a particular test set.  This method works as follows: for the development and test sets that will be translated, every $n$-gram (up to length 10) is gathered into a map $\mathcal{W}$ and associated with an initial count of zero.  Proceeding in order through the training data, for each sentence pair whose source-to-target length ratio is within one standard deviation of the average, if any $n$-gram found in the \emph{source sentence} is also found in $\mathcal{W}$ with a count of less than $k$, the sentence is selected.  When a sentence is selected, the count of every $n$-gram in $\mathcal{W}$ that is found in the source sentence is incremented by the number of its occurrences in the source sentence. \ignore{Thus, there are two conditions in which a sentence will not be selected: 1) it only contains $n$-grams that are not found in $\mathcal{W}$ (making it useless for learning in the highly lexicalized models we use) or 2) it only contains $n$-grams that have already been attested in the selected set $k$ or more times.} For our submission, we used $k=20$, which resulted in 1.5 million (out of 23 million) sentence pairs being selected for use as training data.  There were 30,037,600 English words and 30,083,927 French words in the subsampled training corpus. 

\subsection{Suffix-array Grammar Extraction}

Hierarchical phrase-based translation requires a translation grammar extracted from a parallel corpus, where grammar rules include associated feature values. In real translation tasks, the grammars extracted from large training corpora are often far too large to fit into available memory.

% Features such as the translation probability $p(f|e)$ and reverse translation probability $p(e|f)$ are typically calculated using relative frequency estimation . 
In such tasks, feature calculation is also very expensive in terms of time required; huge sets of extracted rules must be sorted in two directions for relative frequency calculation of such features as the translation probability $p(f|e)$ and reverse translation probability $p(e|f)$ \cite{Koehn2003}. Since the extraction steps must be re-run if any change is made to the input training data, the time required can be a major hindrance to researchers, especially those investigating the effects of tokenization or word segmentation.

%Worse, the grammars extracted from large training corpora are often far too large to fit into available memory.

To alleviate these issues, we extract only a subset of all available rules. Specifically, we follow \newcite{Callison-Burch2005b,Lopez2007} and use a source language suffix array to extract only those rules which will actually be used in translating a particular set of test sentences. This results in a vastly smaller rule set than techniques which extract all rules from the training set.

The current code requires suffix array rule extraction to be run as a pre-processing step to extract the rules needed to translate a particular test set. However, we are currently extending the decoder to directly access the suffix array. This will allow the decoder at runtime to efficiently extract exactly those rules needed to translate a particular sentence, without the need for a rule extraction pre-processing step.

% which will be allow the decoder to extract a sub-set of rules

%
%Worse, the extracted grammars

% to extract all allowed rules from a large parallel corpus, and to 

%When rule extraction is performed over an entire large parallel corpus, 

%With large training corpora, a substantial amount of processing time is required to extract all rules and to per

%Traditional phrase-based and hierarchical translation approaches require a translation grammar extracted from a parallel corpus, where grammar rules include associated feature values. Features such as the translation probability $p(f|e)$ and reverse translation probability $p(e|f)$ are typically calculated using relative frequency estimation \cite{Koehn2003}. 

%Lane: please extend this paragraph

%Suffix-array Translation Grammar ExtractionSuffix-array Translation Grammar ExtractionSuffix-array Translation Grammar ExtractionSuffix-array Translation Grammar ExtractionSuffix-array Translation Grammar ExtractionSuffix-array Translation Grammar ExtractionSuffix-array Translation Grammar ExtractionSuffix-array Translation Grammar ExtractionSuffix-array Translation Grammar ExtractionSuffix-array Translation Grammar ExtractionSuffix-array Translation Grammar ExtractionSuffix-array Translation Grammar ExtractionSuffix-array Translation Grammar ExtractionSuffix-array Translation Grammar ExtractionSuffix-array Translation Grammar ExtractionSuffix-array Translation Grammar ExtractionSuffix-array Translation Grammar ExtractionSuffix-array Translation Grammar ExtractionSuffix-array Translation Grammar ExtractionSuffix-array Translation Grammar ExtractionSuffix-array Translation Grammar

\subsection{Decoding Algorithms\footnote{More details on the decoding algorithms are provided in \cite{Li-PBML}.}}

\textbf{Grammar formalism:} Our decoder assumes a probabilistic synchronous context-free grammar (SCFG). Currently, it only handles SCFGs of the kind extracted by Heiro \cite{Chiang2007}, but is easily extensible to more general SCFGs (e.g., \cite{Galley2006}) and closely related formalisms like synchronous tree substitution grammars \cite{Eisner2003}.


\textbf{Chart parsing:} Given a source sentence to decode, the decoder generates a one-best or $k$-best translations using a CKY algorithm. Specifically,
the decoding algorithm  maintains a \emph{chart}, which contains an array of \emph{cells}. Each cell in turn maintains a list of proven \emph{items}. The parsing process starts with the axioms, and proceeds by applying the inference rules repeatedly to prove new items until proving a goal item. Whenever the parser proves a new item, it adds the item to the appropriate chart cell. The item also maintains backpointers to antecedent items, which are used for $k$-best extraction.

\textbf{Pruning:} Severe pruning is needed in order to make the decoding computationally feasible for SCFGs with large target-language vocabularies. In our decoder, we incorporate two pruning techniques: beam and cube pruning \cite{Chiang2007}.

\textbf{Hypergraphs and $k$-best extraction:}
For each source-language sentence, the chart-parsing algorithm produces a \emph{hypergraph}, which represents an exponential set of likely derivation hypotheses. Using the $k$-best extraction algorithm \cite{Huang2005}, we extract the $k$ most likely derivations from the hypergraph.

\textbf{Parallel and distributed decoding:}
We also implement \emph{parallel decoding} and a \emph{distributed language model} by exploiting multi-core and multi-processor architectures and distributed computing techniques. More details on these two features are provided by \newcite{Li2008b}.

\subsection{Language Models}
%Jonny: please check the bloom filter LM part
In addition to the distributed LM mentioned above, we implement three local $n$-gram language models. Specifically, we first provide a straightforward implementation of the $n$-gram scoring function in Java. This Java implementation is able to read the standard ARPA backoff $n$-gram models, and thus the decoder can be used independently from the SRILM toolkit.\footnote{This feature allows users to easily try the Joshua toolkit without installing the SRILM toolkit and compiling the native bridge code. However, users should note that the basic Java LM implementation is not as scalable as the native bridge code.} We also provide a native code bridge that allows the decoder to use the SRILM toolkit to read and score $n$-grams. This native implementation is more scalable than the basic Java LM implementation. We have also implemented a Bloom Filter LM in Joshua, following \newcite{Talbot2007a}.

\subsection{Minimum Error Rate Training}

Johsua's MERT module optimizes parameter weights so as to maximize performance on a development set as measuered by an automatic evaluation metric, such as Bleu. The optimization consists of a series of line-optimizations along the dimensions corresponding to the parameters. The search across a dimension uses the efficient method of \newcite{Och2003c}. Each iteration of our MERT implementation consists of multiple weight updates, each reflecting a greedy selection of the dimension giving the most gain. Each iteration also optimizes several random ``intermediate initial'' points in addition to the one surviving from the previous iteration, as an approximation to performing multiple random restarts. More details on the MERT method and the implementation can be found in \newcite{Zaidan2009forwmt}.\footnote{The module is also available as a standalone application, {\em Z-MERT}, that can be used with other MT systems. (Software and documentation at: \url{http://cs.jhu.edu/~ozaidan/zmert.html}.)}



\section{WMT-09 Translation Task Results}
%In this section, we report results on the WMT-09 French-English translation task.
\subsection{Training and Dev Data}

We assembled a very large French-English training corpus  \cite{billion-word-parallel-corpus} by conducting a web crawl that targted bilingual web sites from the Canadian government, the European Union, and various international organizations like the Amnesty International and the Olympic Committee.  The crawl gathered approximately 40 million files, consisting of over 1TB of data.  We converted pdf, doc, html, asp, php, etc. files into text, and preserved the directory structure of the web crawl.  We wrote set of simple heuristics to transform French URLs onto English URLs, and considered matching documents to be translations of each other.  This yielded 2 million French documents paired with their English equivalents.  We split the sentences and paragraphs in these documents, performed sentence-aligned them using software that IBM Model 1 probabilities into account \cite{Moore2002}.   We filtered and de-duplcated the resulting parallel corpus.  After discarding 630 thousand sentence pairs which had more than 100 words, our final corpus had 21.9 million sentence pairs with 587,867,024 English words and 714,137,609 French words.  

We distributed the corpus to the other WMT09 participants to use in addition to the Europarl v4 French-English parallel corpus \cite{Koehn-europarl}, which consists of approximately 1.4 million sentence pairs with 39 million English words and 44 million French words.  Our translation model was trained on these corpora using the subsampling descried in Section \ref{subsampling}.  

For language model training, we used the monolingual news and blog data that was assembled by the University of Edinburgh and distributed as part of WMT09.  This data consisted of 21.2 million English sentences with half a billion words.  We used SRILM to train a 5-gram language model using a vocabulary containing the 500,000 most frequent words in this corpus.  Note that we did not use the English side of the parallel corpus as language model training data.

To tune the system parameters we used News Test Set from WMT08 \cite{Callison-Burch2008a}, which consists of 2,051 sentence pairs with 43 thousand English words and 46 thousand French words.  This is in-domain data that was gathered from the same news sources as the WMT09 test set.

\subsection{Translation Scores}
The translation scores for four different systems are reported in Table \ref{results-wmt09}.\footnote{Note that the implementation of the novel techniques used to produce the non-baseline results is not part of the current Joshua release, though we plan to incorporate it in the next release.}


\textbf{Baseline: } In this system, we use the GIZA++ toolkit \cite{Och2003}, a suffix-array architecture \cite{Lopez2007}, the SRILM toolkit \cite{Stolcke2002}, and minimum error rate training \cite{Och2003c} to obtain word-alignments, a translation model, language models, and the optimal weights for combining these models, respectively.


\textbf{Minimum Bayes Risk Rescoring: } In this system, we re-ranked the n-best output of our baseline system using Minimum Bayes Risk \cite{Kumar2004b}.  We re-score the top 300 translations to minimize expected loss under the Bleu metric.

\textbf{Deterministic Annealing: } In this system, instead of using the regular MERT \cite{Och2003c} whose training objective is to minimize the one-best error, we use the deterministic annealing training procedure described in \newcite{Smith2006}, whose objective is to minimize the \emph{expected} error (together with the entropy regularization technique).

\textbf{Variational Decoding: }  A hierarchical machine translation system like Hiero exhibits \emph{spurious ambiguity}, a situation where the system
produces many distinct derivation \emph{trees} that yield the same translation \emph{string}.\footnote{A regular phrase-based system also has spurious ambiguity due to different ways of segmenting the translation output.} However, no tractable extraction algorithm is available to marginalize over derivations during decoding time. Therefore, most systems simply approximate the goodness of a translation string by using the goodness of its most-probable derivation. Instead, we have developed a novel approximation algorithm, using a \emph{variational principle}, to approximate the sum.
More details will be provided in \newcite{Li2009}. In this system, we have used both deterministic annealing (for training) and variational decoding (for decoding).



\begin{table}[t]
\begin{center}
\begin{tabular}{c c}\hline
System & BLEU-4 \\ \hline
Joshua Baseline & 25.92 \\
Minimum Bayes Risk Rescoring & 26.16 \\
Deterministic Annealing & 25.98 \\
Variational Decoding & {\bf 26.52} \\ \hline
\end{tabular}
\end{center}
\caption{The uncased BLEU scores on WMT-09 French-English Task.  The test set consists of 2525 segments, each with one reference translation.}
\label{results-wmt09}
\end{table}

\section{Conclusions}

We have described a scalable toolkit for parsing-based machine translation. It is written in Java and implements all the essential algorithms described in \newcite{Chiang2007} and \newcite{Li2008b}: chart-parsing, $n$-gram language model integration, beam- and cube-pruning, and $k$-best extraction.
The toolkit also implements suffix-array grammar extraction \cite{Callison-Burch2005b,Lopez2007} and minimum error rate training \cite{Och2003c}. Additionally, parallel and distributed computing techniques are exploited to make it scalable. The decoder achieves state of the art translation performance.



%%%lzf add this section

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\section*{Acknowledgments}
This research was supported in part by the Defense Advanced Research Projects Agency's GALE program under Contract No.\,HR0011-06-2-0001 and the National Science Foundation under grants No.\,0713448 and 0840112. The views and findings are the authors' alone.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\bibliographystyle{acl}
\bibliography{../bibliography}
\end{document} 
<commit_msg>Fixed comma and spacing before Omar's name in list of authors. Uppercased 'group' for Aachen. Made 'Dev' into 'Development' for section title, since it's cleaner and doesn't cost any extra space.<commit_after>% TODO:
% * List the feature functions that we use in our decoder.

\documentclass[11pt]{article}
\usepackage{acl08}
\usepackage{times}
\usepackage{latexsym}
\usepackage{multirow}
\usepackage{clrscode}
\usepackage{amscd}
\usepackage{amsmath}
\usepackage{amssymb}
\usepackage{color}
\usepackage{epsfig}
\usepackage{float}
\usepackage{subfigure}
\usepackage{url}
\newcommand{\ignore}[1]{}



\title{Joshua: An Open Source Toolkit for Parsing-based Machine Translation}

\author{
<NAME>,\,\,\,
<NAME>,\,\,\, %add a footnote to mention that CCB is the project leader
<NAME>,$^\dagger$\,\,\,
<NAME>,$^+$\,\,\,
<NAME>,\,\,\, \\
{\bf <NAME>,$^\star$\,\,\,
<NAME>.\,G.\,Thornton,\,\,\,
<NAME>\,\,
{\textnormal{and}}\,\,\,<NAME>}\\
Center for Language and Speech Processing, Johns Hopkins University, Baltimore, MD\\
$\dagger$ Computational Linguistics and Information Processing Lab, University of Maryland, College Park, MD\\
$+$ Human Language Technology and Pattern Recognition Group, RWTH Aachen University, Germany\\
$\star$ Natural Language Processing Lab, University of Minnesota, Minneapolis, MN }


\date{}

\begin{document}

\maketitle


\begin{abstract}
We describe \textbf{Joshua}, an open source toolkit for statistical machine translation.  Joshua implements all of the algorithms required for synchronous context free grammars (SCFGs): chart-parsing, $n$-gram language model integration, beam- and cube-pruning, and $k$-best extraction. The toolkit also implements suffix-array grammar extraction and minimum error rate training. It uses parallel and distributed computing techniques for scalability. We demonstrate that the toolkit achieves state of the art translation performance on the WMT09 French-English translation task.

\end{abstract}


\section{Introduction}
Large scale parsing-based statistical machine translation (e.g., \newcite{Chiang2007}, \newcite{Quirk2005}, \newcite{Galley2006}, and \newcite{Liu2006}) has made remarkable progress in the last few years.
However, most of the systems mentioned above employ tailor-made, dedicated software that is not open source.  This results in a high barrier to entry for other researchers, and makes experiments difficult to duplicate and compare.
In this paper, we describe \textbf{Joshua}, a general-purpose open source toolkit for parsing-based machine translation, serving the same role as Moses \cite{Moses} does for regular phrase-based machine translation.

Our toolkit is written in Java and implements all the essential algorithms described in \newcite{Chiang2007}: chart-parsing, $n$-gram language model integration, beam- and cube-pruning, and $k$-best extraction.  The toolkit also implements suffix-array grammar extraction \cite{Lopez2007} and minimum error rate training \cite{Och2003c}. Additionally, parallel and distributed computing techniques are exploited to make it scalable \cite{Li2008b}. We have also made great effort to ensure that our toolkit is easy to use and to extend.

The toolkit has been used to translate roughly a million sentences in a parallel corpus for large-scale discriminative training experiments \cite{Li2008}.
%The decoder has also been successfully used by other researchers. For example, \newcite{sg-boxing} have demonstrated that our decoder achieves performance competitive with Moses \cite{Moses}.
We hope the release of the toolkit will greatly contribute the progress of the syntax-based machine translation research.\footnote{The toolkit can be downloaded at \url{http://www.sourceforge.net/projects/joshua}, and the instructions in using the toolkit are at \url{http://cs.jhu.edu/~ccb/joshua}.}



\section{Joshua Toolkit}
When designing our toolkit,  we applied general principles of software engineering to achieve three major goals: \emph{extendibility}, \emph{end-to-end coherence}, and \emph{scalability}.

\textbf{Extendibility:} The Joshua code is organized into separate \emph{packages} for each major aspect of functionality. In this way it is clear which files contribute to a given functionality and researchers can focus on a single package without worrying about the rest of the system. Moreover, to minimize the problems of unintended interactions and unseen dependencies, which is common hinderance to extensibility in large projects, all extensible components are defined by Java \emph{interfaces}. Where there is a clear point of departure for research, a basic implementation of each interface is provided as an \emph{abstract class} to minimize the work necessary for new extensions.

\textbf{End-to-end Cohesion:} There are many components to a machine translation pipeline. One of the great difficulties with current MT pipelines is that these diverse components are often designed by separate groups and have different file format and interaction requirements. This leads to a large investment in scripts to convert formats and connect the different components, and often leads to untenable and non-portable projects as well as hindering repeatability of experiments.
To combat these issues, the Joshua toolkit integrates most critical components of the machine translation pipeline. Moreover, each component can be treated as a stand-alone tool and does not rely on the rest of the toolkit we provide.

\textbf{Scalability}: Our third design goal was to ensure that the decoder is scalable to large models and data sets. The parsing and pruning algorithms are carefully implemented with dynamic programming strategies, and efficient data structures are used to minimize overhead. Other techniques contributing to scalability includes suffix-array grammar extraction, parallel and distributed decoding, and bloom filter language models.

Below we give a short description about the main functions implemented in our Joshua toolkit.

\subsection{Training Corpus Sub-sampling}\label{subsampling} 

Rather than inducing a grammar from the full parallel training data, we made use of a method proposed by <NAME> (personal communication) to select the subset of the training data consisting of  sentences useful for inducing a grammar to translate a particular test set.  This method works as follows: for the development and test sets that will be translated, every $n$-gram (up to length 10) is gathered into a map $\mathcal{W}$ and associated with an initial count of zero.  Proceeding in order through the training data, for each sentence pair whose source-to-target length ratio is within one standard deviation of the average, if any $n$-gram found in the \emph{source sentence} is also found in $\mathcal{W}$ with a count of less than $k$, the sentence is selected.  When a sentence is selected, the count of every $n$-gram in $\mathcal{W}$ that is found in the source sentence is incremented by the number of its occurrences in the source sentence. \ignore{Thus, there are two conditions in which a sentence will not be selected: 1) it only contains $n$-grams that are not found in $\mathcal{W}$ (making it useless for learning in the highly lexicalized models we use) or 2) it only contains $n$-grams that have already been attested in the selected set $k$ or more times.} For our submission, we used $k=20$, which resulted in 1.5 million (out of 23 million) sentence pairs being selected for use as training data.  There were 30,037,600 English words and 30,083,927 French words in the subsampled training corpus. 

\subsection{Suffix-array Grammar Extraction}

Hierarchical phrase-based translation requires a translation grammar extracted from a parallel corpus, where grammar rules include associated feature values. In real translation tasks, the grammars extracted from large training corpora are often far too large to fit into available memory.

% Features such as the translation probability $p(f|e)$ and reverse translation probability $p(e|f)$ are typically calculated using relative frequency estimation . 
In such tasks, feature calculation is also very expensive in terms of time required; huge sets of extracted rules must be sorted in two directions for relative frequency calculation of such features as the translation probability $p(f|e)$ and reverse translation probability $p(e|f)$ \cite{Koehn2003}. Since the extraction steps must be re-run if any change is made to the input training data, the time required can be a major hindrance to researchers, especially those investigating the effects of tokenization or word segmentation.

%Worse, the grammars extracted from large training corpora are often far too large to fit into available memory.

To alleviate these issues, we extract only a subset of all available rules. Specifically, we follow \newcite{Callison-Burch2005b,Lopez2007} and use a source language suffix array to extract only those rules which will actually be used in translating a particular set of test sentences. This results in a vastly smaller rule set than techniques which extract all rules from the training set.

The current code requires suffix array rule extraction to be run as a pre-processing step to extract the rules needed to translate a particular test set. However, we are currently extending the decoder to directly access the suffix array. This will allow the decoder at runtime to efficiently extract exactly those rules needed to translate a particular sentence, without the need for a rule extraction pre-processing step.

% which will be allow the decoder to extract a sub-set of rules

%
%Worse, the extracted grammars

% to extract all allowed rules from a large parallel corpus, and to 

%When rule extraction is performed over an entire large parallel corpus, 

%With large training corpora, a substantial amount of processing time is required to extract all rules and to per

%Traditional phrase-based and hierarchical translation approaches require a translation grammar extracted from a parallel corpus, where grammar rules include associated feature values. Features such as the translation probability $p(f|e)$ and reverse translation probability $p(e|f)$ are typically calculated using relative frequency estimation \cite{Koehn2003}. 

%Lane: please extend this paragraph

%Suffix-array Translation Grammar ExtractionSuffix-array Translation Grammar ExtractionSuffix-array Translation Grammar ExtractionSuffix-array Translation Grammar ExtractionSuffix-array Translation Grammar ExtractionSuffix-array Translation Grammar ExtractionSuffix-array Translation Grammar ExtractionSuffix-array Translation Grammar ExtractionSuffix-array Translation Grammar ExtractionSuffix-array Translation Grammar ExtractionSuffix-array Translation Grammar ExtractionSuffix-array Translation Grammar ExtractionSuffix-array Translation Grammar ExtractionSuffix-array Translation Grammar ExtractionSuffix-array Translation Grammar ExtractionSuffix-array Translation Grammar ExtractionSuffix-array Translation Grammar ExtractionSuffix-array Translation Grammar ExtractionSuffix-array Translation Grammar ExtractionSuffix-array Translation Grammar ExtractionSuffix-array Translation Grammar

\subsection{Decoding Algorithms\footnote{More details on the decoding algorithms are provided in \cite{Li-PBML}.}}

\textbf{Grammar formalism:} Our decoder assumes a probabilistic synchronous context-free grammar (SCFG). Currently, it only handles SCFGs of the kind extracted by Heiro \cite{Chiang2007}, but is easily extensible to more general SCFGs (e.g., \cite{Galley2006}) and closely related formalisms like synchronous tree substitution grammars \cite{Eisner2003}.


\textbf{Chart parsing:} Given a source sentence to decode, the decoder generates a one-best or $k$-best translations using a CKY algorithm. Specifically,
the decoding algorithm  maintains a \emph{chart}, which contains an array of \emph{cells}. Each cell in turn maintains a list of proven \emph{items}. The parsing process starts with the axioms, and proceeds by applying the inference rules repeatedly to prove new items until proving a goal item. Whenever the parser proves a new item, it adds the item to the appropriate chart cell. The item also maintains backpointers to antecedent items, which are used for $k$-best extraction.

\textbf{Pruning:} Severe pruning is needed in order to make the decoding computationally feasible for SCFGs with large target-language vocabularies. In our decoder, we incorporate two pruning techniques: beam and cube pruning \cite{Chiang2007}.

\textbf{Hypergraphs and $k$-best extraction:}
For each source-language sentence, the chart-parsing algorithm produces a \emph{hypergraph}, which represents an exponential set of likely derivation hypotheses. Using the $k$-best extraction algorithm \cite{Huang2005}, we extract the $k$ most likely derivations from the hypergraph.

\textbf{Parallel and distributed decoding:}
We also implement \emph{parallel decoding} and a \emph{distributed language model} by exploiting multi-core and multi-processor architectures and distributed computing techniques. More details on these two features are provided by \newcite{Li2008b}.

\subsection{Language Models}
%Jonny: please check the bloom filter LM part
In addition to the distributed LM mentioned above, we implement three local $n$-gram language models. Specifically, we first provide a straightforward implementation of the $n$-gram scoring function in Java. This Java implementation is able to read the standard ARPA backoff $n$-gram models, and thus the decoder can be used independently from the SRILM toolkit.\footnote{This feature allows users to easily try the Joshua toolkit without installing the SRILM toolkit and compiling the native bridge code. However, users should note that the basic Java LM implementation is not as scalable as the native bridge code.} We also provide a native code bridge that allows the decoder to use the SRILM toolkit to read and score $n$-grams. This native implementation is more scalable than the basic Java LM implementation. We have also implemented a Bloom Filter LM in Joshua, following \newcite{Talbot2007a}.

\subsection{Minimum Error Rate Training}

Johsua's MERT module optimizes parameter weights so as to maximize performance on a development set as measuered by an automatic evaluation metric, such as Bleu. The optimization consists of a series of line-optimizations along the dimensions corresponding to the parameters. The search across a dimension uses the efficient method of \newcite{Och2003c}. Each iteration of our MERT implementation consists of multiple weight updates, each reflecting a greedy selection of the dimension giving the most gain. Each iteration also optimizes several random ``intermediate initial'' points in addition to the one surviving from the previous iteration, as an approximation to performing multiple random restarts. More details on the MERT method and the implementation can be found in \newcite{Zaidan2009forwmt}.\footnote{The module is also available as a standalone application, {\em Z-MERT}, that can be used with other MT systems. (Software and documentation at: \url{http://cs.jhu.edu/~ozaidan/zmert.html}.)}



\section{WMT-09 Translation Task Results}
%In this section, we report results on the WMT-09 French-English translation task.
\subsection{Training and Development Data}

We assembled a very large French-English training corpus  \cite{billion-word-parallel-corpus} by conducting a web crawl that targted bilingual web sites from the Canadian government, the European Union, and various international organizations like the Amnesty International and the Olympic Committee.  The crawl gathered approximately 40 million files, consisting of over 1TB of data.  We converted pdf, doc, html, asp, php, etc. files into text, and preserved the directory structure of the web crawl.  We wrote set of simple heuristics to transform French URLs onto English URLs, and considered matching documents to be translations of each other.  This yielded 2 million French documents paired with their English equivalents.  We split the sentences and paragraphs in these documents, performed sentence-aligned them using software that IBM Model 1 probabilities into account \cite{Moore2002}.   We filtered and de-duplcated the resulting parallel corpus.  After discarding 630 thousand sentence pairs which had more than 100 words, our final corpus had 21.9 million sentence pairs with 587,867,024 English words and 714,137,609 French words.  

We distributed the corpus to the other WMT09 participants to use in addition to the Europarl v4 French-English parallel corpus \cite{Koehn-europarl}, which consists of approximately 1.4 million sentence pairs with 39 million English words and 44 million French words.  Our translation model was trained on these corpora using the subsampling descried in Section \ref{subsampling}.  

For language model training, we used the monolingual news and blog data that was assembled by the University of Edinburgh and distributed as part of WMT09.  This data consisted of 21.2 million English sentences with half a billion words.  We used SRILM to train a 5-gram language model using a vocabulary containing the 500,000 most frequent words in this corpus.  Note that we did not use the English side of the parallel corpus as language model training data.

To tune the system parameters we used News Test Set from WMT08 \cite{Callison-Burch2008a}, which consists of 2,051 sentence pairs with 43 thousand English words and 46 thousand French words.  This is in-domain data that was gathered from the same news sources as the WMT09 test set.

\subsection{Translation Scores}
The translation scores for four different systems are reported in Table \ref{results-wmt09}.\footnote{Note that the implementation of the novel techniques used to produce the non-baseline results is not part of the current Joshua release, though we plan to incorporate it in the next release.}


\textbf{Baseline: } In this system, we use the GIZA++ toolkit \cite{Och2003}, a suffix-array architecture \cite{Lopez2007}, the SRILM toolkit \cite{Stolcke2002}, and minimum error rate training \cite{Och2003c} to obtain word-alignments, a translation model, language models, and the optimal weights for combining these models, respectively.


\textbf{Minimum Bayes Risk Rescoring: } In this system, we re-ranked the n-best output of our baseline system using Minimum Bayes Risk \cite{Kumar2004b}.  We re-score the top 300 translations to minimize expected loss under the Bleu metric.

\textbf{Deterministic Annealing: } In this system, instead of using the regular MERT \cite{Och2003c} whose training objective is to minimize the one-best error, we use the deterministic annealing training procedure described in \newcite{Smith2006}, whose objective is to minimize the \emph{expected} error (together with the entropy regularization technique).

\textbf{Variational Decoding: }  A hierarchical machine translation system like Hiero exhibits \emph{spurious ambiguity}, a situation where the system
produces many distinct derivation \emph{trees} that yield the same translation \emph{string}.\footnote{A regular phrase-based system also has spurious ambiguity due to different ways of segmenting the translation output.} However, no tractable extraction algorithm is available to marginalize over derivations during decoding time. Therefore, most systems simply approximate the goodness of a translation string by using the goodness of its most-probable derivation. Instead, we have developed a novel approximation algorithm, using a \emph{variational principle}, to approximate the sum.
More details will be provided in \newcite{Li2009}. In this system, we have used both deterministic annealing (for training) and variational decoding (for decoding).



\begin{table}[t]
\begin{center}
\begin{tabular}{c c}\hline
System & BLEU-4 \\ \hline
Joshua Baseline & 25.92 \\
Minimum Bayes Risk Rescoring & 26.16 \\
Deterministic Annealing & 25.98 \\
Variational Decoding & {\bf 26.52} \\ \hline
\end{tabular}
\end{center}
\caption{The uncased BLEU scores on WMT-09 French-English Task.  The test set consists of 2525 segments, each with one reference translation.}
\label{results-wmt09}
\end{table}

\section{Conclusions}

We have described a scalable toolkit for parsing-based machine translation. It is written in Java and implements all the essential algorithms described in \newcite{Chiang2007} and \newcite{Li2008b}: chart-parsing, $n$-gram language model integration, beam- and cube-pruning, and $k$-best extraction.
The toolkit also implements suffix-array grammar extraction \cite{Callison-Burch2005b,Lopez2007} and minimum error rate training \cite{Och2003c}. Additionally, parallel and distributed computing techniques are exploited to make it scalable. The decoder achieves state of the art translation performance.



%%%lzf add this section

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\section*{Acknowledgments}
This research was supported in part by the Defense Advanced Research Projects Agency's GALE program under Contract No.\,HR0011-06-2-0001 and the National Science Foundation under grants No.\,0713448 and 0840112. The views and findings are the authors' alone.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\bibliographystyle{acl}
\bibliography{../bibliography}
\end{document} 

{'fraction_non_alphanumeric': 0.06021212690069457, 'fraction_numerical': 0.014313872723859583, 'mean_word_length': 5.2232768691588785, 'pattern_counts': {'":': 0, '<': 23, '<?xml version=': 0, '>': 23, 'https://': 0, 'lorem ipsum': 0, 'www.': 2, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 4, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'dir': 'git-commits-cleaned', 'id': '6872904', 'n_tokens_mistral': 10785, 'n_tokens_neox': 9650, 'n_words': 5599}