Dependency Tree Abstraction for Long-Distance Reordering in
Statistical Machine Translation
Chenchen Ding
Department of Computer Science
University of Tsukuba
1-1-1 Tennodai, Tsukuba, Ibaraki , Japan
tei@mibel.cs.tsukuba.ac.jp

Yuki Arase
Microsoft Research
No. 5 Danling St., Haidian Dist.
Beijing, P.R. China
yukiar@microsoft.com

Abstract[X],

Word reordering is a crucial techniquein statistical machine translation in whichsyntactic information plays an importantrole. Synchronous context-free grammar has typically been used for this purpose with various modifications for adding
flexibilities to its synchronized tree generation. We permit further flexibilities
in the synchronous context-free grammar
in order to translate between languages
with drastically different word order. Our
method pre-processes a parallel corpus by
abstracting source-side dependency trees,and performs long-distance reordering on
top of an off-the-shelf phrase-based system. Experimental results show that our
method significantly outperforms previous
phrase-based and syntax-based models fortranslation between English and Japanese.

1[X](root)[N]isgradually
applied
.

when
[N]
is
used

the
fluid
pressurecylinder31

fluidwhen the fluid pressure cylinder 31 is used, fluid is gradually applied.

Figure 1: English abstraction tree example
Ullman, 1972). The original SCFG assumes thatthe syntactic trees of the source and target languages can be derived synchronously. However,this assumption is too strict for handling parallel sentences that are often comparable rather thanparallel. For alleviating this assumption, some researchers have added flexibilities in synchronizedtree generation (Wu, 1997; Burkett et al., 2010).
In addition, in the SMT framework, there is anapproach that alleviates the assumption by only
generating the source-side syntactic tree and projecting it to the target-side sentence (Yamada andKnight, 2001; Liu et al., 2006).

Introduction

In practice, these existing methods are not flexible enough to handle parallel sentence pairs, especially those of SVO and SOV languages. Therefore, we permit further flexibility in SCFG aiming
to effectively conduct long-distance reordering.
We design our method as a pre-processing procedure so that we can use a well-developed phrasebased system without adding heavy computational
complexity to the system. Specifically, we propose
an abstraction tree that is a shallow and nested
representation, i.e., abstraction of the dependency
tree as Fig. 1 depicts. Our method pre-processes aparallel corpus by generating source-side abstraction trees and projecting the trees onto the targetside sentences. It then decomposes the corpus
by collecting corresponding node pairs as a new
corpus, and finally trains the phrase-based model.
In this manner, the source-side grammar is determined on the fly for each sentence based on a de-Since the inception of statistical machine translation (SMT), long-distance word reordering has
been a notable challenge, particularly when translating between languages with drastically different
word orders, such as subject-verb-object (SVO)
and subject-object-verb (SOV) languages like English and Japanese, respectively. Phrase-basedmodels (Koehn et al., 2003; Och and Ney, 2004;
Xiong et al., 2006) have been strong in local
translation and reordering. However, phrase-basedmodels cannot effectively conduct long-distance
reordering because they are based purely on statistics of syntax-independent phrases. As a complementary approach to phrase-based models, someresearchers have incorporated syntactic information into an SMT framework (Wu, 1997; Yamada
and Knight, 2001; Liu et al., 2006) using synchronous context-free grammar (SCFG) (Aho and424

Proceedings of the 14th Conference of the European Chapter of the Association for Computational Linguistics, pages 424–433,
Gothenburg, Sweden, April 26-30 2014. c 2014 Association for Computational Linguistics

Algorithm 1 CKY-style decoding

pendency parse of the source sentence. The target
side of each production in the grammar is determined by running the phrase-based decoder.
We empirically show effectiveness of our
method for English-to-Japanese and Japanese-toEnglish translations by comparing it to phrasebased and syntax-based models. Experimental results show that our method significantly outperforms the previous methods with respect to the
BLEU (Papineni et al., 2002) metric.

2

Input: Input sentence u and its dependency tree ru , translation model T M , block-LM bLM , sentence-LM sLM ,size of m-best m
1: τu ← generate abstraction tree of u using ru
2: N odeT rans[][] ← ∅3: for all node in τu do
4:
m-best ← Decode(node, T M, bLM, m)
5:(start, end) ← start and end indices of node in u
6:
N odeT rans[start][end] ← m-best
7: end for
8: for start := 1 to |u| do
9:for span := 0 to |u| − 1 do
10:
end ← start + span
11:
ChildT rans[] ← ∅12:for all (i, j) such that start ≤ i ≤ j ≤ end do
13:
if N odeT rans[i][j] 6= ∅ then14:
add N odeT rans[i][j] to ChildT rans
15:
end if16:
end for
17:
CubeP runing(N odeT rans[start][end],
ChildT rans, sLM, m)
18:
end forRelated WorkFor adding flexibilities to SCFG under an SMT
scenario, previous studies generate only a sourceside syntactic tree and project it to the target-side
sentence regardless of the true target-side syntactic
structure. Liu et al. (2006) propose a tree-to-stringmodel using a source-side constituency tree to extract correspondences between the source-side tree
and the target-side sentence. Quirk et al. (2005)
and Xie et al. (2011) use a dependency tree for thesame purpose. Since these methods project a finegrained source-side syntax tree, an accurate projection is possible only when the target-side sentence has a syntactic structure that is similar tothe source-side. Zhu and Xiao (2011) and Huang
and Pendus (2013) generalize rules obtained by
the tree-to-string model to increase the chance ofrule matching at decoding. Despite their merits,
none of these methods resolves the problem of tree
projection to the target-side.
The hierarchical phrase-based model (HIERO)
proposed by Chiang (2007) is independent of any
syntactic information and generates SCFG rules
only from parallel sentence pairs. Li et al. (2012)
and Feng et al. (2012) incorporate syntactic information into HIERO as soft constraints. Since thesemethods are bound by the original HIERO rulesthat are independent of syntactic information, theirrules cannot represent the global syntactic structure of a sentence.
There are also pre-reordering methods for longdistance reordering in SVO-to-SOV translations
using heuristics designed based on source-side
syntactic structures (Xu et al., 2009; Isozaki et al.,2010; Isozaki et al., 2012). They are fine-tuned tohandle only specific reordering problems in a predetermined language pair. Another approach is tostatistically learn pre-reordering rules from a corpus; however, this requires a highly parallel training corpus consisting of literal translations to learn

19: end for

effective rules (Neubig et al., 2012; Navratil et al.,2012). Such a training dataset is not widely available in many languages.

3

Overview of the Proposed Method

Our method pre-processes sentences in a parallel corpus based on source-side abstraction trees.
It first generates an abstraction tree τs of a sourceside sentence s by abstracting its dependency treers : (s, rs ) → τs . It then projects the tree to thetarget-side sentence t for generating a target-side
abstraction tree τt that has exactly the same structure to τs , i.e., (τs , t) → τt . The abstractiontree generation process can be adapted to translating languages by specifying source-side part-ofspeeches (POSs) as input. Abstraction tree structures also depend on the dependency grammar thata parser uses. In this study, we assume commonlyused Stanford typed dependency (de Marneffe etal., 2006) for English and the chunk-based dependency with ipadic (Asahara and Matsumoto, 2003)
for Japanese. Investigation of effects of different
dependency grammars is our future work.
We decompose the sentence pair into node pairs
according to correspondences between the source
and target abstraction trees, and generate a new
corpus referred to as a block-corpus (Fig. 6). Using the block-corpus and the original corpus, wetrain a phrase-based model. Its translation modelis trained with the block-corpus, and two targetside language models (LMs) are trained with theblock-corpus (referred to as block-LM) and the425when [N]a high pressure hot water cylinder is used

Figure 3: [X] and [P] node detection. Since the word

Figure 2: [N] node detection example“used” is a head, it and its governing span are detached fromoriginal corpus (referred to as sentence-LM), respectively. Thus the sentence-LM can be trainedusing a larger-scale monolingual corpus. Compared to previous methods that also decompose
sentence pairs (Xu et al., 2005; Sudoh et al., 2010),
our method is more syntax-oriented.
In decoding, we adopt the parsing algorithmwith cube-pruning (Huang and Chiang, 2005) intoa phrase-based decoder to translate the abstraction tree of an input sentence efficiently. As
Algorithm 1 shows, our decoder first generates
the abstraction tree of the input sentence (line1), and independently translates each node using the block-LM that models ordering among
non-terminals and lexical words (line 3–7). It
then combines the m-best translation hypothesesof each node to construct a sentence-level translation (line 8–19). Specifically, we insert sets ofthe m-best translation hypotheses of child nodes
into the m-best hypotheses of their parent node
by replacing the corresponding non-terminals using the cube-pruning (line 17). The ordering ofthese child nodes has been determined in theirparent node by the phrase-based model that regards non-terminals only as single words. By
doing so, long-distance reordering is solved considering the global syntactic structure and contexts (lexical strings) preserved in the node. In
cube-pruning, we use the sentence-LM to compose fluent sentence-level translation. The blockLM and sentence-LM scores are treated as independent features.
The computational complexity of our decoder(line 3–19) is O(|N |C), where |N | is the numberof nodes in the abstraction-tree and C is a constant representing the complexity of phrase-based
decoder and cube-pruning. Since combinations ofhypotheses in cube-pruning are determined by theabstraction-tree in our method, the computational
cost is significantly smaller than HIERO’s case.

4

the root “applied” as a child node.

edges. For conducting abstraction based on syntactic structures, we merge a span governed by adependency head as a node and represent it by anon-terminal in a parent node. As a result, the i-th
node Ni consists of a sequence of lexical words w
and non-terminals L that replace spans governedby heads in the corresponding child nodes:
Ni = {Ψ|ψ1 , . . . , ψ|Ni | }, ψk ∈ {w, L}.
The edge Eij between a parent node Ni andits child node Nj corresponds to a governordependent relationship from the head in Ni to its
dependent wx in Nj . wx is another head and governs other words in Nj . The span covered by Nj
is replaced by a non-terminal in Ni .
We use three kinds of labels to represent L for
explicitly using syntactic information that is useful for long-distance reordering; [N], [P], and [X]according to the head in the corresponding node.
We label a child node [N] when its head word isa noun and forms a base noun phrase, [P] when
its head word is an adposition1 , and [X] for others
like verb phrases, conjunctive phrases, and relative phrases. These nodes play different roles in a
sentence. An [N] node, i.e., a base noun phrase,
adds context to a sentence. A [P] node depends
on other phrases and generally appears relatively
freely in a sentence. Thus, we assume that the [P]node requires special reordering.
The abstraction tree depicted in Fig. 1 has a parent [X] node “when [N] is used” and its child [N]node “the fluid pressure cylinder 31.” The word
“used” governs “cylinder” in the [N] node, and the[N] node folds the context in the [X] node.
4.2

Tree Construction

We begin with detecting [N] nodes, then proceed to [P] and [X] nodes. These processes requireto specify source-side POSs as input for adapting
to translating languages. We finally flatten fragmented nodes.
For detecting [N] nodes, we take a POS of noun
as input and identify each noun and its governingspan, i.e., a string of all governed words, using thesource-side dependency tree as Fig. 2 shows. We

Abstraction Tree Generation

In this section, we provide the formal definition ofan abstraction tree and the generation method.
4.1

is used , [N] is gradually applied .

Definition of Abstraction TreeWe define an abstraction tree as τ = {N , E},
where N is a set of nodes and E is a set of1426

A preposition in English and a postposition in Japanese.

Algorithm 2 [P] and [X] node detection… machine uses the cylinder that is …

Input: Source-side sentence s and its dependency tree rs ,POS list of adpositions P P os, [N] node list N -N odes
Output: [P] and [X] nodes P -N odes, X-N odes
1: P -N odes[] ← ∅, X-N odes[] ← ∅2: HeadList[] ← root of rs
3: repeat4:
head ← pop node from HeadList
5:ChildList[] ← all dependents of head
6:
for all child in ChildList do
7:
if child ∈/ N -N odes and child has dependents
then8:
add child to HeadList
9:remove child from ChildList
10:
end if
11:
end for12:
start ← smallest start index of nodes in ChildList
13:
end ← largest end index of nodes in ChildList
14:
if POS of head ∈ P P os then15:
add span [start, end] of s to P -N odes
16:
else
17:
add span [start, end] of s to X-N odes
18:
end if19:
remove head from HeadList

original [N][X]

Figure 4: Handling a complex noun phrase
clause. Such a complex node may require longdistance reordering of an inside clause when translating. Therefore, we separate the noun phrase andclause. We take a POS list whose word can be ahead of [P] and [X] nodes (preposition, verb, to,Wh-determiner/pronoun/adverb, and coordinating
conjunction for English) as input. If the POS of anoun’s dependent is in the list, we detach the dependency arc, and then re-attach the dependency
arc to the head of the noun. As a result, the basenoun phrase becomes an [N] node and its clause
becomes a [P] or [X] node that is transformed to asibling of the [N] node.
In Fig. 4, the word “cylinder” in the original [N]node has a relative clause and governs “is.” We detach the dependency arc and re-attach it to “uses”(the head of “cylinder”), so that the noun phrase
and the clause become sibling [N] and [X] nodes.

20: until HeadList = ∅regard descendant dependents as being governedby the noun for detecting a noun phrase of a complete form. We extract the span as a node and replace it by an [N] label in the sentence.
Next, we identify [P] and [X] nodes given a listof source-side POSs of adpositions as input. As
Algorithm 2 shows, after [N] node detection, we
trace the dependency tree from its root to leaves(line 3–20). We find all the dependents to the root,
then check if each dependent is a head. If a dependent of the root is a head and governs otherwords, we detach the dependent to process later(line 6–11). We then find the smallest start index
and largest end index of dependent words and set
the corresponding span as a node (if a dependentis in an [N] node, we use the start and end indicesof the [N] node). Each node is labeled according to the POS of its head as [P] or [X] (line 14–18). We then take the detached dependent as a newroot and repeat the process until no more detachment is possible. The computational complexity
is O(|s|2 ). Through this process, a span with direct dependencies is extracted as a node, and otherspans with descendant dependencies become descendant nodes, replaced by non-terminals in theirparent node as shown in Fig. 3.
4.3

[N]

4.4

Flattening Fragmented Nodes

The above processes are independent of the sizeof each node, meaning they produce fragmented
nodes of only a few words. Such fragmented
nodes make the tree projection to the target-sidedifficult. To solve this problem, we flatten the abstraction tree as shown in Algorithm 3. We process an internal node in τs from bottom to top. If
the covering span of an internal node is less than athreshold γ ∈ N, its child nodes are merged (line 3
and 4, Algorithm 3). Specifically, we reinsert thechild nodes by replacing the corresponding nonterminals with lexical strings that the child nodes
have been covered by. The computational cost isO(|N |). We investigate the effect of γ in the following evaluation section (Table 2).

5

Abstraction Tree Projection

In this section, we describe a method for projecting the obtained source-side abstraction tree onto
the target-side sentence.
5.1

Handling Complex Noun Phrase

Tree Structure Projection

We use word alignment results for tree structure
projection. However, accurate word alignment
is challenging when handling language pairs inwhich long-distance reordering is needed, and thealignment noise propagates to the tree projection.

As described in Sec. 4.2, we detect a noun phrase
as an [N] node. However, an [N] node becomes more complex than a base noun phrase
when the head governs a clause, such as a relative
427

Algorithm 3 Tree flattening

Algorithm 4 Tree projection

Input: Abstraction tree τs , threshold γ
Output: Flattened tree τs0
1: for all internal node in τs , from bottom to top do
2:(start, end) ← start and end indices of node3:
if end − start + 1 < γ then4:
τs0 ← M ergeChildN odes(node, τs )5:
end ifInput: Source-side abstraction tree τs , target-side sentencet, word alignment Aw between s and t
Output: Target-side abstraction tree τt
1: τt [] ← ∅2: remove links of function words in Aw
3: for span := |s| − 1 to 0 do
4:
for start := 1 to |s| do
5:end ← start + span
6:
if span [start, end] ∈ τs then7:c ← GenerateV ector([start, end], Aw )8:c∗ ← Solve(c)  Eq. (1) and Eq. (2)9:(i, j) ← start and end indices of c∗
10:
add span [i, j] of t as a node into τt
11:
Aw ← U pdateW ordAlignment(c, c∗ )12:
end if13:
end for

6: end for

To avoid this problem, we first omit alignment
links of function words whose alignment quality
tends to be lower than that of the content words.
We then complement the quality of word alignment by adapting the syntactic cohesion assumption (Yamada and Knight, 2001) that assumes aword string covered by a sub-tree of the sourceside syntactic tree corresponds to a string of contiguous words in the target-side sentence. Following the assumption, we project the k-th node of(s)
the source-side abstraction tree Nk to a string ofcontiguous words in the target-side:(s)Nk

14: end forthe original vector c while satisfying the hard constraint, and Eq. (2) selects the one whose norm islargest, i.e., a vector that has longest contiguous
word links to the target-side. For computational
efficiency, we use the greedy-search so that thecomputational cost is O(|t|). When Eq. (2) has
multiple solutions, word links in these solutions
are equally likely, and thus we merge them into a
unique solution. Specifically, we take the unionof the solutions and find the smallest index il andlargest index ir whose elements are 1. We then set
all elements between il and ir to 1.
As Algorithm 4 shows, we conduct this process in a top-down manner throughout the abstraction tree (line 3–14). When processing each node,
word alignment links are updated by overwriting
links in c with the ones in c∗ (line 11). The computational cost is O(|N (s) ||t|), where |N (s) | is thenumber of nodes in τs . Figure 5 shows a projection
example of a node. A node of “when [N] is used”
covers a span of “when the fluid pressure cylinder 31 is used.” The words in the span are aligned
to the 1st, 2nd, and 5th target words (chunks)2 ;however, the link to the 5th target word (chunk)is a mis-alignment. With the alignment vector cof [1, 1, 0, 0, 1, 0, 0], we can remove this misalignment and derive c∗ of [1, 1, 0, 0, 0, 0, 0].

7→ ti , . . . , tj , s.t. 1 ≤ i ≤ j ≤ |t|,where ti is the i-th word in the target-side sentenceand |t| is the number of words in the sentence.
For each node of the source-side abstraction
tree, we first obtain its covering span. We thendefine a vector c ∈ {0, 1}n whose elements represent word alignment links in a binary manner. If
and only if the i-th target word is aligned to a wordin the span, the i-th element of c becomes 1, otherwise it is 0. Since the original word alignment
represented by the vector c may be noisy, we finda vector c∗ ∈ {0, 1}n that maximizes the syntactic cohesion assumption. In c∗ , only consecutive
elements between two indices i and j are 1, andothers are 0. We derive such c∗ as follows:
Cmin (c) = {c0 | argmin kc0 − ck},(1)
c0
s.t. ∃ i, j, 1 ≤ i ≤ j ≤ n and
1 i ≤ k ≤ j,0ck =0 otherwise,c∗ =argmax kc0 k.
c0 ∈Cmin (c)

(2)

5.2

Fixed-Expression Recovery

The abstraction tree generation and projection are
based on a dependency tree, and thus may oversegment a fixed-expression, such as idioms andmulti-word expressions. Since a fixed-expression
composes a complete meaning using a contiguous
word string, splitting it into different nodes results

The operator k · k computes the Euclidean normof a vector and c0k is the k-th element of a vector
c0 . Finally, c∗ represents the best possible wordlinks that maximize the syntactic cohesion assumption, i.e., the longest contiguous word stringin the target-side, and that are closest to the original word alignment. Specifically, Eq. (1) determines vectors that have the smallest distance to

2
In Japanese, a unit of dependency is a chunk in general,and thus we conduct chunking before projection.

428

Node: whenis used[N]
Span: when the fluid pressure cylinder 31 is used

Input parallel corpus
When the fluid pressure cylinder 31
is used , fluid is gradually applied .

Target
流体 圧 シリンダ 31 の 場合 は 液体 が 徐々 に 排出 さ れる
sentence: こと と なる 。

Block-Corpus

𝒄 = 1, 1, 0, 0, 1, 0, 0

[X] 0 , [N] 0 is gradually applied .
when [N] 1 is used

Figure 5: Abstraction tree projection

the fluid pressure cylinder 31

in poor translation. To avoid this issue, we generate a list of fixed-expressions using conventional
methods (Evert, 2008) and force them to remain in
one node. On both the source and target abstraction trees, we recursively reinsert nodes to theirparent node when such a fixed-expression is oversegmented and spread over multiple nodes.
5.3

fluid

れる こと と なる 。

[N] 1 の 場合 は
流体 圧 シリンダ 31
流体

terminals in the source and target exemplars.

and test sets have one reference per sentence. Thisdataset is bidirectional and can be used for both EJ
and JE translation evaluation.
6.2

Block-Corpus Construction

Implementation of Proposed Method

We implement our method for EJ and JEtranslation tasks. In both cases, we use an
in-house implementation of English POS tagger (Collins, 2002) and a Japanese morphological analyzer (Kudo et al., 2004) for tokenization and POS tagging. As for EJ translation,
we use the Stanford parser (de Marneffe et al.,2006) to obtain English abstraction trees. We
also use an in-house implementation of a Japanesechunker (Kudo and Matsumoto, 2002) to obtainchunks in Japanese sentences. We apply the chunker just before tree projection for using a chunkas a projection unit, since a chunk is the basic
unit in Japanese. As for JE translation, we use
a popular Japanese dependency parser (Kudo andMatsumoto, 2002) to obtain Japanese abstraction
trees. We convert Japanese chunk-level dependency tree to a word-level using a simple heuristic. We use GIZA++ (Och and Ney, 2003) with thegrow-diag-final-and heuristic for word alignment.
We use an in-house implementation of
the bracketing transduction grammar (BTG)
model (Xiong et al., 2006) as the phrase-basedmodel that our method relies on for translation.
Non-terminals in our block-corpus are regarded
as a single word, and their alignments AL determined in the block-corpus are exclusively used toalign them. We set the maximum phrase length to
5 when training the translation model, since wefind that the performance is stable even setting
larger values as in (Koehn et al., 2003). We thentrain the sentence-LM and block-LM using theoriginal corpus and the obtained block-corpus,
respectively. We ignore a sentence-end tag (
)
in the block-LM. With each corpus, we train a
5-gram LM using the SRI toolkit (Stolcke, 2002).

Evaluation

We evaluate our method in English-to-Japanese(EJ) and Japanese-to-English (JE) translation
tasks, since long-distance reordering is a serious
problem in this language pair.
6.1[X] 0 [N] 0 が 徐々 に 排出 さ

Figure 6: Block-corpus example. Boxed indices link non-After tree structure projection, we extract corresponding node pairs as a block-corpus. Eachnode pair has a form hΨs , Ψt , AL i, where Ψs ∈{Ωs , L}n represents the source-side node oflength n. It consists of a sequence of lexical
words in the source-side vocabulary Ωs and nonterminals L. Ψt ∈ {Ωt , L}m similarly represents
the target-side node of length m. AL preserves
correspondences between the non-terminals in thesource and target nodes.
Specifically, we extract a pair of leaf nodes asa pair of lexical strings. As for internal nodes,
we use the same non-terminal labels appearing
in the source-side node at the target-side node.
Namely, the span covered by child nodes are replaced by corresponding non-terminal labels in thesource-side node. At the same time, we record thecorrespondence between the non-terminals. Figure 6 shows an example of the block-corpus, inwhich the boxed indices indicate correspondencesof non-terminals in the source and target nodes.

6

流体 圧 シリンダ 31 の 場合 は
流体 が 徐々 に 排出 さ れること と なる 。

Experiment Corpus

We use NTCIR-7 PATMT (Fujii et al., 2008), a
publicly available standard evaluation dataset, for
EJ and JE machine translation. The dataset is constructed using English and Japanese patents andconsists of 1.8 million parallel sentence pairs fortraining, 915 sentence pairs for development, and1, 381 sentence pairs for testing. The development
429

6.3

MethodProposed method (γ = 10)
BTG
HIERO
Tree-to-string
Head-Finalization

Comparison Method

Since our method pre-processes the parallel corpus based on SCFG with increased flexibility andtrains a BTG model using the processed corpus,
we compare our method to another BTG modeltrained only with the original corpus (simply referred to as the BTG model). We also compare to the tree-to-string model and HIERO usingstate-of-the-art implementations available in theMoses system (Koehn et al., 2007), since they arebased on SCFG. The tree-to-string model requires
source-side constituency trees. For EJ translation, we use a state-of-the-art English constituency
parser (Miyao and Tsujii, 2005; Miyao and Tsujii,2008). For JE translation, we transform a Japanese
dependency tree into a constituency tree using asimple heuristic because there is no publicly available constituency parser. During the translation
model training, we use the same setting as our
method. In addition, we set the maximum spanof rule extraction to infinity for the tree-to-stringmodel and 10 for HIERO following Moses’ default. We use the sentence-LM in these models as
they assume.
In addition, we compare our method to HeadFinalization (Isozaki et al., 2010; Isozaki et al.,2012) because it has achieved the best BLEU score
in EJ translation by handling long-distance reordering. It is a specialized method to EJ translation, where a syntactic head in an English sentence is reordered behind its constituents for complying with the head-final nature of the Japanese
language. We pre-process the parallel corpus using the Head-Finalization and train a BTG modelusing the same setting with our method to observe
the effect of different pre-processing methods.
During decoding, we set the translation tablesize to 10 for each source string, and the stackand beam sizes in the cube pruning to 100 for our
method (i.e., m-best = 100) and all other models. The maximum reordering span in the tree-tostring model and HIERO is the same as the rule
extraction setting (infinity and 10, respectively).
We set the word reordering limit to infinity for our
method and the BTG model, while we set it to 3
for Head-Finalization as their papers report.
We tune feature weights by the minimum error
rate training (Och, 2003) to maximize the BLEU
score using the development set. As an evaluation
metric, we compute the BLEU score using the test
set, and all the scores discussed in Sec. 6.4 are the

EJ
31.78
28.82∗∗
29.27∗∗
30.97∗∗
29.52∗∗

JE
28.55
26.98∗∗
27.96∗
26.28∗∗NA

Table 1: Test-set BLEU scores. The symbol ∗∗ represents
a significant difference at the p < .01 level and ∗ indicates asignificant difference at the p < .05 level against our method.

test-set BLEU scores. Significance tests are conducted using bootstrap sampling (Koehn, 2004).
6.4

Result and Discussion

In this section, we present experimental results
and discuss them in detail.
Overall Performance Table 1 shows the BLEU
scores, in which our method significantly outperforms all other models for both EJ and JE translation tasks. These results indicate that our method
effectively incorporates syntactic information into
the phrase-based model and improves the translation quality.
For EJ translation, our method outperforms
the BTG model by 2.96, the HIERO by 2.51,
the tree-to-string model by 0.81, and the HeadFinalization3 by 2.26 in terms of BLEU score.
When we compare our method to the HeadFinalization, both of them improve the BTG modelby pre-processing the parallel corpus. Moreover,
our method outperforms the Head-Finalization using richer syntactic information.
For JE translation, our method outperforms the
BTG model by 1.57, the HIERO by 0.59, and thetree-to-string model by 2.27 in terms of BLEU
score. Our method and the tree-to-string model,
which depend on syntactic information, largely
outperform the BTG model and HIERO in EJ
translation. While the BTG model and HIERO,
which are independent of syntactic information,outperform the tree-to-string model in JE translation. One reason for this phenomenon is that
English is a strongly configurational language thathas rigid word order while Japanese is an agglutinative language that has relatively free word order. A rigid syntactic structure provides solid clues
for word reordering when translated into a flexible
language, while a flexible structure provides weakclues for fitting it to a rigid structure.
3

The BLEU score reported in this experiment differs fromtheir papers. This may be because they use a phrase-basedmodel in the Moses system, while we use the BTG model.

430

γ
0
3
5
8
10
12
15
∞

BLEU
31.15
30.88
31.21
31.61
31.78
31.76
31.25
28.82

EJ

height4.1 (1.5)
3.8 (1.7)
3.7 (1.5)
3.4 (1.4)
3.1 (1.3)
2.9 (1.3)
2.6 (1.2)
1.0 (–)

BLEU
28.41
28.34
28.39
28.52
28.55
28.54
28.21
26.98

JE

MethodProposed
BTG
Tree-to-stringheight4.2 (1.4)
3.9 (1.6)
3.8 (1.5)
3.4 (1.4)
3.2 (1.3)
3.0 (1.3)
2.7 (1.2)
1.0 (–)

acceptable ↑
52
34
47

global ↓30
38
32

local ↓
4
7
7

Table 3: Error distribution in 100 samples of EJ translation
Error Analysis We randomly sample 100 translation outputs per our method (γ = 10), BTG, andtree-to-string models for each EJ and JE translation tasks, and manually categorize errors basedon (Vilar et al., 2006). We focus primarily on
reordering errors and exclusively categorize thesamples into acceptable translations, translations
with only global or local reordering errors, as wellas others that are complicated combinations of various errors. An acceptable translation correctly
conveys the information in a source sentence even
if it contains minor grammatical errors.
Table 3 shows the distribution of acceptabletranslations and those with global/local reordering
errors in the EJ task (results of JE task are omitted
due to the severe space limitation, but their trend
is similar). It confirms that our method reduces reordering errors, not only for long-distance but for
local reordering, and increases the ratio of acceptable translations compared to the BTG and treeto-string models. We also find that long-distance
reordering was attempted in 85, 66, and 70 sentences by our method, BTG, and tree-to-string, respectively, among these translations. The results
show that our method performs long-distance reordering more frequently than others.
When we compare translations performed byour method to those performed by the tree-tostring model, we observe that their effectiveness
depends on a range of reordering. Our method iseffective in long-distance reordering like those ofclauses, while the tree-to-string model performs
middle-range reordering well. This is due to thetrade-off regarding the level of abstraction as discussed in the flattening threshold experiment.

Table 2: Effect of threshold γ
Effect of Flattening Threshold Table 2 shows
BLEU scores when changing the flattening threshold γ in our method, and averages and standard
deviations of the abstraction tree heights (γ = ∞is equal to the BTG model). The performance improves as we increase the threshold, i.e., increasing the level of abstraction. Our method achieves
the best BLEU score when γ = 10 for both EJ andJE translation, with the performance degrading as
we further increase the threshold.
This trend shows the trade-off between phrasebased and syntax-based approaches. When thethreshold is too small, an abstraction tree becomes closer to the dependency tree and the treeprojection becomes difficult. In addition, context information becomes unavailable when conducting long-distance reordering with a deep tree.
On the other hand, when setting the threshold toolarge, the abstraction tree becomes too abstracted
and syntactic structures useful for long-distanceword reordering are lost. We need to balance theseeffects by setting an appropriate threshold.
Effect of Non-Terminals and Fixed-Expressions
We change the kinds of non-terminal labels in an
abstraction tree to investigate their effect on thetranslation quality. When we merge the [P] label
to the [X] label, i.e., use only [N] and [X] labels,
the BLEU score drops 0.40 in EJ translation while
the score is unaffected in JE translation. This isbecause flexible Japanese syntax does not differentiate postpositional phrases with others, while
English syntax prohibits such a flexibility.
When we merge all labels and only use the [X]label, the BLEU score drops 0.57 in EJ translation and 0.43 in JE translation. This result supports our design of the abstraction tree that distinguishes non-terminals according to their different
functionalities in a sentence.
We also evaluate the effect of fixed-expressions
as described in Sec. 5.2. Results show a significant
change when over-splitting fixed-expressions; the
BLEU score drops 1.13 for EJ and 0.36 for JE
translation without reinserting fixed-expressions.

7

Conclusion and Future Work

We have proposed an abstraction tree for effectively conducting long-distance reordering using
an off-the-shelf phrase-based model. Evaluation
results show that our method outperforms conventional phrase-based and syntax-based models.
We plan to investigate the effect of translating
language pairs and dependency grammars in abstraction tree generation. In addition, we will apply a structure-aware word aligner (Neubig et al.,2011) to improve the tree projection.
431

References

Hideki Isozaki, Katsuhito Sudoh, Hajime Tsukada, andKevin Duh. 2012. HPSG-based preprocessing
for English-to-Japanese translation. ACM Transactions on Asian Language Information Processing(TALIP), 11(3):8:1–8:16.

Alfred V. Aho and Jeffrey D. Ullman. 1972. The theory of parsing, translation, and compiling. PrenticeHall Inc.
Masayuki Asahara and Yuji Matsumoto.
2003.
ipadic version 2.7.0 user’s manual.
http://sourceforge.jp/projects/ipadic/
docs/ipadic-2.7.0-manual-en.pdf.

Philipp Koehn, Franz J. Och, and Daniel Marcu. 2003.
Statistical phrase-based translation. In Proceedingsof Conference of the North American Chapter ofthe Association for Computational Linguistics on
Human Language Technology (NAACL-HLT 2003),
pages 48–54.

David Burkett, John Blitzer, and Dan Klein. 2010.
Joint parsing and alignment with weakly synchronized grammars. In Proceedings of Conferenceof the North American Chapter of the Association
for Computational Linguistics on Human Language
Technology (NAACL-HLT 2010), pages 127–135.

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 machine translation. In Proceedings of Annual Meeting of the Association for Computational Linguistics (ACL 2007),
pages 177–180.

David Chiang. 2007. Hierarchical phrase-based translation. Computational Linguistics, 33(2):201–228.
Michael Collins. 2002. Discriminative training methods for hidden Markov models: Theory and experiments with perceptron algorithms. In Proceedings of Conference on Empirical Methods in Natural
Language Processing (EMNLP 2002), pages 1–8.

Philipp Koehn. 2004. Statistical significance tests formachine translation evaluation. In Proceedings ofConference on Empirical Methods in Natural Language Processing (EMNLP 2004), pages 388–395.

Marie-Catherine de Marneffe, Bill MacCartney, andChristopher D. Manning. 2006. Generating typed
dependency parses from phrase structure parses. In
Proceedings of International Conference on Language Resources and Evaluation (LREC 2006),
pages 449–454.

Taku Kudo and Yuji Matsumoto. 2002. Japanese dependency analysis using cascaded chunking. In Proceedings of Conference on Natural Language Learning (CoNLL 2002), pages 1–7.
Taku Kudo, Kaoru Yamamoto, and Yuji Matsumoto.
2004.
Applying conditional random fields toJapanese morphological analysis. In Proceedings ofConference on Empirical Methods in Natural Language Processing (EMNLP 2004), pages 230–237.

Stefan Evert. 2008. Corpora and collocations. In Anke
Lüdeling and Merja Kytö, editors, Corpus Linguistics. An International Handbook, volume 2, chapter 58. Mouton de Gruyter.
Yang Feng, Dongdong Zhang, Mu Li, Ming Zhou,
and Qun Liu. 2012. Hierarchical chunk-to-stringtranslation. In Proceedings of Annual Meeting of
the Association for Computational Linguistics (ACL2012), pages 950–958.

Junhui Li, Zhaopeng Tu, Guodong Zhou, and Josef van
Genabith. 2012. Head-driven hierarchical phrasebased translation. In Proceedings of Annual Meeting of the Association for Computational Linguistics(ACL 2012), pages 33–37.

Atsushi Fujii, Masao Utiyama, Mikio Yamamoto, andTakehito Utsuro. 2008. Overview of the patenttranslation task at the NTCIR-7 workshop. In Proceedings of NTCIR-7 Workshop Meeting (NTCIR),
pages 389–400.

Yang Liu, Qun Liu, and Shouxun Lin. 2006. Treeto-string alignment template for statistical machinetranslation. In Proceedings of International Conference on Computational Linguistics and Annual
Meeting of the Association for Computational Linguistics (COLING-ACL 2006), pages 609–616.

Liang Huang and David Chiang. 2005. Better k-best
parsing. In Proceedings of International Workshop
on Parsing Technology (IWPT 2005), pages 53–64.

Yusuke Miyao and Jun’ichi Tsujii. 2005. Probabilistic disambiguation models for wide-coverage HPSG
parsing. In Proceedings of Annual Meeting on Association for Computational Linguistics (ACL 2005),
pages 83–90.

Fei Huang and Cezar Pendus. 2013. Generalized reordering rules for improved SMT. In Proceedingsof Annual Meeting of the Association for Computational Linguistics (ACL 2013), pages 387–392.

Yusuke Miyao and Jun’ichi Tsujii. 2008. Feature forest models for probabilistic HPSG parsing. Computational Linguistics, 34(1):35–80.

Hideki Isozaki, Katsuhito Sudoh, Hajime Tsukada, andKevin Duh. 2010. Head Finalization: A simple reordering rule for SOV languages. In Proceedingsof Joint Workshop on Statistical Machine Translation and Metrics MATR (WMT-MetricsMATR 2010),
pages 244–251.

Jiri Navratil, Karthik Visweswariah, and Ananthakrishnan Ramanathan. 2012. A comparison of syntactic reordering methods for English-German machine

432

Jun Xie, Haitao Mi, and Qun Liu. 2011. A novel
dependency-to-string model for statistical machinetranslation. In Proceedings of Conference on Empirical Methods in Natural Language Processing(EMNLP 2011), pages 216–226.

translation. In Proceedings of International Conference on Computational Linguistics (COLING 2012),
pages 2043–2058.
Graham Neubig, Taro Watanabe, Eiichiro Sumita,
Shinsuke Mori, and Tatsuya Kawahara. 2011.
An unsupervised model for joint phrase alignment
and extraction. In Proceedings of Annual Meetingof the Association for Computational Linguistics:
Human Language Technologies (ACL-HLT 2011),
pages 632–641.

Deyi Xiong, Qun Liu, and Shouxun Lin. 2006. Maximum entropy based phrase reordering model for statistical machine translation. In Proceedings of International Conference on Computational Linguistics and Annual Meeting on Association for Computational Linguistics (COLING-ACL 2006), pages
521–528.

Graham Neubig, Taro Watanabe, and Shinsuke Mori.
2012. Inducing a discriminative parser to optimize
machine translation reordering. In Proceedings ofJoint Conference on Empirical Methods in Natural
Language Processing and Computational Natural
Language Learning (EMNLP-CoNLL 2012), pages
843–853.

Jia Xu, Richard Zens, and Hermann Ney. 2005.
Sentence segmentation using IBM word alignment
model 1. In Proceedings of Annual Conference of
the European Association for Machine Translation(EAMT 2005), pages 280–287.

Franz J. Och and Hermann Ney. 2003. A systematiccomparison of various statistical alignment models.
Computational Linguistics, 29(1):19–51.

Peng Xu, Jaeho Kang, Michael Ringgaard, and Franz J.
Och. 2009. Using a dependency parser to improve
SMT for subject-object-verb languages. In Proceedings of Conference of the North American Chapterof the Association for Computational Linguistics on
Human Language Technology (NAACL-HLT 2009),
pages 245–253.

Franz J. Och and Hermann Ney. 2004. The alignment
template approach to statistical machine translation.
Computational Linguistics, 30(4):417–449.
Franz J. Och. 2003. Minimum error rate training instatistical machine translation. In Proceedings ofAnnual Meeting on Association for Computational
Linguistics (ACL 2003), pages 160–167.

Kenji Yamada and Kevin Knight. 2001. A syntaxbased statistical translation model. In Proceedingsof Annual Meeting on Association for Computational Linguistics (ACL 2001), pages 523–530.

Kishore Papineni, Salim Roukos, Todd Ward, and WeiJing Zhu. 2002. BLEU: a method for automatic
evaluation of machine translation. In Proceedings ofAnnual Meeting on Association for Computational
Linguistics (ACL 2002), pages 311–318.

Jingbo Zhu and Tong Xiao. 2011. Improving decoding
generalization for tree-to-string translation. In Proceedings of Annual Meeting of the Association for
Computational Linguistics: Human Language Technologies (ACL-HLT 2001), pages 418–423.

Chris Quirk, Arul Menezes, and Colin Cherry. 2005.
Dependency treelet translation: Syntactically informed phrasal SMT. In Proceedings of Annual
Meeting on Association for Computational Linguistics (ACL 2005), pages 271–279.
Andreas Stolcke. 2002. SRILM - An extensible language modeling toolkit. In Proceedings of International Conference on Spoken Language Processing(ICSLP 2002), pages 901–904.
Katsuhito Sudoh, Kevin Duh, Hajime Tsukada, Tsutomu Hirao, and Masaaki Nagata. 2010. Divide
and translate: Improving long distance reorderingin statistical machine translation. In Proceedingsof Joint Workshop on Statistical Machine Translation and Metrics MATR (WMT-MetricsMATR 2010),
pages 418–427.
David Vilar, Jia Xu, Luis Fernando d’Haro, and Hermann Ney. 2006. Error analysis of statistical machine translation output. In Proceedings of International Conference on Language Resources and Evaluation (LREC 2006), pages 697–702.
Dekai Wu. 1997. Stochastic inversion transduction
grammars and bilingual parsing of parallel corpora.
Computational Linguistics, 23(3):377–403.

433