Improving fast align by Reordering
Chenchen Ding, Masao Utiyama, Eiichiro Sumita
Multilingual Translation Laboratory
National Institute of Information and Communications Technology
3-5 Hikaridai, Seikacho, Sorakugun, Kyoto, 619-0289, Japan{chenchen.ding, mutiyama, eiichiro.sumita}@nict.go.jp

Abstract
fast align is a simple, fast, and efficient approach for word alignment basedon the IBM model 2. fast align performs well for language pairs with relatively similar word orders; however, it
does not perform well for language pairs
with drastically different word orders. We
propose a segmenting-reversing reordering process to solve this problem by alternately applying fast align and reordering source sentences during training. Experimental results with JapaneseEnglish translation demonstrate that the
proposed approach improves the performance of fast align significantly
without the loss of efficiency. Experiments
using other languages are also reported.

1

Introduction

Aligning words in a parallel corpus is a basic task
for almost all state-of-the-art statistical machinetranslation (SMT) systems. Word alignment isused to extract translation rules in various way,such as the phrase pairs used in a phrase-based(PB) SMT system (Koehn et al., 2003), the hierarchical rules used in a HIERO system (Chiang,
2007), and the sophisticated translation templates
used in tree-based SMT systems (Liu et al., 2006).
Among different approaches, GIZA++1 (Ochand Ney, 2003), which is based on the IBM
translation models, is the most widely used wordalignment tool. Other well-known tools are
the BerkeleyAligner2 , Nile3 (Riesa et al.,2011), and pialign4 (Neubig et al., 2011).
1

http://www.statmt.org/moses/giza/
GIZA++.html
2
https://code.google.com/p/
berkeleyaligner/3
http://jasonriesa.github.io/nile/4
http://www.phontron.com/pialign/

fast align5 (Dyer et al., 2013) is a recently
proposed word alignment approach based on thereparameterization of the IBM model 2, which
is usually referred to as a zero-order alignment
model (Och and Ney, 2003). Taking advantage ofthe simplicity of the IBM model 2, fast alignintroduces a “tension” parameter to model theoverall accordance of word orders and an efficient parameter re-estimation algorithm is devised.
It has been reported that the fast align approach is more than 10 times faster than baseline
GIZA++, with comparable results in end-to-end
French-, Chinese-, and Arabic-to-English translation experiments.
However, the simplicity of the IBM model 2
also leads to a limitation. As demonstrated inthis study, fast align does not perform wellwhen applied to language pairs with drasticallydifferent word orders, e.g., Japanese and English.
The problem is because of the IBM model 2’s intrinsic inability to handle complex distortions. In
this study, we propose a simple and efficient reordering approach to improve the fast align’s
performance in such situations, referred to as
segmenting-reversing (seg rev). Our motivation
is to apply a rough but robust reordering to makethe source and target sentences have more similar word orders, where fast align can show
its power. Specifically, seg rev first segmentsa source-target sentence pair into a sequence ofminimal monotone chunk pairs6 based on the automatically generated word alignment. Within the
chunk pairs, source word sequences are examined to determine whether they should be completely reversed or the original order should be
retained. The objective of this step is to convert the source sentence to a roughly target-likeword order. The seg rev process is applied recursively but not deeply (only twice in our ex5
6

https://github.com/clab/fast_alignsame as the “tuple” used in Mariño et al. (2006)

1034
Proceedings of the 2015 Conference on Empirical Methods in Natural Language Processing, pages 1034–1039,
Lisbon, Portugal, 17-21 September 2015. c 2015 Association for Computational Linguistics.

 
rev.

reverse reverse 

thissignalbycuttingunit
8
isactivatedthe.

signalthisbyactivatedis8
unit
cuttingthe.

the
cuttingunit
8
isactivatedby
thissignal
.
この
信号
により
切断
部
８
が
作動
する 
。

この
信号
により
切断
部
８
が
作動
する
。

Figure 1: Example of seg rev applied to a word-aligned English-Japanese sentence pair. Based on theword alignment, the source sentence is reordered in a target-like order after applying seg rev twice.
periments) for each source sentence in the training data. Consequently, the seg rev process islightweight and shallow. Local word sequences,
except those at chunk boundaries, are not scrambled, while global word orders are re-arranged if
there are large chunks.
Our primary experimental results for JapaneseEnglish translation show that applying seg rev
significantly improves fast align’s performance to a level comparable to GIZA++. The
training time becomes 2–4 times that of a baseline
fast align, which is still at least 2 – 4 times
faster than the training time required by baseline GIZA++. Results for German-, French-, andChinese-English translations are also reported.

2

Segmenting-Reversing Reordering

The seg rev is inspired by the “REV preorder”(Katz-Brown and Collins, 2008), which is a simple pre-reordering approach originally designed
for the Japanese-to-English translation task. Moreefficient pre-reordering approaches usually require
trained parsers and sophisticated machine learning
frameworks (de Gispert et al., 2015; Hoshino etal., 2015). We adopt the REV method in KatzBrown and Collins (2008) considering it is thesimplest and lightest pre-reordering approach (toour knowledge), which may bring a minimal effect on the efficiency of fast align.
An example seg rev process, where the wordalignment is generated by fast align, is illustrated in Fig. 1. The example we selected has relatively correct word alignment and seg rev performs well. In general cases, the alignment has
significant noise and the reordering is rougher .
Algorithm 1 describes the repeated (δ times)
application of the seg rev process, and Algorithm 2 describes a single application. Specifi-

cally, Algorithm 1 applies Algorithm 2 δ times.
For each application of Algorithm 2, source sentence S and source indices in alignment A are
reordered, and the overall permutation RI is updated and recorded. In Fig. 1, the original English sentence had 10 words (including the period), being indexed as [0, 1, 2, 3, 4, 5, 6, 7, 8, 9].
After the first application of seg rev, RI was[ 8,7,6,5,4,3,2,1,0 , 9], and after the second application, RI was [ 7,8 , 6, 1,2,3,4,5 , 0, 9] (reversed
parts are boxed).
In Algorithm 2, the main for loop (line 3) scans
the source sentence from the beginning to the end
to obtain monotone segmentation. The foreach(line 5) and if (line 11) are general phrase pair extraction process. The if (line 13) guarantees thatthe chunk is monotone on the target side. The
rev function (line 16), which is described in Algorithm 3, determines whether the sub-sequence
from sstart to send should be reversed by examining the related alignment Asub . For example,
in the first application shown in Fig.1, two subsequences [0 : 8] and [9 : 9] are processed by rev
and [0 : 8] is reversed. Four sub-sequences [0 : 1],[2 : 2], [3 : 7], and [9 : 9] are processed in the second application and [0 : 1] and [3 : 7] are reversed.7
Finally, source sentence S and source indices inalignment A are reordered (lines 19 – 20).8
Algorithm 3 performs the reversal. We countthe concordant and discordant pairs9 and reverse
7

The sub-sequences are based on the input, not the original sentence, e.g., sub-sequence[0 : 1]contains the 8th and 7thword of the original source sentence in the 2nd application.
8
Unaligned words between chunks on the source side areproblematic. They are not touched by line 18. Although they
can be attached to preceding or succeeding chunks, we do
not use further heuristics to handle them. An example is thedrifting “the” in the English sentence in Fig. 1, which ourapproach cannot handle properly.
9
As used in Kendall’s τ or Goodman and Kruskal’s γ.

1035

Algorithm 3: rev

Algorithm 1: seg revδ

input : index sequence Isub ; word alignment Asub ;con ← 0; dis ← 0;
foreach unordered tuple ((i0 , j0 ), (i1 , j1 )) :(i0 , j0 ) ∈ Asub ∧ (i1 , j1 ) ∈ Asub do3x ← (i1 − i0 ) × (j1 − j0 );4
if x > 0 then5con ← con + 1;
6else if x < 0 then7
dis ← dis + 1;
8else
9continue;

input : same as Algorithm 2 and a depth δ;
output : same as Algorithm 2 except RA ;1 RI ← [0, · · · , I]; RS ← S; RA ← A;
2 for i ← 1 to δ do
3
RS , RA , RI 0 ← seg rev (RS , T, RA );4
permute RI with RI 0 ;5

1
2

return RS , RI ;Algorithm 2: seg rev
input: source sentence S = s0 , · · · , sI ;target sentence T = t0 · · · , tJ ;word alignment A = {(i, j)|si , tj are aligned, i ∈ [0, I], j ∈ [0, J]};
output : reordered source sentence RS ;source index reordered alignmentRA ;reordered indices RI = π(0, · · · , I),
which is a permutation from 0 to I;
1 RI ← [0, · · · , I];
2 sstart ← 0; tpre end ← −1;
3 for send ← sstart to I do
4
tstart ← J + 1; tend ← −1;5
foreach (i, j) ∈ A do
6
if i ∈ [sstart , send ] then7
if j < tstart then8
tstart ← j;
9
10

12
13
14

if ∃(i, j) ∈ A : j ∈ (tpre end , tstart ) thencontinue;

15

Asub ← {(i, j)|(i, j) ∈ A,i ∈ [sstart , send ] ∧ j ∈ [tstart , tend ]};rev (RI [sstart : send ], Asub );tpre end ← tend ;sstart ← min({i|i > send ∧ ∃(i, j) ∈ A});

16
17
18
19
20
21

if dis > con thenIsub ← reverse Isub ;Algorithm 4: fast align with seg rev
input: parallel corpus C with N sentence pairs
C = {(S 1 , T 1 ) · · · , (S N , T N )};maximum iteration M ; depth δ for seg rev;
output : word alignment A = {A1 , · · · , AN };1 A ← ∅;
2 for iter ← 1 to M do3
I ← ∅; C 0 ← ∅;4
if A 6= ∅ then5
for n ← 1 to N do
6
RS ,RI ← seg revδ (S n, T n, An );7
append (RS , T n ) to C 0 ;8append RI to I;

if j > tend thentend ← j;if ∃(i, j) ∈ A :j ∈ [tstart , tend ] ∧ i ∈/ [sstart , send ] thencontinue;

11

10
11

9
10

else

11
12
13
14

A ← sym ◦ fast align (C 0 );if I =
6 ∅ thenfor n ← 1 to N do
recover An by I [n];15RS ← permute S according to RI ;RA ← permute i in A according to RI ;return RS , RA , RI ;the sub-sequence if and only if there are more discordant pairs than the concordant pairs. In Fig.1,
the sub-sequence [0 : 8] in the first application has
C82 = 28 pairs of aligned word pair (i.e., 28 grayblock pairs for eight gray blocks); however, only
11 pairs are concordant (C52 = 10 pairs in [1 : 5] andone pair in [7 : 8]), Consequently, the sub-sequence[0 : 8] is reversed because there are more discordant pairs (17 = 28 − 11). The two reversed subsequences in the second application are obvious.
Algorithm 4 describes the training framework, where fast align and seg rev are applied alternately. To generate word alignment,
fast align is run bi-directionally and symmetrization heuristics are applied to reduce noise(line 11). In each iteration, the source sentences for seg rev are the original sentences,

C 0 ← C;

return A;

and fast align uses the reordered sentenceswith the exception of the first iteration. The wordalignment generated is thus based on the reordered
source sentences; consequently, the recorded permutation (line 14) is used to recover word alignment before the next iteration. The permutation isa one-to-one mapping; therefore, recovering is realized by the inverse mapping of the permutation,
which transfers the source-side word alignment indices to match the original source sentences.
The time complexity of Algorithm 3 is O(l2 ),where l is the size of Asub that is related to the
chunk size. If the average chunk size is a constantC depending on languages pairs or data sets, then
the time complexity of Algorithm 2 is O(C · I 2 )assuming J and the size of A are both linear
against I. The average chunk size will be reduced
when seg rev is applied successively; therefore, the time required for subsequent seg rev
processes will decrease. In practice, comparedwith the training time required by fast align,1036

seg rev processing time is negligible. Note thatseg rev processes are accelerated easily by parallel processing.

3

GIZA++
FAλini =4.0FAλini =0.1
iteration 2
iteration 3
iteration 4

Experiments and Discussion

We applied the proposed approach to JapaneseEnglish translation, a language pair with dramatically different word orders. In addition, we applied the approach to German-English translation,a language pair with relatively different word orders among European languages.
For Japanese-English translation, we used
NTCIR-7 PAT-MT data (Fujii et al., 2008). For
German-English translation, we used the Europarl v7 corpus10 (Koehn, 2005) for training, theWMT 0811 / WMT 0912 test sets for development/ testing, respectively. Default settings for the PB
SMT in MOSES13 (Koehn et al., 2007) were used,
except for Japanese-English translations where thedistortion-limit was set to 12 to reach a recently
reported baseline (Isozaki et al., 2012). MERT
(Och, 2003) was used to tune development set parameter weights and BLEU (Papineni et al., 2002)
was used on test sets to evaluate the translation
performance. Bootstrap sampling (Koehn, 2004)
was employed to test statistical significance using
bleu kit14 .
We compared GIZA++ and fast align withdefault settings. GIZA++ was used as a module of MOSES. The bi-directional outputs offast align were symmetrized by atools in
cdec15 (Dyer et al., 2010), and further training
steps were conducted using MOSES. grow-diagfinal-and symmetrization was used consistently inthe experiments. For the the proposed approach,
we set δ = 2 and M = 4 in Algorithm 4. Note that
δ can be set to a larger value and seg rev could
be applied repeatedly until no additional reordering is possible. As mentioned, the word alignment
is noisy and our intention is a robust and roughprocess; therefore, we restricted seg rev to two
applications and did not consider the difference
in sentence lengths or different languages during
training. Within each iteration, fast align was
run with default settings, except initial diagonal10

http://www.statmt.org/europarl/
http://www.statmt.org/wmt08/
12
http://www.statmt.org/wmt09/
13
http://www.statmt.org/moses/
14
http://www.nlp.mibel.cs.tsukuba.ac.
jp/bleu_kit/
15
http://www.cdec-decoder.org/
11

ja-en
28.8
28.1‡
28.0‡
28.3†
28.4†
28.8

en-ja
30.8
29.5‡
29.8‡
30.9
30.1‡
30.7

de-en
18.2
18.0†
17.5‡
17.9‡
18.1
18.1

en-de
12.9
12.7†
12.5‡
12.8
12.7†
12.7†

Table 1: Test set BLEU scores for JapaneseEnglish and German-English translations. (‡, statistical significance at p < 0.01; †, at p < 0.05; boldface, no significance; all compared with GIZA++)
tension (λini ) was set to 0.1 in the first iteration,
to avoid overly strong monotone preference at the
beginning of training.
Experimental results for Japanese-English andGerman-English translations in both directions
are listed in Table 1. The first two rows show
the baseline performance. fast align (using
a default λini = 4.0) performance was statistically significantly lower than GIZA++, particularly for Japanese-English translation. The following four rows show the results of the proposed approach. For the first iteration, λini wasset to 0.1, and the performance did not change
significantly. The translations from English improved (equal to GIZA++) at the second iteration. However, translations to English improved
more slowly. We attribute the difference in improvement rates between translation to and fromEnglish to the relatively fixed word order of English, whereby the reordering process is easierand more consistent. Note that once translations from English improved in the second iteration, performance decreased in the following iterations. The results in Table 1 were obtained using predictable-seed for tuning, which generated
determinate results. Another attempt using random seeds to tune returned test set BLEU scoresof 30.5, 30.4 on en-ja and 12.8, 12.8 on ende, for iterations 3 and 4, respectively. Thesefour scores had no statistical significance against
GIZA++. The instability is largely due to thealignment of function words, which affects translation performance (Riesa et al., 2011). The alignment does not change significantly after the second iteration; however, it is unstable around function words,16 because seg rev does not process
16
Specifically, to, articles, and prepositions in EnglishJapanese; of, have, and relative pronouns in English-German.

1037

GIZA++
FAλini =4.0
iteration 2

fr-en
23.3
23.1
23.1

zh-en
31.4
31.7
31.7

Acknowledgments
We thank Dr. Atsushi Fujita for his helpful discussions on this work.

Table 2: Test set BLEU scores for French-toEnglish and Chinese-to-English translations. For
fr-en, the data sets were the same as for de-en.
For zh-en, NIST 2006 OpenMT data were used
for training and test; test data from 2002 to 2005
OpenMT were used for tuning.
unaligned function words between chunks. Our
approach is too rough to handle function words
precisely. We plan to address this in future.
We also tested our approach on French- andChinese-to-English translations. The results arelisted in Table 2. GIZA++ and fast alignshowed no statistically significant difference inperformance, which is consistent with Dyer et al.
(2013). The proposed approach did not affectperformance for French- and Chinese-to-English
translations. These results are expected as theselanguage pairs have similar word orders.
With regard to processing time, a naı̈ve, singlethread implementation of seg rev in C++ tookapproximately 60s / 40s in the first / second application on the entire Japanese-English corpus17 .
The recover process took less than 30s in each iteration. In contrast, fast align, although very
fast, took approximately one hour for one roundof training (using five iterations for its log-linear
model) on the same corpus. Therefore, the additional time required in our approach is quite small
and can be ignored compared with the training
time of fast align.18

4Conclusion and Future Work

We have proposed a simple and efficient approachto improve the performance of fast align on
language pairs with drastically different word orders. With the proposed approach, fast alignobtained results comparable with GIZA++, and its
efficiency is retained. We are investigating further
properties of seg rev and plan to extend it toachieve greater stability and efficiency.19
17

1.8 M sentence pairs with an average length of 35 words.
GIZA++ actually took around 18 hours to align theJapanese-English corpus (parallel processes for two directions, including mkcls, five iterations for the model 1 andthe HMM model, three iteration for the model 3 and 4).
19
Ongoing experiments using seg rev with GIZA++ returned negative results. BLEU decreases by approx. 1 point.
18

References
David Chiang. 2007. Hierarchical phrase-based translation. Computational Linguistics, 33(2):201–228.
Adrià de Gispert, Gonzalo Iglesias, and Bill Byrne.
2015. Fast and accurate preordering for SMT using neural networks. In Proc. of NAACL-HLT, pages
1012–1017.
Chris Dyer, Adam Lopez, Juri Ganitkevitch, Johnathan
Weese, Ferhan Ture, Phil Blunsom, Hendra Setiawan, Vladimir Eidelman, and Philip Resnik. 2010.
cdec: A decoder, alignment, and learning frameworkfor finite-state and context-free translation models.
In Proc. of ACL (System Demonstrations), pages 7–
12.
Chris Dyer, Victor Chahuneau, and Noah A Smith.
2013. A simple, fast, and effective reparameterization of IBM model 2. In Proc. of NAACL-HLT,
pages 644–648.
Atsushi Fujii, Masao Utiyama, Mikio Yamamoto,Takehito Utsuro, Terumasa Ehara, Hiroshi Echizenya, and Sayori Shimohata. 2008. Overview of thepatent translation task at the NTCIR-7 workshop. In
Proc. of NTCIR, pages 389–400.
Sho Hoshino, Yusuke Miyao, Katsuhito Sudoh, Katsuhiko Hayashi, and Masaaki Nagata. 2015. Discriminative preordering meets Kendall’s Tau maximization. In Proc. of ACL (Short Papers), pages
139–144.
Hideki Isozaki, Katsuhito Sudoh, Hajime Tsukada, andKevin Duh. 2012. HPSG-based preprocessing
for English-to-Japanese translation. ACM Transactions on Asian Language Information Processing,11(3):8.
Jason Katz-Brown and Michael Collins. 2008. Syntactic reordering in preprocessing for Japanese →English translation: MIT system description for
NTCIR-7 patent translation task. In Proc. of NTCIR,
pages 409–414.
Philipp Koehn, Franz Josef Och, and Daniel Marcu.
2003. Statistical phrase-based translation. In Proc.
of HLT-NAACL, pages 48–54.
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 Proc. of ACL (Demo and Poster Sessions),
pages 177–180.

1038

Philipp Koehn. 2004. Statistical significance tests formachine translation evaluation. In Proc. of EMNLP,
pages 388–395.
Philipp Koehn. 2005. Europarl: A parallel corpus forstatistical machine translation. In Proc. of MT summit, pages 79–86.
Yang Liu, Qun Liu, and Shouxun Lin. 2006. Treeto-string alignment template for statistical machinetranslation. In Proc. of ACL, pages 609–616.
José B. Mariño, Rafael E. Banchs, Josep M. Crego,
Adrià de Gispert, Patrik Lambert, José A. R. Fonollosa, and Marta R. Costa-Jussà. 2006. N-grambased machine translation. Computational Linguistics, 32(4):527–549.
Graham Neubig, Taro Watanabe, Eiichiro Sumita,
Shinsuke Mori, and Tatsuya Kawahara. 2011. An
unsupervised model for joint phrase alignment andextraction. In Proc. of ACL-HLT, pages 632–641.
Franz Josef Och and Hermann Ney. 2003. A systematic comparison of various statistical alignment
models. Computational Linguistics, 29(1):19–51.
Franz Josef Och. 2003. Minimum error rate training
in statistical machine translation. In Proc. of ACL,
pages 160–167.
Kishore Papineni, Salim Roukos, Todd Ward, and WeiJing Zhu. 2002. BLEU: a method for automatic
evaluation of machine translation. In Proc. of ACL,
pages 311–318.
Jason Riesa, Ann Irvine, and Daniel Marcu. 2011.
Feature-rich language-independent syntax-basedalignment for statistical machine translation. In
Proc. of EMNLP, pages 497–507.

1039