Reverse Pre-reordering for SMT
from Head-final to Head-initial Languages:
A Case Study on Japanese-to-Khmer
Chenchen Ding† , Vichet Chea‡ , Masao Utiyama† , Eiichiro Sumita†† Multilingual Translation Laboratory,

National Institute of Information and Communications Technology, Japanmutiyama, eiichiro.sumita}@nict.go.jp‡ National Institute of Posts, Telecommunication and Information Communication Technology, Cambodia‡ Email: vichet.chea@niptict.edu.kh† Email: {chenchen.ding,Abstract—We conduct a case study on applying an approachcalled reverse pre-reordering (REV-REO) to Japanese-to-Khmer(JKm) statistical machine translation (SMT). The REV-REO is asimple but efficient approach originally designed for Japanese-toEnglish SMT to resolve the word ordering problem in translation.
Theoretically, REV-REO can be applied on translation tasks from ahead-final language to a head-initial language. As Khmer is a more
typical head-initial language than English is, REV-REO shouldhave effects on JKm SMT. We conducted experiments of JKm
SMT using a standard phrase-based SMT system with a JapaneseKhmer parallel corpus of more than 100 thousand sentence pairs.
The performance of REV-REO is evaluated and investigated bythree automatic measures. The experimental results suggest that
established natural language processing techniques can work wellon the understudied Khmer language.

I. I NTRODUCTION
Statistical machine translation (SMT) is one of the mostimportant research fields in natural language processing (NLP).
SMT techniques have been well developed and widely appliedin practice. Linguistic knowledge-free SMT frameworks, such asphrase-based (PB) SMT [1] and hierarchical phrase-based SMT(HIERO) [2], handle many translation tasks efficiently as longas sufficient training data prepared.
In this paper, we conduct a case study on applying an approach called reverse pre-reordering (REV-REO) on Japaneseto-Khmer (JKm) SMT. Our intention is to investigate whether an
established, efficient technique performs well on SMT of Khmer,with a consideration of linguistic features of the Khmer language. The REV-REO is a simple rule-based approach originallydesigned for Japanese-to-English SMT. Because it is an rulebase approach, no training data are needed, which is especiallysuitable for an understudied language without enough resource
for model training. Theoretically, REV-REO can be applied ontranslation tasks from a head-final language (i.e., Japanese, Korean) to a head-initial language (i.e., English, French). Because
Khmer is a typical head-initial language, REV-REO should haveeffects on JKm SMT and the experimental results demonstrated
it works.
More generally, the research on Khmer language processing
has not been studied deeply, despite there have been many
mature theories and efficient techniques developed in the NLP
field nowadays. This paper, although just a case study of ansimple approach, suggests that well-developed techniques canbe directly used to process the Khmer language as long as
considering the linguistic features of Khmer.
The paper is organized as follows. Section II contains related
work on pre-reordering in SMT. In section III, we give a brief introduction and comparison of the linguistic head-directionality,i.e., the difference between head-final and head-initial languages.
In section IV, we give the introduction of the approach of REVREO. In section V, we conduct experiments and give discussions
based on the experimental results. Section VI is the conclusion.
II. R ELATED W ORK ON P RE - REORDERING IN SMT
Word reordering is a problematic issue in SMT, when translating those language pairs with significantly different word orders.
Among different lines of researches, pre-reordering has been
widely applied in practice and still studied in recent researches[3], [4]. The process of a pre-reordering approach tries to arrange
the word order on the source side into a target-like order before
a standard SMT system applied.
Different pre-reordering approaches have been proposed.
Language-independent pre-reordering approaches typically utilize designed statistical models to learn and conduct the reordering (e.g., [5]); language-dependent approaches typicallyutilize a trained parser with reordering rules, which can be either
manually designed (e.g., [6]) or automatically extracted (e.g.,[7] and [8]). Generally, a rule-based pre-reordering approach
offers fast and crisp reordering, but parsing errors and a lack ofrobustness are drawbacks. In contrast, a statistical pre-reordering
approach is more robust but also slower.

SSS
PPN

NP

VP

VP
NOsaka V

PNPVNP
大阪 はisNP

PPDETNPPN

PPN

P

ADJP

日本 で

theADJPADVADJ

P 大きいNPN

second largest

N

ADJ 都市PP

N in JapancityですNP

NにFig. 2. A Japanese syntactic tree.

III. H EAD -F INAL AND H EAD -I NITIAL L ANGUAGES
In linguistics, the head of a phrase is the word that determines
the syntactic type of the phrase it belongs to. For example, thephrase “good day” is a noun phrase because it has the noun
day as its head; further, the phrase “have a good day” is a verb
phrase because it has the verb have as its head.
Heads are crucial to establishing the direction of branching insyntactic structure of specific languages, i.e., head-initial phrases
are right-branching and head-final phrases are left-branching.
Some languages are consistently head-initial or head-final at
all phrasal levels. English is considered to be strongly (notconsistently) head-initial, while Japanese is an example of alanguage that is consistently head-final.
As to the Khmer language we focus on in this paper, it isprimarily an analytic language, with no inflection, but using
some derivation by means of prefixes. Since Khmer is ananalytic language, word order is relatively fixed, as changes
in word order are very likely to affect meaning. Khmer isgenerally a subject-verb-object language, using prepositions (asused in English) rather than postpositions (as used in Japanese).
Correspondingly, Khmer is overwhelmingly head-initial, thatis, modifiers follow the head they modify with in phrases.
Topicalization is also typical in Khmer (as Japanese), whereby
the topic of the sentence is placed at its beginning, and the restof the sentence serves as a comment on the topic.
To offer an intuitive comparison, we show syntactic tree
examples of English, Japanese and Khmer in Fig. 1, fig. 2,and Fig. 3, respectively. It can be observed that English has
a head-initial (right-branching) tendency but not strictly. WhileJapanese is typical head-final (left-branching) and Khmer typicalhead-initial (right-branching).

NVNPទីប្រងុ អូសាកា គឺជាNPNPP
ADJPPទីប្រងុ ADJADVPធំADJ NPNPរនុងNNប្បទទស ជបុនបំផុត N Nទី ពីរ

二 番目Fig. 1. An English syntactic tree.

NVPFig. 3. A Khmer syntactic tree.

Generally, the SMT between a head-final language and ahead-initial language always suffers the word reordering problem because of the extremely different word orders. However,for language pairs with consistent head-final / head-initial properties, consistent (and thus simple) reordering approaches should
handle the problem efficiently. So we consider the translationfrom Japanese, which is typically head-final, to Khmer, which
is typically head-initial, will be an interesting task on which wetest the simple but efficient REV-REO approach.

IV. R EVERSE P RE - REORDERINGThe REV-REO is originally proposed by [9] for the NTCIR7 Japanese-to-English Patent MT translation task. The approachhas been described in detail in the original papers, we here givean example in Fig. 4 to illustrate and explain the approach.
REV-REO focuses on only one specific Japanese morphemes:
the topic-marker. Within the processing, the sequence before
and after the topic-marker are totally reversed for source-side
Japanese sentences to match up the head-initial target-sideword order (i.e., Khmer in this paper). The word alignmentsof between original / reordered Japanese sentence and Khmer
sentence are also shown in Fig. 4. Because the alignments
are generated by the automatic word aligner GIZA++, there
are several errors; however, the performance of REV-REO isimpressive, that the Khmer and reordered Japanese sentences
nearly have similar word orders after the REV-REO process.
For the implementation of REV-REO, an important point
is to avoid the reordering across punctuations, otherwise
the reordering will become excessive. We used four marks totopic-marker locative-marker
OsakaTABLE I
DATA SETS USED IN EXPERIMENTS .

reversereverseJapantwodative-marker-thcopulalargecity

Set
Training
DevelopmentTest.

大阪 は 日本 で 二 番目 に 大きい 都市 です 。

ទីក្រុង អូសាកា គឺជា ទីក្រុង ធំ បំផុត ទី ពីរ រនុង ក្បទទស ជបុន ។
は 大阪 です 都市 大きい に 番目 二 で 日本 。

Fig. 4. REV-REO example for a Japanese sentence “Osaka is the second
largest city in Japan.” The glosses and explanations of Japanese morphemes areillustrated over the original Japanese sentence in the top rank. The reorderedJapanese sentence is placed in the bottom rank, where the parts before / after
the topic-marker are reversed. The automatically generated word alignments of
between the original / reordered Japanese sentence, and Khmer translation are
also shown, form which the effect of REV-REO is obvious.

compose the punctuation set: U+002C1 , U+FF0C2 , U+30013 ,and U+30024 . For the Japanese topic-marker, which plays thekey role of the approach, we did not judge it only by its surface
form, but also referred to its part-of-speech tag.
V. E XPERIMENT
We conducted translation experiment using the JapaneseKhmer version of Basic Travel Expression Corpus (BTEC),
which is translated form the original English-Japanese version[10]. As the data mainly contain short, daily expressions, weselect relately long sentences as test set for evluation. we used
MeCab5 (IPA dictionary) for Japanese word segmentation andan indoor, conditional random field based tool for Khmer word
segmentation [11]6 . The details of the data sets we used arelisted in Table I.
We used PB SMT and in Moses7 [12] as a baseline SMTsystem. For word aligner, we used GIZA++8 [13] with thedefault setting of Moses, and the grow-diag-final-and symmetrization heuristics [1]. The max-phrase-length was 7 and thereordering model was trained with using the msd-bidirectionalfe option. In decoding, we used the default setting of Moses’
decoder, with different distortion-limit (DL) for comparison. The
language model used in decoding was an interpolated modified
1 i.e., the ordinary comma.
2 “fullwidth comma”, the Chinese comma.
3 “ideographic comma”, the Japanese tōten.
4 “ideographic full stop”, the Japanese kuten.

Sentences122, 269
500
500

J-Words
1, 139, 317
16, 117
16, 059

Km-Words
1, 044, 552
13, 229
13, 285

Kneser-Ney discounting 5-gram model, trained on the Khmer
side of the training set by SRILM9 [14]. MERT [15] wasused to tune the feature weights for the development sets tooptimize the BLEU score [16] and the translation performancewas evaluated on the test sets with the tuned weights. The
decoding settings were identical for the development and test
sets in our experiments. The REV-REO was applied consistently
on the training, development, and test sets before the baseline
PB SMT applied, in training and decoding phases.
We used three automatic measures to evaluate the performance of REV-REO on JKm SMT: Kendall’s τ [6] on training
set, BLEU score and RIBES [17] on test set. Kendall’s τmeasures the reordering performance on training set; BLEU
score measures the precision of the N-gram matching rate
between the SMT system output and corresponding referencetranslations on test set; and RIBES evaluates the accordance ofword order on test set.
The Kendall’s τ is calculated according toτ =2#increasing pairs− 1,#all pairs(1)

where the pairs here are the pairs of aligned words10 . The
range of this measure is in [−1.0, +1.0]. A larger value suggests
the the source and target languages tend to have similar word
order and a smaller valuer suggests different order. Specifically,τ = +1.0 means the source and target languages have a totally
identical word order and τ = −1.0 means they have a totally
reversed order. Fig. 5 gives four examples of the calculation of
Kendall’s τ .
123123123123123123123123

τ=+1.00τ=+0.33

τ=-0.33

τ=-1.00

Fig. 5. Examples of Kendall’s τ . For all four cases, the #all pairs in Exp. 1is three (C32 ), from left to right the #increasing pairs in Exp. 1 is three, two([1-2, 3-3] and [2-1, 3-3] are increasing), one (only [1-2, 2-3] is increasing),and zero, respectively.

5 http://taku910.github.io/mecab/
6 The referenced paper is expected to be accepted and appear in the the Second
Annual Conference on Khmer Natural language Processing (KNLP 2015).
7 http://www.statmt.org/moses/
8 http://www.statmt.org/moses/giza/GIZA++.html

9 http://www.speech.sri.com/projects/srilm/
10 More detailed description and example can be found in the paper of [6].
In the calculations for Kendall’s τ , we used only the one-to-one aligned words
from the GIZA++ alignment file as used in [6].

TABLE IV
T EST SET RIBES.

TABLE IIIT EST SET BLEU SCORES .

100%
90%

80%

Baseline

70%

REV-REO

DL
6
91215
18∞

60%
50%
40%

30%
20%

Baseline
14.5
16.2
15.9
16.2
16.2
16.0

REV-REO
15.816.0
16.3
16.5
15.4
15.9

DL69121518∞

Baseline.626
.639
.633
.638
.623
.564

REV-REO.655
.639
.645
.635
.619
.580

10%
[0.9, 1.0]

[0.8, 0.9)

[0.7, 0.8)

[0.6, 0.7)

[0.5, 0.6)

[0.4, 0.5)

[0.3, 0.4)

[0.2, 0.3)

[0.1, 0.2)

[0.0, 0.1)[-0.1, 0.0)[-0.2. -0.1)[-0.3, -0.2)[-0.4, -0.3)[-0.5. -0.4)[-0.6, -0.5)[-0.7, -0.6)[-0.8. -0.7)[-0.9, -0.8)[-1.0, -0.9)

0%Fig. 6. Distribution of Kendall’s τ on training set.
TABLE IIT RAINING SET AVERAGE K ENDELL’ S τ .
Baseline
0.22

REV-REO
0.88

work and our experimental results on three different automatic
evaluation measures have given positive confirmations.
Although the NLP is an active research field nowadays, theresearch on Khmer language processing has not been studied
systematically and insightfully. In this paper, we prove that welldeveloped techniques can be directly used to process the Khmerlanguage as long as considering the typical head-initial featureof Khmer.
R EFERENCES

The distribution of Kendall’s τ [6] on training set is shownin Fig. 6 and the averages are list in Table II, for baseline
PB SMT and for REV-REO, respectively. The improvement on
Kendall’s τ brought by REV-REO is extremely obvious, that
there are originally only around 30% sentences in the training
data have a τ over 0.9 but REV-REO can increase it to over70%. Consequently, the average value is improved greatly. The
results suggest that the REV-REO actually reorder the Japanese
sentences to Khmer-like word orders.
The evaluation results of the translation performance are list in
Table III and Table IV, with different settings of distortion-limit.
The REV-REO can give better results than the baseline systemon both BLEU score and RIBES. As mentioned, the translation
between head-final and head-initial languages requires very
heavy reordering, so the best performance of the baseline PB
SMT system can only be reached by a relative large distortionlimit (DL = 15), which means the reordering range covers 15
words in translation. However, the translation performance canreach a mediocre BLEU score even with a small distortion-limit
and can be further improved with the increasing of the distortionlimit setting. On the other hand, REV-REO have already reached
its best RIBES using a small distortion-limit (DL = 6), whichcannot be improved by larger distortion-limit settings. From thephenomena, the good reordering ability of the REV-REO canbe observed.
VI. C ONCLUSION
In this paper, we have applied the REV-REO, an approachoriginally designed for Japanese-to-English SMT to Japanese-toKhmer SMT. In linguistic theories, the specific technique should[1] P. Koehn, F. J. Och, and D. Marcu, “Statistical phrase-based translation,”in Proc. of HTL-NAACL, 2003, pp. 48–54.
[2] D. Chiang, “Hierarchical phrase-based translation,” Computational Linguistics, vol. 33, no. 2, pp. 201–228, 2007.
[3] A. de Gispert, G. Iglesias, and B. Byrne, “Fast and accurate preordering
for SMT using neural networks,” in Proc. of NAACL-HLT, 2015, pp. 1012–1017.
[4] S. Hoshino, Y. Miyao, K. Sudoh, K. Hayashi, and M. Nagata, “Discriminative preordering meets Kendall’s Tau maximization,” in Proc. of ACL(Short Papers), 2015, pp. 139–144.
[5] G. Neubig, T. Watanabe, and S. Mori, “Inducing a discriminative parser
to optimize machine translation reordering,” in Proc. of EMNLP-CoNLL,
2012, pp. 843–853.
[6] H. Isozaki, K. Sudoh, H. Tsukada, and K. Duh, “HPSG-based preprocessing for English-to-Japanese translation,” ACM Transactions on AsianLanguage Information Processing, vol. 11, no. 3, p. 8, 2012.
[7] D. Genzel, “Automatically learning source-side reordering rules for large
scale machine translation,” in Proc. of COLING, 2010, pp. 376–384.
[8] X. Wu, K. Sudoh, K. Duh, H. Tsukada, and M. Nagata, “Extracting preordering rules from predicate-argument structures,” in Proc. of IJCNLP,
2011, pp. 29–37.
[9] J. Katz-Brown and M. Collins, “Syntactic reordering in preprocessing forJapanese → English translation: MIT system description for NTCIR-7
patent translation task,” in Proc. of NTCIR, 2008, pp. 409–414.
[10] G. Kikui, “Creating corpora for speech-to-speech translation,” in Proc. ofINTERSPEECH, 2003, pp. 381–384.
[11] V. Chea, Ye Kyaw Thu, C. Ding, A. Finch, M. Utiyama, and S. Eiichiro,“Khmer word segmentation using conditional random field,” in Proc. ofKNLP, 2015.
[12] P. Koehn, H. Hoang, A. Birch, C. Callison-Burch, M. Federico, N. Bertoldi,B. Cowan, W. Shen, C. Moran, R. Zens, C. Dyer, O. Bojar, A. Constantin,
and E. Herbst, “Moses: Open source toolkit for statistical machine translation,” in Proc. of ACL, 2007, pp. 177–180.
[13] F. J. Och and H. Ney, “A systematic comparison of various statisticalalignment models,” Computational Linguistics, vol. 29, no. 1, pp. 19–51,
2003.
[14] A. Stolcke, “SRILM–an extensible language modeling toolkit,” in Proc.
of ICSLP 2002, 2002, pp. 901–904.
[15] F. J. Och, “Minimum error rate training in statistical machine translation,”in Proc. of ACL, 2003, pp. 160–167.

[16] K. Papineni, S. Roukos, T. Ward, and W.-J. Zhu, “BLEU: a method forautomatic evaluation of machine translation,” in Proc. of ACL, 2002, pp.
311–318.
[17] H. Isozaki, T. Hirao, K. Duh, K. Sudoh, and H. Tsukada, “Automaticevaluation of translation quality for distant language pairs,” in Proc. ofEMNLP, 2010, pp. 944–952.