    \documentclass[english]{jnlp_2.1}

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

\usepackage{multirow}
\makeatletter
\newcommand*{\rom}[1]{\expandafter\@slowromancap\romannumeral #1@}
\makeatother


\Volume{25}
\Number{5}
\Month{December}
\Year{2018}

\received{2018}{2}{23}
\revised{2018}{7}{26}
\accepted{2018}{8}{30}


\setcounter{page}{487}

\esubject{Paper}
\etitle{Improved BTG-based Preordering for SMT via Parallel Parameter Averaging: An Empirical Study}
\eauthor{Hao Wang\affiref{Author_1} \and Yves Lepage\affiref{Author_1}} 
\eabstract{
Preordering has proven useful in improving the translation quality of statistical machine translation (SMT), especially for language pairs with different syntax. The top-down bracketing transduction grammar (BTG)-based preordering method \cite{nakagawa2015efficient} has achieved a state-of-the-art performance since it relies on aligned parallel text only and deos not require any linguistic annotations. Although this online learning algorithm adopted is efficient and effective, it is very susceptible to alignment errors. In a production environment, in particular, such a preorderer is commonly trained on noisy word alignments obtained using an automatic word aligner, resulting in a worse performance compared to those trained on manually annotated datasets. In order to achieve better preordering using automatically aligned datasets, this paper seeks to improve the top-down BTG-based preordering method using various parameter mixing techniques to increase the accuracy of the preorderer and speed up training via parallelisation. The parameters mixing methods and the original online training method \cite{nakagawa2015efficient} were empirically compared, and the experimental results show that such parallel parameter averaging methods can dramatically reduce the training time and improve the quality of preordering.
}
\ekeywords{Preordering, Machine Translation, Parallelisation}

\headauthor{Wang and Lepage}
\headtitle{Improved BTG-based Preordering via Parallel Parameter Averaging}

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


\begin{document}

\maketitle


\section{Introduction}

Preordering is an essential preprocessing step in statistical machine translation \cite{koehn2003statistical}, especially for language pairs with different syntax. When translating from a subject-verb-object (SVO) language such as English to a subject-object-verb (SOV) language such as Japanese, the English verb in a sentence often moves to the end of the Japanese sentence/clause. Phrase-based SMT (PB-SMT) exhibits lower BLEU scores on distant language pairs, like English--Japanese, because the lexical reordering component used in PB-SMT is incapable of performing long-distance reorderings \cite{sudoh2010divide} owing to different word orders.

To cope with this problem, previous studies have investigated reordering before word alignment as it is in the preprocessing phase of SMT, called \textit{preordering}. Preordering has been proven to improve the translation of language pairs with different word orders \cite{xia2004improving,collins2005clause} as it reduces the complexity of decoding due to the source words being permuted in the word order of the target language. The majority of those works tend to employ a syntactic parser for the source language, and other methods only rely on word-aligned parallel text. \citeA{denero2011inducing} showed that it is possible to learn some reordering rules from source sentences, after which \citeA{neubig2012inducing} proposed to learn a discriminative parser (also called \textit{preorderer}) directly for preordering by treating hidden synchronous parse trees as latent variables. The training time of the parser substantially increases if the data contain many long sentences because of the high complexity ($O(n^5)$) of the used algorithm, i.e., the bottom-up CYK algorithm.  \citeA{nakagawa2015efficient} adopted the top-down parsing algorithm to improve the parser efficiency ($O(kn^2)$ ) for a beam width of $k$ and sentence length $n$, but training such a preorderer on large datasets is still very time-consuming.

Regarding the quality of the training data, Nakagawa's top-down BTG-based preordering method learns the reordering model using the general framework of large-margin online structured prediction \cite{crammer2006online,watanabe2007online}. To train an accurate preorderer, high quality word alignments are essentia but given the expensive cost of manual annotation, production environment often produce word alignments automatically using unsupervised word aligners. The top-down BTG-based preordering method, which is using such an online training algorithm, suffers from small mistakes in training examples. The resulting preorderer trained on large automatically aligned datasets exhibits lower reordering scores. 


The online pairwise updating strategy used in the top-down BTG-based preordering method is not suitable for training on automatically aligned datasets, given its inability to deal with massive, noisy alignment errors. A large body of research on batch learning and ensemble learning has been empirically observed to be helpful in handling noisy training data for many NLP tasks \cite{breiman1996bagging,freund1999large,dvzeroski2004combining,rokach2010ensemble,li2014efficient}. These methods mainly fall into two categories: inner parameter mixing methods and outer parameter mixing methods. The inner parameter mixing methods perform parameter mixing on small batches, called \textit{mini-batch} training in machine learning  \cite{freund1999large,li2014efficient}. The outer parameter mixing methods are part of the framework of \textit{distributed training}  in machine learning \cite{mcdonald2010distributed}, or \textit{ensemble learning} in neural network research \cite{naftaly1997optimal,dietterich2000ensemble}. A small number of studies have concentrated on online to parallel conversions, despite the simplicity of using parameter mixing techniques to improve the top-down BTG-based preordering method.

This paper investigates the training of a top-down BTG-based preorderer using parameter averaging techniques. The training algorithm was parallelised using bootstrap aggregating with several techniques (mini-batch, distributed, iterative distributed and k-best list), and these methods were empirically compared with the original online method used by \citeA{nakagawa2015efficient}. The experimental results in Section~\ref{exp_results} show that the proposed methods, which were more robust and stable, surpassed that of \cite{nakagawa2015efficient} when using automatically aligned datasets.


\section{Preordering}

\subsection{Background}

Preivous research has shown that preordering can improve SMT \cite{xia2004improving,neubig2012inducing,lerner2013source,goto2015preordering,nakagawa2015efficient} because preordering introduces a preprocessing step in which source words are permuted in a target-like order before the standard SMT pipeline. SMT with preordering involves two phases: reordering and translation. In the first phase (i.e., reordering), $E$ is transformed into $E'$ in the same word order of the target sentence $J$. In the second phase (i.e., translation), the permuted source sentence is translated into the target language using an SMT system (see Fig.~\ref{fig1}). Preordering is always performed ahead of other processes in SMT pipelines, e.g., word alignment, tuning and decoding. The final goal of preordering is to reduce the computational complexity of the phrase-based decoding.

\begin{figure}[b]
\begin{center}
\includegraphics{25-5ia1f1.eps} 
\end{center}
\caption{Preordering an English sentence into a Japanese word order.}
\label{fig1}
\end{figure}

Most preordering methods depend on the source-side syntactic parser to perform a series of tree transformations. For example, \citeA{isozaki2010head} finalised the head of an English dependency parse tree to the last node so that the order of source words came to resemble a head-final target language (in this case, Japanese). Similary, \citeA{cai2014dependency} employed a dependency parser to perform preordering for Chinese--English. 

Other preordering methods need no syntactic information. For example, \citeA{denero2011inducing} proposed to learn a joint model from a word-aligned parallel corpus for both reordering and translation using the source-side syntactic information to reorder the words. This method resembles the work of bracketing transduction grammar \citeA{wu1997stochastic}.

In the recent dominant paradigm, preordering has also aroused interest within neural machine translation (NMT) studies \cite{cho2014learning,bahdanau2014neural}. For example, although \cite{P15-1082} have proposed an RNN-based preordering model for SMT, \cite{du2017pre} found that preordering deteriorates the performance of NMT, but using preordering features such as reordered indices in word embedding has benefited NMT. Hence, studying the learning methods for preordering is still essential. 


\subsection{Top-down BTG-based Preordering}

Inspired by \citeA{denero2011inducing} and \citeA{neubig2012inducing}, \citeA{nakagawa2015efficient} proposed preordering using a top-down parser utilizing BTG \cite{wu1997stochastic}. BTG is a simplified case of synchronous context-free grammar. According to the definition of BTG, both the source and target sentences should share the same underlying structures, i.e., BTG parse trees, and the order of constituents may be different. A BTG parse tree may has two types of non-terminal nodes, \textit{straight} (\textit{S}) and \textit{inverted} (\textit{I}), and only one type of leaves, \textit{terminal} (\textit{T}). If $X$ and $Y$ denote the non-terminal and terminal symbols, respectively, the BTG rules that generate a parse tree are the following:
\begin{equation}
X \rightarrow
\left\{\begin{matrix}
& [X_1X_2], &\textit{straight}\\ 
 &\langle X_1X_2 \rangle, & \textit{inverted}\\ 
  &Y_{E}/Y_{J}, & \textit{terminal}.\end{matrix}\right.
\end{equation}
\textit{Straight} represents the case where the order of the child nodes is kept. In \textit{inverted}, the child nodes are permuted in reverse. \textit{Terminal} stands for the case of termination.\footnote{$Y_{J}$ can also be a phrase, or even $\varepsilon$.} BTG provides a simple and effective way to represent permutations and perform word reordering.\footnote{There exist some permutations that BTG cannot represent, e.g., $X_2X_4X_1X_3$ to $X_1X_2X_3X_4$, see \cite{wu1997stochastic} Multiple BTG parse trees may lead to same word orders.} For example, the source and target sentences in Fig.~\ref{fig1} can be represented as a BTG parse tree in Fig.~\ref{fig2}.\footnote{In Fig.~\ref{fig2}, the non-terminals upon terminals were omitted for simplicity.}

\begin{figure}[t]
\begin{center}
\includegraphics{25-5ia1f2.eps} 
\end{center}
\hangcaption{Example of BTG parsing and two parser derivations: $D'$, system derivation with the highest model score; $D^*$, oracle derivation with the highest model score from the valid subset.}
\label{fig2}
\end{figure}

Consider the case of preordering, where the BTG parse tree becomes incomplete beacuse of lack of target words. Such a partial BTG parse tree is sufficient to perform accurate reorderings as it is interchangeable with a parser derivation in left-to-right top-down parsing. If $D$ denotes the parser derivation, which is a latent variable, in a BTG-based preordering framework \cite{neubig2012inducing,nakagawa2015efficient}, the inference procedure is defined as follows:
\begin{align}
\tilde{E'} & = \underset{E' \in \hat{E}}  {\mbox{argmax}} \;   P (E', D|E)  \\
 & =\underset{D \in \hat{D}}  {\mbox{argmax}} \;   P(E'|D, E)P(D|E).
\label{equation3}
\end{align}
where $\hat{E}$ stands for all possible permutations and $\tilde{E'}$ is the best one given the target word order. Only one deterministic derivation for a particular BTG tree exists, thus, the first part of formula~\ref{equation3} can be eliminated. Therefore, the task of preordering can be solved as monolingual parsing with the extension of reordering operations. For source sentence $E$, finding the best reordering is equivalent to finding an underlying parser derivation $D$ licensed by BTG. 
\citeA{nakagawa2015efficient} assigned
a score for a particular derivation with the score function in a linear form:
\begin{align}
P(D|E,\bf{w}) & =  \mbox{Score} (D|E)  \\
 & =  {\bf{w}}^\top \cdot \Phi(D, E) \\
 & =  \underset{ d\in D}{\sum} \;  {\bf{w}}^\top  \cdot \Phi(d, E).
\label{equ6}
\end{align}
where $\Phi$ is the feature function and $\bf{w}$ is the weight vector. The parser/preorderer makes greedy selections at each parsing step so that $D$ is a sequence of the atomic derivations. Each atomic derivation $d$ is a triple $\langle E_{[p,q)}, r, o \rangle$, where $E_{[p,q)}$ is a parse span, e.g., $E_{[0,7)}$, denoted by $[p,q)$, covers the source words $E_p, \dots, E_{q-1}$; $r$ is the splitting point; and $o$ is the type of non-terminal nodes (\textit{straight} or \textit{inverted}). To represent the atomic derivation, \citeA{neubig2012inducing} factored $d$ as a set of local features (e.g., POS tags/word classes of the first/last words in the former/latter parse spans) intersected with the node type label $S$ or $I$. The score for $d$ is the sum of the feature weights. The top-down parser starts with the whole source sentence ($E_{[0,7)}$, i.e., the initial span) and then splits the span dichotomously and recursively until it terminates. Finally, the derivation with the highest score is picked up to perform reordering.


\section{Learning Preordering Models}

\subsection{Online Learning} 

Syntactic parsers are trained on tree-annotated datasets. The BTG-based preordering method offers a substantial advantage over the conventional methods by relying on word alignments.

This section will briefly introduce the online learning algorithm passive-aggressive-\rom{1} (PA-\rom{1}) \cite{crammer2006online} used in \cite{nakagawa2015efficient}. Given a training example ($E, \bf{a}$), the trainer runs as follows:

\begin{enumerate}
\item Produce \textit{k}-best parser derivations using beam search; 
\item Select a pair of derivations $\langle D', D^* \rangle$: one derivation with the highest model score from all candidates (called \textit{system} derivation, notes $D'$) and another with the highest model score from the valid subset; (called \textit{oracle} derivation, notes  $D^*$) 
\item If these two derivations diverge or the valid derivation falls off the beam, the weights are updated.
\end{enumerate}
\begin{figure}[t]
\begin{center}
\includegraphics{25-5ia1f3.eps} 
\end{center}
\caption{An example of derivation validation.}
\label{fig3}
\end{figure}
The above procedure allows the oracle derivation to vary from one example to another during training. \citeA{nakagawa2015efficient} extended the atomic derivation $d$ to the four tuple $\langle E_{[p,q)}, r, o, v \rangle$, where the extra $v\in $\{\textit{true}, \textit{false}\} records the validity of the current atomic derivation. $\Lambda(\cdot)$, the validation function (see Fig.~\ref{fig3}), returns \textit{true} if and only if the following property holds:
\begin{eqnarray}
\max(\{{y_i} | {i \in [p,r)}, y_i \neq -1 \} ) \leq \min(\{{y_j} | {j \in [r,q)}, y_j \neq -1 \} ) &  \mbox{if} \quad  o= \mbox{\textit{straight}}\\
\max(\{{y_j} | {j \in [r,q)}, y_j \neq -1 \} ) \leq \min(\{{y_i} | {i \in [p,r)}, y_i \neq -1 \} ) &  \mbox{if} \quad o= \mbox{\textit{inverted}}.
\end{eqnarray}
where ${\bf{y}}$ $= \{y_0,\dots, y_{|x-1|}\}$ is the reordered ranks converted from $\bf{a}$. The above formula checks the crossings of word alignments. The parser starts with an empty derivation $D$ (valid). During parsing, the following condition is checked to validate the current derivation: 
\begin{equation}
\forall d \in D,\, \Lambda({\bf{y}}, d)= \mbox{\textit{true}}  
\end{equation}
Let ${\bf{z}}_0^n=\{ {\bf{z}}_1,\dots, {\bf{z}}_n \}=\langle D', D^*  \rangle_{0}^n$ denote the training examples. The trainer updates the feature weights ${\bf{w}}$ towards the solution to the following projection problem:
\begin{equation}
{\bf{w}}_{t+1} = \underset{{\bf{w}} \in {\mathbb{R}}^n}{\arg\min} \; \frac{1}{2} || {\bf{w}} - {\bf{w}}_t||^2 \quad\mbox{\textbf{s.t.}} \quad{\ell}({\bf{w}}; {\bf{z}}_t) =0
\label{objecteq}
\end{equation}
where ${\ell}(\cdot)$ is a structured hinge-loss function, which separates $D'$ from $D^*$ by a margin that is proportional to the square root of the errors. ${\bf{w}}_{t}$/${\bf{w}}_{t+1}$ are the previous and new weight vectors respectively. According to the different case of \textit{passive} or \textit{aggressive}, the following update rules are derived for optimisation:\footnote{For details, see the mathematical proof with the Lagrange multipliers in \cite{crammer2006online}.}
\begin{equation}
{\bf{w}}_{t+1} =
\left\{\begin{matrix}
{\bf{w}}_{t}  & \mbox{if\quad}\quad{\ell}({\bf{w}}; {\bf{z}}_t) =0, & \mbox{\textit{passive}}\\
{\bf{w}}_{t}+ {\eta_t}   \cdot \Phi({{\bf{z}}_t}) & \mbox{if\quad} \quad{\ell}({\bf{w}}; {\bf{z}}_t) \neq 0, & \mbox{\textit{aggressive}}\end{matrix}\right.
\end{equation}
Namely, ${\ell}(\cdot)$ computes the errors, $\mathcal{E}$ returns the error cost and $\gamma$ is the margin: 
\begin{gather}
{\ell}({\bf{w}}; {\bf{z}}) =
\left\{\begin{matrix}
&0 &  \mbox{if\quad}\mathcal{E}({\bf{z}}) = 0 \\ 
 & \mathcal{E}({\bf{z}}) - \gamma({\bf{w}}; {\bf{z}})  &\mbox{otherwise}\end{matrix}\right. \\
\mathcal{E}({\bf{z}}) = ||D^* - D'||^\frac{1}{2} \\
\gamma ({\bf{w}}; {\bf{z}}) = {\bf{w}}^\top   \cdot   \Phi(D^*)- {\bf{w}}^\top  \cdot \Phi(D')
\end{gather}
$\eta_t$ is the aggressiveness parameter controlled with an upper bound $C$. 
\pagebreak
During training, $\eta_t$ changes with epochs and examples.\footnote{$C$ is equal to 1.}
\begin{equation}
\eta_t = \min \;\left \{  C, \;\frac{{\ell}({\bf{w}}_t; {\bf{z}}_t)}{||\Phi({\bf{z}}_t)||^2}\right \} 
\end{equation}


\subsection{Existing Problem: Gradient Noise}

\citeA{nakagawa2015efficient} applied pairwise updating of parameters if two parses (one: \textit{system} derivation; another: \textit{oracle} derivation) diverged. The accuracy of the prerodering model substantially relies on the quality of word alignments. \citeA{nakagawa2015efficient} suggested using the symmetrised bidirectional word alignments with the INTERSECTION heuristic\footnote{Other heuristics: \textit{union}, \textit{grow-diag-final}, and \textit{grow-diag-final-and}.} heuristic using {\tt{GIZA++}}.

However, using the intersected word alignment has two problems:
\begin{enumerate}
 \item Alignment errors exist in word alignments obtained from {\tt{GIZA++}}, which will heavily affect the performance of MT systems.
 \item The intersected word alignment contains less alignment points, resulting in less constraint on determining the oracle derivation.
\end{enumerate}
Both of the above problems lead to gradient noise.
\begin{itemize}
\item \textbf{Alignment Errors}

The first problem is easy to understand. For example, Fig.~\ref{fig3} shows a particular case of a mistake (assuming that the alignment point ``4-4'' underlined is incorrect). When using the online algorithm, incorrect updates will frequently cause a higher variance \cite{klasner1995noise}, making the resulting preorderer less accurate. Considering that a noisy gradient signal will be observed,\footnote{This does not mean that the online PA-\rom{1} algorithm is not good; on the contrary, it works very well on manual datasets.} this paper proposes to adopt parallel training approaches to reduce gradient noise. 
\item \textbf{Missing Alignment}

Fig.~\ref{fig4} illustrates the second case. On the one hand, if the underlined alignment point ``4-4'' is removed from the example, both derivations have chances to be the ``oracle''; thus, an oracle derivation is probably not the best. On the other hand, micro-reordering (coloured in Fig.~\ref{fig4}) is meaningless for phrase-based SMT (see Fig.~\ref{fig1}). As a consequence, as observed by \citeA{nakagawa2015efficient}, a preorderer trained on automatically aligned datasets underperforms compared to one trained on small manual datasets. For this reason, the authors propose to utilise the remains of  the derivations in the beam, i.e., the \textit{k}-best list, instead of only two derivations.
\end{itemize}

\begin{figure}[t]
\begin{center}
\includegraphics{25-5ia1f4.eps} 
\end{center}
\hangcaption{A particular case where two derivations tend to be valid, resulting from a weak constraint with fewer alignments. However, pairwise updating considers only one derivation as the oracle.}
\label{fig4}
\end{figure}


\section{Solutions to Reduce Noise}

\subsection{Parallel Averaging Strategies}

The main focus of this paper is the parallel training of a top-down BTG-based preorderer. Previous studies have shown that parameter averaging in model learning step can promote the learnt model \cite{breiman1996bagging,freund1999large,dvzeroski2004combining,rokach2010ensemble,mcdonald2010distributed,broderick2013streaming,li2014efficient}. The first aim was to distribute the training algorithm similarly to \citeA{mcdonald2010distributed,broderick2013streaming}. In this case, parameter mixing was performed outside the course of data processing and did not change the training algorithm. Two distributed parameter mixing strategies we adopted: \textit{distributed averaging} and \textit{iterative distributed averaging}. The second aim was to modify the inside algorithm to perform parameter averaging on mini-batches, called \textit{mini-batch averaging}. Though these methods fall into different categories of the learning frameworks, the idea behind them is the same: computing the margins at different levels or using training examples of different sizes reduces the variance of the learnt models. A visual comparison can be found in Fig.~\ref{charac}. The expectation is that the preorderer using parallel training algorithms will be more stable and robust against errors when trained on automatically aligned datasets.


\begin{figure}[t]
\begin{center}
\includegraphics{25-5ia1f5.eps} 
\end{center}
\caption{Characterization of three parallel averaging methods.}
\label{charac}
\end{figure}


\subsubsection{Distributed Averaging}

Distributed averaging is the most straightforward application: it trains the model to convergence separately and then performs parameter mixing. The training examples $\mathcal{T}$ are divided into several disjoint shards as $\{\mathcal{T}_1, \dots, \mathcal{T}_m\}$ and then train on each shard $\mathcal{T}_i$ in parallel as distributed systems.\footnote{Here, while other techniques of bootstrap aggregating or boosting are also suitable for this situation, we only test the most straightforward solution.} \citeA{mcdonald2010distributed} found that, compared to a standard online perceptron, the distributed perceptron algorithm with parameter averaging yields comparable or better performance in the tasks of named entity recognization (NER) and dependency parsing.\footnote{The proof of the convergence can be found in \citeA{mcdonald2010distributed}.} Such a distributed strategy is also capable of other online algorithms because during the whole period of training parameters are updated without any commutations among the child processes. The final model parameters are calculated by taking the average of all submodels.


\subsubsection{Iterative Distributed Averaging} 

Iterative distributed averaging also divides the training data into several shards. Iterative distributed averaging differs from distributed averaging in that it combines the parameters of submodels after each epoch, i.e., `iterative', and then, resends the averaged weights to child processes and updates the weights of submodels. The main shortcoming of iterative distributed averaging is that it needs extra memory to cache the submodels. \citeA{mcdonald2010distributed} showed that iterative distributed averaging outperforms distributed averaging or the standard online method in the task of dependency parsing.


\subsubsection{Mini-batch Averaging}

In the PA-\rom{1} algorithm, some parameters are not linearly separable. For instance, $\eta$ is a parameter that needs to be computed dynamically during training, hence simple batch processing is impractical. To adapt batch learning on the PA algorithm, it needs several tricks. Theoretically, it is possible to estimate $\eta$ approximately on mini-batch instead of examples. Concretely, $\beta \in \mathbb{R}$ is a small positive number, ${\bf{\hat{z}}} = \{\bf{z}_1, . . . , \bf{z}_m\}$ denotes the fixed training set (i.e., one mini-batch), ${\bf{w}}_{t-1}$ denotes the initial weights before the current mini-batch, and ${\bf{w}}_t$ denotes the weights after training. If all examples are iterated in ${\bf{\hat{z}}}$ and weights are updated using ${\ell}({\bf{w}}_1; {\bf{z}}) > \beta$, then the loss for any ${\bf{z}}  \in {\bf{\hat{z}}}$ at time $t$ will be less than $\beta$, i.e., ${\ell}({\bf{w}}_t; {\bf{z}}) \leq \beta$. Hence, the decrease in the loss function guarantees its convergence, which makes the PA-\rom{1} algorithm compatible with batch learning.\footnote{Proof of the convergence (see \cite{crammer2006online}, p.~6).}

In the current implementation,all errors were collected $\Delta\mathcal{E}({\bf{\hat{z}}})$ in a mini-batch, and the aggressiveness parameter ${\Delta\eta}_t$ was computed using the following formula:
\begin{equation}
{\Delta\eta}_t = \min \;\left \{  C, \;\frac{{\sum_{i=1}^{m}}{ {\ell}({\bf{w}}_t; {\bf{z_i}})}}{{||\Phi({\bf{\hat{z}}})||^2}}\right \}
\end{equation}
The variance of the gradient for the mini-batch was reduced by a factor of $m$ (i.e., batch size) compared to the original online PA-\rom{1} algorithm.

\subsection{Using \textit{k}-best List}
Weight updating can also be carried out on multiple derivations (the so-called \textit{\textit{k}-best-based}). For example, in SMT, batch MIRA tuning generates multiple translation hypotheses at each time \cite{cherry2012batch}. The decoder is tuned using two lists of \textit{k}-best hypotheses in parallel (one: \textit{hope}, another: \textit{fear}). Inspired by this idea, this paper proposes to minimize the sum of hinge-losses, taking all derivations in the \textit{k}-best list into consideration.
\begin{align}
\hat{D}_{\mbox{\scriptsize hope}} & =  \{D|D \in \hat{D}_{\mbox{{\scriptsize top-\textit{k}}}} \; \wedge   \; \forall d \in D, \Lambda(d)=true\}\\
\hat{D}_{\mbox{\scriptsize fear}} & =  \{D|D \in \hat{D}_{\mbox{{\scriptsize top-\textit{k}}}}  \; \wedge  \; D  \notin  \hat{D}_{\mbox{\scriptsize hope}}\}
\end{align}
Rather than using only two derivations $D'$ and $D^*$ to update the weights in a pairwise style, the current research makes use of two lists ($\hat{D}_{\mbox{\scriptsize hope}}$ and $\hat{D}_{\mbox{\scriptsize fear}}$) extracted from the top-\textit{k} derivations, where:
\begin{gather}
\mathcal{E}({\bf{z}}) = ||\hat{D}_{\mbox{\scriptsize hope}} - \hat{D}_{\mbox{\scriptsize fear}}||^\frac{1}{2} \\
\gamma ({\bf{w}}; {\bf{z}}) = {\bf{w}}^\top   \cdot   \Phi(\hat{D}_{\mbox{\scriptsize hope}})- {\bf{w}}^\top  \cdot \Phi(\hat{D}_{\mbox{\scriptsize fear}})
\end{gather}
The resulting parser is more accurate when training on large datasets and the training was faster to converge.


\section{Experimental Setup}

\subsection{Data}

To evaluate the proposed methods, the KFTT Corpus\footnote{http://www.phontron.com/kftt/index-ja.html} (English--Japanese) was used to conduct experiments. The total training set was made up of around 330,000 sentences. For the preordering experiments, four training sets were prepared: one small, dataset aligned by human annotators, called Manual-653, which was initially provided in KFTT corpus; one small dataset aligned using {\tt{GIZA++}},\footnote{We ran {\tt{GIZA++}} on the whole training corpus.} called EM-653; one large set called EM-10K contains 100,000 sentence pairs and another called EM-100K contains 100,000 sentence pairs with word alignments using {\tt{GIZA++}}.\footnote{We randomly selected the sentences from the training set.} Word alignments were extracted using the standard training regimen up to IBM~Model~4), and then bidirectional word alignments were symmetrised with the intersection heuristic. The test set provided in the KFTT corpus was used for evaluation. For the translation experiments, the official training, tuning and test sets were
used.


\subsection{Features}

In order to have a fair comparison, the same features as \citeA{nakagawa2015efficient} were used, e.g., the head and tail of the current parser span (unigram, bigram and trigram), the prefix and suffix of the splitting point, and the parent BTG tree type of the current parser span. Each word was factored with its: lexical form, part-of-speech (POS) tag and word class~\cite{brown1992class}.


\subsection{Experimental Settings}

In the present experiments, the parallel averaging methods (without the \textit{k}-best list) were
compared with the online training method in \citeA{nakagawa2015efficient}. The {\tt{TD-BTG-Preorderer}}\footnote{https://github.com/google/topdown-btg-preordering} was used for the baseline systems and the {\tt{HieraParser}}\footnote{https://github.com/wang-h/HieraParser} was used for parallel implementation. For the SMT experiments, the {\tt{Moses}} toolkit\footnote{https://github.com/moses-smt/mosesdecoder} was used. Standard phrase-based SMT systems \cite{koehn2007moses} were built with lexical reordering \cite{koehn2005edinburgh}, Minimum Error Rate Training \cite{och2003minimum}, and 5-gram {\tt{KenLM}} language model \cite{heafield2011kenlm}.\footnote{https://kheafield.com/code/kenlm/}

For POS taggers, the Stanford Part-Of-Speech Tagger\footnote{https://nlp.stanford.edu/software/tagger.shtml} was used for English \cite{toutanova2003feature} and KyTea\footnote{http://www.phontron.com/kytea/index-en.html} was used for Japanese \cite{neubig2011pointwise}. To obtain word class tags, the same implementation\footnote{https://github.com/percyliang/brown-cluster} as \citeA{liang2005semi} was used. The class number was fixed to $256$. Results were compared in both cases: 1) no basic lexical reordering permitted (distortion $\text{limit}=0$) and 2) combining the default lexical reordering model with preordering (distortion $\text{limit}=6$). 

For all experiments, the preorderers for 20 and 40 epochs were trained. For distributed methods, the training dataset was divided into eight shards linearly and eight threads for multi-threading processing were used. For both the {\tt{TD-BTG-Preorderer}} and the {\tt{HieraParser}}, a beam of size 20 was employed. For the \textit{k}-best list, the top-five derivations were selected. Preordering for SMT experiments were performed using the model-trained 20 epochs. The experiments reported in this paper were measured on the same machine with an Intel Core i7-960 3.20~GHz CPU (four cores, and eight threads) with 32~GB RAM. 


\section{Experimental Results}\label{exp_results}


\subsection{Intrinsic Evaluation}

\subsubsection{Intrinsic Metrics}

To evaluate preordering accuracy, Fuzzy Reordering Score (FRS), Normalized Kendall's $\tau$ (NKT) and Complete Matching Score (CMS) were measured using the manual dataset provided in KFTT corpus. 

\begin{figure}[t]
\begin{center}
\includegraphics{25-5ia1f6.eps} 
\end{center}
\hangcaption{Best reordering scores changed over the training time (English--Japanese). Each curve stands for 40 epochs.}
\label{characterization}
\label{learning_curve}
\end{figure}

The FRS \cite{talbot2011lightweight} is a widely-used evaluation metric which measures the quality of reordering and measures the continuity of the output order against the reference. Given the reference permutation $E_{r}$, FRS  is calculated as the precision of word bigrams:
\begin{equation}
\mbox{FRS}(E_{r},E)= \frac{B(E_{r},E)}{M(E)+1}
\end{equation}
where $B$ stands for the count of overlap bigrams that appear both in the reference sentence and the reordered source sentence. $M$ stands for the total number of words in the source sentence.

Kendall's $\tau$ \cite{kendall1938new} is another simple metric to measure reordering:
\begin{equation}
\tau =  2 \times \frac{\mbox{number of increasing pairs}}{\mbox{the total number of pairs}}-1
\end{equation}
Kendall's $\tau$ may be a negative value; hence, this metric is justified with normalization  similarly to \citeA{isozaki2010automatic}. Normalized Kendall's $\tau$ is defined as the following:
\begin{equation}
\mbox{NKT} = 1 - \frac{C }{M \times (M-1)/2}
\end{equation}
where $C$ is the count of errors that pairs are not increasing.

The CMS measures the percentage of complete matches (the one where $\tau = 1.0$) against the total number of testing examples. Assuming that the test set contains $N$ sentences, the complete matching score is computed as:
\begin{equation}
\mbox{CMS} = \frac{\# \mbox{ of complete matches}}{N}
\end{equation}

\begin{table}[p]
\caption{Reordering scores and training times (in minutes) for English--Japanese}
\label{table1}
\input{01table01.tex}
\vspace{4pt}
\small
Bold numbers indicate statistically significant difference with the baseline system (bootstrap resampling $p<0.05$).
\end{table}


\subsubsection{Reordering Results}

The scores of reordering can be found in Table~\ref{table1} and Fig.~6. Compared with the online training method of \citeA{nakagawa2015efficient}, all parallel averaging strategies for training the preorderer were effective in reducing the training time. In addition, these methods significantly improved the accuracy of reorderings in terms of the CMS, FRS and NKT when trained on automatically-aligned datasets, although they underperformed on the small hand-aligned dataset. Distributed averaging is not so effective on the small dataset, but it substantially upgraded with the size of the training dataset. Iterative distributed averaging and mini-batch averaging had a competitive performance. Using the \textit{k}-best list improved the results on the EM-100K and no significant difference was found on the EM-10K, resulting in slight changes in the training time. The \textit{k-best} mini-batch averaging showed an outstanding result on the small dataset (Manual-653). The results also found that increasing the training data improved the overall reordering performance.


\begin{table}[p]
\caption{Translation scores for each system}
\label{table2}
\input{01table02.tex}
\vspace{4pt}\small
Bold numbers indicate no statistically significant difference with the best system. $^\dag/^{\dag\dag}$: significantly better than the baseline system ($p<0.05/p<0.01$).
\end{table}


\subsection{Extrinsic Evaluation}

\subsubsection{Extrinsic Metrics}

For translation evaluation, standard automatic evaluation metrics were used in all experiments, including BLEU \cite{papineni2002bleu} and RIBES \cite{isozaki2010automatic}. BLEU was used because it is the most widely used metric, but because it does not take into account word order, especially for distant language pairs such as English--Japanese, other metrics were used like RIBES, which is an automatic evaluation metric based on word order correlation coefficients between reference sentences and MT output. 

\subsubsection{Translation Results}

Table~\ref{table2} shows the translation scores. All parallel averaging methods had comparable performances in the SMT experiments either using EM-10K or EM-100K. It is worth noting that automatically word-aligned datasets were noisy (contained alignment errors). Compared with \citeA{nakagawa2015efficient}, the proposed methods achieved comparable results on the large datasets (EM-10K and EM-100K). In other words, training using parallel averaging methods was more stable near the convergence. Among these methods, distributed averaging underperformed on Manual-653 because of the unbalanced aggregation of the submodels. While using the larger training dataset (EM-100K), it performed as well as the other methods. The \textit{k}-best mini-batch averaging had the best performance.

Comparing Table~\ref{table1} and Table~\ref{table2}, it became clear that the higher quality preordering does not necessarily lead to better translations. There are some reasons that can explain this phenomenon. On the one hand, for phrase-based SMT, it is well known that the performance of SMT systems is not strongly correlated with the quality of the latent variables, e.g., word alignment. For example, a lower alignment error rate (AER) does not necessarily entail better translation scores. On the other hand, micro-reorderings between two leaves in a parse tree often lead to a higher reordering score. However, if the correspondence between two words in the source language and two words in the target language is captured in the phrase table, the translation accuracy may not change.    


\section{Conclusion}

In this paper, the training algorithm of \citeA{nakagawa2015efficient} wase improved using bootstrap aggregating with several learning techniques (mini-batch, distributed, iterative distributed and \textit{k}-best list). These parallel training methods were capable of dealing with alignment errors that existed in the training examples. The conducted experiments demonstrated that the current proposal is more effective and efficient when trained on automatically aligned datasets, making fast training a reality. As a possible direction for future work, the author plan to apply neural models to build more accurate parsers. This paper shows that such parameter mixing techniques may benefit other NLP tasks when learning from noisy datasets. The resulting C++ implementation for BTG-based preordering described in this paper is available via Github at the following address: https://github.com/wang-h/HieraParser.


\acknowledgment

This research was supported in part by China Scholarship Council (CSC) under the CSC Grant No. 201406890026. The authors wish to thank the anonymous reviewers for their insightful comments. 



\bibliographystyle{jnlpbbl_1.5}
\newcommand{\NeubigMB}[1]{}\newcommand{\NakagawaMB}[1]{}
\begin{thebibliography}{}

\bibitem[\protect\BCAY{Bahdanau, Cho, \BBA\ Bengio}{Bahdanau
  et~al.}{2014}]{bahdanau2014neural}
Bahdanau, D., Cho, K., \BBA\ Bengio, Y. \BBOP 2014\BBCP.
\newblock \BBOQ Neural Machine Translation by Jointly Learning to Align and
  Translate.\BBCQ\
\newblock In {\Bem ICLR 2015}.

\bibitem[\protect\BCAY{Breiman}{Breiman}{1996}]{breiman1996bagging}
Breiman, L. \BBOP 1996\BBCP.
\newblock \BBOQ Bagging Predictors.\BBCQ\
\newblock {\Bem Machine Learning}, {\Bbf 24}  (2), \mbox{\BPGS\ 123--140}.

\bibitem[\protect\BCAY{Broderick, Boyd, Wibisono, Wilson, \BBA\
  Jordan}{Broderick et~al.}{2013}]{broderick2013streaming}
Broderick, T., Boyd, N., Wibisono, A., Wilson, A.~C., \BBA\ Jordan, M.~I. \BBOP
  2013\BBCP.
\newblock \BBOQ Streaming Variational Bayes.\BBCQ\
\newblock In {\Bem Advances in Neural Information Processing Systems},
  \mbox{\BPGS\ 1727--1735}.

\bibitem[\protect\BCAY{Brown, Desouza, Mercer, Pietra, \BBA\ Lai}{Brown
  et~al.}{1992}]{brown1992class}
Brown, P.~F., Desouza, P.~V., Mercer, R.~L., Pietra, V. J.~D., \BBA\ Lai, J.~C.
  \BBOP 1992\BBCP.
\newblock \BBOQ Class-based n-gram Models of Natural Language.\BBCQ\
\newblock {\Bem Computational Linguistics}, {\Bbf 18}  (4), \mbox{\BPGS\
  467--479}.

\bibitem[\protect\BCAY{Cai, Utiyama, Sumita, \BBA\ Zhang}{Cai
  et~al.}{2014}]{cai2014dependency}
Cai, J., Utiyama, M., Sumita, E., \BBA\ Zhang, Y. \BBOP 2014\BBCP.
\newblock \BBOQ Dependency-based Pre-ordering for Chinese-English Machine
  Translation.\BBCQ\
\newblock In {\Bem ACL (2)}, \mbox{\BPGS\ 155--160}.

\bibitem[\protect\BCAY{Cherry \BBA\ Foster}{Cherry \BBA\
  Foster}{2012}]{cherry2012batch}
Cherry, C.\BBACOMMA\ \BBA\ Foster, G. \BBOP 2012\BBCP.
\newblock \BBOQ Batch Tuning Strategies for Statistical Machine
  Translation.\BBCQ\
\newblock In {\Bem Proceedings of the 2012 Conference of the North American
  Chapter of the Association for Computational Linguistics: Human Language
  Technologies}, \mbox{\BPGS\ 427--436}. Association for Computational
  Linguistics.

\bibitem[\protect\BCAY{Cho, van Merrienboer, Gulcehre, Bahdanau, Bougares,
  Schwenk, \BBA\ Bengio}{Cho et~al.}{2014}]{cho2014learning}
Cho, K., van Merrienboer, B., Gulcehre, C., Bahdanau, D., Bougares, F.,
  Schwenk, H., \BBA\ Bengio, Y. \BBOP 2014\BBCP.
\newblock \BBOQ Learning Phrase Representations using RNN Encoder--Decoder for
  Statistical Machine Translation.\BBCQ\
\newblock In {\Bem Proceedings of the 2014 Conference on Empirical Methods in
  Natural Language Processing (EMNLP)}, \mbox{\BPGS\ 1724--1734}, Doha, Qatar.
  Association for Computational Linguistics.

\bibitem[\protect\BCAY{Collins, Koehn, \BBA\ Ku{\v{c}}erov{\'{a}}}{Collins
  et~al.}{2005}]{collins2005clause}
Collins, M., Koehn, P., \BBA\ Ku{\v{c}}erov{\'{a}}, I. \BBOP 2005\BBCP.
\newblock \BBOQ Clause Restructuring for Statistical Machine Translation.\BBCQ\
\newblock In {\Bem Proceedings of the 43rd Annual Meeting on Association for
  Computational Linguistics}, \mbox{\BPGS\ 531--540}. Association for
  Computational Linguistics.

\bibitem[\protect\BCAY{Crammer, Dekel, Keshet, Shalev-Shwartz, \BBA\
  Singer}{Crammer et~al.}{2006}]{crammer2006online}
Crammer, K., Dekel, O., Keshet, J., Shalev-Shwartz, S., \BBA\ Singer, Y. \BBOP
  2006\BBCP.
\newblock \BBOQ Online Passive-aggressive Algorithms.\BBCQ\
\newblock {\Bem Journal of Machine Learning Research}, {\Bbf 7}  (Mar),
  \mbox{\BPGS\ 551--585}.

\bibitem[\protect\BCAY{DeNero \BBA\ \mbox{Uszkoreit}}{DeNero \BBA\
  \mbox{Uszkoreit}}{2011}]{denero2011inducing}
DeNero, J.\BBACOMMA\ \BBA\ \mbox{Uszkoreit}, J. \BBOP 2011\BBCP.
\newblock \BBOQ Inducing Sentence Structure from Parallel Corpora for
  Reordering.\BBCQ\
\newblock In {\Bem Proceedings of the Conference on Empirical Methods in
  Natural Language Processing}, \mbox{\BPGS\ 193--203}. Association for
  Computational Linguistics.

\bibitem[\protect\BCAY{Dietterich}{Dietterich}{2000}]{dietterich2000ensemble}
Dietterich, T.~G. \BBOP 2000\BBCP.
\newblock \BBOQ Ensemble Methods in Machine Learning.\BBCQ\
\newblock In {\Bem International Workshop on Multiple Classifier Systems},
  \mbox{\BPGS\ 1--15}. Springer.

\bibitem[\protect\BCAY{Du \BBA\ Way}{Du \BBA\ Way}{2017}]{du2017pre}
Du, J.\BBACOMMA\ \BBA\ Way, A. \BBOP 2017\BBCP.
\newblock \BBOQ Pre-Reordering for Neural Machine Translation: Helpful or
  Harmful?\BBCQ\
\newblock {\Bem The Prague Bulletin of Mathematical Linguistics}, {\Bbf 108}
  (1), \mbox{\BPGS\ 171--182}.

\bibitem[\protect\BCAY{D{\v{z}}eroski \BBA\ {\v{Z}}enko}{D{\v{z}}eroski \BBA\
  {\v{Z}}enko}{2004}]{dvzeroski2004combining}
D{\v{z}}eroski, S.\BBACOMMA\ \BBA\ {\v{Z}}enko, B. \BBOP 2004\BBCP.
\newblock \BBOQ Is Combining Classifiers with Stacking Better than Selecting
  the Best One?\BBCQ\
\newblock {\Bem Machine Learning}, {\Bbf 54}  (3), \mbox{\BPGS\ 255--273}.

\bibitem[\protect\BCAY{Freund \BBA\ Schapire}{Freund \BBA\
  Schapire}{1999}]{freund1999large}
Freund, Y.\BBACOMMA\ \BBA\ Schapire, R.~E. \BBOP 1999\BBCP.
\newblock \BBOQ Large Margin Classification using the Perceptron
  Algorithm.\BBCQ\
\newblock {\Bem Machine Learning}, {\Bbf 37}  (3), \mbox{\BPGS\ 277--296}.

\bibitem[\protect\BCAY{Goto, Utiyama, Sumita, \BBA\ Kurohashi}{Goto
  et~al.}{2015}]{goto2015preordering}
Goto, I., Utiyama, M., Sumita, E., \BBA\ Kurohashi, S. \BBOP 2015\BBCP.
\newblock \BBOQ Preordering using a Target-Language Parser via Cross-language
  Syntactic Projection for Statistical Machine Translation.\BBCQ\
\newblock {\Bem ACM Transactions on Asian and Low-Resource Language Information
  Processing}, {\Bbf 14}  (3), \mbox{\BPG~13}.

\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 Sixth 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.}{2010a}]{isozaki2010automatic}
Isozaki, H., Hirao, T., Duh, K., Sudoh, K., \BBA\ Tsukada, H. \BBOP 2010a\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{Isozaki, Sudoh, Tsukada, \BBA\ Duh}{Isozaki
  et~al.}{2010b}]{isozaki2010head}
Isozaki, H., Sudoh, K., Tsukada, H., \BBA\ Duh, K. \BBOP 2010b\BBCP.
\newblock \BBOQ Head Finalization: A Simple Reordering Rule for SOV
  Languages.\BBCQ\
\newblock In {\Bem Proceedings of the Joint 5th Workshop on Statistical Machine
  Translation and MetricsMATR}, \mbox{\BPGS\ 244--251}. Association for
  Computational Linguistics.

\bibitem[\protect\BCAY{Kendall}{Kendall}{1938}]{kendall1938new}
Kendall, M.~G. \BBOP 1938\BBCP.
\newblock \BBOQ A New Measure of Rank Correlation.\BBCQ\
\newblock {\Bem Biometrika}, {\Bbf 30}  (1/2), \mbox{\BPGS\ 81--93}.

\bibitem[\protect\BCAY{Klasner \BBA\ Simon}{Klasner \BBA\
  Simon}{1995}]{klasner1995noise}
Klasner, N.\BBACOMMA\ \BBA\ Simon, H.~U. \BBOP 1995\BBCP.
\newblock \BBOQ From Noise-free to Noise-tolerant and from On-line to Batch
  Learning.\BBCQ\
\newblock In {\Bem Proceedings of the 8th Annual Conference on Computational
  Learning Theory}, \mbox{\BPGS\ 250--257}. ACM.

\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, et~al.}{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., et~al. \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
  InteractivevPoster 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-Volume 1}, \mbox{\BPGS\ 48--54}. Association for Computational
  Linguistics.

\bibitem[\protect\BCAY{Lerner \BBA\ Petrov}{Lerner \BBA\
  Petrov}{2013}]{lerner2013source}
Lerner, U.\BBACOMMA\ \BBA\ Petrov, S. \BBOP 2013\BBCP.
\newblock \BBOQ Source-side Classifier Preordering for Machine
  Translation.\BBCQ\
\newblock In {\Bem EMNLP}, \mbox{\BPGS\ 513--523}.

\bibitem[\protect\BCAY{Li, Zhang, Chen, \BBA\ Smola}{Li
  et~al.}{2014}]{li2014efficient}
Li, M., Zhang, T., Chen, Y., \BBA\ Smola, A.~J. \BBOP 2014\BBCP.
\newblock \BBOQ Efficient Mini-batch Training for Stochastic
  Optimization.\BBCQ\
\newblock In {\Bem Proceedings of the 20th ACM SIGKDD International Conference
  on Knowledge Discovery and Data Mining}, \mbox{\BPGS\ 661--670}. ACM.

\bibitem[\protect\BCAY{Liang}{Liang}{2005}]{liang2005semi}
Liang, P. \BBOP 2005\BBCP.
\newblock {\Bem Semi-supervised Learning for Natural Language}.
\newblock Ph.D.\ thesis, University of California, Berkeley.

\bibitem[\protect\BCAY{McDonald, Hall, \BBA\ Mann}{McDonald
  et~al.}{2010}]{mcdonald2010distributed}
McDonald, R., Hall, K., \BBA\ Mann, G. \BBOP 2010\BBCP.
\newblock \BBOQ Distributed Training Strategies for the Structured
  Perceptron.\BBCQ\
\newblock In {\Bem Human Language Technologies: The 2010 Annual Conference of
  the North American Chapter of the Association for Computational Linguistics},
  \mbox{\BPGS\ 456--464}. Association for Computational Linguistics.

\bibitem[\protect\BCAY{Miceli~Barone \BBA\ Attardi}{Miceli~Barone \BBA\
  Attardi}{2015}]{P15-1082}
Miceli~Barone, A.~V.\BBACOMMA\ \BBA\ Attardi, G. \BBOP 2015\BBCP.
\newblock \BBOQ Non-projective Dependency-based Pre-Reordering with Recurrent
  Neural Network for Machine Translation.\BBCQ\
\newblock In {\Bem Proceedings of the 53rd Annual Meeting of the Association
  for Computational Linguistics and the 7th International Joint Conference on
  Natural Language Processing (Volume 1: Long Papers)}, \mbox{\BPGS\ 846--856}.
  Association for Computational Linguistics.

\bibitem[\protect\BCAY{Naftaly, Intrator, \BBA\ Horn}{Naftaly
  et~al.}{1997}]{naftaly1997optimal}
Naftaly, U., Intrator, N., \BBA\ Horn, D. \BBOP 1997\BBCP.
\newblock \BBOQ Optimal Ensemble Averaging of Neural Networks.\BBCQ\
\newblock {\Bem Network: Computation in Neural Systems}, {\Bbf 8}  (3),
  \mbox{\BPGS\ 283--296}.

\bibitem[\protect\BCAY{\NakagawaMB{Nakagawa}}{\NakagawaMB{Nakagawa}}{2015}]{nakagawa2015efficient}
\NakagawaMB{Nakagawa}, T. \BBOP 2015\BBCP.
\newblock \BBOQ Efficient Top-Down BTG Parsing for Machine Translation
  Preordering.\BBCQ\
\newblock In {\Bem ACL 2015}, \mbox{\BPGS\ 208--218}. Association for
  Computational Linguistics.

\bibitem[\protect\BCAY{Neubig, Nakata, \BBA\ Mori}{Neubig
  et~al.}{2011}]{neubig2011pointwise}
Neubig, G., Nakata, Y., \BBA\ Mori, S. \BBOP 2011\BBCP.
\newblock \BBOQ Pointwise Prediction for Robust, Adaptable Japanese
  Morphological Analysis.\BBCQ\
\newblock In {\Bem Proceedings of the 49th Annual Meeting of the Association
  for Computational Linguistics: Human Language Technologies: Short
  Papers-Volume 2}, \mbox{\BPGS\ 529--533}. Association for Computational
  Linguistics.

\bibitem[\protect\BCAY{\NeubigMB{Neubig}, Watanabe, \BBA\
  Mori}{\NeubigMB{Neubig} et~al.}{2012}]{neubig2012inducing}
\NeubigMB{Neubig}, G., Watanabe, T., \BBA\ Mori, S. \BBOP 2012\BBCP.
\newblock \BBOQ Inducing a Discriminative Parser to Optimize Machine
  Translation Reordering.\BBCQ\
\newblock In {\Bem Proceedings of the 2012 Joint Conference on Empirical
  Methods in Natural Language Processing and Computational Natural Language
  Learning}, \mbox{\BPGS\ 843--853}. 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-Volume 1}, \mbox{\BPGS\ 160--167}. Association for
  Computational Linguistics.

\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 Annual Meeting on Association for
  Computational Linguistics}, \mbox{\BPGS\ 311--318}. Association for
  Computational Linguistics.

\bibitem[\protect\BCAY{Rokach}{Rokach}{2010}]{rokach2010ensemble}
Rokach, L. \BBOP 2010\BBCP.
\newblock \BBOQ Ensemble-based Classifiers.\BBCQ\
\newblock {\Bem Artificial Intelligence Review}, {\Bbf 33}  (1-2), \mbox{\BPGS\
  1--39}.

\bibitem[\protect\BCAY{Sudoh, Duh, Tsukada, Hirao, \BBA\ Nagata}{Sudoh
  et~al.}{2010}]{sudoh2010divide}
Sudoh, K., Duh, K., Tsukada, H., Hirao, T., \BBA\ Nagata, M. \BBOP 2010\BBCP.
\newblock \BBOQ Divide and Translate: Improving Long Distance Reordering in
  Statistical Machine Translation.\BBCQ\
\newblock In {\Bem Proceedings of the Joint 5th Workshop on Statistical Machine
  Translation and MetricsMATR}, \mbox{\BPGS\ 418--427}. Association for
  Computational Linguistics.

\bibitem[\protect\BCAY{Talbot, Kazawa, Ichikawa, Katz-Brown, Seno, \BBA\
  Och}{Talbot et~al.}{2011}]{talbot2011lightweight}
Talbot, D., Kazawa, H., Ichikawa, H., Katz-Brown, J., Seno, M., \BBA\ Och,
  F.~J. \BBOP 2011\BBCP.
\newblock \BBOQ A Lightweight Evaluation Framework for Machine Translation
  Reordering.\BBCQ\
\newblock In {\Bem Proceedings of the 6th Workshop on Statistical Machine
  Translation}, \mbox{\BPGS\ 12--21}. Association for Computational
  Linguistics.

\bibitem[\protect\BCAY{Toutanova, Klein, Manning, \BBA\ Singer}{Toutanova
  et~al.}{2003}]{toutanova2003feature}
Toutanova, K., Klein, D., Manning, C.~D., \BBA\ Singer, Y. \BBOP 2003\BBCP.
\newblock \BBOQ Feature-rich Part-of-speech Tagging with a Cyclic Dependency
  Network.\BBCQ\
\newblock In {\Bem Proceedings of the 2003 Conference of the North American
  Chapter of the Association for Computational Linguistics on Human Language
  Technology-Volume 1}, \mbox{\BPGS\ 173--180}. Association for Computational
  Linguistics.

\bibitem[\protect\BCAY{Watanabe, Suzuki, Tsukada, \BBA\ Isozaki}{Watanabe
  et~al.}{2007}]{watanabe2007online}
Watanabe, T., Suzuki, J., Tsukada, H., \BBA\ Isozaki, H. \BBOP 2007\BBCP.
\newblock \BBOQ Online Large-margin Training for Statistical Machine
  Translation.\BBCQ\
\newblock In {\Bem Proceedings of the 2007 Joint Conference on Empirical
  Methods in Natural Language Processing and Computational Natural Language
  Learning (EMNLP-CoNLL)}, \mbox{\BPGS\ 764--773}.

\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{Xia \BBA\ McCord}{Xia \BBA\
  McCord}{2004}]{xia2004improving}
Xia, F.\BBACOMMA\ \BBA\ McCord, M. \BBOP 2004\BBCP.
\newblock \BBOQ Improving a Statistical MT System with Automatically Learned
  Rewrite Patterns.\BBCQ\
\newblock In {\Bem Proceedings of the 20th International Conference on
  Computational Linguistics}, \mbox{\BPG\ 508}. Association for Computational
  Linguistics.

\end{thebibliography}


\begin{biography}
\bioauthor[:]{\textbf{Hao Wang}}{
Hao Wang received his M.E. from Waseda University and M.Sc from Shanghai University in 2014. He is currently a PhD 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 and machine learning, especially machine translation. 
}

\bioauthor[:]{\textbf{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}
