On the Elements of an Accurate
Tree-to-String Machine Translation System
Graham Neubig, Kevin Duh
Graduate School of Information Science
Nara Institute of Science and Technology
8916-5 Takayama-cho, Ikoma-shi, Nara, Japan{neubig,kevinduh}@is.naist.jp
Abstracttranslation has a number of attractive theoreticalproperties, such as joint consideration of global reordering and lexical choice while maintaining relatively fast decoding times.

While tree-to-string (T2S) translation theoretically holds promise for efficient, accurate translation, in previous reports T2S
systems have often proven inferior to othermachine translation (MT) methods such asphrase-based or hierarchical phrase-based
MT. In this paper, we attempt to clarify
the reason for this performance gap byinvestigating a number of peripheral elements that affect the accuracy of T2S systems, including parsing, alignment, andsearch. Based on detailed experimentson the English-Japanese and JapaneseEnglish pairs, we show how a basic T2S
system that performs on par with phrasebased systems can be improved by 2.6-4.6
BLEU, greatly exceeding existing stateof-the-art methods. These results indicate that T2S systems indeed hold muchpromise, but the above-mentioned elements must be taken seriously in construction of these systems.

However, building an accurate T2S system is
not trivial. On one hand, there have been multiple
reports (mainly from groups with a long historyof building T2S systems) stating that systems using source-side syntax greatly out-perform phrasebased systems (Mi et al., 2008; Liu et al., 2011;
Zhang et al., 2011; Tamura et al., 2013). On theother hand, there have been also been multiple reports noting the exact opposite result that sourceside syntax systems perform worse than Hiero,S2T, PBMT, or PBMT with pre-ordering (Ambati
and Lavie, 2008; Xie et al., 2011; Kaljahi et al.,2012). In this paper, we argue that this is due to thefact that T2S systems have the potential to achieve
high accuracy, but are also less robust, with a number of peripheral elements having a large effect ontranslation accuracy.
Our motivation in writing this paper is to provide a first step in examining and codifying themore important elements that make it possible toconstruct a highly accurate T2S MT system. To doso, we perform an empirical study of the effect ofparsing accuracy, packed forest input, alignment
accuracy, and search. The reason why we choosethese elements is that past work that has reported
low accuracy for T2S systems has often neglected
to consider one or all of these elements.

1 Introduction
In recent years, syntactic parsing is being viewed
as an ever-more important element of statisticalmachine translation (SMT) systems, particularly
for translation between languages with large differences in word order. There are many ways ofincorporating syntax into MT systems, including
the use of string-to-tree translation (S2T) to ensure
the syntactic well-formedness of the output (Galley et al., 2006; Shen et al., 2008), tree-to-string(T2S) using source-side parsing as a hint during
the translation process (Liu et al., 2006), or preor post-ordering to help compensate for reordering problems experienced by non-syntactic methods such as phrase-based MT (PBMT) (Collins etal., 2005; Sudoh et al., 2011). Among these, T2S

As a result of our tests on English-Japanese (enja) and Japanese-English (ja-en) machine translation, we find that a T2S system not considering
these elements performs only slightly better than astandard PBMT system. However, after accounting for all these elements we see large increases ofaccuracy, with the final system greatly exceeding
not only standard PBMT, but also state-of-the-art
methods based on syntactic pre- or post-ordering.
143

Proceedings of the 52nd Annual Meeting of the Association for Computational Linguistics (Short Papers), pages 143–149,
Baltimore, Maryland, USA, June 23-25 2014. c 2014 Association for Computational Linguistics

2 Experimental Setup
2.1

SystemPBMT
Hiero
Pre/Post
T2S-all
T2S+all

Systems ComparedIn our experiments, we use a translation model
based on T2S tree transducers (Graehl and Knight,
2004), constructed using the Travatar toolkit (Neubig, 2013). Rules are extracted using the GHKM
algorithm (Galley et al., 2006), and rules withup to 5 composed minimal rules, up to 2 nonterminals, and up to 10 terminals are used.
We also prepare 3 baselines not based on T2S
to provide a comparison with other systems in theliterature. The first two baselines are standard systems using PBMT or Hiero trained using Moses(Koehn et al., 2007). We use default settings, except for setting the reordering limit or maximum
chart span to the best-performing value of 24. As
our last baselines, we use two methods based onsyntactic pre- or post-ordering, which are state-ofthe-art methods for the language pairs. Specifically, for en-ja translation we use the head finalization pre-ordering method of (Isozaki et al., 2010b),
and for ja-en translation, we use the syntactic postordering method of (Goto et al., 2012). For all
systems, T2S or otherwise, the language model isa Kneser-Ney 5-gram, and tuning is performed tomaximize BLEU score using minimum error rate
training (Och, 2003).
2.2

ja-en
BLEU RIBES
30.49
69.80
29.41
69.51
29.42
73.85
31.15
72.87
33.70
75.94

Table 1: Overall results for five systems.
we compare the 3 non-T2S baselines with two
T2S systems that vary the settings of the parser,alignment, and search, as described in the following Sections 3, 4, and 5. The first system “T2Sall” is a system that uses the worst settings1 foreach of these elements, while the second system“T2S+all” uses the best settings.2 The results forthe systems are shown in Table 1.
The most striking result is that T2S+all significantly exceeds all of the baselines, even including the pre/post-ordering baselines, which provide
state-of-the-art results on this task. The gains are
particularly striking on en-ja, with a gain of over 4
BLEU points over the closest system, but still significant on the ja-en task, where the use of sourceside syntax has proven less effective in previous
work (Sudoh et al., 2011). The next thing to noticeis that if we had instead used T2S-all, our conclusion would have been much different. This system
is able to achieve respectable accuracy compared
to PBMT or Hiero, but does not exceed the morecompetitive pre/post-ordering systems.3 With thisresult in hand, we will investigate the contributionof each of these elements in detail in the following
sections. In the remainder of the paper settings
follow T2S+all except when otherwise noted.

Data and Evaluation

We perform all of our experiments on en-ja
and ja-en translation over data from the NTCIRPatentMT task (Goto et al., 2011), the most standard benchmark task for these language pairs. We
use the training data from NTCIR 7/8, a total of
approximately 3.0M sentences, and perform tuning on the NTCIR 7 dry run, testing on the NTCIR
7 formal run data. As evaluation measures, we use
the standard BLEU (Papineni et al., 2002) as well
as RIBES (Isozaki et al., 2010a), a reorderingbased metric that has been shown to have highcorrelation with human evaluations on the NTCIR
data. We measure significance of results usingbootstrap resampling at p < 0.05 (Koehn, 2004).
In tables, bold numbers indicate the best system
and all systems that were not significantly different from the best system.
2.3

en-ja
BLEU RIBES
35.84
72.89
34.45
72.94
36.69
77.05
36.23
76.60
40.84
80.15

3 Parsing
3.1 Parsing Overview
As T2S translation uses parse trees both in training and testing of the system, an accurate syntactic
parser is required. In order to test the extent thatparsing accuracy affects translation, we use two
1 Stanford/Eda, GIZA++, pop-limit 5000 cube pruning.

2 Egret forests, Nile, pop-limit 5000 hypergraph search.

3 We have also observed similar trends on other genres andlanguage pairs. For example, in a Japanese-Chinese/English
medical conversation task (Neubig et al., 2013), forests,alignment, and search resulted in BLEU increases of en-ja
24.55→30.81, ja-en 19.28→22.46, zh-ja 15.22→20.67, ja-zh
30.88→33.89.

Motivational Experiment

Before going into a detailed analysis, we firstpresent results that stress the importance of the elements described in the introduction. To do so,144different syntactic parsers and examine the translation accuracy realized by each parser.
For English, the two most widely referenced
parsers are the Stanford Parser and Berkeley
Parser. In this work, we compare the Stanford
Parser’s CFG model, with the Berkeley Parser’s
latent variable model. In previous reports, it has
been noted (Kummerfeld et al., 2012) that the latent variable model of the Berkeley parser tends tohave the higher accuracy of the two, so if the accuracy of a system using this model is higher then it
is likely that parsing accuracy is important for T2S
translation. Instead of the Berkeley Parser itself,
we use a clone Egret,4 which achieves nearly identical accuracy, and is able to output packed forests
for use in MT, as mentioned below. Trees areright-binarized, with the exception of phrase-final
punctuation, which is split off before any other element in the phrase.
For Japanese, our first method uses the MSTbased pointwise dependency parser of Flannery etal. (2011), as implemented in the Eda toolkit.5
In order to convert dependencies into phrasestructure trees typically used in T2S translation,
we use the head rules implemented in the Travatar
toolkit. In addition, we also train a latent variable
CFG using the Berkeley Parser and use Egret forparsing. Both models are trained on the JapaneseWord Dependency Treebank (Mori et al., 2014).
In addition, Mi et al. (2008) have proposed amethod for forest-to-string (F2S) translation using packed forests to encode many possible sentence interpretations. By doing so, it is possible toresolve some of the ambiguity in syntactic interpretation at translation time, potentially increasingtranslation accuracy. However, the great majorityof recent works on T2S translation do not consider
multiple syntactic parses (e.g. Liu et al. (2011),
Zhang et al. (2011)), and thus it is important toconfirm the potential gains that could be acquiredby taking ambiguity into account.
3.2

en-ja
BLEU RIBES
38.95
78.47
39.26
79.26
40.84
80.15

SystemStan/Eda
Egret-T
Egret-F

ja-en
BLEU RIBES
32.56
73.03
32.97
74.94
33.70
75.94

Table 2: Results for Stanford/Eda, Egret with tree
input, and Egret with forest input.
1.0
42
en-ja
ja-en

41
0.8

BLEU

40
0.6
39
35
0.4

3.06

2.03

0.0
32
110

3.73

4.61

2.58

1.75

34
0.2
33

3.21 3.70

1.21

1

1.32

100

1.39 1.50

1.61 1.74 2.05

10
Forest n-best Cutoff

2.07

100

Figure 1: BLEU scores using various levels of forest pruning. Numbers in the graph indicate decoding time in seconds/sentence.
Egret achieves greater accuracy than that using theother two parsers. This improvement is particularly obvious in RIBES, indicating that an increasein parsing accuracy has a larger effect on global
reordering than on lexical choice. When goingfrom T2S to F2S translation using Egret, we seeanother large gain in accuracy, although this timewith the gain in BLEU being more prominent. We
believe this is related to the observation of Zhang
and Chiang (2012) that F2S translation is not necessarily helping fixing parsing errors, but instead
giving the translation system the freedom to ignore
the parse somewhat, allowing for less syntacticallymotivated but more fluent translations.
As passing some degree of syntactic ambiguity on to the decoder through F2S translation has
proven useful, a next natural question is how muchof this ambiguity we need to preserve in our forest.
The pruning criterion that we use for the forest isbased on including all edges that appear in one ormore of the n-best parses, so we perform translation setting n to 1 (trees), 3, 6, 12, 25, 50, 100, and200. Figure 1 shows results for these settings withregards to translation accuracy and speed. Overall, we can see that every time we double the sizeof the forest we get an approximately linear in-

Effect of Parsing and Forest Input

In Table 2 we show the results for Stanford/Eda
with 1-best tree input vs. Egret with trees orforests as input. Forests are those containing alledges in the 100-best parses.
First looking at the difference between the twoparsers, we can see that the T2S system using
4 http://code.google.com/p/egret-parser

5 http://plata.ar.media.kyoto-u.ac.jp/tool/EDA

145

Name
GIZA++
Nile/16
Nile/4
Nilecrease in BLEU at the cost of an increase in decoding time. Interestingly, the increases in BLEU did
not show any sign of saturating even when setting
the n-best cutoff to 200, although larger cutoffs resulted in exceedingly large translation forests that
required large amounts of memory.

Alignment Overview

The second element that we investigate is alignment accuracy. It has been noted in many previous works that significant gains in alignment accuracy do not make a significant difference in translation results (Ayan and Dorr, 2006; Ganchev etal., 2008). However, none of these works have explicitly investigated the effect on T2S translation,
so it is not clear whether these results carry over toour current situation.
As our baseline aligner, we use the GIZA++ implementation of the IBM models (Och and Ney,
2003) with the default options. To test the effectof improved alignment accuracy, we use the discriminative alignment method of Riesa and Marcu(2010) as implemented in the Nile toolkit.6 Thismethod has the ability to use source- and targetside syntactic information, and has been shown to
improve the accuracy of S2T translation.
We trained Nile and tested both methods on
the Japanese-English alignments provided with
the Kyoto Free Translation Task (Neubig, 2011)(430k parallel sentences, 1074 manually aligned
training sentences, and 120 manually aligned test
sentences).7 As creating manual alignment data is
costly, we also created two training sets that consisted of 1/4 and 1/16 of the total data to test if
we can achieve an effect with smaller amounts ofmanually annotated data. The details of data size
and alignment accuracy are shown in Table 3.
4.2

Prec.
60.46
70.21
72.85
72.73

Rec.
55.48
60.81
62.70
63.97

F-meas
57.86
65.17
67.40
68.07

Table 3: Alignment accuracy (%) by method andnumber of manually annotated training sentences.

4 Alignment
4.1

Sent.
0
68
269
1074

SystemPBMT-GPBMT-N
Hiero-G
Hiero-N
T2S-G
T2S-N/16
T2S-N/4
T2S-N

en-ja
BLEU RIBES
35.84
72.89
36.05
71.84
34.45
72.94
33.90
72.63
39.57
78.94
40.79
80.05
40.97
80.32
40.84
80.15

ja-en
BLEU RIBES
30.49
69.80
30.77
69.75
29.41
69.51
28.90
69.83
32.62
75.19
32.82
74.89
33.35
75.46
33.70
75.94

Table 4: Results varying the aligner (GIZA++ vs.
Nile), including results for Nile when using 1/4 or
1/16 of the annotated training data.

Figure 2: Probabilities for SVO→SOV rules.
improving the alignment accuracy gives significant gains for T2S translation. The reason for thisdifference is two-fold. The first is that in rule
extraction in syntax-based translation (Galley etal., 2006), a single mistaken alignment crossing
phrase boundaries results not only in a bad rule being extracted, but also prevents the extraction of anumber of good rules. This is reflected in the sizeof the rule table; the en-ja system built using Nilecontains 92.8M rules, while the GIZA++ system
contains only 83.3M rules, a 11.2% drop.
The second reason why alignment is importantis that while one of the merits of T2S models istheir ability to perform global re-ordering, it is difficult to learn good reorderings from bad alignments. We show an example of this in Figure 2.
When translating SVO English to SOV Japanese,
we expect rules containing a verb and a following
noun phrase (VO) to have a high probability of being reversed (to OV), possibly with the addition of

Effect of Alignment on Translation

In Table 4, we show results when we vary thealigner between GIZA++ and Nile. For reference,
we also demonstrate results when using the samealignments for PBMT and Hiero.
From this, we can see that while for PBMT and
Hiero systems the results are mixed, as has been
noted in previous work (Fraser and Marcu, 2007),
6 http://code.google.com/p/nile

7 This data is from Wikipedia articles about Kyoto City,and is an entirely different genre than our MT test data. It is
likely that creating aligned data that matches the MT genre
would provide larger gains in MT accuracy.

146the Japanese direct object particle “wo.” From thefigure, we can see that the probabilities learned by
Nile match this intuition, while the probabilities
learned by GIZA heavily favor no reordering.
Finally, looking at the amount of data needed totrain the model, we can see that a relatively small
amount of manually annotated data proves sufficient for large gains in alignment accuracy, witheven 68 sentences showing a 7.31 point gain in Fmeasure over GIZA++. This is because Nile’s feature set uses generalizable POS/syntactic information and also because mis-alignments of common
function words (e.g. a/the) will be covered evenby small sets of training data. Looking at the MT
results, we can see that even the smaller data setsallow for gains in accuracy, although the gains are
more prominent for en-ja.

1.0
42
41

BLEU (F2S)

40
0.8
39

33
0.2
32
31

0.66

1.04

1.81
1.77

3.73 5.60 9.59
4.43 9.60

17.40
en-ja HSen-ja CP

0.43
0.33

0.22
0.24

0.30

0.32

0.41 0.58 0.91

2.05 3.54 6.44

1.01

2.29 4.73 9.18

0.43 0.71

ja-en HS
ja-en CP1000
Pop Limit

10000

1.0
41
40

BLEU (T2S)

39
0.8
38

0.08

0.12

0.25 0.43
0.27

37
0.6
36
34
0.4
33

0.10

32
0.2
31

0.10

0.76

0.38 0.71

1.75 2.96 4.80
1.75 4.34 8.73
en-ja HSen-ja CP

0.09
0.08
0.14

0.13

0.25 0.37 0.57
0.24 0.44 0.64

1.21 2.22 3.97
1.60 3.83 5.74
ja-en HS
ja-en CP

30
0.0
29
100
1000 100 10000

1000
Pop Limit

10000

Figure 3: Hypergraph search (HS) and cube
pruning (CP) results for F2S and T2S. Numbers
above and below the lines indicate time in seconds/sentence for HS and CP respectively.

Search Overview

Finally, we examine the effect that the choice of
search algorithm has on the accuracy of translation. The most standard search algorithm for T2S
translation is bottom-up beam search using cube
pruning (CP, Chiang (2007)). However, there are
a number of other search algorithms that havebeen proposed for tree-based translation in general (Huang and Chiang, 2007) or T2S systems
in particular (Huang and Mi, 2010; Feng et al.,2012). In this work, we compare CP and the hypergraph search (HS) method of Heafield et al.
(2013), which is also a bottom-up pruning algorithm but performs more efficient search by grouping together similar language model states.
5.2

0.72 1.07

0.0
30
100
1000 100 10000

5 Search
5.1

38
0.6
37
35
0.4
34

0.33

0.42

6 Conclusion
In this paper, we discussed the importance of three
peripheral elements that contribute greatly to theaccuracy of T2S machine translation: parsing,alignment, and search. Put together, a T2S system that uses the more effective settings for thesethree elements greatly outperforms a system thatuses more standard settings, as well as the current
state-of-the-art on English-Japanese and JapaneseEnglish translation tasks.
Based on these results we draw three conclusions. The first is that given the very competitive
results presented here, T2S systems do seem tohave the potential to achieve high accuracy, evenwhen compared to strong baselines incorporating
syntactic reordering into a phrase-based system.
The second is that when going forward with research on T2S translation, one should first be sureto account for these three elements to ensure a
sturdy foundation for any further improvements.
Finally, considering the fact that parsing and alignment for each of these languages is far from perfect, further research investment in these fields
may very well have the potential to provide additional gains in accuracy in the T2S framework.
Acknowledgments: This work was supported
by JSPS KAKENHI Grant Number 25730136.

Effect of Search

Figure 3 shows BLEU and decoding speed results
using HS or CP on T2S and F2S translation, using a variety of pop limits. From this, we can seethat HS out-performs CP for both F2S and T2S,
especially with smaller pop limits. Comparing thegraphs for F2S and T2S translation, it is notablethat the shapes of the graphs for the two methods are strikingly similar. This result is somewhat
surprising, as the overall search space of F2S islarger and it would be natural for the characteristics of the search algorithm to vary between these
two settings. Finally, comparing ja-en and en-ja,
search is simpler for the former, a result of the factthat the Japanese sentences contain more words,
and thus more LM evaluations per sentence.
147

References
Vamshi Ambati and Alon Lavie. 2008. Improving syntax driven translation models by re-structuring divergent and non-isomorphic parse tree structures. In
Proc. AMTA, pages 235–244.
Necip Ayan and Bonnie Dorr. 2006. Going beyond
AER: an extensive analysis of word alignments andtheir impact on MT. In Proc. ACL.
David Chiang. 2007. Hierarchical phrase-based translation. Computational Linguistics, 33(2):201–228.
Michael Collins, Philipp Koehn, and Ivona Kucerova.
2005. Clause restructuring for statistical machinetranslation. In Proc. ACL, pages 531–540.
Yang Feng, Yang Liu, Qun Liu, and Trevor Cohn.
2012. Left-to-right tree-to-string decoding with prediction. In Proc. EMNLP, pages 1191–1200.
Daniel Flannery, Yusuke Miyao, Graham Neubig, andShinsuke Mori. 2011. Training dependency parsers
from partially annotated corpora. In Proc. IJCNLP,
pages 776–784.
Alexander Fraser and Daniel Marcu. 2007. Measuring
word alignment quality for statistical machine translation. Computational Linguistics, 33(3):293–303.
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.
Isao Goto, Bin Lu, Ka Po Chow, Eiichiro Sumita, andBenjamin K. Tsou. 2011. Overview of the patentmachine translation task at the NTCIR-9 workshop.
In Proceedings of NTCIR, volume 9, pages 559–578.
Isao Goto, Masao Utiyama, and Eiichiro Sumita. 2012.
Post-ordering by parsing for Japanese-English statistical machine translation. In Proc. ACL, pages
311–316.
Jonathan Graehl and Kevin Knight. 2004. Training
tree transducers. In Proc. HLT, pages 105–112.
Kenneth Heafield, Philipp Koehn, and Alon Lavie.
2013. Grouping language model boundary words tospeed k–best extraction from hypergraphs. In Proc.
NAACL, pages 958–968.

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.
Hideki Isozaki, Katsuhito Sudoh, Hajime Tsukada, andKevin Duh. 2010b. Head finalization: A simple
reordering rule for SOV languages. In Proc. WMTand MetricsMATR.
Rasoul Samad Zadeh Kaljahi, Raphael Rubino, Johann
Roturier, and Jennifer Foster. 2012. A detailed
analysis of phrase-based and syntax-based machinetranslation: The search for systematic differences.
In Proc. AMTA.
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.
Philipp Koehn. 2004. Statistical significance tests formachine translation evaluation. In Proc. EMNLP.
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.
Yang Liu, Qun Liu, and Shouxun Lin. 2006. Treeto-string alignment template for statistical machinetranslation. In Proc. ACL.
Yang Liu, Qun Liu, and Yajuan Lü. 2011. Adjoining tree-to-string translation. In Proc. ACL, pages
1278–1287.
Haitao Mi, Liang Huang, and Qun Liu. 2008. Forestbased translation. In Proc. ACL, pages 192–199.
Shinsuke Mori, Hideki Ogura, and Tetsuro Sasada.
2014. A Japanese word dependency corpus. In
Proc. LREC.
Graham Neubig, Sakriani Sakti, Tomoki Toda, Satoshi
Nakamura, Yuji Matsumoto, Ryosuke Isotani, andYukichi Ikeda. 2013. Towards high-reliability
speech translation in the medical domain. In Proc.
MedNLP, pages 22–29.
Graham Neubig. 2011. The Kyoto free translation
task. http://www.phontron.com/kftt.

Liang Huang and David Chiang. 2007. Forest rescoring: Faster decoding with integrated language models. In Proc. ACL, pages 144–151.

Graham Neubig. 2013. Travatar: A forest-to-stringmachine translation engine based on tree transducers. In Proc. ACL Demo Track, pages 91–96.

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.

148

Franz Josef Och. 2003. Minimum error rate training instatistical machine translation. In Proc. 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. ACL,
pages 311–318.
Jason Riesa and Daniel Marcu. 2010. Hierarchicalsearch for word alignment. In Proc. ACL, pages
157–166.
Libin Shen, Jinxi Xu, and Ralph Weischedel. 2008. A
new string-to-dependency machine translation algorithm with a target dependency language model. In
Proc. ACL, pages 577–585.
Katsuhito Sudoh, Xianchao Wu, Kevin Duh, Hajime
Tsukada, and Masaaki Nagata. 2011. Post-orderingin statistical machine translation. In Proc. MT Summit.
Akihiro Tamura, Taro Watanabe, Eiichiro Sumita, Hiroya Takamura, and Manabu Okumura. 2013. Partof-speech induction in dependency trees for statistical machine translation. In Proc. ACL, pages 841–
851.
Jun Xie, Haitao Mi, and Qun Liu. 2011. A novel
dependency-to-string model for statistical machinetranslation. In Proc. EMNLP, pages 216–226.
Hui Zhang and David Chiang. 2012. An explorationof forest-to-string translation: Does translation help
or hurt parsing? In Proc. ACL, pages 317–321.
Hao Zhang, Licheng Fang, Peng Xu, and Xiaoyun Wu.
2011. Binarized forest to string translation. In Proc.
ACL, pages 835–845.

149