



\section{
\label{confusion-networks.tex}
Confusion Networks Decoding}


Machine translation input currently takes the form of simple sequences of words. However, there are increasing demands to integrate machine translation technology in larger information processing systems with upstream natural language and/or speech processing tools (such as named entity recognizers, automatic speech recognizers, morphological analyzers, etc.). These upstream processes tend to generate multiple, erroneous hypotheses with varying confidence. Current MT systems are designed to process only one input hypothesis, making them vulnerable to errors in the input. We extend current MT decoding methods to process multiple, ambiguous hypotheses in the form of an input lattice. A lattice representation allows an MT system to arbitrate between multiple ambiguous hypotheses from upstream processing so that the best translation can be produced.



As lattice has usually a complex topology, an approximation of it, called {\bf confusion network},  is used instead. The extraction of a confusion network from a lattice can be performed by means of a publicly available {\tt lattice-tool} contained in the {\bf SRILM toolkit}. See the SRILM manual pages\footnote{\sf http://www.speech.sri.com/projects/srilm/manpages} for details and user guide.



\subsection{
Confusion Networks}


A {\bf Confusion Network} (CN), also known as a {\bf sausage}, is a weighted directed graph with the peculiarity  that each path  from the start  node to the  end node goes    through    all    the    other    nodes.



Each edge is labeled with a word and a (posterior) probability.
The total probability of all edges between two consecutive nodes sum up to 1. Notice that this is not a strict constraint from the point of view of the decoder; any score can be provided. A path from the start  node to the  end node is scored  by multiplying the scores of its edges. If the previous constrain is satisfied, the product represents the likelihood of the path, and the sum of the likelihood of all paths  equals to 1.



Between any two consecutive nodes, one (at most) special word {\tt \_eps\_} can be inserted;
{\tt \_eps\_} words allows paths having different lengths.









\begin{center}
\includegraphics[scale=0.245098039215686]{images/mesh.png}
\end{center}




Any path within a CN represents a {\bf realization} of the CN.
Realizations of a CN can differ in terms of either sequence of words or total score. It is possible that two (or more) realizations have the same sequence of words, but different scores. Word lengths can also differ due to presence of the {\tt \_eps\_}. This is a list of some realization of the previous CN.






\begin{SaveVerbatim}{myverb}
aus der Zeitung       score=0.252       length=3
Aus der Zeitung       score=0.126       length=3
Zeitung               score=0.021       length=1
Haus Zeitungs         score=0.001       length=2
\end{SaveVerbatim}
\begin{shaded}
\small
\UseVerbatim{myverb}
\end{shaded}

\subsubsection*{
Notes}

\begin{compactitem}
\item A CN contains all paths of the lattice which is originated from.

\item A CN can contain more paths than the lattice which is originated from (due {\tt \_eps\_}).

\end{compactitem}

\subsection{
Representation of Confusion Network}


Moses adopts the following computer-friendly representation for a CN.






\begin{SaveVerbatim}{myverb}
Haus 0.1 aus 0.4 _eps_ 0.3 Aus 0.2
der 0.9 _eps_ 0.1
Zeitung 0.7 _eps_ 0.2 Zeitungs 0.1
\end{SaveVerbatim}
\begin{shaded}
\small
\UseVerbatim{myverb}
\end{shaded}

where a line contains the alternative edges (words and probs) between two consecutive nodes.



In the factored representation, each line gives alternatives over the full factor space:






\begin{SaveVerbatim}{myverb}
Haus|N 0.1 aus|PREP 0.4 Aus|N 0.4 _eps_|_eps_ 0.1
der|DET 0.1 der|PREP 0.8 _eps_|_eps_ 0.1
Zeitung|N 0.7 _eps_|_eps_ 0.2 Zeitungs|N 0.1
\end{SaveVerbatim}
\begin{shaded}
\small
\UseVerbatim{myverb}
\end{shaded}

Notice that if you project the above CN on a single factor, 
repetitions of factors must be merged and the respective  probs
summed up. The corresponding word-projected CN is the one of the first
example, while the part-of-speech projected CN is:






\begin{SaveVerbatim}{myverb}
N 0.5 PREP 0.4 _eps_ 0.1
DET 0.1 PREP 0.8 _eps_ 0.1
N 0.8 _eps_ 0.2  
\end{SaveVerbatim}
\begin{shaded}
\small
\UseVerbatim{myverb}
\end{shaded}










\begin{center}\textit{\small Subsection last  modified on March 26, 2013, at 10:18 AM}\end{center}
