Travatar: A Forest-to-String Machine Translation Engine
based on Tree Transducers
Graham Neubig
Graduate School of Information Science
Nara Institute of Science and Technology
8916-5 Takayama-cho, Ikoma-shi, Nara, Japanneubig@is.naist.jp

Abstract

McCord, 2004; Isozaki et al., 2010b), and treebased decoding techniques, which take a tree orforest as input and choose the reordering andtranslation jointly (Yamada and Knight, 2001; Liuet al., 2006; Mi et al., 2008). While pre-ordering is
not able to consider both translation and reordering in a joint model, it is useful in that it is done
before the actual translation process, so it can be
performed with a conventional translation pipeline
using a standard phrase-based decoder such as
Moses (Koehn et al., 2007). For tree-to-string systems, on the other hand, it is necessary to haveavailable or create a decoder that is equipped withthis functionality, which becomes a bottleneck in
the research and development process.
In this demo paper, we describe Travatar, an
open-source tree-to-string or forest-to-string translation system that can be used as a tool for translation using source-side syntax, and as a platform
for research into syntax-based translation methods. In particular, compared to other decoders
which mainly implement syntax-based translationin the synchronous context-free grammar (SCFG)
framework (Chiang, 2007), Travatar is built upon
the tree transducer framework (Graehl and Knight,
2004), a richer formalism that can help capture
important distinctions between parse trees, as weshow in Section 2. Travatar includes a fully documented training and testing regimen that was modeled around that of Moses, making it possible forusers familiar with Moses to get started with Travatar quickly. The framework of the software isalso designed to be extensible, so the toolkit is applicable for other tree-to-string transduction tasks.
In the evaluation of the decoder on EnglishJapanese machine translation, we perform a comparison to Moses’s phrase-based, hierarchicalphrase-based, and SCFG-based tree-to-string

In this paper we describe Travatar, aforest-to-string machine translation (MT)engine based on tree transducers. It provides an open-source C++ implementation
for the entire forest-to-string MT pipeline,
including rule extraction, tuning, decoding, and evaluation. There are a numberof options for model training, and tuning
includes advanced options such as hypergraph MERT, and training of sparse features through online learning. The training pipeline is modeled after that of the
popular Moses decoder, so users familiar with Moses should be able to getstarted quickly. We perform a validation experiment of the decoder on EnglishJapanese machine translation, and find that
it is possible to achieve greater accuracy
than translation using phrase-based andhierarchical-phrase-based translation. As
auxiliary results, we also compare different syntactic parsers and alignment techniques that we tested in the process of developing the decoder.
Travatar is available under the LGPL at
http://phontron.com/travatar

1

Introduction

One of the recent trends in statistical machinetranslation (SMT) is the popularity of models thatuse syntactic information to help solve problemsof long-distance reordering between the source
and target language text. These techniques canbe broadly divided into pre-ordering techniques,
which first parse and reorder the source sentence
into the target order before translating (Xia and91
Proceedings of the 51st Annual Meeting of the Association for Computational Linguistics, pages 91–96,
Sofia, Bulgaria, August 4-9 2013. c 2013 Association for Computational Linguistics

the preposition attatched to the verb, and the fourth
has the preposition attached to the noun.
For the SCFGs, it can be seen that on the sourceside of the rule, there are placeholders corresponding to syntactic phrases, and on the target side of
the rule there corresponding placeholders that do
not have a syntactic label. On the other hand in theexample of the translation rules using tree transducers, it can be seen that similar rules can be expressed, but the source rules are richer than simple
SCFG rules, also including the internal structureof the parse tree. This internal structure is important for achieving translation results faithful tothe input parse. In particular, the third and fourth
rules show an intuitive example in which this internal structure can be important for translation.
Here the full tree structures demonstrate importantdifferences in the attachment of the prepositional
phrase to the verb or noun. While this is one of
the most difficult and important problems in syntactic parsing, the source side in the SCFG is identical, losing the ability to distinguish between thevery information that parsers are designed to disambiguate.
In traditional tree-to-string translation methods,
the translator uses a single one-best parse tree output by a syntactic parser, but parse errors have thepotential to degrade the quality of translation. An
important advance in tree-to-string translation thathelps ameliorate this difficulity is forest-to-stringtranslation, which represents a large number ofpotential parses as a packed forest, allowing thetranslator to choose between these parses during
the process of translation (Mi et al., 2008).

Figure 1: Tree-to-string translation rules for
SCFGs and tree transducers.
translation. Based on the results, we find that treeto-string, and particularly forest-to-string, translation using Travatar provides competitive or superior accuracy to all of these techniques. As auxiliary results, we also compare different syntactic
parsers and alignment techniques that we tested in
the process of developing the decoder.

2

Tree-to-String Translation

2.1 Overview
Tree-to-string translation uses syntactic information to improve translation by first parsing thesource sentence, then using this source-side parsetree to decide the translation and reordering of the
input. This method has several advantages, including efficiency of decoding, relatively easy handling of global reordering, and an intuitive representation of de-lexicalized rules that express general differences in order between the source andtarget languages. Within tree-to-string translation
there are two major methodologies, synchronouscontext-free grammars (Chiang, 2007), and treetransducers (Graehl and Knight, 2004).
An example of tree-to-string translation rules
supported by SCFGs and tree transducers is shownin Figure 1. In this example, the first rule is a
simple multi-word noun phrase, the second example is an example of a delexicalized rule expressing translation from English SVO word order toJapanese SOV word order. The third and fourth
examples are translations of a verb, noun phrase,and prepositional phrase, where the third rule has

2.2 The State of Open Source Software
There are a number of open-source software packages that support tree-to-string translation in the
SCFG framework. For example, Moses (Koehn etal., 2007) and NiuTrans (Xiao et al., 2012) support the annotation of source-side syntactic labels,
and taking parse trees (or in the case of NiuTrans,
forests) as input.
There are also a few other decoders that support other varieties of using source-side syntax
to help improve translation or global reordering. For example, the cdec decoder (Dyer et al.,2010) supports the context-free-reordering/finitestate-translation framework described by Dyer andResnik (2010). The Akamon decoder (Wu etal., 2012) supports translation using head-driven

92

stored as sparse vectors by default, which allows
for scoring using an arbitrarily large number offeature functions.

phrase structure grammars as described by Wu etal. (2010).
However, to our knowledge, while there is a
general-purpose tool for tree automata in general(May and Knight, 2006), there is no open-source
toolkit implementing the SMT pipeline in the treetransducer framework, despite it being a target of
active research (Graehl and Knight, 2004; Liu etal., 2006; Huang et al., 2006; Mi et al., 2008).

3

3.3 Decoding
Given a translation model Travatar is able to decode parsed input sentences to generate translations. The decoding itself is performed using thebottom-up forest-to-string decoding algorithm of
Mi et al. (2008). Beam-search implemented using cube pruning (Chiang, 2007) is used to adjust
the trade-off between search speed and translation
accuracy.
The source side of the translation model isstored using a space-efficient trie data structure(Yata, 2012) implemented using the marisa-trie
toolkit.1 Rule lookup is performed using left-toright depth-first search, which can be implemented
as prefix lookup in the trie for efficient search.
The language model storage uses the implementation in KenLM (Heafield, 2011), and particularly the implementation that maintains left andright language model states for syntax-based MT(Heafield et al., 2011).

The Travatar Machine Translation
ToolkitIn this section, we describe the overall frameworkof the Travatar decoder, following the order of the
training pipeline.
3.1 Data Preprocessing
This consists of parsing the source side sentence
and tokenizing the target side sentences. Travatar
can decode input in the bracketed format of thePenn Treebank, or also in forest format. There is
documentation and scripts for using Travatar withseveral parsers for English, Chinese, and Japanese
included with the toolkit.
3.2 Training

3.4 Tuning and Evaluation

Once the data has been pre-processed, a treeto-string model can be trained with the training
pipeline included in the toolkit. Like the training pipeline for Moses, there is a single script that
performs alignment, rule extraction, scoring, andparameter initialization. Language model training
can be performed using a separate toolkit, and instructions are provided in the documentation.
For word alignment, the Travatar training
pipeline is integrated with GIZA++ (Och and Ney,
2003) by default, but can also use alignments fromany other aligner.
Rule extraction is performed using the GHKM
algorithm (Galley et al., 2006) and its extension torule extraction from forests (Mi and Huang, 2008).
There are also a number of options implemented,
including rule composition, attachment of nullaligned target words at either the highest point in
the tree, or at every possible position, and left andright binarization (Galley et al., 2006; Wang et al.,2007).
Rule scoring uses a standard set of forward
and backward conditional probabilities, lexicalized translation probabilities, phrase frequency,
and word and phrase counts. Rule scores are

For tuning the parameters of the model, Travatar
natively supports minimum error rate training(MERT) (Och, 2003) and is extension to hypergraphs (Kumar et al., 2009). This tuning canbe performed for evaluation measures including
BLEU (Papineni et al., 2002) and RIBES (Isozaki
et al., 2010a), with an easily extendable interface
that makes it simple to support other measures.
There is also a preliminary implementation of
online learning methods such as the structured perceptron algorithm (Collins, 2002), and regularized
structured SVMs trained using FOBOS (Duchi
and Singer, 2009). There are plans to implement
more algorithms such as MIRA or AROW (Chiang, 2012) in the near future.
The Travatar toolkit also provides an evaluation
program that can calculate the scores of translation output according to various evaluation measures, and calculate the significance of differences between systems using bootstrap resampling(Koehn, 2004).
193

http://marisa-trie.googlecode.com

4

Experiments

4.1 Experimental Setup
In our experiments, we validated the performanceof the translation toolkit on English-Japanesetranslation of Wikipedia articles, as specified by
the Kyoto Free Translation Task (KFTT) (Neubig,2011). Training used the 405k sentences of training data of length under 60, tuning was performedon the development set, and testing was performedon the test set using the BLEU and RIBES measures. As baseline systems we use the Moses2 implementation of phrase-based (MOSES - PBMT), hierarchical phrase-based (MOSES - HIER), and treeto-string translation (MOSES - T 2 S). The phrasebased and hierarchical phrase-based models weretrained with the default settings according to tutorials on each web site.
For all systems, we use a 5-gram Kneser-Ney
smoothed language model. Alignment for eachsystem was performed using either GIZA++3 or
Nile4 with main results reported for the alignerthat achieved the best accuracy on the dev set, anda further comparison shown in the auxiliary experiments in Section 4.3. Tuning was performed withminimum error rate training to maximize BLEU
over 200-best lists. Tokenization was performed
with the Stanford tokenizer for English, and the
KyTea word segmenter (Neubig et al., 2011) forJapanese.
For all tree-to-string systems we use Egret5 as
an English parser, as we found it to achieve highaccuracy, and it allows for the simple output offorests. Rule extraction was performed using onebest trees, which were right-binarized, and lowercased post-parsing. For Travatar, composed rulesof up to size 4 and a maximum of 2 non-terminals
and 7 terminals for each rule were used. Nullaligned words were only attached to the top node,and no count normalization was performed, in
contrast to Moses, which performs count normalization and exhaustive null word attachment. Decoding was performed over either one-best trees(TRAV- T 2 S), or over forests including all edges included in the parser 200-best list (TRAV- F 2 S), anda pop limit of 1000 hypotheses was used for cube

MOSES - PBMTMOSES - HIER
MOSES - T 2 S
TRAV- T 2 S
TRAV- F 2 S

BLEU
22.27
22.04
23.81
23.15
23.97

RIBES
68.37
70.29
72.01
72.32
73.27

Rules
10.1M
34.2M
52.3M
9.57M
9.57M

Sent/s.
5.69
1.36
1.71
3.29
1.11

Table 1: Translation results (BLEU, RIBES), rule
table size, and speed in sentences per second foreach system. Bold numbers indicate a statisticallysignificant difference over all other systems (bootstrap resampling with p > 0.05) (Koehn, 2004).
pruning.
4.2 System Comparison
The comparison between the systems is shown in
Table 1. From these results we can see that thesystems utilizing source-side syntax significantly
outperform the PBMT and Hiero, validating theusefulness of source side syntax on the English-toJapanese task. Comparing the two tree-to-stringsytems, we can see that TRAV- T 2 S has slightly
higher RIBES and slightly lower BLEU than
MOSES - T 2 S . One reason for the slightly higher
BLEU of MOSES - T 2 S is because Moses’s rule extraction algorithm is more liberal in its attachmentof null-aligned words, resulting in a much larger
rule table (52.3M rules vs. 9.57M rules) and memory footprint. In this setting, TRAV- T 2 S is approximately two times faster than MOSES - T 2 S. Whenusing forest based decoding in TRAV- F 2 S, we see
significant gains in accuracy over TRAV- T 2 S, with
BLEU slightly and RIBES greatly exceeding thatof MOSES - T 2 S.
4.3 Effect of Alignment/Parsing
In addition, as auxiliary results, we present a comparison of Travatar’s tree-to-string and forest-tostring systems using different alignment methods
and syntactic parsers to examine the results ontranslation (Table 2).
For parsers, we compared Egret with the Stanford parser.6 While we do not have labeled data
to calculate parse accuracies with, Egret is a cloneof the Berkeley parser, which has been reported toachieve higher accuracy than the Stanford parser
on several domains (Kummerfeld et al., 2012).
From the translation results, we can see that STAN -2

http://statmt.org/moses/
http://code.google.com/p/giza-pp/4
http://code.google.com/p/nile/ As Nile isa supervised aligner, we trained it on the alignments provided
with the KFTT.
5
http://code.google.com/p/
egret-parser/
36
http://nlp.stanford.edu/software/
lex-parser.shtml

94

PBMT
HIER
STAN - T 2 S
EGRET- T 2 S
EGRET- F 2 S

GIZA++BLEU RIBES
22.28
68.37
22.05
70.29
21.47
70.94
22.82
71.90
23.35
71.77

search speed (Huang and Mi, 2010). In addition,
there is a preliminary implementation of the ability to introduce target-side syntactic information,either through hard constraints as in tree-to-treetranslation systems (Graehl and Knight, 2004), or
through soft constraints, as in syntax-augmented
machine translation (Zollmann and Venugopal,
2006). Finally, we will provide better support ofparallelization through the entire pipeline to increase the efficiency of training and decoding.
Acknowledgements: We thank Kevin Duh and an
anonymous reviewer for helpful comments. Partof this work was supported by JSPS KAKENHI
Grant Number 25730136.

Nile
BLEU RIBES
22.37
68.43
21.77
69.31
22.44
72.02
23.15
72.32
23.97
73.27

Table 2: Translation results (BLEU, RIBES), forseveral translation models (PBMT, Hiero, T2S,
F2S), aligners (GIZA++, Nile), and parsers (Stanford, Egret).
T 2 S significantly underperforms EGRET- T 2 S , confirming that the effectiveness of the parser plays alarge effect on the translation accuracy.
Next, we compared the unsupervised aligner
GIZA++, with the supervised aligner Nile, whichuses syntactic information to improve alignment
accuracy (Riesa and Marcu, 2010). We held out
10% of the hand aligned data provided with the
KFTT, and found that GIZA++ achieves 58.32%
alignment F-measure, while Nile achieves 64.22%
F-measure. With respect to translation accuracy,
we found that for translation that does not use syntactic information, improvements in alignment do
not necessarily increase translation accuracy, as
has been noted by Ganchev et al. (2008). However, for all tree-to-string systems, the improvedalignments result in significant improvements inaccuracy, showing that alignments are, in fact, important in our syntax-driven translation setup.

References
David Chiang. 2007. Hierarchical phrase-based translation. Computational Linguistics, 33(2).
David Chiang. 2012. Hope and fear for discriminative
training of statistical translation models. Journal of
Machine Learning Research, pages 1159–1187.
Michael Collins. 2002. Discriminative training methods for hidden Markov models: Theory and experiments with perceptron algorithms. In Proc. EMNLP,
pages 1–8.
John Duchi and Yoram Singer. 2009. Efficient online
and batch learning using forward backward splitting.
Journal of Machine Learning Research, 10:2899–
2934.
Chris Dyer and Philip Resnik. 2010. Context-free
reordering, finite-state translation. In Proc. HLTNAACL.

5 Conclusion and Future Directions

Chris Dyer, Adam Lopez, Juri Ganitkevitch, Jonathan
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 Proceedings of the ACL 2010 System Demonstrations, pages 7–12.

In this paper, we introduced Travatar, an opensource toolkit for forest-to-string translation using
tree transducers. We hope this decoder will be
useful to the research community as a test-bed forforest-to-string systems. The software is alreadysufficiently mature to be used as is, as evidenced
by the competitive, if not superior, results in our
English-Japanese evaluation.
We have a number of plans for future development. First, we plan to support advanced rule
extraction techniques, such as fuller support for
count regularization and forest-based rule extraction (Mi and Huang, 2008), and using the EM
algorithm to choose attachments for null-aligned
words (Galley et al., 2006) or the direction of rulebinarization (Wang et al., 2007). We also plan
to incorporate advances in decoding to improve

Michel Galley, Jonathan Graehl, Kevin Knight, Daniel
Marcu, Steve DeNeefe, Wei Wang, and Ignacio
Thayer. 2006. Scalable inference and training ofcontext-rich syntactic translation models. In Proc.
ACL, pages 961–968.
Kuzman Ganchev, João V. Graça, and Ben Taskar.
2008. Better alignments = better translations? In
Proc. ACL.
Jonathan Graehl and Kevin Knight. 2004. Training
tree transducers. In Proc. HLT, pages 105–112.
Kenneth Heafield, Hieu Hoang, Philipp Koehn, Tetsuo
Kiso, and Marcello Federico. 2011. Left language

95

model state for syntactic machine translation. In
Proc. IWSLT.

Graham Neubig, Yosuke Nakata, and Shinsuke Mori.
2011. Pointwise prediction for robust, adaptable
Japanese morphological analysis. In Proc. ACL,
pages 529–533, Portland, USA, June.

Kenneth Heafield. 2011. Kenlm: Faster and smaller
language model queries. In Proc. WMT, pages 187–
197.

Graham Neubig. 2011. The Kyoto free translation
task. http://www.phontron.com/kftt.

Liang Huang and Haitao Mi. 2010. Efficient incremental decoding for tree-to-string translation. In
Proc. EMNLP, pages 273–283.

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

Liang Huang, Kevin Knight, and Aravind Joshi. 2006.
Statistical syntax-directed translation with extended
domain of locality. In Proceedings of AMTA, pages
66–73.

Franz Josef Och. 2003. Minimum error rate training instatistical machine translation. In Proc. ACL.
Kishore Papineni, Salim Roukos, Todd Ward, and WeiJing Zhu. 2002. BLEU: a method for automatic
evaluation of machine translation. In Proc. ACL,
pages 311–318, Philadelphia, USA.

Hideki Isozaki, Tsutomu Hirao, Kevin Duh, Katsuhito
Sudoh, and Hajime Tsukada. 2010a. Automatic
evaluation of translation quality for distant language
pairs. In Proc. EMNLP, pages 944–952.

Jason Riesa and Daniel Marcu. 2010. Hierarchicalsearch for word alignment. In Proc. ACL, pages
157–166.

Hideki Isozaki, Katsuhito Sudoh, Hajime Tsukada, andKevin Duh. 2010b. Head finalization: A simple
reordering rule for SOV languages. In Proc. WMTand MetricsMATR.

Wei Wang, Kevin Knight, and Daniel Marcu. 2007.
Binarizing syntax trees to improve syntax-based machine translation accuracy. In Proc. EMNLP, pages
746–754.

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. ACL, pages 177–180, Prague, Czech Republic.

Xianchao Wu, Takuya Matsuzaki, and Jun’ichi Tsujii.
2010. Fine-grained tree-to-string translation rule extraction. In Proc. ACL, pages 325–334.
Xianchao Wu, Takuya Matsuzaki, and Jun’ichi Tsujii. 2012. Akamon: An open source toolkit fortree/forest-based statistical machine translation. In
Proceedings of the ACL 2012 System Demonstrations, pages 127–132.

Philipp Koehn. 2004. Statistical significance tests formachine translation evaluation. In Proc. EMNLP.
Shankar Kumar, Wolfgang Macherey, Chris Dyer,
and Franz Och. 2009. Efficient minimum error
rate training and minimum Bayes-risk decoding fortranslation hypergraphs and lattices. In Proc. ACL,
pages 163–171.

Fei Xia and Michael McCord. 2004. Improving
a statistical MT system with automatically learned
rewrite patterns. In Proc. COLING.
Tong Xiao, Jingbo Zhu, Hao Zhang, and Qiang Li.
2012. Niutrans: An open source toolkit for phrasebased and syntax-based machine translation. In Proceedings of the ACL 2012 System Demonstrations,pages 19–24.

Jonathan K Kummerfeld, David Hall, James R Curran, and Dan Klein. 2012. Parser showdown at thewall street corral: an empirical investigation of error types in parser output. In Proc. EMNLP, pages
1048–1059.

Kenji Yamada and Kevin Knight. 2001. A syntaxbased statistical translation model. In Proc. ACL.

Yang Liu, Qun Liu, and Shouxun Lin. 2006. Treeto-string alignment template for statistical machinetranslation. In Proc. ACL.

Susumu Yata. 2012. Dictionary compression using
nested prefix/Patricia tries (in Japanese). In Proc.
17th NLP.

Jonathan May and Kevin Knight. 2006. Tiburon:A weighted tree automata toolkit. In Implementation and Application of Automata, pages 102–113.
Springer.

Andreas Zollmann and Ashish Venugopal. 2006. Syntax augmented machine translation via chart parsing.
In Proc. WMT.

Haitao Mi and Liang Huang. 2008. Forest-based translation rule extraction. In Proc. EMNLP, pages 206–
214.
Haitao Mi, Liang Huang, and Qun Liu. 2008. Forestbased translation. In Proc. ACL, pages 192–199.

96