    \documentclass[english]{jnlp_1.4}

\usepackage{jnlpbbl_1.3}
\usepackage[dvipdfmx]{graphicx}
\usepackage{hangcaption_jnlp}
\usepackage{array}

\usepackage{amsmath}
\usepackage{algorithm}
\usepackage{algpseudocode}
\usepackage{multirow}
\newcommand{\tolstrut}{}
\DeclareRobustCommand{\textoverline}[1]{
  \ensuremath{\overline{\mbox{\tolstrut#1}}}
}
\DeclareRobustCommand{\textnooverline}[1]{
  \ensuremath{ \mbox{\tolstrut#1} }
}


\Volume{24}
\Number{4}
\Month{September}
\Year{2017}

\received{2017}{3}{3}
\revised{2017}{5}{24}
\accepted{2017}{7}{6}

\setcounter{page}{619}


\etitle{Hierarchical Sub-sentential Alignment with IBM Models for Statistical Phrase-based Machine Translation}
\eauthor{Hao Wang\affiref{Author_1} \and Yves Lepage\affiref{Author_1}} 
\eabstract{
In this paper, we describe a novel method for joint word alignment and symmetrization. Based on initial parameters from simple IBM models, we synchronously parse the parallel sentence pair under the framework of bracket transduction grammar constraints. Our 2-phase method can achieve nearly the same run-time as {\tt{fast\_align}} while delivering better alignments on distantly-related language pairs such as English--Japanese. We show how to integrate this method into a standard phrase-based SMT pipeline. Although the alignment quality results are mixed, by forcing all words to be aligned (\textit{1-to-many/many-to-1}), our method significantly reduces the phrase table size with no difference in translation quality and even outperforms {\tt{fast\_align}} in some end-to-end translation experiments.
}
\ekeywords{Word Alignment, Symmetrization, Machine Translation, Parsing}

\headauthor{Wang, Lepage}
\headtitle{Hierarchical Sub-sentential Alignment with IBM Models}

\affilabel{Author_1}{}{Graduate School of Information, Production and Systems, Waseda University} 


\begin{document}

\maketitle

\section{Introduction}

Word alignment is the fundamental issue in many tasks of natural language processing. For instance, state-of-the-art statistical machine translation (SMT) methods require word-to-word aligned data on a parallel corpus, for the various purposes of extracting reusable translation fragments, e.g., word pairs \cite{brown1988statistical}, phrase pairs \cite{koehn2003statistical}, hierarchical rules \cite{chiang2007hierarchical}, tree-to-string correspondences \cite{liu2006tree} and tree-to-tree templates \cite{zhang2007tree}. Since word alignment is the basis to perform these tasks, the reliability and accuracy of the word aligner directly affect the end-to-end MT performance in most cases \cite{fraser2007measuring}, which seems intuitive.

A standard phrase-based SMT pipeline can be summarized as a serial process: \textit{align-extract-tune-decode}. Word alignment is the essential preprocessing step for phrase extraction. Most of the word alignment methods are based on the generative models, like IBM models \cite{brown1993mathematics} and, besides, they can also be augmented with an HMM-based model \cite{vogel1996hmm}. In general, we can group these models into two types, as the pioneering work \cite{liang2006alignment}: sequence-based models (IBM model 1, 2 and HMM model) and fertility-based models (IBM model 3, 4 and 5). Intuitively, the high-level fertility-based models become intractable from simpler sequence-based models, which is not easy to implement. As a result, even when using {\tt {GIZA++}},\footnote{http://www.statmt.org/moses/giza/{\tt {GIZA++}}.html} the most widely used aligner at present, which consists of various IBM models and their extensions, IBM model 4 is selected as default to find a trade-off between alignment quality and efficiency.

There exist several problems in the presented models. For sequence-based models, the EM algorithm \cite{dempster1977maximum} is applied to find the optimal parameters. Recently, some researchers also work on Bayesian word alignment, using techniques such as Gibbs sampling \cite{mermer2011bayesian}. Typically to say, the training process runs in both directions, then yields two sets of parameters, and eventually two directional alignments. Since sequence-based models restrict to \textit{many-to-1} alignments, they are prone to produce discontinuous alignments. For example, under the definition of IBM models for alignment, we can map several indices of the source side to the same index of the target side, and it is possible that some indices on the target side are not being mapped. Because the phrase-based SMT relies more on alignments of multi-word units (\textit{many-to-many}), called phrase pairs, which commonly cannot be correctly extracted during processing, especially when these phrase pairs are needed to build the translation hypothesis during decoding. Intuitively, this will have a significant influence on the final quality of the translation. 

Due to the drawback of discontinuity in sequence-based models, high-level fertility-based models were developed. These models are expected to generate more word alignments to fill the empty cells between cells with high confident in alignment matrices. There is no doubt that these models generate state-of-the-art alignments but the fact that IBM model 3 and above are often criticized for their complexity, which is much time-consuming during training, even within the highly optimized implementations in {\tt {GIZA++}}. To deal with this problem, \citeA{dyer2013simple} employ a variation of sequence-based models rather than fertility-based models to generate word alignment. They showed that in the implementation ({\tt{fast\_align}}\footnote{https://github.com/clab/fast\_align}) can yield comparable results on some language pairs in end-to-end translation experiments. {\tt{Fast\_align}} yields less alignment. \citeA{wang2016combining} showed that the number of word alignments output by {\tt{fast\_align}} is 19\% less with {\tt {GIZA++}}.
Moreover, word-position-featured method is not really suitable for the distantly-related language pairs, \citeA{ding2015improving} demonstrated that {\tt{fast\_align}} does not outperform {\tt {GIZA++}} on Japanese-English and English-German experiments.

However,  both sequence-based and fertility-based models still generate asymmetrical alignments and mono-directional alignments are not suitable for the bilingual tasks, like a phrase-based SMT. In order to obtain symmetric alignment, \citeA{och2003systematic} proposed to train models in both forward and reverse directions, whereafter merging the outcome of mono-directional alignments with some symmetrization heuristics. Among these heuristics, the \textit{grow-diag-final-and} heuristic (GDFA) has been shown to be the most effective for phrase extraction for phrased-based SMT \cite{wu2007comparative}. Contrary to introducing heuristics, there exists some work \cite{liang2006alignment} which tries to train a balanced model by maximizing the agreement between two directional word alignments. Such work is beyond the scope of our focus because it would lead to more time during training. It is, therefore, natural to explore other methods for word alignment symmetrization.

Another challenge in word alignment, especially for distinctly-related language pairs, is modeling the permutations of words between the source and target sentences while, theoretically, IBM models have not studied such a problem. Due to the diversity of natural languages, the word orders of the source and target sentences are quite different, e.g., English and Japanese. For some free-order languages, there is even no significant relationship between the current alignment and previous alignment in sequence from left to right, seems in contrast with the presumption of HMM model and IBM model 2 under this case. In this work, we prefer to model our problem with Bracket Transduction Grammar (BTG) \cite{wu1995stochastic}. BTG is an effective method that can capture the reordering of words across bilingual sentence pair. In fact, constraints of BTG were better matched to the IBM decoding model \cite{zens2004reordering}. Differing with the IBM models, BTG has shown its efficiency in a way that constrained the search space of distortion in word alignment \cite{zhang2005stochastic,haghighi2009better,riesa2010hierarchical}.

In this paper, rather than reparameterizing IBM models, we expect to achieve better translation results addressing the reason of discontiguous word alignment directly. To address this problem, we concentrate our attention on hierarchical alignment with BTG parsing. Instead of using synchronous parsing to search for Viterbi BTG alignments as in \cite{li2012beam}, we propose to employ the bi-partitioning algorithm presented in \cite{lardilleux2012hierarchical} to generate symmetrical BTG block alignments (\textit{1-to-many/many-to-1}) with our beam search implementation. In particular, our method starts with an adjacency matrix which is initialized using the lexicon translation model obtained via fast running EM estimation with IBM models; then we apply the bi-partitioning algorithm. Our two-phase method takes a radically different strategy compared with previous BTG-based unsupervised/supervised methods for word alignment. 

To summarize, we propose a novel method for joint word alignment and symmetrization, which can be regarded as a hybridization of BTG parsing and IBM models. In Section~\ref{related_work}, we introduce the previous related works and notions in word alignment. We also describe each alignment method briefly. In Section~\ref{proposed_method}, we justify the proposed method with mathematical principles and give multiple comparisons with state-of-the-art methods in Section~\ref{experiment}. We also report statistics on speed, alignment scores, translation table sizes and translation scores (BLEU and RIBES) in end-to-end translation experiments, which we discuss in detail in this article.


\section{Related Works}
\label{related_work}

\subsection{Viterbi Alignment and Symmetrization}

State-of-the-art word alignment models contain a large number of parameters (e.g., word translation probabilities) that need to estimate in addition to the desired hidden alignment variables.  
The basic idea of the previous methods is to develop a model where the word alignment is a hidden variable \cite{och2003systematic}, by applying some statistical estimation to obtain the most possible/Viterbi alignments. The problem of translation can be defined as:
$Pr(\mathbf{e}|\mathbf{f}) =\sum_{\mathbf{a}}^{ } p(\mathbf{e}, \mathbf{a} | \mathbf{f})$.
Here we use the symbol $p(\cdot )$ to denote general probability distributions. $\mathbf{a}$ is a ``hidden'' variable which is mapping from a source position $i$ to a target position $a_i$. It is always possible to find a best alignment by maximizing the likelihood on the given parallel training corpus. Under sequence-based models, we have
\begin{equation} 
p(\mathbf{e}, \mathbf{a} | \mathbf{f}) = \prod_{j=1}^{n} \sum_{i=0}^{m} \theta(e_j|f_{a_j}) \delta(a_j= i| j, m, n) 
\end{equation}
where $\mathbf{f}= (f_1, \dots, f_m)$ is the source sentence and $\mathbf{e} = (e_1, \dots, e_n)$  is the target sentence. The translation parameters $\theta(e_j|f_{a_j})$ are parameterized by an appropriate local conditional probability distributions. 
\begin{equation}
\delta(a_j= i|j, m, n) =
\begin{cases}
p_0                                          &  i=0   \\
(1-p_0) \times h(a_j= i| j,m,n)  &  i\neq 0 
\end{cases}
\end{equation}
For modeling the distortion parameters $\delta(a_j= i| j,m,n)$, IBM models are the popular models. There are summarized as follows as 
\pagebreak
\cite{liang2006alignment}:
\begin{equation}
h(a_j= i| j,m,n,a_{j-1}=i')\propto 
\begin{cases}
1     & \mbox{ IBM 1 } \\
\phi(\frac{i}{m}, \frac{j}{n}) & \mbox{ IBM 2 }\\ 
\phi(i,i')    & \mbox{ HMM}
\end{cases}
\end{equation}
In the formula, we write $i'$ to denote the last alignment point $( i',j-1)$ in history. Among these models, IBM model 1 assumes a uniform distribution for $p(a)$, which effectively means that the word order of the sentences are considered irrelevant. This is clearly not true in real translated sentences of most language pairs. However, $a_j$ and $a_{j-1}$ tend to be strongly correlated, for example, this is the case in English-French. Most research on word alignment has assumed some version of a word order model to capture this dependency. Perhaps the simplest version \cite{dyer2013simple} is used in IBM model 2 where the observation is made that ${i/m} \approx {j/n}$. In other words, sentences tend to have the same order of words in both languages. This is a very rough approximation. \citeA{vogel1996hmm} proposed instead to directly model $P(a_{j} - a_{j-1} = x|m)$. This describes the length $x$ of the ``jump'' in the source sentence when moving one word forward in the target sentence, conditioned on the source sentence length $n$.  

Based on the above defined model, a Viterbi alignment model returns mono-directional alignments ($\mathbf{f} \rightarrow \mathbf{e}$ or vice-versa) which maximize the following formula. 
\begin{equation}
\mathbf{\hat{a}} = \hat{a}_1^n = \underset{a_j \in \{\mbox{all alignments}\}}{\mbox{argmax}} \sum_{\mathbf{j=1}}^{n} p(e_j,  a_j=i  | f_i)
\end{equation}

This processing explains the reason why Viterbi alignment methods generate discontinuity in word alignments. Although the influence of discontinuity can be reduced by combining two sets of alignments $\hat{\mathbf{a}}=\hat{a}_1^n$ $(\mathbf{f} \rightarrow \mathbf{e})$ and $\hat{\mathbf{b}}=\hat{b}_1^m$ $(\mathbf{e} \rightarrow \mathbf{f})$ into one alignment matrix $A$ using the \textit{grow-diag-final-and} algorithm, sometimes, there may still exist some unaligned target words. Given the merged alignment, we can easily factor the lexical translation probabilities. Obviously, the existence of unaligned target words makes the process of phrase extraction to produce more translation fragments, and it is reasonable to allow \textit{null-to-1} alignments when iterating over all possible boundaries in target side. This strategy largely increases the size of extracted phrase table enormously at the same time. To alleviate this problem, we can force to align each source word with a target word and vice versa by forbidding that any source/target word be unaligned in the given sentence pair. In our experiments, we showed our strategy is effective to reduce the size of phrase table. 


\subsection{BTG-based Word Alignment}

Bracket Transduction Grammar (BTG) is an effective method to restrict the exploration of all the possible permutations. There has been some interest in using BTGs for the purpose of alignment \cite{zhang2005stochastic,wang2007binarizing,xiong2010learning,neubig2012machine}. Initially, the BTG formalism \cite{wu1995stochastic} offers a special case of synchronous context-free grammars, which are quite suitable as the weak constraint regarding synchronous parsing. In particular, \citeA{haghighi2009better,riesa2010hierarchical} showed that BTG, which captures structural coherence between parallel sentences, helps in word alignment. During parsing, a BTG builds a synchronous parse tree for both the source and the target sentence, assuming that the trees have the same underlying structure (BTG tree) but that order of constituents may differ in the two languages. Hence, each leaf in the BTG tree stands for a word-to-word correspondence. There are three types of rule in a BTG: 
\begin{equation}
S:  \gamma \rightarrow   [X_1 X_2]  \quad | \quad I:  \gamma   \rightarrow  <X_1 X_2> \quad |\quad  T:  \gamma \rightarrow (f, e) \empty 
\end{equation} 
where $X_1, X_2$ and $\gamma$ are non-terminal symbols, $f$ and
$e$ are terminal strings, and $[$ $]$ denotes the same order for the two non-terminals in two languages, $<>$ denotes the inversion case. These formalisms are slightly different with Inversion Transduction Grammar (ITG) \cite{wu1997stochastic}, where the lexical rule $\gamma \rightarrow(f, e)$ does not include any source/target empty rules. In our case, we force to output the phrase pair $(f, e)$ as a single block alignment which the length is one at least and three at most to prevent $null$ blocks.

The complexity of word alignment grows exponentially with the length of the source and the target sentences.  BTG models provide a natural, alternative method to reduce the search space in aligning. By estimating the joint word alignment relation directly, it eliminates the need for any of the conventional heuristics. The biggest barrier to applying BTG for Viterbi alignment is the time complexity of na\"{\i}ve CYK parsing ($O(n^6)$), which makes it hard to deal with long sentences or large grammars in practice.

Most of the previous research attempts to reduce the computational complexity of BTG parsing with some pruning methods. \citeA{zhang2005stochastic} propose \textit{tic-tac-toe} pruning by extending BTG with the additional lexical information based on IBM model 1 Viterbi probability. \citeA{haghighi2009better} investigate pruning based on the posterior predictions from two joint estimated models. \citeA{li2012beam} present a simple beam search algorithm for searching the Viterbi BTG alignments. \citeA{lardilleux2012hierarchical} propose to binary segment the alignment matrix recursively to compute BTG-like alignments based on word level association scores but have not reported the alignment performance independently. 
\citeA{cherry2007inversion} presented a phrasal BTG to the joint phrasal translation model and reported the results of the word alignment evaluation experiment. \citeA{neubig-EtAl:2011:ACL-HLT2011} incorporated a non-parametric Bayesian method with joint phrase alignment and extraction model. Given it is not able to explain many translation phenomena that extracting phrase using word-to-word alignment as a pivot, \citeA{cohn2013infinite} proposed to learn the BTG phrasal model using a recursive Bayesian method. \citeA{kamigaitounsupervised} modified the bidirectional agreement constraints and applied a more complex version (BTG-style agreement) to train the BTG model jointly. 
Differing from the previous works, in this paper, we propose a BTG-forest-based word alignment as the heuristic to explore probable alignment points in alignment matrix. We will discuss the details in Section~\ref{proposed_method}.


\subsection{Hierarchical Sub-sentential Alignment and \textbf{\itshape Ncut}}

Hierarchical sub-sentential alignment (HSSA) \cite{lardilleux2012hierarchical} was first introduced as a complement for {\tt{Anymalign}}.\footnote{https://anymalign.limsi.fr/} Given the soft alignment matrix built using the parameters output by {\tt{Anymalign}}, the HSSA method takes all the cells in the soft alignment matrix into consideration and relies on a precise criterion to determine a good partition in a similar way as image segmentation. HSSA makes use of an unsupervised clustering criterion called \textit{normalized cuts} \cite{shi2000normalized,zha2001bipartite}, or  $\text {\it Ncut}$ for short, to recursively segment the matrix into two parts. During the segmentation processing, HSSA is supervised by the BTG constraint to decide the search scope of next level on the diagonal (rep: anti-diagonal) corresponding exactly to the case of \textit{straight} (rep:  \textit{inverted}.)  HSSA terminates when all words in the source and target sentences are aligned and generate symmetric alignments at the same time.

Consider a source phrase $A:\textnooverline{$X$}\textoverline{$X$}$ and a target phrase $B:\textnooverline{$Y$}\textoverline{$Y$}$, which can be split at source index $i$ and $j$ in target side in a dichotomic way. The sub-spans $\textnooverline{$X$}$, $\textoverline{$X$}$ in source side are corresponding to $\textnooverline{$Y$}$, $\textoverline{$Y$}$ or $\textoverline{$Y$}$, $\textnooverline{$Y$}$. If we record the segmentation option as $\gamma \in \{0, 1, 2\}$ (diagonal, anti-diagonal and terminal), the association within groups $asso(A, B)$ and the risk of cutting $cut$ at point $(i, j)$ is defined by the underlying formula followed the definition of \cite{shi2000normalized}:
\begin{equation}  
asso(A, B) = \sum_{f \in A}^{} \sum_{e \in B}^{} w(f,e) 
\end{equation}
where $w(f,e)$ stands for the weighted score 
\pagebreak
that $f$ is aligned with $e$.
\begin{gather}  
\resizebox{0.45\hsize}{!}{$cut(i, j| \gamma=0) = \underbrace{asso(\textnooverline{$X$},\textoverline{$Y$})}_\text{left} +\underbrace{asso(\textoverline{$X$},\textnooverline{$Y$})}_\text{right}$},\quad\quad\quad\quad\quad\quad \mbox{\textit{straight}} \\
\resizebox{0.45\hsize}{!}{$cut(i, j| \gamma=1) = \underbrace{asso(\textnooverline{$X$},\textnooverline{$Y$})}_\text{left}  + \underbrace{asso(\textoverline{$X$},\textoverline{$Y$})}_\text{right} $}, \quad\quad\quad\quad\quad\quad \mbox{\textit{inverted}}
\end{gather}
The optimal bi-partitioning of such a matrix (graph) is the one that minimizes this \textit{cut} value. However, the minimum cut criterion favors cutting small sets of isolated nodes in the graph, which is counterintuitive, so \cite{shi2000normalized} propose $\text {\it Ncut}$ as a measure for total normalized association within groups for a given partition. In our case,  $\text {\it Ncut}$ can be defined as:
\begin{equation}
\resizebox{0.8\hsize}{!}{$Ncut(i, j | \gamma) = \frac{cut(i, j | \gamma)}{cut(i, j | \gamma) + 2\times cut_{\text{left}}(i, j | \bar{\gamma})} \nonumber + \frac{cut(i, j | \bar{\gamma})}{cut(i, j | \bar{\gamma})  + 2 \times cut_{\text{right}}(i, j | \bar{\gamma}) }$}
\end{equation} 
Each possible splitting point $(i,j)$ in the matrix divides the parent matrix into 4 sub-matrices ($\textnooverline{$X$}\textnooverline{$Y$}$, $\textnooverline{$X$}\textoverline{$Y$}$, $\textoverline{$X$}\textnooverline{$Y$}$, $\textoverline{$X$}\textoverline{$Y$}$). Either the two sub-matrices on the diagonal ($\textnooverline{$X$}\textnooverline{$Y$}$, $\textoverline{$X$}\textoverline{$Y$}$) or the two sub-matrices on the anti-diagonal ($\textnooverline{$X$}\textoverline{$Y$}$, $\textoverline{$X$}\textnooverline{$Y$}$) will be explored recursively on the next layer, referring to $\gamma$ equals 0 or 1. Hence, recursive segmentation eventually consists in determining these indices $(i, j)$ which minimize $Ncut(i, j | \gamma)$ or $Ncut(i, j | \bar{\gamma})$ over all possible indices. Hence, the criterion $\text {\it Ncut}$ that we seek in our recursive partition algorithm, minimizing the disassociation between the blocks unaligned and maximizing the association within the blocks aligned. Since the the worst case time complexity of top-down HSSA is cubic $O(m\times n\times\min(m,n))$ and the best case is $O( m \times n \times \log \min(m,n))$ in the length of the input sentence pair, it is faster than the original BTG method $O(n^6)$.


\section{Joint Alignment and Symmetrization Model}
\label{proposed_method}

In this paper, we propose a novel joint model (see Figure 1) for the unsupervised training of a word aligner by applying IBM models with HSSA. The next sections show how to combine various IBM models with HSSA method to obtain symmetric word alignments. 

\begin{figure}[t]
\begin{center}
\includegraphics{24-4ia5f1.eps}
\end{center} 
\hangcaption{Comparison of standard bidirectional word alignment pipeline and our proposed joint method pipeline.} 
\end{figure} 


\subsection{Building the Soft Alignment Matrices}

Given a source sentence $\mathbf{f} = f^m_1 = f_1, \dots, f_i , \dots, f_m$ and a target sentence $\mathbf{e} = e^n_1 = e_1, \dots, e_j, \dots, e_n$, alignment associations between a source sentence $\mathbf{f}$ and a target sentence $\mathbf{e}$ can be regarded as a contingency matrix \cite{matusov2004symmetric,moore2005association,liu2009weighted}, noted as $\mathcal{M}$, in which $m$ is the length of source sentence in words and $n$ for target side. For example, in \cite{liu2009weighted}, a weighted matrix was employed for extracting more candidates of phrase pairs, which consists of the cells that corresponding to a arbitrary word pair. Each of these cells has been assigned with a probability score to measure the confidence of aligning the two words. Following this definition, we define a function $w$ which measuring the probability of alignment between any source and target word pair ($f_i, e_j$) but use it for BTG parsing. The symmetric alignment between word $f_i$ and $e_j$ presents a weighted cell ($i, j$) in the alignment matrix.

Let $\mathcal{M}$ be such a soft alignment matrix (a weighted adjacent matrix in fact) which is used to represent the graph of the sentence pair, in which each pair of words in such a graph is connected, with weight on the edges between the nodes. Formally, when given a source word $f$ and a target word $e$, we define a soft link $l = (f, e)$ to exist if $f$ and $e$ are probable translation. There are plenty of ways to define the weight of $l(f, e)$ and perhaps the most simple way to inference is using the posterior IBM model 1 probabilities. Since the sparsity of the data for counting, Laplace smoothing is used here to handle the unseen alignments and remove the small values, with assigned a smoothing parameter $p_0= 10^{-4}$ and force $ l(f,e) >= p_0$. 
\begin{equation}
l(f,e)  = \begin{cases}
 \quad\quad\quad p_0 & \text{ if }  l = \varepsilon\\ 
 \quad\sqrt[]{l(f| e)  \times l(e|f)} & \text{ otherwise}  
\end{cases}
\end{equation}
After computed the posterior probabilities with the EM algorithm, the symmetrical score $l(f, e)$ can be obtained by taking the geometric mean of the lexical translation probabilities in both directions $l(f|e)$ and $l(e|f)$ and we can approximate $w(f_i,e_j)$ by $l(f, e)$. As our task is not only aiming at better results but also at saving time in alignment computation, the simpler the faster. In \cite{haghighi2009better,liu2010discriminative}, more features to achieve better results. However, their work focuses on supervised BTG models, while our joint model is purely unsupervised. Other works like training with agreement \cite{liang2006alignment} perhaps give better initial parameters but also require more time for training and result in a computationally expensive process. \citeA{moore2005association} pointed that IBM model 1 has many disadvantages, it is either too sensitive to rare words or over-weights frequent words (like function words). For this reason, incorporating variational Bayes (VB) \cite{riley2012improving} into our model is necessary. We implemented VB for the translation probabilities in M step and assume the distribution of the target vocabulary to be a Dirichlet distribution, with a symmetric Dirichlet prior as $\alpha$ so that we have 
\begin{equation}
l(e|f) \sim \mbox{Dirichlet}(\alpha)
\end{equation}
Here, we assume the prior $\alpha=0.01$. As an alternative, other probability models for estimation can also be used, and we can change the original IBM model with the max operator (as \cite{zhang2005stochastic}). Given the asymmetrical alignments in both directions, it is easy to reestimate the Viterbi probabilities. This reestimation processing can significantly reduce the size of the trained models. Some heuristic like \textit{grow-diag-final-and} can also be applied before re-estimating. We found that it does yield better results in our alignment experiments. 

Until now, we have not discussed any effect of position information yet. As we known, in IBM model 2 and HMM model, for a given word pair $(f_i,e_j)$, position information $(i,j)$ is a very important term. In addition, our joint model takes the position information as a complementary component. It is expected to work under the condition that the sentence pair contains multiple possible word translation pairs for identical $(f,e)$, i.e., the case when $(f_i,e_j)=(f_{i'},e_{j'})$. An effective solution is to define the score $w$ which connecting two nodes $f_i$ and $e_j$, as the product of a feature translation term (translation probability) and spatial proximity term (relative position similarity) as in \cite{shi2000normalized}: 
\begin{equation}
w(f_i,e_j)  = e^{\frac{\theta(f_i,e_j)}{\sigma_{\theta} }}\times 
\begin{cases}
 \quad\quad p_0 & \text{ otherwise}  \\ 
 e^{\frac{\delta(i, j, m ,n)}{\sigma_{\delta} }}  & \text{ if } h(i, j, m ,n)< r  
\end{cases}
\end{equation} 
where $w$ measures the strength of the translation link between a source word and a target word $(f_i,e_j)$. $\theta(f_i,e_j)=\log(l(i,j))$ is a translation model and $\delta(i, i, m ,n)=\log(1-h(i,j, m ,n))$ is a distortion model. $r$ is a threshold, which depends on language. It usually should take a value in the range $[0.5, 0.9]$. $\sigma_\theta$ and $\sigma_\delta$ are hyper-parameters. To compute the value of $h(i,j, m ,n)$, we assume $h(i,j, m ,n)=|i/m-j/n|$. Although this is not necessary but in our case, we adjust values to a specified range $w(j,i) \in [{p_0}^2, 1)$. Since $\text {\it Ncut}$ is a normalized score, it does not require any normalization term. The hyper-parameters $\sigma_\theta$ and $\sigma_\delta$ are fixed at the beginning of experimentation by maximizing the \textit{Recall} in the preliminary experiments. Since tuning such hyper-parameters for each language pairs is expensive, we just show that it is possible to obtain reasonable results without careful tuning. Figure~\ref{changeTheta} shows how matrices change when changing these hyper-parameters. Since we also want to address the influence of imported distortion sub-model, we performed the comparable experiment. The results are found in Table 5 and Table~\ref{mt_eval}. 

\begin{figure}[t]
\begin{center}
\includegraphics{24-4ia5f2.eps}
\end{center} 
\hangcaption{Grey-scale map of soft alignment matrix. Three sub-graphs without spatial proximity term (top), three with spatial proximity term (bottom).} 
\label{changeTheta} 
\end{figure} 


\subsection{Top-down Parsing and Reranking} 

In \cite{lardilleux2012hierarchical}, 1-best parsing was employed to find the optimal \textit{Ncut} at each layer. However, experimentally, we found that the strategy of 1-best parsing used in the original HSSA does not generate the best global derivation. Hence, we define a scoring function $Score()$ aiming to find the best derivation $\tilde{D}$ 
\pagebreak
with the minimal value:
\begin{equation}
\tilde{D} = \underset{D}{\mbox{ argmin }}  Score(D_{Ncut}|  \mathbf{f},\mathbf{e} ) = \underset{D}{\mbox{argmin}} Score(D_{Ncut}| \mathcal{M} )
\end{equation} 
$D_{Ncut}$ stands for the parser derivation obtained according to $Ncut$. Due to an equivalent way of writing $Ncut$ is the function of arithmetic mean of F-measure, as described in \cite{wang2016yet}, in sub-matrices $(X,Y)$ and $(\bar{X},\bar{Y})$, notes $F_{avg}$:
\begin{equation}
\resizebox{0.5\hsize}{!}{$Ncut(i, j | \gamma) \propto  1-\frac{F_1 (\textnooverline{$X$},\textnooverline{$Y$}) +F_1 (\textoverline{$X$},\textoverline{$Y$})}{2} = 1- F_{avg}  $ } 
\end{equation} 
Where we compute the $F_1$ score as:
\begin{equation}
\resizebox{0.6\hsize}{!}{$F_1 (X,Y) = 1-\frac{  \textnooverline{$asso$}(\textoverline{$X$} ,\textnooverline{$Y$})+\textnooverline{$asso$}(\textnooverline{$X$},\textoverline{$Y$})}{\textnooverline{$2\times$} \textnooverline{$asso$}(\textnooverline{$X$},\textnooverline{$Y$})+ \textnooverline{$asso$}(\textoverline{$X$} ,\textnooverline{$Y$})+\textnooverline{$asso$}(\textnooverline{$X$},\textoverline{$Y$})} $ } 
\end{equation}
With this interpretation, minimizing \textit{Ncut} is equivalent to maximizing the value $F_{avg}$. Intuitively, it suffices to replace \textit{Ncut} with $F_{avg}$ to derive the following formula, the probability of a parsing tree or the probability of a sequence of derivation $D=\{d_0,\dots,d_K\}$ and best word alignment $\mathbf{\hat{a}}$ based on the derivation $\tilde{D}$ can be defined as,
\begin{gather}
\tilde{D} = \underset{D}{\mbox{ argmax }}  Score(D_{F_{avg}}|\mathcal{M} )= \underset{d_k \in D}{\mbox{ argmax }} \prod_{k=0}^{K} {F_{avg}} (d_k) \\
\mathbf{\hat{a}} = Proj(\tilde{D})
\end{gather} 
The use of $Ncut$ or $F_{avg}$ is equivalent. Hence the derivation either $D_{F_{avg}}$ or $D_{Ncut}$ obtained should be same.
$Proj()$ is a projection function A projection function which produces the final word-to-word alignment from the leaves of the BTG parser tree. Let $d_k$ denote the operation of derivation at step $k$, in which $d_k$ is defined as a triple $<i, j, \gamma>$.  During parsing, where $i$ stands for the index of the splitting point on the source side and $j$ stands for the index of the splitting point on the target side. We implement our top-down parser with beam search see Figure~\ref{fig3}. The incremental top-down BTG parsing algorithm used is presented in Algorithm~\ref{alg:the_top_down_alg}. 

\begin{figure}[p]
\begin{center}
\includegraphics{24-4ia5f3.eps}
\end{center} 
\caption{Hierarchical sub-sentential alignment with beam search as top-down BTG forest parsing.}\label{fig3} 
\end{figure} 

\begin{algorithm}[p]
   \caption{Top-Down Parsing}
   \label{alg:the_top_down_alg}
\input{05algo01.txt}
\end{algorithm}

We consider that the incremental parser has a
parser hypothesis at each step. We define the hypothesis
as a four-tuple $\langle P, Q, v, c\rangle$. $P$ is a stack of the unsolved blocks. $Q$ is a list of the previous derivations $\{d_0,\dots,d_{k-1}\}$. A block denoted by $([i_0, i_1),[j_0, j_1))$ covers the source words from $f_{i_0}$ to $f_{i_1-1}$ and the target words from $e_{j_0}$ to $e_{j_1-1}$. $v$ records the current score. We set $c$ to $true$ on termination (stack $P$ is empty). At the beginning, the initial hypothesis contains only a block which covers all the words in the source and target sentences. Then, we split the block in each step, and decide the node type (\textit{straight} or \textit{inverted}) when the splitting point is determined according to the defined score function. $top_k(S)$ returns the first $k$-th hypotheses from stack $S$ in terms of their scores. The computational complexity of the top-down parsing algorithm is $O( n  \times m \times k \times \log \min(m,n))$ for sentence lengths $m, n$, beam size $k$. $\log \min(m,n)$ stands for the parsing depth. For each iteration, each hypothesis in the history will be used to generate new hypotheses as shown in Algorithm~\ref{alg:expand_hypo_alg}. Algorithm~\ref{alg:the_top_down_alg} terminates when no new hypothesis is generated or has reached the maximum number of iterations $\min(m,n)$.

\begin{algorithm}[b]
   \caption{Expand Hypotheses}
   \label{alg:expand_hypo_alg}
\input{05algo02.txt}
\end{algorithm} 

To reduce the time complexity in calculating the value of $asso(A, B)$, we make use of a specialized data structure for fast computation. For each built soft alignment matrix, a summed area table (SAT) is created for fast calculating the summation of cells in the corresponding soft alignment matrix $\mathcal{M}(m,n)$. This preprocessing step is to build a new ($m+1,n+1$) matrix $\mathcal{M'}$, where each entry is the sum of the sub-matrix to the upper-left of that entry. Any arbitrary sub-matrix sum can be calculated by looking up and combining only 4 entries in the SAT. For instance, assume that $A, B$ extends from point ($i_0,j_0$) to point ($i_1,j_1$). We have,
\begin{equation}
asso(A,B ) =  \sum_{i=i_0+1 }^{i_1 }\sum_{j= j_0+1 }^{j_1 } w(i,j)= \mathcal{M'}(i_1,j_1)-\mathcal{M'}(i_0,j_1)  -\mathcal{M'}(i_1,j_0) +\mathcal{M'}(i_0,j_0)
\end{equation}
The time complexity here is reduced from $O(m \times n )$ to $O(1)$ when calculating the summation of all cells in the block of $(A,B)$.


\section{Experiments}
\label{experiment}

\subsection{Data}

We first describe the data used in our experiments. The data sets for word alignment and translation tasks are from the different corpora. For word alignment subtasks, we use the Hansard Corpus\footnote{http://web.eecs.umich.edu/{\textasciitilde}mihalcea/wpt/index.html\#resources} from 2003 NAACL shared task \cite{mihalcea2003evaluation} for English--French and KFTT Corpus\footnote{http://www.phontron.com/kftt/} for English--Japanese. Table~\ref{alignment_corpus} gives some counts on the training set and test set for word alignment evaluation and the training set includes the test set.

\begin{table}[b]
\hangcaption{Statistics of Hansard Corpus and KFTT Corpus for alignment evaluation in our experiment (M: million, K: thousand).}
\label{alignment_corpus}
\input{05table01.txt}
\end{table}

For the translation task, we conduct experiments in several language pairs: English--French (en--fr), English--German (en--de), Spanish-Portuguese (es--pt), English--Japanese (en--ja) and Japanese--English (ja--en). The English--Japanese and Japanese--English subtasks use the KFTT corpus. For English--French, Spanish-Portuguese and English--German, we make use of four different corpora, two large corpora (English--French and English--German) from the WMT 2008 Shared Task\footnote{http://www.statmt.org/wmt08/shared-task.html} and two smaller corpora (English--French and Spanish-Portuguese) from the Europarl Corpus.\footnote{http://www.statmt.org/europarl/} 
For translation evaluation, training, development, test sets are independent. Table~\ref{mt_corpus} gives some statistics on the training, development and test sets.

\begin{table}[t]
\hangcaption{Statistics of data from WMT08 Shared tasks, KFTT Corpus and Europarl Corpus v7 for translation evaluation used in our experiments.}
\label{mt_corpus}
\input{05table02.txt}
\end{table}


\subsection{Experiment Setup}

For word alignment, we preprocess the data by lowercasing. In the case of {\tt {GIZA++}} and {\tt {fast\_align}}, we train word alignments in both directions with the default settings, likes the standard bootstrap for IBM model 4 alignment in {\tt {GIZA++}} as $\{1^5 H^5 3^3 4^3\}$\footnote{$1^5 H^5 3^3 4^3$ denotes 5 iterations for IBM model 1, 5 iterations for HMM model, 3 iterations for IBM model 3, 3 iterations for IBM model 4.} and $5$ iterations in {\tt {fast\_align}}. We then symmetrize the word alignments using \textit{grow-diag-final-and} and evaluate with the final obtained alignments. For our implementation, {\tt {Hieralign}},\footnote{https://github.com/wang-h/Hieralign} in order to limit the run-time to that of {\tt {fast\_align}}, we apply 5 iterations of parameter updates by EM with IBM model 1. Since reestimating the Viterbi probability is very fast when an initial word alignment is given for reference, we also employ various methods to compute $l(f,e)$, like IBM1, IBM1 using variational Bayes (VBIBM1), IBM1 Viterbi with heuristic (IBM1+VBH), IBM1 using variational Bayes Viterbi with heuristic (VBIBM1+VBH), IBM2 Viterbi with heuristic (IBM2+VBH),\footnote{We use the variation of IBM model 2 \cite{dyer2013simple}, which is fast and relatively simple model.} IBM4 Viterbi with heuristic (IBM4+VBH), etc. Figure~\ref{modelSizes} illustrates the size of obtained models using different initialization methods. 

\begin{table}[b]
\hangcaption{Wall-clock time (minutes:seconds) required to obtain the symmetric alignments. The total time also includes the time for symmetrizing asymmetric alignments for {\tt {GIZA++}} and {\tt {fast\_align}} with the standard symmetrization heuristic: \textit{grow-diag-final-and}. ``online'' means that Hieralign can run in the ``online'' mode (a trained model is given). This provides an ``online'' service: when new sentences are input, it directly runs the second step to output word alignments.}
\label{time}
\input{05table03.txt}
\end{table}

\begin{figure}[b]
\begin{center}
\includegraphics{24-4ia5f4.eps}
\end{center} 
\caption{Comparsion of model sizes (\# of entries) with different initialization methods.} 
\label{modelSizes} 
\end{figure} 

Some comparison with other BTG alignment methods is necessary to confirm the advantages of our proposed method. For this consideration, we use another open-sourced BTG-based word aligner, {\tt{pialign}} \cite{neubig-EtAl:2011:ACL-HLT2011},\footnote{http://www.phontron.com/pialign/} which uses hierarchical BTG models (hier). For {\tt{pialign}}, we run it with 8 threads and train the model with batch size 40 and only taking 1 sample during parameter inference. We extract phrases directly from the word-to-word alignment (1-to-many, many-to-1 and many-to-many) with traditional heuristic \cite{koehn2003statistical} for translation. Our BTG-style parsing is on the basic of top-down bi-partitioning. This is different from previous CKY-based models \cite{xiong2010learning,neubig-EtAl:2011:ACL-HLT2011}. In the work \cite{neubig-EtAl:2011:ACL-HLT2011}, they employed another heuristic in phrase extraction rather the standard one \cite{koehn2003statistical}. To make our work traceable, we compare the phrase-table size extracted with the simple heuristic-based phrase extraction \cite{koehn2005edinburgh} with the model-based phrase extraction approach in \cite{neubig-EtAl:2011:ACL-HLT2011}. For scoring phrases, four features are used in each phrase table for all experiments: the conditional phrase probabilities in both directions, $p(f|e)$ and $p(e|f)$, lexical weighting probabilities in both directions, $p_{lex}(f|e)$ and $p_{lex}(e|f)$ \cite{koehn2003statistical}.\footnote{In the experiment reported in \cite{neubig-EtAl:2011:ACL-HLT2011}, three additional features are employed (the joint probability of the phrase, the average posterior probability of a span and the uniform phrase penalty)}

For translation evaluation in all experiments, the phrase-based SMT systems are standard statistical machine translation systems built by using the {\tt {Moses}}\footnote{http://www.statmt.org/moses/} toolkit \cite{koehn2007moses} with Minimum Error Rate Training \cite{och2003minimum} and a 5-gram language model learnt using  {\tt {KenLM}} \cite{heafield2011kenlm}. We use the training set for training translation, lexical reordering, and target language models, the development set for tuning the parameters of the log-linear model in decoding and the test set for evaluation.
For phrase extraction, we employ the traditional heuristic \cite{koehn2003statistical} for all methods used in experiment. In our experiment, the maximum length of phrases entered into phrase table is limited to 7. Before that, \textit{grow-diag-final-and} was used for {\tt {GIZA++}}, {\tt {fast\_align}}. Specially for {\tt {pialign}}, we make use of {\tt {pialign:itgstats.pl}}\footnote{https://github.com/neubig/pialign/tree/master/script} to extract the final word alignments used for phrase extraction. 
The baselines are the PB-SMT systems with the default distortion limit set to 6. We also filter the data to remove the long sentences (more than 100 words) from the training set. We do the same preprocessing (lowercasing and tokenization) using the scripts provided in {\tt {Moses}}\footnote{https://github.com/moses-smt/mosesdecoder/tree/master/scripts/tokenizer} and baseline processing as WAT\footnote{http://lotus.kuee.kyoto-u.ac.jp/WAT/WAT2015/baseline/tools.html} for English-Japanese and Japanese-English. Finally, we conduct translation experiments and compare {\tt {Hieralign}}, {\tt {fast\_align}}, {\tt{pialign}} and {\tt {GIZA++}} for performance and time.  


\subsection{Alignment and Speed Evaluation}

We evaluate the performance of our proposed method and report the performance of various alignment methods in terms of precision, recall and alignment error rate (AER) as defined in \cite{och2003systematic}. Figure~\ref{beamAER} shows that we found the alignment scores improve until a beam size of 20. Larger sizes do not help. In a real situation, given the result in Table~\ref{beam_effect} and Figure~\ref{beamAER} shown, a beam size of 10 should give a reasonable trade-off between time and accuracy (achieved comparable running time and accuracy with {\tt{fast\_align}} see Table 3 and 5). Since our implementation does not require any extra information except the word-to-word translation probabilities, it can be regarded as an online word aligner. 

\begin{table}[t]
\hangcaption{Effect of beam size on alignment quality on Japanese-English data in terms of match number, precision, recall, AER and running time of HSSA. ``Test'' means the total count of word-to-word alignments in the file output by each method. ``Matches'' means the count of ``true positives'' alignment found in the output of each method. }
\label{beam_effect}
\input{05table04.txt}
\end{table}

\begin{figure}[t]
\begin{center}
\includegraphics{24-4ia5f5.eps}
\end{center} 
\hangcaption{Detemining the proper value for beam size acording to AER on the KFTT corpus. Larger beam sizes have lower AER. The default beam size in {\tt {Hieralign}} is setted as 10 given the trade-off between accuracy and speed.} 
\label{beamAER} 
\end{figure}

\begin{table}[t]
\hangcaption{Evaluation of alignment results on Hansard Corpus and KFTT Corpus using various configuration of {\tt{GIZA++}} (+GDFA), {\tt{Fast\_align}} (+GDFA), {\tt{pialign}} and {\tt{Hieralign}}.}
\label{table5}
\input{05table05.txt}
\end{table}

Table~\ref{table5} gives the performance of various alignment profiles on the basis of human annotated alignment data provided with the KFTT Corpus and Hansard Corpus. The first and second lines show the alignment difference using {\tt {GIZA++}} + \textit{grow-diag-final-and} and {\tt {fast\_align}} + \textit{grow-diag-final-and}. From the table,  we found both {\tt {GIZA++}} and {\tt {fast\_align}} output less alignments than {\tt {Hieralign}}. {\tt {Hieralign}} tends to output more matches than {\tt {fast\_align}} but not as much as {\tt {GIZA++}} from the point view of matching alignments and recall against the reference, which we can explain the reason may be: although {\tt {Hieralign}} cannot explore some alignments because of the limitation of BTG constraints, when we force it to align each source and target word, it is prone to group the neighbouring alignments aggressively into the same block. This strategy makes it to output more alignments. AER and precision are behind {\tt {fast\_align}}, even more than {\tt {GIZA++}}. However, \citeA{fraser2007measuring,ganchev2008better} question the link between
this word alignment quality metrics and translation results.
There is no proof that improvements in alignment quality metrics lead to improvements in phrase-based machine translation performance. In other words, a lower AER does not imply a better translation accuracy, and we will show this in the following discussion. When sampling the alignment results, we found that the output of the proposed joint method usually generates more alignments against the reference. From this table, we can also draw the conclusion that adding the distortion feature slightly improves the alignment results. Figure~\ref{comparison4} plots the different alignments output by different methods. 

\begin{figure}[t]
\begin{center}
\includegraphics{24-4ia5f6.eps}
\end{center} 
\hangcaption{Example of alignment matrices output by {\tt {GIZA++}} (+GDFA), {\tt {fast\_align}} (+GDFA) , {\tt {pialign}} and {\tt {Hieralign}}. {\tt {pialign}} only outputs asymmetric block alignments (1-to-m). {\tt {Hieralign}} outputs block alignments which is symmetrical (1-to-m/m-to-1) .}
\label{comparison4}
\end{figure} 

\begin{table}[p]
\hangcaption{BLEU and RIBES scores in translation experiments, $\dag$ means significantly different with the {\tt {fast\_align}} baseline according to statistical significance tests ($\mathrm{p}<0.05$).}
\label{mt_eval}
\input{05table06.txt}
\end{table}

\begin{figure}[p]
\vspace{1\Cvs}
\begin{center}
\includegraphics{24-4ia5f7.eps}
\end{center} 
\hangcaption{Phrase-table sizes (\# of entries) using {\tt {GIZA++}} (+GDFA), {\tt {fast\_align}} (+GDFA), {\tt {pialign}} and {\tt {Hieralign}} with heuristic of phrase extraction (Koehn et al. 2003). For {\tt {pialign}}, we also give the size of the table using model-based extraction (MOD) (Neubig et al. 2011).} 
\label{figure3}
\end{figure} 


\subsection{Translation Evaluation}

Since we proposed to solve the problem of discontiguity in phrase extraction because of discontiguous alignment. We force the word alignment at least 1-1, which should generate fewer entries in the translation tables. We also measured the sizes of the translation tables obtained. Figure~\ref{figure3} shows the comparison of phrase tables. 
We compare the translations produced by our method to those produced by Vitebi-based aligner {\tt {GIZA++}} (+GDFA), {\tt {fast\_align}} (+GDFA) and BTG-based aligner {\tt {pialign}}. For the evaluation of machine translation accuracy, some standard automatic evaluation metrics have been used: BLEU \cite{papineni2002bleu} and RIBES \cite{isozaki2010automatic}. In order to compare the performance between MT systems, we also apply bootstrap re-sampling method as described in \cite{koehn2004statistical}. The results in Table~\ref{mt_eval} show that the final translation scores are approximately the same. There is insignificant difference on the final results of machine translation when using the alignments output by the proposed method and those output by {\tt {GIZA++}} or {\tt {fast\_align}}. It can be seen {\tt {GIZA++}} and {\tt {fast\_align}} have comparable BLEU score but {\tt {pialign}} (MOD) and our methods slightly behind the baseline on a very large size corpus. From Figure~\ref{figure3}, we found that {\tt {pialign}} (MOD) 
can significantly reduce the phrase table sizes while the traditional heuristic phrase extraction methods were not able to be observed. 
For our method {\tt {Hieralign}}, we use (IBM 1+ VBH) to represent the remains, because tables obtained using {\tt {Hieralign}} with differently initialized parameters have approximately the same size. The findings are not unexpected but are relevant, the size of the phrase table obtained from the alignments produced by {\tt {Hieralign}} is smaller by a third in comparison to those of the baseline in (en--fr, en--de, es--pt) (see Figure~\ref{figure3}, right). In en--ja and ja--en, that is reduced by even two thirds (see Figure~\ref{figure3}, left). {\tt {pialign}} achieve a higher reduction ratio using model-based phrase extraction approach (MOD) than our method {\tt {pialign}} but remember the training for {\tt {pialign}} is really time-consuming (much more than 4 hours in our experiment while {\tt {Hieralign}} is 2 minutes) and the translation results were not superior to our method. 


\section{Conclusion}

In this paper, we proposed a novel joint hierarchical sub-sentential alignment method on the basis of IBM models. Our proposed method has several advantages: it is simple, fast and delivers small phrase tables. 
To summarize, when restricting the search space against all the possible permutations during aligning using BTG constraints, our BTG-forest-based alignment method can get better results than the previous best-1 hierarchical alignment method \cite{lardilleux2012hierarchical}. 
Experiments on word alignment showed that our proposed method align more words than other methods so as to largely reduced the phrase tables. 
Phrase-based machine translation systems using the smaller phrase tables produced by our method were able to achieve comparable results, even better results on distant language pairs, like English-Japanese, with the traditional phrase extraction pipeline. The final experiment results show our method keeps the translation quality without significantly different while the speed of our methods was comparable with {\tt {fast\_align}}. As for future work, we will investigate better ways to build soft matrices using neural-based attention models, and we expect it deliver a better result. We will also investigate the possibility of using bilingual word-embedding vectors in our proposed framework.


\acknowledgment

This work is supported in part by China Scholarship Council (CSC) under the CSC Grant No. 201406890026. We also thank the anonymous reviewers for their insightful comments. 


\bibliographystyle{jnlpbbl_1.5}
\begin{thebibliography}{}

\bibitem[\protect\BCAY{Brown, Cocke, Pietra, Pietra, Jelinek, Mercer, \BBA\
  Roossin}{Brown et~al.}{1988}]{brown1988statistical}
Brown, P., Cocke, J., Pietra, S.~D., Pietra, V.~D., Jelinek, F., Mercer, R.,
  \BBA\ Roossin, P. \BBOP 1988\BBCP.
\newblock \BBOQ A Statistical Approach to Language Translation.\BBCQ\
\newblock In {\Bem Proceedings of the 12th Conference on Computational
  Linguistics}, \lowercase{\BVOL}~1, \mbox{\BPGS\ 71--76}. Association for
  Computational Linguistics.

\bibitem[\protect\BCAY{Brown, Pietra, Pietra, \BBA\ Mercer}{Brown
  et~al.}{1993}]{brown1993mathematics}
Brown, P.~F., Pietra, V. J.~D., Pietra, S. A.~D., \BBA\ Mercer, R.~L. \BBOP
  1993\BBCP.
\newblock \BBOQ The Mathematics of Statistical Machine Translation: Parameter
  Estimation.\BBCQ\
\newblock {\Bem Computational Linguistics}, {\Bbf 19}  (2), \mbox{\BPGS\
  263--311}.

\bibitem[\protect\BCAY{Cherry \BBA\ Lin}{Cherry \BBA\
  Lin}{2007}]{cherry2007inversion}
Cherry, C.\BBACOMMA\ \BBA\ Lin, D. \BBOP 2007\BBCP.
\newblock \BBOQ Inversion Transduction Grammar for Joint Phrasal Translation
  Modeling.\BBCQ\
\newblock In {\Bem Proceedings of the NAACL-HLT 2007/AMTA Workshop on Syntax
  and Structure in Statistical Translation}, \mbox{\BPGS\ 17--24}. Association
  for Computational Linguistics.

\bibitem[\protect\BCAY{Chiang}{Chiang}{2007}]{chiang2007hierarchical}
Chiang, D. \BBOP 2007\BBCP.
\newblock \BBOQ Hierarchical Phrase-based Translation.\BBCQ\
\newblock {\Bem Computational Linguistics}, {\Bbf 33}  (2), \mbox{\BPGS\
  201--228}.

\bibitem[\protect\BCAY{Cohn \BBA\ Haffari}{Cohn \BBA\
  Haffari}{2013}]{cohn2013infinite}
Cohn, T.\BBACOMMA\ \BBA\ Haffari, G. \BBOP 2013\BBCP.
\newblock \BBOQ An Infinite Hierarchical Bayesian Model of Phrasal
  Translation.\BBCQ\
\newblock In {\Bem Proceedings of the 51st Annual Meeting of the Association
  for Computational Linguistics (ACL 2013), Volume 1}, \mbox{\BPGS\ 780--790}.

\bibitem[\protect\BCAY{Dempster, Laird, \BBA\ Rubin}{Dempster
  et~al.}{1977}]{dempster1977maximum}
Dempster, A.~P., Laird, N.~M., \BBA\ Rubin, D.~B. \BBOP 1977\BBCP.
\newblock \BBOQ Maximum Likelihood from Incomplete Data via the EM
  Algorithm.\BBCQ\
\newblock {\Bem Journal of the Royal Statistical Society. Series B}, {\Bbf 39},
  \mbox{\BPGS\ 1--38}.

\bibitem[\protect\BCAY{Ding, Utiyama, \BBA\ Sumita}{Ding
  et~al.}{2015}]{ding2015improving}
Ding, C., Utiyama, M., \BBA\ Sumita, E. \BBOP 2015\BBCP.
\newblock \BBOQ Improving fast\_align by Reordering.\BBCQ\
\newblock In {\Bem Proceedings of the on Empirical Methods on Natural Language
  Processing}, \mbox{\BPGS\ 1034--1039}. Association for Computational
  Linguistics.

\bibitem[\protect\BCAY{Dyer, Chahuneau, \BBA\ Smith}{Dyer
  et~al.}{2013}]{dyer2013simple}
Dyer, C., Chahuneau, V., \BBA\ Smith, N.~A. \BBOP 2013\BBCP.
\newblock \BBOQ A Simple, Fast, and Effective Reparameterization of IBM Model
  2.\BBCQ\
\newblock In {\Bem Proceedings for the NAACL}, \mbox{\BPGS\ 644--648}.
  Association for Computational Linguistics.

\bibitem[\protect\BCAY{Fraser \BBA\ Marcu}{Fraser \BBA\
  Marcu}{2007}]{fraser2007measuring}
Fraser, A.\BBACOMMA\ \BBA\ Marcu, D. \BBOP 2007\BBCP.
\newblock \BBOQ Measuring Word Alignment Quality for Statistical Machine
  Translation.\BBCQ\
\newblock {\Bem Computational Linguistics}, {\Bbf 33}  (3), \mbox{\BPGS\
  293--303}.

\bibitem[\protect\BCAY{Ganchev, Graca, \BBA\ Taskar}{Ganchev
  et~al.}{2008}]{ganchev2008better}
Ganchev, K., Graca, J.~V., \BBA\ Taskar, B. \BBOP 2008\BBCP.
\newblock \BBOQ Better Alignments = Better Translations?\BBCQ\
\newblock In {\Bem ACL-08: HLT}, \mbox{\BPG\ 986}. Association for
  Computational Linguistics.

\bibitem[\protect\BCAY{Haghighi, Blitzer, DeNero, \BBA\ Klein}{Haghighi
  et~al.}{2009}]{haghighi2009better}
Haghighi, A., Blitzer, J., DeNero, J., \BBA\ Klein, D. \BBOP 2009\BBCP.
\newblock \BBOQ Better Word Alignments with Supervised ITG Models.\BBCQ\
\newblock In {\Bem Proceedings of the Joint Conference of the 47th Annual
  Meeting of the ACL and the 4th International Joint Conference on Natural
  Language Processing of the AFNLP: Volume 2}, \mbox{\BPGS\ 923--931}.
  Association for Computational Linguistics.

\bibitem[\protect\BCAY{Heafield}{Heafield}{2011}]{heafield2011kenlm}
Heafield, K. \BBOP 2011\BBCP.
\newblock \BBOQ KenLM: Faster and Smaller Language Model Queries.\BBCQ\
\newblock In {\Bem Proceedings of the 6th Workshop on Statistical Machine
  Translation}, \mbox{\BPGS\ 187--197}. Association for Computational
  Linguistics.

\bibitem[\protect\BCAY{Isozaki, Hirao, Duh, Sudoh, \BBA\ Tsukada}{Isozaki
  et~al.}{2010}]{isozaki2010automatic}
Isozaki, H., Hirao, T., Duh, K., Sudoh, K., \BBA\ Tsukada, H. \BBOP 2010\BBCP.
\newblock \BBOQ Automatic Evaluation of Translation Quality for Distant
  Language Pairs.\BBCQ\
\newblock In {\Bem Proceedings of the 2010 Conference on Empirical Methods in
  Natural Language Processing}, \mbox{\BPGS\ 944--952}. Association for
  Computational Linguistics.

\bibitem[\protect\BCAY{Kamigaito, Tamura, Takamura, Okumura, \BBA\
  Sumita}{Kamigaito et~al.}{2016}]{kamigaitounsupervised}
Kamigaito, H., Tamura, A., Takamura, H., Okumura, M., \BBA\ Sumita, E. \BBOP
  2016\BBCP.
\newblock \BBOQ Unsupervised Word Alignment by Agreement Under ITG
  Constraint.\BBCQ\
\newblock In {\Bem EMNLP}, \mbox{\BPGS\ 1998--2004}.

\bibitem[\protect\BCAY{Koehn}{Koehn}{2004}]{koehn2004statistical}
Koehn, P. \BBOP 2004\BBCP.
\newblock \BBOQ Statistical Significance Tests for Machine Translation
  Evaluation.\BBCQ\
\newblock In {\Bem EMNLP}, \mbox{\BPGS\ 388--395}. Citeseer.

\bibitem[\protect\BCAY{Koehn, Axelrod, Birch, Callison-Burch, Osborne, Talbot,
  \BBA\ White}{Koehn et~al.}{2005}]{koehn2005edinburgh}
Koehn, P., Axelrod, A., Birch, A., Callison-Burch, C., Osborne, M., Talbot, D.,
  \BBA\ White, M. \BBOP 2005\BBCP.
\newblock \BBOQ Edinburgh System Description for the 2005 IWSLT Speech
  Translation Evaluation.\BBCQ\
\newblock In {\Bem IWSLT}, \mbox{\BPGS\ 68--75}.

\bibitem[\protect\BCAY{Koehn, Hoang, Birch, Callison-Burch, Federico, Bertoldi,
  Cowan, Shen, Moran, Zens, Dyer, Bojar, Constantin, \BBA\ Herbst}{Koehn
  et~al.}{2007}]{koehn2007moses}
Koehn, P., Hoang, H., Birch, A., Callison-Burch, C., Federico, M., Bertoldi,
  N., Cowan, B., Shen, W., Moran, C., Zens, R., Dyer, C., Bojar, O.,
  Constantin, A., \BBA\ Herbst, E. \BBOP 2007\BBCP.
\newblock \BBOQ Moses: Open Source Toolkit for Statistical Machine
  Translation.\BBCQ\
\newblock In {\Bem Proceedings of the 45th Annual Meeting of the ACL on
  Interactive Poster and Demonstration Sessions}, \mbox{\BPGS\ 177--180}.
  Association for Computational Linguistics.

\bibitem[\protect\BCAY{Koehn, Och, \BBA\ Marcu}{Koehn
  et~al.}{2003}]{koehn2003statistical}
Koehn, P., Och, F.~J., \BBA\ Marcu, D. \BBOP 2003\BBCP.
\newblock \BBOQ Statistical Phrase-based Translation.\BBCQ\
\newblock In {\Bem Proceedings of the 2003 Conference of the North American
  Chapter of the Association for Computational Linguistics on Human Language
  Technology}, \lowercase{\BVOL}~1, \mbox{\BPGS\ 48--54}. Association for
  Computational Linguistics.

\bibitem[\protect\BCAY{Lardilleux, Yvon, \BBA\ Lepage}{Lardilleux
  et~al.}{2012}]{lardilleux2012hierarchical}
Lardilleux, A., Yvon, F., \BBA\ Lepage, Y. \BBOP 2012\BBCP.
\newblock \BBOQ Hierarchical Sub-sentential Alignment with Anymalign.\BBCQ\
\newblock In {\Bem Proceedings of the 16th Annual Conference of the European
  Association for Machine Translation}, \mbox{\BPGS\ 279--286}.

\bibitem[\protect\BCAY{Li, Yang, \BBA\ Sun}{Li et~al.}{2012}]{li2012beam}
Li, P., Yang, L., \BBA\ Sun, M. \BBOP 2012\BBCP.
\newblock \BBOQ A Beam Search Algorithm for ITG Word Alignment.\BBCQ\
\newblock In {\Bem Proceedings of the 24th International Conference on
  Computational Linguistics}, \mbox{\BPG\ 673}.

\bibitem[\protect\BCAY{Liang, Taskar, \BBA\ Klein}{Liang
  et~al.}{2006}]{liang2006alignment}
Liang, P., Taskar, B., \BBA\ Klein, D. \BBOP 2006\BBCP.
\newblock \BBOQ Alignment by Agreement.\BBCQ\
\newblock In {\Bem Proceedings of the Main Conference on Human Language
  Technology Conference of the North American Chapter of the Association of
  Computational Linguistics}, \mbox{\BPGS\ 104--111}. Association for
  Computational Linguistics.

\bibitem[\protect\BCAY{Liu, Liu, \BBA\ Lin}{Liu et~al.}{2006}]{liu2006tree}
Liu, Y., Liu, Q., \BBA\ Lin, S. \BBOP 2006\BBCP.
\newblock \BBOQ Tree-to-string Alignment Template for Statistical Machine
  Translation.\BBCQ\
\newblock In {\Bem Proceedings of the 21st International Conference on
  Computational Linguistics and the 44th Annual Meeting of the Association for
  Computational Linguistics}, \mbox{\BPGS\ 609--616}. Association for
  Computational Linguistics.

\bibitem[\protect\BCAY{Liu, Liu, \BBA\ Lin}{Liu
  et~al.}{2010}]{liu2010discriminative}
Liu, Y., Liu, Q., \BBA\ Lin, S. \BBOP 2010\BBCP.
\newblock \BBOQ Discriminative Word Alignment by Linear Modeling.\BBCQ\
\newblock {\Bem Computational Linguistics}, {\Bbf 36}  (3), \mbox{\BPGS\
  303--339}.

\bibitem[\protect\BCAY{Liu, Xia, Xiao, \BBA\ Liu}{Liu
  et~al.}{2009}]{liu2009weighted}
Liu, Y., Xia, T., Xiao, X., \BBA\ Liu, Q. \BBOP 2009\BBCP.
\newblock \BBOQ Weighted Alignment Matrices for Statistical Machine
  Translation.\BBCQ\
\newblock In {\Bem Proceedings of the 2009 Conference on Empirical Methods in
  Natural Language Processing}, \lowercase{\BVOL}~2, \mbox{\BPGS\ 1017--1026}.
  Association for Computational Linguistics.

\bibitem[\protect\BCAY{Matusov, Zens, \BBA\ Ney}{Matusov
  et~al.}{2004}]{matusov2004symmetric}
Matusov, E., Zens, R., \BBA\ Ney, H. \BBOP 2004\BBCP.
\newblock \BBOQ Symmetric Word Alignments for Statistical Machine
  Translation.\BBCQ\
\newblock In {\Bem Proceedings of the 20th International Conference on
  Computational Linguistics}, \mbox{\BPG\ 219}. Association for Computational
  Linguistics.

\bibitem[\protect\BCAY{Mermer \BBA\ Saraclar}{Mermer \BBA\
  Saraclar}{2011}]{mermer2011bayesian}
Mermer, C.\BBACOMMA\ \BBA\ Saraclar, M. \BBOP 2011\BBCP.
\newblock \BBOQ Bayesian Word Alignment for Statistical Machine
  Translation.\BBCQ\
\newblock In {\Bem Proceedings of the 49th Annual Meeting of the Association
  for Computational Linguistics: Human Language Technologies: short papers},
  \lowercase{\BVOL}~2, \mbox{\BPGS\ 182--187}. Association for Computational
  Linguistics.

\bibitem[\protect\BCAY{Mihalcea \BBA\ Pedersen}{Mihalcea \BBA\
  Pedersen}{2003}]{mihalcea2003evaluation}
Mihalcea, R.\BBACOMMA\ \BBA\ Pedersen, T. \BBOP 2003\BBCP.
\newblock \BBOQ An Evaluation Exercise for Word Alignment.\BBCQ\
\newblock In {\Bem Proceedings of the HLT-NAACL 2003 Workshop on Building and
  using Parallel Texts: Data Driven Machine Translation and Beyond},
  \lowercase{\BVOL}~3, \mbox{\BPGS\ 1--10}. Association for Computational
  Linguistics.

\bibitem[\protect\BCAY{Moore}{Moore}{2005}]{moore2005association}
Moore, R.~C. \BBOP 2005\BBCP.
\newblock \BBOQ Association-based Bilingual Word Alignment.\BBCQ\
\newblock In {\Bem Proceedings of the ACL Workshop on Building and Using
  Parallel Texts}, \mbox{\BPGS\ 1--8}. Association for Computational
  Linguistics.

\bibitem[\protect\BCAY{Neubig, Watanabe, Mori, \BBA\ Kawahara}{Neubig
  et~al.}{2012}]{neubig2012machine}
Neubig, G., Watanabe, T., Mori, S., \BBA\ Kawahara, T. \BBOP 2012\BBCP.
\newblock \BBOQ Machine Translation without Words Through Substring
  Alignment.\BBCQ\
\newblock In {\Bem Proceedings of the 50th Annual Meeting of the Association
  for Computational Linguistics}, \mbox{\BPGS\ 165--174}. Association for
  Computational Linguistics.

\bibitem[\protect\BCAY{Neubig, Watanabe, Sumita, Mori, \BBA\ Kawahara}{Neubig
  et~al.}{2011}]{neubig-EtAl:2011:ACL-HLT2011}
Neubig, G., Watanabe, T., Sumita, E., Mori, S., \BBA\ Kawahara, T. \BBOP
  2011\BBCP.
\newblock \BBOQ An Unsupervised Model for Joint Phrase Alignment and
  Extraction.\BBCQ\
\newblock In {\Bem Proceedings of the 49th Annual Meeting of the Association
  for Computational Linguistics: Human Language Technologies}, \mbox{\BPGS\
  632--641}, Portland, Oregon, USA. Association for Computational Linguistics.

\bibitem[\protect\BCAY{Och}{Och}{2003}]{och2003minimum}
Och, F.~J. \BBOP 2003\BBCP.
\newblock \BBOQ Minimum Error Rate Training in Statistical Machine
  Translation.\BBCQ\
\newblock In {\Bem Proceedings of the 41st Annual Meeting on Association for
  Computational Linguistics}, \lowercase{\BVOL}~1, \mbox{\BPGS\ 160--167}.
  Association for Computational Linguistics.

\bibitem[\protect\BCAY{Och \BBA\ Ney}{Och \BBA\ Ney}{2003}]{och2003systematic}
Och, F.~J.\BBACOMMA\ \BBA\ Ney, H. \BBOP 2003\BBCP.
\newblock \BBOQ A Systematic Comparison of Various Statistical Alignment
  Models.\BBCQ\
\newblock {\Bem Computational Linguistics}, {\Bbf 29}  (1), \mbox{\BPGS\
  19--51}.

\bibitem[\protect\BCAY{Papineni, Roukos, Ward, \BBA\ Zhu}{Papineni
  et~al.}{2002}]{papineni2002bleu}
Papineni, K., Roukos, S., Ward, T., \BBA\ Zhu, W.-J. \BBOP 2002\BBCP.
\newblock \BBOQ BLEU: A Method for Automatic Evaluation of Machine
  Translation.\BBCQ\
\newblock In {\Bem Proceedings of the 40th ACL}, \mbox{\BPGS\ 311--318}.
  Association for Computational Linguistics.

\bibitem[\protect\BCAY{Riesa \BBA\ Marcu}{Riesa \BBA\
  Marcu}{2010}]{riesa2010hierarchical}
Riesa, J.\BBACOMMA\ \BBA\ Marcu, D. \BBOP 2010\BBCP.
\newblock \BBOQ Hierarchical Search for Word Alignment.\BBCQ\
\newblock In {\Bem Proceedings of the 48th Annual Meeting of the Association
  for Computational Linguistics}, \mbox{\BPGS\ 157--166}. Association for
  Computational Linguistics.

\bibitem[\protect\BCAY{Riley \BBA\ Gildea}{Riley \BBA\
  Gildea}{2012}]{riley2012improving}
Riley, D.\BBACOMMA\ \BBA\ Gildea, D. \BBOP 2012\BBCP.
\newblock \BBOQ Improving the IBM Alignment Models using Variational
  Bayes.\BBCQ\
\newblock In {\Bem Proceedings of the 50th Annual Meeting of the Association
  for Computational Linguistics: Short Papers}, \lowercase{\BVOL}~2,
  \mbox{\BPGS\ 306--310}. Association for Computational Linguistics.

\bibitem[\protect\BCAY{Shi \BBA\ Malik}{Shi \BBA\
  Malik}{2000}]{shi2000normalized}
Shi, J.\BBACOMMA\ \BBA\ Malik, J. \BBOP 2000\BBCP.
\newblock \BBOQ Normalized Cuts and Image Segmentation.\BBCQ\
\newblock {\Bem IEEE Transactions on Pattern Analysis and Machine
  Intelligence}, {\Bbf 22}  (8), \mbox{\BPGS\ 888--905}.

\bibitem[\protect\BCAY{Vogel, Ney, \BBA\ Tillmann}{Vogel
  et~al.}{1996}]{vogel1996hmm}
Vogel, S., Ney, H., \BBA\ Tillmann, C. \BBOP 1996\BBCP.
\newblock \BBOQ HMM-based Word Alignment in Statistical Translation.\BBCQ\
\newblock In {\Bem Proceedings of the 16th Conference on Computational
  Linguistics}, \lowercase{\BVOL}~2, \mbox{\BPGS\ 836--841}. Association for
  Computational Linguistics.

\bibitem[\protect\BCAY{Wang \BBA\ Lepage}{Wang \BBA\
  Lepage}{2016a}]{wang2016combining}
Wang, H.\BBACOMMA\ \BBA\ Lepage, Y. \BBOP 2016a\BBCP.
\newblock \BBOQ Combining fast\_align with Hierarchical Sub-sentential
  Alignment for Better Word Alignments.\BBCQ\
\newblock In {\Bem Proceedings of the 6th Workshop on Hybrid Approaches to
  Translation, COLING 2016}, \mbox{\BPGS\ 1--7}.

\bibitem[\protect\BCAY{Wang \BBA\ Lepage}{Wang \BBA\
  Lepage}{2016b}]{wang2016yet}
Wang, H.\BBACOMMA\ \BBA\ Lepage, Y. \BBOP 2016b\BBCP.
\newblock \BBOQ Yet Another Symmetrical and Real-time Word Alignment Method:
  Hierarchical Sub-sentential Alignment using F-measure.\BBCQ\
\newblock In {\Bem Proceedings of the 30th Pacific Asia Conference on Language,
  Information and Computation}, \mbox{\BPGS\ 143--152}. PALCIC.

\bibitem[\protect\BCAY{Wang, Knight, \BBA\ Marcu}{Wang
  et~al.}{2007}]{wang2007binarizing}
Wang, W., Knight, K., \BBA\ Marcu, D. \BBOP 2007\BBCP.
\newblock \BBOQ Binarizing Syntax Trees to Improve Syntax-Based Machine
  Translation Accuracy.\BBCQ\
\newblock In {\Bem EMNLP-CoNLL}, \mbox{\BPGS\ 746--754}. Citeseer.

\bibitem[\protect\BCAY{Wu}{Wu}{1995}]{wu1995stochastic}
Wu, D. \BBOP 1995\BBCP.
\newblock \BBOQ Stochastic Inversion Transduction Grammars, with Application to
  Segmentation, Bracketing, and Alignment of Parallel Corpora.\BBCQ\
\newblock In {\Bem Proceedings of the 14th International Joint Conference on
  Artificial Intelligence}, \lowercase{\BVOL}~95, \mbox{\BPGS\ 1328--1335}.

\bibitem[\protect\BCAY{Wu}{Wu}{1997}]{wu1997stochastic}
Wu, D. \BBOP 1997\BBCP.
\newblock \BBOQ Stochastic Inversion Transduction Grammars and Bilingual
  Parsing of Parallel Corpora.\BBCQ\
\newblock {\Bem Computational Linguistics}, {\Bbf 23}  (3), \mbox{\BPGS\
  377--403}.

\bibitem[\protect\BCAY{Wu \BBA\ Wang}{Wu \BBA\ Wang}{2007}]{wu2007comparative}
Wu, H.\BBACOMMA\ \BBA\ Wang, H. \BBOP 2007\BBCP.
\newblock \BBOQ Comparative Study of Word Alignment Heuristics and Phrase-based
  SMT.\BBCQ\
\newblock In {\Bem Proceedings of the MT Summit XI}.

\bibitem[\protect\BCAY{Xiong, Zhang, \BBA\ Li}{Xiong
  et~al.}{2010}]{xiong2010learning}
Xiong, D., Zhang, M., \BBA\ Li, H. \BBOP 2010\BBCP.
\newblock \BBOQ Learning Translation Boundaries for Phrase-based
  Decoding.\BBCQ\
\newblock In {\Bem Proceedings of the Annual Conference of the North American
  Chapter of the Association for Computational Linguistics: Human Language
  Technologies}, \mbox{\BPGS\ 136--144}. Association for Computational
  Linguistics.

\bibitem[\protect\BCAY{Zens, Ney, Watanabe, \BBA\ Sumita}{Zens
  et~al.}{2004}]{zens2004reordering}
Zens, R., Ney, H., Watanabe, T., \BBA\ Sumita, E. \BBOP 2004\BBCP.
\newblock \BBOQ Reordering Constraints for Phrase-based Statistical Machine
  Translation.\BBCQ\
\newblock In {\Bem Proceedings of the 20th International Conference on
  Computational Linguistics}, \mbox{\BPG\ 205}. Association for Computational
  Linguistics.

\bibitem[\protect\BCAY{Zha, He, Ding, Simon, \BBA\ Gu}{Zha
  et~al.}{2001}]{zha2001bipartite}
Zha, H., He, X., Ding, C., Simon, H., \BBA\ Gu, M. \BBOP 2001\BBCP.
\newblock \BBOQ Bipartite Graph Partitioning and Data Clustering.\BBCQ\
\newblock In {\Bem Proceedings of the 10th International Conference on
  Information and knowledge Management}, \mbox{\BPGS\ 25--32}. ACM.

\bibitem[\protect\BCAY{Zhang \BBA\ Gildea}{Zhang \BBA\
  Gildea}{2005}]{zhang2005stochastic}
Zhang, H.\BBACOMMA\ \BBA\ Gildea, D. \BBOP 2005\BBCP.
\newblock \BBOQ Stochastic Lexicalized Inversion Transduction Grammar for
  Alignment.\BBCQ\
\newblock In {\Bem Proceedings of the 43rd Annual Meeting on Association for
  Computational Linguistics}, \mbox{\BPGS\ 475--482}. Association for
  Computational Linguistics.

\bibitem[\protect\BCAY{Zhang, Jiang, Aw, Sun, Li, \BBA\ Tan}{Zhang
  et~al.}{2007}]{zhang2007tree}
Zhang, M., Jiang, H., Aw, A., Sun, J., Li, S., \BBA\ Tan, C.~L. \BBOP
  2007\BBCP.
\newblock \BBOQ A Tree-to-tree Alignment-based Model for Statistical Machine
  Translation.\BBCQ\
\newblock In {\Bem MT-Summit-07}, \mbox{\BPGS\ 535--542}.

\end{thebibliography}


\begin{biography}
\bioauthor[:]{Hao Wang}{
Hao Wang received his M.E. from Waseda University and M.Sc from Shanghai University in 2014. He is currently a Ph.D. candidate at Graduate School of Information, Production and Systems, Waseda University, supported by Oversea Graduate Student Project of the China Scholarship Council. His research interests include natural language processing, especially machine translation. 
}

\bioauthor[:]{Yves Lepage}{
Yves Lepage received his Ph.D. degree from GETA, Grenoble university, France.
He worked for ATR labs, Japan, as an invited researcher and a senior researcher
until 2006. He joined Waseda University, Graduate School of Information, Production and Systems in April 2010. He is a member of the Information Processing
Society of Japan, the Japanese Natural Language Processing Association, and the French Natural Language Processing Association, ATALA. He was editor-in-chief of the French journal on Natural Language Processing, TAL, from 2008 to 2016.
}
\end{biography}

\biodate



\end{document}
