Inducing a Discriminative Parser to Optimize MachineTranslation Reordering
Graham Neubig1,2 , Taro Watanabe2 , Shinsuke Mori1
1
Graduate School of Informatics, Kyoto University
Yoshida Honmachi, Sakyo-ku, Kyoto, Japan
2
National Institute of Information and Communication Technology
3-5 Hikari-dai, Seika-cho, Soraku-gun, Kyoto, Japan

Abstract
This paper proposes a method for learninga discriminative parser for machine translation reordering using only aligned parallel text. This is done by treating theparser’s derivation tree as a latent variable
in a model that is trained to maximize reordering accuracy. We demonstrate thateﬃcient large-margin training is possibleby showing that two measures of reordering accuracy can be factored over the parsetree. Using this model in the pre-ordering
framework results in signiﬁcant gains intranslation accuracy over standard phrasebased SMT and previously proposed unsupervised syntax induction methods.

1

Introduction

Finding the appropriate word ordering in thetarget language is one of the most diﬃcult problems for statistical machine translation (SMT),
particularly for language pairs with widely divergent syntax. As a result, there is a large
amount of previous research that handles the
problem of reordering through the use of improved reordering models for phrase-based SMT(Koehn et al., 2005), hierarchical phrase-basedtranslation (Chiang, 2007), syntax-based translation (Yamada and Knight, 2001), or preordering (Xia and McCord, 2004).
In particular, systems that use sourcelanguage syntax allow for the handling of longdistance reordering without large increases in
The ﬁrst author is now aﬃliated with the Nara Instituteof Science and Technology.

decoding time. However, these require a goodsyntactic parser, which is not available for many
languages. In recent work, DeNero and Uszkoreit (2011) suggest that unsupervised grammar
induction can be used to create source-sentenceparse structure for use in translation as a partof a pre-ordering based translation system.
In this work, we present a method for inducing
a parser for SMT by training a discriminativemodel to maximize reordering accuracy while
treating the parse tree as a latent variable. As alearning framework, we use online large-margin
methods to train the model to directly minimize
two measures of reordering accuracy. We propose a variety of features, and demonstrate thatlearning can succeed when no linguistic information (POS tags or parse structure) is available inthe source language, but also show that this linguistic information can be simply incorporated
when it is available. Experiments ﬁnd that the
proposed model improves both reordering andtranslation accuracy, leading to average gainsof 1.2 BLEU points on English-Japanese andJapanese-English translation without linguistic
analysis tools, or up to 1.5 BLEU points whenthese tools are incorporated. In addition, weshow that our model is able to eﬀectively maximize various measures of reordering accuracy,
and that the reordering measure that we choose
has a direct eﬀect on translation results.

2 Preordering for SMT
Machine translation is deﬁned as transformation of source sentence F = f1 . . . fJ to target
sentence E = e1 . . . eI . In this paper, we take

Figure 1: An example with a source sentence F reordered into target order F 0 , and its corresponding
target sentence E. D is one of the BTG derivations
that can produce this ordering.

the pre-ordering approach to machine translation (Xia and McCord, 2004), which performs
translation as a two step process of reorderingand translation (Figure 1). Reordering ﬁrst deterministically transforms F into F 0 , which contains the same words as F but is in the order of
E. Translation then transforms F 0 into E using
a method such as phrase-based SMT (Koehn etal., 2003), which can produce accurate translations when only local reordering is required.
This general framework has been widely studied, with the majority of works relying on asyntactic parser being available in the source
language. Reordering rules are deﬁned overthis parse either through machine learning techniques (Xia and McCord, 2004; Zhang et al.,2007; Li et al., 2007; Genzel, 2010; Dyer andResnik, 2010; Khalilov and Sima’an, 2011) or
linguistically motivated manual rules (Collins etal., 2005; Xu et al., 2009; Carpuat et al., 2010;
Isozaki et al., 2010b). However, as building aparser for each source language is a resourceintensive undertaking, there has also been someinterest in developing reordering rules without
the use of a parser (Rottmann and Vogel, 2007;
Tromble and Eisner, 2009; DeNero and Uszkoreit, 2011; Visweswariah et al., 2011), and wewill follow this thread of research in this paper.
In particular, two methods deserve mention
for being similar to our approach. First, DeNero
and Uszkoreit (2011) learn a reordering modelthrough a three-step process of bilingual grammar induction, training a monolingual parser
to reproduce the induced trees, and training

a reordering model that selects a reordering
based on this parse structure. In contrast, ourmethod trains the model in a single step, treating the parse structure as a latent variable ina discriminative reordering model. In addition
Tromble and Eisner (2009) and Visweswariah etal. (2011) present models that use binary classiﬁcation to decide whether each pair of words
should be placed in forward or reverse order. In
contrast, our method uses traditional contextfree-grammar models, which allows for simple
parsing and ﬂexible parameterization, including
features such as those that utilize the existenceof a span in the phrase table. Our work is also
unique in that we show that it is possible to directly optimize several measures of reordering
accuracy, which proves important for achieving
good translations.1

3 Training a Reordering Model with
Latent Derivations
In this section, we provide a basic overview ofthe proposed method for learning a reorderingmodel with latent derivations using online discriminative learning.
3.1 Space of Reorderings
The model we present here is based on thebracketing transduction grammar (BTG, Wu(1997)) framework. BTGs represent a binary
tree derivation D over the source sentence F
as shown in Figure 1. Each non-terminal nodecan either be a straight (str) or inverted (inv)
production, and terminals (term) span a nonempty substring f .2
The ordering of the sentence is determined by
the tree structure and the non-terminal labels
str and inv, and can be built bottom-up. Eachsubtree represents a source substring f and its
reordered counterpart f 0 . For each terminal
node, no reordering occurs and f is equal to f 0 .
1

The semi-supervised method of Katz-Brown et al.
(2011) also optimizes reordering accuracy, but requires
manually annotated parses as seed data.
2
In the original BTG framework used in translation,
terminals produce a bilingual substring pair f /e, but as
we are only interested in reordering the source F , wesimplify the model by removing the target substring e.

For each non-terminal node spanning f with its
left child spanning f 1 and its right child spanning f 2 , if the non-terminal symbol is str, thereordered strings will be concatenated in order
as f 0 = f 01 f 02 , and if the non-terminal symbol isinv, the reordered strings will be concatenatedin inverted order as f 0 = f 02 f 01 .
We deﬁne the space of all reorderings that canbe produced by the BTG as F 0 , and attempt toﬁnd the best reordering F̂ 0 within this space.3
3.2

Reorderings with Latent
Derivations

In order to ﬁnd the best reordering F̂ 0 given only
the information in the source side sentence F , wedeﬁne a scoring function S(F 0 |F ), and choose
the ordering of maximal score:Ḟ 0 = arg max S(F 0 |F ).
F0

As our model is based on reorderings licensed
by BTG derivations, we also assume that there
is an underlying derivation D that produced F 0 .
As we can uniquely determine F 0 given F andD, we can deﬁne a scoring function S(D|F ) overderivations, ﬁnd the derivation of maximal scoreḊ = arg max S(D|F )Dand use Ḋ to transform F into F 0 .
Furthermore, we assume that the score
S(D|F ) is the weighted sum of a number of feature functions deﬁned over D and F∑
S(D|F, w) =wi φi (D, F )iwhere φi is the ith feature function, and wi is
its corresponding weight in weight vector w.
Given this model, we must next consider how
to learn the weights w. As the ﬁnal goal of ourmodel is to produce good reorderings F 0 , it isnatural to attempt to learn weights that will allow us to produce these high-quality reorderings.
3

BTGs cannot reproduce all possible reorderings, but
can handle most reorderings occurring in natural translated text (Haghighi et al., 2009).

Figure 2: An example of (a) the ranking functionr(fj ), (b) loss according to Kendall’s τ , (c) loss according to chunk fragmentation.

4 Evaluating Reorderings
Before we explain the learning algorithm, wemust know how to distinguish whether the F 0
produced by the model is good or bad. Thissection explains how to calculate oracle reorderings, and assign each F 0 a loss and an accuracy
according to how well it reproduces the oracle.
4.1 Calculating Oracle Orderings
In order to calculate reordering quality, we ﬁrst
deﬁne a ranking function r(fj |F, A), which indicates the relative position of source word fj inthe proper target order (Figure 2 (a)). In order to calculate this ranking function, we deﬁne
A = a1 , . . . , aJ , where each aj is a set of the indices of the words in E to which fj is aligned.4
Given these alignments, we deﬁne an orderingfunction aj1 < aj2 that indicates that the indices in aj1 come before the indices in aj2 . Formally, we deﬁne this function as “the ﬁrst index
in aj1 is at most the ﬁrst index in aj2 , similarly
for the last index, and either the ﬁrst or lastindex in aj1 is less than that of aj2 .”Given this ordering, we can sort every alignment aj , and use its relative position in the sentence to assign a rank to its word r(fj ). In
4

Null alignments require special treatment. To do so,
we can place unaligned brackets and quotes directly before and after the spans they surround, and attach allother unaligned words to the word directly to the rightfor head-initial languages (e.g. English), or left for headﬁnal languages (e.g. Japanese).

the case of ties, where neither aj1 < aj2 nor
aj2 < aj1 , both fj1 and fj2 are assigned thesame rank. We can now deﬁne measures of reordering accuracy for F 0 by how well it arranges
the words in order of ascending rank. It should
be noted that as we allow ties in rank, there
are multiple possible F 0 where all words are instrictly ascending order, which we will call oracle orderings.
4.2

The ﬁrst measure of reordering accuracy that
we will consider is Kendall’s τ (Kendall, 1938),
a measure of pairwise rank correlation which
has been proposed for evaluating translation reordering accuracy (Isozaki et al., 2010a; Birchet al., 2010) and pre-ordering accuracy (Talbot
et al., 2011). The fundamental idea behind themeasure lies in comparisons between each pair ofelements fj01 and fj02 of the reordered sentence,
where j1 < j2 . Because j1 < j2 , fj01 comes before
fj02 in the reordered sentence, the ranks shouldbe r(fj01 ) ≤ r(fj02 ) in order to produce the correct ordering.
Based on this criterion, we ﬁrst deﬁne a loss
Lt (F 0 ) that will be higher for orderings that are
further from the oracle. Speciﬁcally, we take thesum of all pairwise orderings that do not follow
the expected order
J−1
∑

J
∑

where δ(·) is an indicator function that is 1 when
its condition is true, and 0 otherwise. An example of this is given in Figure 2 (b).
To calculate an accuracy measure for ordering
F 0 , we ﬁrst calculate the maximum loss for thesentence, which is equal to the total number of
non-equal rank comparisons in the sentence5max
Lt (F ) =
0
F

J−1
∑

J
∑

δ(r(fj01 ) 6= r(fj02 )).

j1 =1 j2 =j1 +1(1)
5

Lt (F 0 ),max Lt (F̃ 0 )F̃ 0which will take a value between 0 (when F 0 has
maximal loss), and 1 (when F 0 matches one ofthe oracle orderings). In Figure 2 (b), Lt (F 0 ) =2 and max Lt (F̃ 0 ) = 8, so At (F 0 ) = 0.75.
4.3 Chunk Fragmentation
Another measure that has been used in evaluation of translation accuracy (Banerjee andLavie, 2005) and pre-ordering accuracy (Talbot
et al., 2011) is chunk fragmentation. This measure is based on the number of chunks that thesentence needs to be broken into to reproduce
the correct ordering, with a motivation that the
number of continuous chunks is equal to thenumber of times the reader will have to jump toa diﬀerent position in the reordered sentence toread it in the target order. One way to measure
the number of continuous chunks is considering0whether each word pair fj0 and fj+1
is discon0
tinuous (the rank of fj+1 is not equal to or one
greater than fj0 )0discont(fj0 , fj+1)=
00
δ(r(fj0 ) 6= r(fj+1) ∧ r(fj0 ) + 1 6= r(fj+1))

and sum over all word pairs in the sentence tocreate a sentence-based loss

δ(r(fj01 ) > r(fj02 ))j1 =1 j2 =j1 +1

0

At (F 0 ) = 1 −F̃ 0Kendall’s τ

Lt (F 0 ) =Finally, we use this maximum loss to normalize
the actual loss to get an accuracy

The traditional formulation of Kendall’s τ assumes
no ties in rank, and thus the maximum loss can be calculated as J(J − 1)/2.

Lc (F 0 ) =

J−1
∑

0
discont(fj0 , fj+1
)

(2)

j=1

While this is the formulation taken by previous work, we found that this under-penalizes
bad reorderings of the ﬁrst and last words ofthe sentence, which can contribute to the loss
only once, as opposed to other words which cancontribute to the loss twice. To account for
this, when calculating the chunk fragmentation
score, we additionally add two sentence boundary words f0 and fJ+1 with ranks r(f0 ) = 0 andr(fJ+1 ) = 1 + maxr(fj0 ) and redeﬁne the sum0
fj ∈F 0mation in Equation (2) to consider these words(e.g. Figure 2 (c)).

procedure WeightUpdate(F , A, w)
D ← parse(F, w). Create parse forestḊ ← argmax S(D|F, w) + L(D|F, A)D∈D. Find the model parseD̂ ← argmin L(D|F, A) − αS(D|F, w)
D∈D. Find the oracle parse
if L(D̂|F, A) 6= L(Ḋ|F, A) thenw ← β(w + γ(φ(D̂, F ) − φ(Ḋ, F ))). Perform weight update
end ifend procedure
Figure 3: An online update for sentence F , alignment
A, and weight vector w. α is a very small constant,and β and γ are deﬁned by the update strategy.

Similarly to Kendall’s τ , we can also deﬁne
an accuracy measure between 0 and 1 using the
maximum loss, which will be at most J + 1,
which corresponds to the total number of comparisons made in calculating the loss6
Ac (F 0 ) = 1 −Lc (F 0 ).
J +1

In Figure 2 (c), Lc (F 0 ) = 3 and J + 1 = 6, so
Ac (F 0 ) = 0.5.

5Learning a BTG Parser for
Reordering

Now that we have a deﬁnition of loss over reorderings produced by the model, we have aclear learning objective: we would like to ﬁndreorderings F 0 with low loss. The learning algorithm we use to achieve this goal is motivatedby discriminative training for machine translation systems (Liang et al., 2006), and extended
to use large-margin training in an online framework (Watanabe et al., 2007).
5.1

Learning Algorithm

Learning uses the general framework of largemargin online structured prediction (Crammer
et al., 2006), which makes several passes throughthe data, ﬁnding a derivation with high modelscore (the model parse) and a derivation with6

It should be noted that for sentences of length one orsentences with tied ranks, the maximum loss may be lessthan J + 1, but for simplicity we use this approximation.

minimal loss (the oracle parse), and updating w
if these two parses diverge (Figure 3).
In order to create both of these parses eﬃciently, we ﬁrst create a parse forest encoding alarge number of derivations Di according to themodel scores. Next, we ﬁnd the model parse Ḋi ,which is the parse in the forest Di that maximizes the sum of the model score and the loss
S(Dk |Fk , w)+L(Dk |Fk , Ak ). It should be notedthat here we are considering not only the modelscore, but also the derivation’s loss. This isnecessary for loss-driven large-margin training(Crammer et al., 2006), and follows the basic
intuition that during training, we would like tomake it easier to select negative examples withlarge loss, causing these examples to be penalized more often and more heavily.
We also ﬁnd an oracle parse D̂i , which is selected solely to minimize the loss L(Dk |Fk , Ak ).
One important diﬀerence between the model we
describe here and traditional parsing models isthat the target derivation D̂k is a latent variable.
Because many Dk achieve a particular reordering F 0 , many reorderings F 0 are able to minimize the loss L(Fk0 |Fk , Ak ). Thus it is necessary
to choose a single oracle derivation to treat as
the target out of many equally good reorderings.
DeNero and Uszkoreit (2011) resolve this ambiguity with four features with empirically tuned
scores before training a monolingual parser andreordering model. In contrast, we follow previous work on discriminative learning with latentvariables (Yu and Joachims, 2009), and breakties within the pool of oracle derivations by selecting the derivation with the largest modelscore. From an implementation point of view,
this can be done by ﬁnding the derivation thatminimizes L(Dk |Fk , Ak ) − αS(Dk |Fk , w), where
α is a constant small enough to ensure that theeﬀect of the loss will always be greater than theeﬀect of the score.
Finally, if the model parse Ḋk has a loss thatis greater than that of the oracle parse D̂k , weupdate the weights to increase the score of theoracle parse and decrease the score of the model
parse. Any criterion for weight updates may be
used, such as the averaged perceptron (Collins,
2002) and MIRA (Crammer et al., 2006), butwe opted to use Pegasos (Shalev-Shwartz et al.,2007) as it allows for the introduction of regularization and relatively stable learning.
To perform this full process, given a source
sentence Fk , alignment Ak , and model weights
w we need to be able to eﬃciently calculatescores, calculate losses, and create parse forestsfor derivations Dk , the details of which will be
explained in the following sections.
5.2 Scoring Derivation TreesFirst, we must consider how to eﬃciently assignscores S(D|F, w) to a derivation or forest duringparsing. The most standard and eﬃcient way to
do so is to create local features that can be calculated based only on the information included
in a single node d in the derivation tree. The
score of the whole tree can then be expressed as
the sum of the scores from each node:∑
S(d|F, w)
S(D|F, w) =
d∈D

=

∑∑

d∈D

wi φi (d, F ).

i

Based on this restriction, we deﬁne a number offeatures that can be used to score the parse tree.
To ease explanation, we represent each node in
the derivation as d = hs, l, c, c + 1, ri, where sis the node’s symbol (str, inv, or term), whilel and r are the leftmost and rightmost indicesof the span that d covers. c and c + 1 are therightmost index of the left child and leftmost
index of the right child for non-terminal nodes.
All features are intersected with the node label s, so each feature described below corresponds to three diﬀerent features (or two forfeatures applicable to only non-terminal nodes).
• φlex : Identities of words in positions fl , fr ,fc , fc+1 , fl−1 , fr+1 , fl fr , and fc fc+1 .
• φclass : Same as φlex , but with words abstracted to classes. We use the 50 classes
automatically generated by Och (1999)’s
method that are calculated during alignment in standard SMT systems.
• φbalance : For non-terminals, features indicating whether the length of the left span(c − l + 1) is lesser than, equal to, or greaterthan the length of the right span (r − c).
• φtable : Features, bucketed by length, thatindicate whether “fl . . . fr ” appears as acontiguous phrase in the SMT training
data, as well as the log frequency of thenumber of times the phrase appears total
and the number of times it appears as acontiguous phrase (DeNero and Uszkoreit,2011). Phrase length is limited to 8, andphrases of frequency one are removed.
• φpos : Same as φlex , but with words abstracted to language-dependent POS tags.
• φcf g : Features indicating the label of thespans fl . . . fr , fl . . . fc , and fc+1 . . . fr in asupervised parse tree, and the intersectionof the three labels. When spans do not correspond to a span in the supervised parsetree, we indicate “no span” with the label“X” (Zollmann and Venugopal, 2006).
Most of these features can be calculated fromonly a parallel corpus, but φpos requires a POS
tagger and φcf g requires a full syntactic parser
in the source language. As it is preferable tohave a method that is applicable in languages
where these tools are not available, we perform
experiments both with and without the featuresthat require linguistic analysis tools.
5.3 Finding Losses for Derivation Trees
The above features φ and their corresponding
weights w are all that are needed to calculatescores of derivation trees at test time. However,during training, it is also necessary to ﬁnd model
parses according to the loss-augmented scoring
function S(D|F, w)+L(D|F, A) or oracle parses
according to the loss L(D|F, A). As noted by
Taskar et al. (2003), this is possible if our losses
can be factored in the same way as the feature
space. In this section, we demonstrate that theloss L(d|F, A) for the evaluation measures wedeﬁned in Section 4 can (mostly) be factored
over nodes in a fashion similar to features.

5.3.1 Factoring Kendall’s τ
For Kendall’s τ , in the case of terminal nodes,
Lt (d = hterm, l, ri|F, A) can be calculated by
performing the summation in Equation (1). We
can further deﬁne this sum recursively and use
memoization for improved eﬃciency
Lt (d|F, A) =Lt (hterm, l, r − 1i|F, A)
+

r−1
∑

δ(r(fj ) > r(fr )).

(3)

j=l

For non-terminal nodes, we ﬁrst focus on
straight non-terminals with parent node d =hstr, l, c, c + 1, ri, and left and right child nodes
dl = hsl , l, lc, lc+1, ci and dr = hsr , c+1, rc, rc+
1, ri. First, we note that the loss for the subtree
rooted at d can be expressed as
Lt (d|F, A) =Lt (dl |F, A) + Lt (dr |F, A)rc∑∑
δ(r(fj1 ) > r(fj2 )).
+j1 =l j2 =c+1

In other words, the subtree’s total loss can befactored into the loss of its left subtree, theloss of its right subtree, and the additional loss
contributed by comparisons between the words
spanning both subtrees. In the case of inverted
terminals, we must simply reverse the comparison in the ﬁnal sum to be δ(r(fj1 ) < r(fj2 )).
5.3.2 Factoring Chunk Fragmentation
Chunk fragmentation loss can be factored in asimilar fashion. First, it is clear that the loss forthe terminal nodes can be calculated eﬃciently
in a fashion similar to Equation (3). In order tocalculate the loss for non-terminals d, we notethat the summation in Equation (2) can be divided into the sum over the internal bi-gramsin the left and right subtrees, and the bi-gram
spanning the reordered trees
Lc (d|F, A) =Lc (dl |F, A) + Lc (dr |F, A)
0+ discont(fc0 , fc+1).

However, unlike Kendall’s τ , this equation relies not on the ranks of fc and fc+1 in the origi0in
nal sentence, but on the ranks of fc0 and fc+1
the reordered sentence. In order to keep trackof these values, it is necessary to augment eachnode in the tree to be d = hs, l, c, c + 1, r, tl, tri
with two additional values tl and tr that indicate the position of the leftmost and rightmost
words after reordering. Thus, a straight nonterminal parent d with children dl = hsl , l, lc, lc+
1, c, tl, tlri and dr = hsr , c+1, rc, rc+1, r, trl, tri
will have loss as follows
Lc (d|F, A) =Lc (dl |F, A) + Lc (dr |F, A)+ discont(ftlr , ftrl )with a similar calculation being possible for inverted non-terminals.
5.4 Parsing Derivation Trees
Finally, we must be able to create a parse forestfrom which we select model and oracle parses.
As all feature functions factor over single nodes,
it is possible to ﬁnd the parse tree with the highest score in O(J 3 ) time using the CKY algorithm. However, when keeping track of target
positions for calculation of chunk fragmentation
loss, there are a total of O(J 5 ) nodes, an unreasonable burden in terms of time and memory.
To overcome this problem, we note that this setting is nearly identical to translation using synchronous CFGs with an integrated bigram LM,
and thus we can employ cube-pruning to reduce
our search space (Chiang, 2007).

6 Experiments
Our experiments test the reordering and translation accuracy of translation systems using the
proposed method. As reordering metrics, we use
Kendall’s τ and chunk fragmentation (Talbot etal., 2011) comparing the system F 0 and oracle
F 0 calculated with manually created alignments.
As translation metrics, we use BLEU (Papineni
et al., 2002), as well as RIBES (Isozaki et al.,2010a), which is similar to Kendall’s τ , but evaluated on the target sentence E instead of the reordered sentence F 0 . All scores are the averageof three training runs to control for randomness
in training (Clark et al., 2011).
For translation, we use Moses (Koehn et al.,2007) with lexicalized reordering (Koehn et al.,2005) in all experiments. We test three types

orig
3-step3-step+φpos
3-step+φcf glader
lader+φpos
lader+φcf g

Chunk
61.22
63.51
64.28
65.76
73.19
73.97
75.06

en-ja
τ BLEU
73.46
21.87
72.55
21.45
72.11
21.45
75.32
21.67
78.44 23.11
79.24 23.32
80.53 23.36

RIBES
68.25
67.66
67.44
68.47
69.86
69.78
70.89

Chunk
66.42
67.17
67.56
67.23
75.14
75.49
75.14

ja-en
τ BLEU
72.99
18.34
73.01
17.78
74.21
18.18
74.06
18.18
79.14 19.54
78.79 19.89
77.80
19.35

RIBES
65.36
64.42
64.65
64.93
66.93
67.24
66.12

Table 2: Reordering (chunk, τ ) and translation (BLEU, RIBES) results for each system. Bold numbers
indicate no signiﬁcant diﬀerence from the best system (bootstrap resampling with p > 0.05) (Koehn, 2004).

RM-train
RM-test
TM/LM
Tune
Test

sent.
602
555
329k
1166
1160

word (ja)
14.5k
11.2k
6.08M
26.8k
28.5k

word (en)
14.3k
10.4k
5.91M
24.3k
26.7k

Table 1: The number of sentences and words fortraining and testing the reordering model (RM),
translation model (TM), and language model (LM).

except φpos and φcf g . In addition, we test systems with φpos and φcf g added. For English,
we use the Stanford parser (Klein and Manning,2003) for both POS tagging and CFG parsing.
For Japanese, we use the KyTea tagger (Neubig et al., 2011) for POS tagging,8 and the EDA
word-based dependency parser (Flannery et al.,2011) with simple manual head-rules to convert
a dependency parse to a CFG parse.
6.1 Eﬀect of Pre-orderingof pre-ordering: original order with F 0 ← F(orig), pre-orderings learned using the 3-stepprocess of DeNero and Uszkoreit (2011) (3step), and the proposed model with latent
derivations (lader).7 Except when stated otherwise, lader was trained to minimize chunk
fragmentation loss with a cube pruning stack
pop limit of 50, and the regularization constantof 10−3 (chosen through cross-validation).
We test our systems on Japanese-English andEnglish-Japanese translation using data fromthe Kyoto Free Translation Task (Neubig, 2011).
We use the training set for training translationand language models, the development set forweight tuning, and the test set for testing (Table1). We use the designated development and test
sets of manually created alignments as training
data for the reordering models, removing sentences of more than 60 words.
As default features for lader and the monolingual parsing and reordering models in 3-step,
we use all the features described in Section 5.2
7

Available open-source: http://phontron.com/lader

Table 2 shows reordering and translation resultsfor orig, 3-step, and lader. It can be seenthat the proposed lader outperforms the baselines in both reordering and translation.9 There
are a number of reasons why lader outperforms 3-step. First, the pipeline of 3-step
suﬀers from error propogation, with errors inmonolingual parsing and reordering resulting
in low overall accuracy.10 Second, as Section
5.1 describes, lader breaks ties between oracle parses based on model score, allowing easyto-reproduce model parses to be chosen during training. In fact, lader generally foundtrees that followed from syntactic constituency,
while 3-step more often used terminal nodes
8

In addition, following the example of Sudoh et al.
(2011a)’s reordering rules, we lexicalize all particles.
9
It should be noted that our results for 3-step are
signiﬁcantly worse than those of DeNero and Uszkoreit(2011). Likely reasons include a 20x diﬀerence in training
data size, the fact that we are using naturally translated
text as opposed to text translated speciﬁcally to create
word alignments, or diﬀerences in implementation.
10
When using oracle parses, chunk accuracy was up to81%, showing that parsing errors are highly detrimental.

Lc
Lt
Lc + Lt

Chunk
73.19
70.37
72.55

en-ja
τ BLEU
78.44 23.11
79.57
22.57
80.58 22.89

RIBES
69.86
69.47
70.34

Chunk
75.14
72.51
74.44

ja-en
τ BLEU
79.14 19.54
78.93
18.52
79.82
19.21

RIBES
66.93
66.26
66.48

Table 3: Results for systems trained to optimize chunk fragmentation (Lc ) or Kendall’s τ (Lt ).

that spanned constituent boundaries (as long as
the phrase frequency was high). Finally, as Section 6.2 shows in detail, the ability of lader tomaximize reordering accuracy directly allows for
improved reordering and translation results.
It can also be seen that incorporating POS
tags or parse trees improves accuracy of bothlader and 3-step, particularly for EnglishJapanese, where syntax has proven useful for
pre-ordering, and less so for Japanese-English,
where syntactic pre-ordering has been less successful (Sudoh et al., 2011b).
We also tested Moses’s implementation of hierarchical phrase-based SMT (Chiang, 2007),
which achieved BLEU scores of 23.21 and 19.30
for English-Japanese and Japanese-English respectively, approximately matching lader inaccuracy, but with a signiﬁcant decrease in decoding speed. Further, when pre-ordering withlader and hierarchical phrase-based SMT werecombined, BLEU scores rose to 23.29 and 19.69,
indicating that the two techniques can be combined for further accuracy improvements.
6.2

Eﬀect of Training Loss

Table 3 shows results when one of three losses is
optimized during training: chunk fragmentation(Lc ), Kendall’s τ (Lt ), or the linear interpolation of the two with weights chosen so that bothlosses contribute equally (Lt + Lc ). In general,training successfully maximizes the criterion it istrained on, and Lt + Lc achieves good results on
both measures. We also ﬁnd that Lc and Lc +Lt
achieve the best translation results, which isin concert with Talbot et al. (2011), who ﬁnd
chunk fragmentation is better correlated withtranslation accuracy than Kendall’s τ . This is
an important result, as methods such as thatof Tromble and Eisner (2009) optimize pairwiseorig
man-602
auto-602
auto-10k

en-ja
BLEU/RIBES
21.87 68.25
23.11 69.86
22.39 69.19
22.53 69.68

ja-en
BLEU/RIBES
18.34 65.36
19.54 66.93
18.58 66.07
18.79 66.89

Table 4: Results based on data size, and whether
manual or automatic alignments are used in training.

word comparisons equivalent to Lt , which may
not be optimal for translation.
6.3 Eﬀect of Automatic Alignments
Table 4 shows the diﬀerence between using manual and automatic alignments in the training oflader. lader is able to improve over the orig
baseline in all cases, but when equal numbersof manual and automatic alignments are used,
the reorderer trained on manual alignments issigniﬁcantly better. However, as the number of
automatic alignments is increased, accuracy improves, approaching that of the system trainedon a smaller number of manual alignments.

7 Conclusion
We presented a method for learning a discriminative parser to maximize reordering accuracy
for machine translation. Future work includes
application to other language pairs, development of more sophisticated features, investigation of probabilistic approaches to inference, andincorporation of the learned trees directly intree-to-string translation.

Acknowledgments
We thank Isao Goto, Tetsuo Kiso, and anonymous reviewers for their helpful comments, andDaniel Flannery for helping to run his parser.

References
Satanjeev Banerjee and Alon Lavie. 2005. METEOR: An automatic metric for MT evaluation
with improved correlation with human judgments.
In Proc. ACL Workshop.
Alexandra Birch, Miles Osborne, and Phil Blunsom.
2010. Metrics for MT evaluation: evaluating reordering. Machine Translation, 24(1):15–26.
Marine Carpuat, Yuval Marton, and Nizar Habash.
2010. Improving arabic-to-english statistical machine translation by reordering post-verbal subjects for alignment. In Proc. ACL.
David Chiang. 2007. Hierarchical phrase-basedtranslation. Computational Linguistics, 33(2).
Jonathan H. Clark, Chris Dyer, Alon Lavie, andNoah A. Smith. 2011. Better hypothesis testing for statistical machine translation: Controlling for optimizer instability. In Proc. ACL, pages
176–181.
Michael Collins, Philipp Koehn, and Ivona Kucerova.
2005. Clause restructuring for statistical machinetranslation. In Proc. ACL.
Michael Collins. 2002. Discriminative training methods for hidden markov models: Theory and experiments with perceptron algorithms. In Proc.
EMNLP, pages 1–8.
Koby Crammer, Ofer Dekel, Joseph Keshet, Shai
Shalev-Shwartz, and Yoram Singer. 2006. Online
passive-aggressive algorithms. Journal of Machine
Learning Research, 7:551–585.
John DeNero and Jakob Uszkoreit. 2011. Inducing sentence structure from parallel corpora forreordering. In Proc. EMNLP.
Chris Dyer and Philip Resnik. 2010. Context-free
reordering, ﬁnite-state translation. In Proc. HLTNAACL.
Daniel Flannery, Yusuke Miyao, Graham Neubig,
and Shinsuke Mori. 2011. Training dependency
parsers from partially annotated corpora. In Proc.
IJCNLP, pages 776–784, Chiang Mai, Thailand,
November.
Dmitriy Genzel. 2010. Automatically learningsource-side reordering rules for large scale machinetranslation. In Proc. COLING.
Aria Haghighi, John Blitzer, John DeNero, and Dan
Klein. 2009. Better word alignments with supervised ITG models. In Proc. ACL.
Hideki Isozaki, Tsutomu Hirao, Kevin Duh, Katsuhito Sudoh, and Hajime Tsukada. 2010a. Automatic evaluation of translation quality for distantlanguage pairs. In Proc. EMNLP, pages 944–952.

Hideki Isozaki, Katsuhito Sudoh, Hajime Tsukada,and Kevin Duh. 2010b. Head ﬁnalization: A
simple reordering rule for sov languages. In Proc.
WMT and MetricsMATR.
Jason Katz-Brown, Slav Petrov, Ryan McDonald, Franz Och, David Talbot, Hiroshi Ichikawa,
Masakazu Seno, and Hideto Kazawa. 2011. Training a parser for machine translation reordering. In
Proc. EMNLP, pages 183–192.
Maurice G. Kendall. 1938. A new measure of rankcorrelation. Biometrika, 30(1/2):81–93.
Maxim Khalilov and Khalil Sima’an. 2011. Contextsensitive syntactic source-reordering by statisticaltransduction. In Proc. IJCNLP.
Dan Klein and Christopher D. Manning. 2003. Accurate unlexicalized parsing. In Proc. ACL, pages
423–430.
Phillip Koehn, Franz Josef Och, and Daniel Marcu.
2003. Statistical phrase-based translation. In
Proc. HLT, pages 48–54.
Philipp Koehn, Amittai Axelrod, Alexandra Birch
Mayne, Chris Callison-Burch, Miles Osborne, andDavid Talbot. 2005. Edinburgh system description for the 2005 IWSLT speech translation evaluation. In Proc. IWSLT.
Philipp Koehn, Hieu Hoang, Alexandra Birch,
Chris Callison-Burch, Marcello Federico, Nicola
Bertoldi, Brooke Cowan, Wade Shen, Christine
Moran, Richard Zens, Chris Dyer, Ondrej Bojar,
Alexandra Constantin, and Evan Herbst. 2007.
Moses: Open source toolkit for statistical machinetranslation. In Proc. ACL, pages 177–180.
Philipp Koehn. 2004. Statistical signiﬁcance tests
for machine translation evaluation. In Proc.
EMNLP.
Chi-Ho Li, Minghui Li, Dongdong Zhang, Mu Li,
Ming Zhou, and Yi Guan. 2007. A probabilistic
approach to syntax-based reordering for statisticalmachine translation. In Proc. ACL.
Percy Liang, Alexandre Bouchard-Côté, Dan Klein,and Ben Taskar. 2006. An end-to-end discriminative approach to machine translation. In Proc.
ACL, pages 761–768.
Graham Neubig, Yosuke Nakata, and Shinsuke Mori.
2011. Pointwise prediction for robust, adaptable
Japanese morphological analysis. In Proc. ACL,
pages 529–533, Portland, USA, June.
Graham Neubig. 2011. The Kyoto free translation
task. http://www.phontron.com/kftt.
Franz Josef Och. 1999. An eﬃcient method for determining bilingual word classes. In Proc. EACL.

Kishore Papineni, Salim Roukos, Todd Ward, andWei-Jing Zhu. 2002. BLEU: a method for automatic evaluation of machine translation. In Proc.
COLING, pages 311–318.
Kay Rottmann and Stephan Vogel. 2007. Word reordering in statistical machine translation with a
pos-based distortion model. In Proc. of TMI-2007.
Shai Shalev-Shwartz, Yoram Singer, and Nathan
Srebro. 2007. Pegasos: Primal estimated subgradient solver for SVM. In Proc. ICML, pages
807–814.
Katsuhito Sudoh, Kevin Duh, Hajime Tsukada,
Masaaki Nagata, Xianchao Wu, Takuya Matsuzaki, and Jun’ichi Tsujii.
2011a.
NTTUT statistical machine translation in NTCIR-9
PatentMT. In Proc. NTCIR.
Katsuhito Sudoh, Xianchao Wu, Kevin Duh, Hajime Tsukada, and Masaaki Nagata. 2011b. Postordering in statistical machine translation. In
Proc. MT Summit.
David Talbot, Hideto Kazawa, Hiroshi Ichikawa, Jason Katz-Brown, Masakazu Seno, and Franz Och.
2011. A lightweight evaluation framework for machine translation reordering. In Proc. WMT.
Ben Taskar, Carlos Guestrin, and Daphne Koller.
2003. Max-margin Markov networks. Proc. NIPS,
16.
Roy Tromble and Jason Eisner. 2009. Learning linear ordering problems for better translation. In
Proc. EMNLP.
Karthik Visweswariah, Rajakrishnan Rajkumar,
Ankur Gandhe, Ananthakrishnan Ramanathan,and Jiri Navratil. 2011. A word reorderingmodel for improved machine translation. In Proc.
EMNLP.
Taro Watanabe, Jun Suzuki, Hajime Tsukada, andHideki Isozaki. 2007. Online large-margin training for statistical machine translation. In Proc.
EMNLP, pages 764–773.
Dekai Wu. 1997. Stochastic inversion transduction
grammars and bilingual parsing of parallel corpora. Computational Linguistics, 23(3).
Fei Xia and Michael McCord. 2004. Improving astatistical MT system with automatically learned
rewrite patterns. In Proc. COLING.
Peng Xu, Jaeho Kang, Michael Ringgaard, and Franz
Och. 2009. Using a dependency parser to improve
smt for subject-object-verb languages. In Proc.
NAACL.
Kenji Yamada and Kevin Knight. 2001. A syntaxbased statistical translation model. In Proc. ACL.
Chun-Nam John Yu and Thorsten Joachims. 2009.
Learning structural SVMs with latent variables.
In Proc. ICML, pages 1169–1176.

Yuqi Zhang, Richard Zens, and Hermann Ney. 2007.
Chunk-level reordering of source language sentences with automatically learned rules for statistical machine translation. In Proc. SSST.
Andreas Zollmann and Ashish Venugopal. 2006.
Syntax augmented machine translation via chartparsing. In Proc. WMT, pages 138–141.