KyotoEBMT System Description for the 1st Workshop on
Asian Translation
John Richardson† Fabien Cromières‡ Toshiaki Nakazawa‡ Sadao Kurohashi††Graduate School of Informatics, Kyoto University, Kyoto 606-8501‡Japan Science and Technology Agency, Kawaguchi-shi, Saitama 332-0012
john@nlp.ist.i.kyoto-u.ac.jp, {fabien, nakazawa}@pa.jst.jp,
kuro@i.kyoto-u.ac.jp
Abstractof complex sentences across distant language
pairs.
Our experiments focus on technical domain translation for Japanese-Chinese andJapanese-English, however our implementation is applicable to any domain and language
pair for which there exist translation examples
and dependency parsers.
A further unique characteristic of our system is that, again contrary to the majority ofsimilar systems, it does not rely on precomputation of translation rules. Instead it matches
each input sentence to the full database oftranslation examples before extracting translation rules online. This has the merit of maximizing the information available when creating and combining translation rules, while retaining the ability to produce excellent translations for input sentences similar to an existing translation example.
The system is mostly developed in C++ andincorporates a web-based translation interface
for ease of use. The web interface (see Figure 1) also displays information useful for error
analysis such as the list of translation examples used. Experiments are facilitated throughthe inclusion of a curses-based graphical interface for performing tuning and evaluation.
The decoder supports multiple threads.
The system has been made available as open-source.
The code can bedownloadedfrom
http://nlp.ist.i.kyotou.ac.jp/kyotoebmt/.

This paper introduces the KyotoEBMT Example-Based MachineTranslation framework. Our system
uses a tree-to-tree approach, employing
syntactic dependency analysis forboth source and target languages
in an attempt to preserve non-localstructure. The effectiveness of oursystem is maximized with online example matching and a flexible decoder.
Evaluation demonstrates BLEU scorescompetitive with state-of-the-art SMT
baselines. The system implementation
is available as open-source.

1Introduction

Corpus-based approaches have become a major focus of Machine Translation research.
We present here a fully-fledged ExampleBased Machine Translation (EBMT) platform making use of both source-language
and target-language dependency structure.
This paradigm has been explored comparatively less, as studies on Syntactic-based
SMT/EBMT tend to focus on constituent
trees rather than dependency trees, andon tree-to-string rather than tree-to-tree approaches. Furthermore, we employ separate
dependency parsers for each language rather
than projecting the dependencies from one language to another, as in (Quirk et. al, 2005).
The dependency structure information isused end-to-end: for improving the qualityof the alignment of the translation examples,for constraining the translation rule extraction
and for guiding the decoding. We believe that
dependency structure, which considers morethan just local context, is important in orderto generate fluent and accurate translations

2 System Overview
Figure 2 shows the basic structure of the Kyoto EBMT translation pipeline.
The training process begins with parsing
and aligning parallel sentences from the training corpus. Alignment uses a Bayesian subtree alignment model based on dependency
83

Proceedings of the 1st Workshop on Asian Translation (WAT2014), pages 83‒88,Tokyo, Japan, 4th October 2014.

Figure 2: The translation pipeline can beroughly divided in 3 steps. Step 1 is the creation of the example database, trained froma parallel corpus. Step 2 is the k-best parsing of an input sentence and the generationof k sets of initial hypotheses. Step 3 consists
in decoding and reranking. The tuning of theweights for decoding and reranking is done bya modified version of step 3. The double arrows indicate the parallel processing of each of
the k parse of the input sentence.

Figure 1: A screenshot of the web interface
showing a Japanese-English translation. Theinterface provides the source and target side
dependency tree, as well as the list of examples used with their alignments. The web interface facilitates easy and intuitive error analysis, and can be used as a tool for computeraided translation.
trees. This contains a tree-based reordering model and can capture non-local reorderings, which sequential word-based models often cannot handle effectively. The alignments
are then used to build an example database(‘translation memory’) containing ‘examples’or ‘treelets’ that form the hypotheses to be
combined during decoding.
Translation is performed by first parsing
an input sentence then searching for treelets
matching entries in the example database.
The retrieved treelets are combined by a decoder that optimizes a log linear model score.
Finally, a reranker select an optimal translation in the n-best list provided by the decoder using additional non-local features (seesection 6).
In order to be more robust with respect toparse errors, the input sentence can be parsed
into a k-best list of posible parses. Each parseis then translated separately and all translations are merged before the final reranking
step (see section 7).
The example retrieval and decoding steps
are explained in more detail in sections 3 and4 respectively. The choice of features and thetuning of the log linear model is described insection 5.
Figure 3 shows the process of combining examples matching the input tree to create an
output sentence.

3 Example retrieval and translation
hypothesis construction
An important characteristic of our system isthat we do not extract and store translation
rules in advance: the alignment of translation
examples is performed offline. However, for agiven input sentence i, the steps for finding
examples partially matching i and extracting
their translation hypotheses is an online process. This approach could be considered to be
more faithful to the original EBMT approachadvocated by Nagao (1984). It has alreadybeen proposed for phrase-based (CallisonBurch et al., 2005), hierarchical (Lopez, 2007),and syntax-based (Cromières and Kurohashi,2011) systems. It does not however, seem tobe very commonly integrated in syntax-based
MT.
This approach has several benefits. The first84

C%!.?,$6D!#!&!+$6
2GBBA4"'()"/6 06

E$6&''(62F74"
2F54">)?@#6A*$$6'()234"
/2946

02:4"

*+2546 ,-.274"

2F54"*6 1"2F74"
2F54"

!"

*+6

=0$6

2F74"

#$%#&''(",-."
2F84" !""2F84"2F84"!284"

B@#?@#6A*$$6
*$!<"
=0$6

#$%#&''("!"')"#*!)+,!-')"?!?$*+"

2F84"#$%&2;4"*$!<"

23".!/01)$"')"!"#*!)+,!-')"#$%&".!/01)$"

Figure 3: The process of translation. The source sentence is parsed and matching subtrees fromthe example database are retrieved. From the examples, we extract translation hypotheses thancan contain optional target words and several position for each non-terminals. For example thetranslation hypothesis containing “textbook” has three possible position for the non-terminal X3(as a left-child before “a”, as a left-child after “a” or as a right-child). The translation hypotheses
are then combined during decoding. Choice of optional words and final Non-Terminal positions
is also done during decoding.
it. A translation hypothesis is defined as ageneric translation rule for a part p of the input sentence that is represented as a targetlanguage treelet, with non-terminals representing the insertion positions for the translations of other parts of the sentence. A translation hypothesis is created from a translation
example as follows:is that we are not required to impose a limiton the size of translation hypotheses. Systems
extracting rules in advance typically restrict
the size and number of extracted rules for fearof becoming unmanageable. In particular, if
an input sentence is the same or very similar
to one of our translation examples, we will beable to retrieve a perfect translation. A second
advantage is that we can make use of the fullcontext of the example to assign features andscores to each translation hypothesis.
The main drawback of our approach is thatit can be computationally more expensive toretrieve arbitrarily large matchings in the example database online than it is to match precomputed rules. We use the techniques described in (Cromières and Kurohashi, 2011)
to perform this step as efficiently as possible.
Once we have found an example translation(s, t) for which s partially matches i, we proceed to extract a translation hypothesis from

1. We project the part of s that is matched
into the target side t using the alignmentof s and t. This is trivial if each word ofs and t is aligned, but this is not typically the case. Therefore our translation
hypotheses will often have some targetwords/nodes marked as optionals: thismeans that we will decide if they should
be added to the final translation only at
the moment of combination.
2. We insert the non-terminals as childnodes of the projected subtree. This is85

Compared with the original cube-pruningalgorithm, our decoder is designed to handle
an arbitrary number of non-terminals. In addition, as we have seen in Section 3, the translation hypotheses we initially extract from examples are ambiguous in term of which target
word is going to be used and which will be thefinal position of each non-terminal. In order tohandle such ambiguities, we use a lattice-based
internal representation that can encode themefficiently (see Figure 4). This lattice representation also allows the decoder to make choices
between various morphological variations of aword (e.g. be/is/are). We use the decoding
algorithm described in (Cromieres and Kurohashi, 2014).

Figure 4: A translation hypothesis endoded
as a lattice. This representation allows us tohandle efficiently the ambiguities of our translation rules. Note that each path in this lattice corresponds to different choices of insertion position for X2, morphological forms of“be”, and the optional insertion of “at”.
simple if i, s and t have the same structure and are perfectly aligned, but again
this is not typically the case. A consequence is that we will sometimes have several possible insertion positions for each
non-terminal. The choice of insertion position is again made during combination.

45 Features and Tuning
During decoding we use a linear model to scoreeach possible combination of hypotheses. This
linear model is based on a linear combinationof both local features (local to each translation
hypothesis) and non-local features (such as a5-gram language model score of the final translation). The decoder considers in total a combination of 42 features, a selection of which are
given below.

Decoding

After having extracted translation hypotheses
for as many parts of the input tree as possible,
we need to decide how to select and combine
them. Our approach here is similar to what
has been proposed for Corpus-Based MachineTranslation. We first choose a number of features and create a linear model scoring eachpossible combination of hypotheses (see Section 5). We then attempt to find the combination that maximizes this model score.
The combination of rules is constrained by
the structure of the input dependency tree. If
we only consider local features1 , then a simple
bottom-up dynamic programming approachcan efficiently find the optimal combination
with linear O(|H|) complexity2 . However,
non-local features (such as language models)
will force us to prune the search space. This
pruning is done efficiently through a variation of cube-pruning (Chiang, 2007). We
use KenLM3 (Heafield, 2011) for computing
the target language model score. Decoding
is made more efficient by using some of themore advanced features of KenLM such as
state-reduction ((Li and Khudanpur, 2008),(Heafield et al., 2011)) and rest-cost estimations(Heafield et al., 2012).

• Example penalty and example size
• Translation probability• Language model score• Optional words added/removed
The optimal weights for each feature are estimated using the implementation of k-bestbatch MIRA (Cherry and Foster, 2012) included in Moses.

6 Reranking
We reranked the n-best output of our systemusing an additional two language models: astandard 7-gram language model with Modified Kneser-Ney smoothing and a Recurrent
Neural Network Language Model (RNNLM)(Mikolov et. al, 2010). The RNNLM model
was trained with hidden layer size 200, and5000 sentences from the training fold wereused as validation data.
Reranking was conducted by first calculating the various language model scores for each1

The score of a combination will be the sum of thelocal scores of each translation hypothesis.
2
H = set of translation hypotheses
3
http://kheafield.com/code/kenlm/86

translation in the n-best list. These features
were added to those used in the first round oftuning, then one final iteration of tuning wasrun. The tuning algorithm and settings were
the same as for standard tuning. This retuning step was added in order to find an optimal
combination of the two additional LMs withrelated features such as sentence length andthe score given by the 5-gram language model
used inside the decoder.

8.1 Results
The results shown are for evaluation on thetest set after tuning. Tuning was conducted
over 20 iterations on the development set using
an n-best list of length 500.

9 Conclusion
We have described the Kyoto example-basedtranslation system. It uses both source andtarget dependency analysis, as well as online
example retrieving, allowing the availability offull translation examples at translation time.
We believe that the use of dependency parsing is important for accurate translation acrossdistant language pairs, especially in settings
such as ours with many long sentences. We
have designed a complete translation framework around this idea, using dependencyparsed trees at each step from alignment toexample retrieval to example combination.

7 K-best parsing
We found that the quality of the source-side
dependency parsing had an important impact
on translation quality. Unfortunately, parsing errors are unavoidable. Chinese parsing ismaybe especially challenging and our Chineseparser still produces a significant number ofparsing errors. In order to mitigate this problem, we use a k-best list of parses of the inputsentence. Each parse is translated in parallel, and the list of translation thus obtained ismerged before the reranking step. In the future, we intend to move from a k-best list representation of multiple parses to a more compact and efficient forest representation. Furthermore, we will also have to consider multiple parses for all the translation examples (andnot just the input sentence).

References
Eugene Charniak and Mark Johnson.
2005.
Coarse-to-Fine n-Best Parsing and MaxEnt Discriminative Reranking. In Proceedings of the43rd Annual Meeting of the Association for
Computational Linguistics, ACL 2005.
Fabien Cromières and Sadao Kurohashi. 2011. Efficient retrieval of tree translation examples forsyntax-based machine translation. In Proceedings of the 2011 Conference on Empirical Methods in Natural Language Processing.

8 Experiments
The following dependency parsers were used.
The scores in parentheses are the approximate
parsing accuracies (micro-average), whichwere evaluated by hand on a random subset ofsentences from the test data. The parsers weretrained on domains different to those used inthe experiments.

Isao Goto, Ka Po Chow, Bin Lu, Eiichiro Sumita
and Benjamin Tsou.
2013.
Overview ofthe Patent Machine Translation Task at theNTCIR-10 Workshop. In Proceedings of the 10thNTCIR Workshop Meeting on Evaluation of Information Access Technologies (NTCIR-10).
Daisuke Kawahara and Sadao Kurohashi. 2006.
A Fully-Lexicalized Probabilistic Model for
Japanese Syntactic and Case Structure Analysis. In Proceedings of the Human Language
Technology Conference of the NAACL.

• English: NLParser4 (92%) (Charniak andJohnson, 2005)• Japanese: KNP (96%) (Kawahara andKurohashi, 2006)

Makoto Nagao. 1984. A framework of a mechanical translation between Japanese and English
by analogy principle. In A. Elithorn and R.
Banerji. Artificial and Human Intelligence.

• Chinese: SKP (88%) (Shen et al., 2012)
K-best dependency parsing was done with kset to 20.

Toshiaki Nakazawa and Sadao Kurohashi. 2012.
Alignment by bilingual generation and monolingual derivation. In Proceedings of COLING
2012.

4
Converted to dependency parses with in-housetool.

87

Language Pair
JA–EN
EN–JA
JA–ZH
ZH–JA

Reranking
No
Yes
No
Yes
No
Yes
No
Yes

BLEU
20.60
21.07
29.76
31.09
27.21
27.67
33.57
34.75

RIBES
70.12
69.90
75.21
75.96
79.13
78.83
80.10
80.26

HUMAN
21.50
25.00
33.75
38.00
-0.75
-8.75
6.00
7.50

Table 1: Scores
Mo Shen, Daisuke Kawahara and Sadao Kurohashi. 2012. A Reranking Approach for Dependency Parsing with Variable-sized SubtreeFeatures. In Proceedings of 26th Pacific Asia
Conference on Language Information and Computing.

on Syntax and Structure in Statistical Translation. Association for Computational Linguistics,2008.
Adam Lopez. 2007. Hierarchical phrase-basedtranslation with suffix arrays. In EMNLPCoNLL, 2007.

Chris Callison-Burch, Colin Bannard, and Josh
Schroeder. 2005. Scaling phrase-based statistical machine translation to larger corpora
and longer phrases. In Proceedings of the 43rd
Annual Meeting on Association for Computational Linguistics, pages 255–262. Associationfor Computational Linguistics, 2005.

Tomas Mikolov, Martin Karafiat, Lukas Burget, Jan Cernocky and Sanjeev Khudanpur.
2010. Recurrent Neural Network Based Language Model. In Proceedings of the 11th Annual
Conference of the International Speech Communication Association, 2010.
Chris Quirk, Arul Menezes, and Colin Cherry.
2005. Dependency Treelet Translation: Syntactically Informed Phrasal SMT. In Proceedings of the 43rd Annual Meeting on Association
for Computational Linguistics. Association for
Computational Linguistics, 2005.

Colin Cherry and George Foster. 2012. Batch Tuning Strategies for Statistical Machine Translation. In HLT-NAACL, 2012.
David Chiang. 2007. Hierarchical phrase-basedtranslation. In Computational Linguistics.
Cromieres Fabien and Sadao Kurohashi. 2014.
Translation Rules with Right-Hand Side Lattices. In Proceedings of EMNLP 2014
Kenneth Heafield. 2011. KenLM: faster andsmaller language model queries. In Proceedingsof the EMNLP 2011 Sixth Workshop on Statistical Machine Translation, 2011.
Kenneth Heafield, Hieu Hoang, Philipp Koehn,Tetsuo Kiso, and Marcello Federico. 2011.
Left language model state for syntactic machine translation. In Proceedings of the International Workshop on Spoken Language Translation, 2011.
Kenneth Heafield, Philipp Koehn, and Alon Lavie.
2012. Language model rest costs and spaceefficient storage. In Proceedings of the Joint
Conference on Empirical Methods in NaturalLanguage Processing and Computational Natural Language Learning, 2012.
Zhifei Li and Sanjeev Khudanpur. 2008. A scalable decoder for parsing-based machine translation with equivalent language model state maintenance. In Proceedings of the Second Workshop88