Bayesian Subtree Alignment Model based on Dependency Trees
Toshiaki Nakazawa
Sadao Kurohashi
Graduate School of Informatics, Kyoto University
Yoshida-honmachi, Sakyo-ku
Kyoto, 606-8501, Japannakazawa@nlp.kuee.kyoto-u.ac.jp kuro@i.kyoto-u.ac.jp

Abstract

et al., 1993), which handle sentences as sequencesof words, usually followed by some heuristic symmetrization rules to combine the alignment resultsin both directions. Since the accuracy is to someextent good for some language pairs, many researchers focus not on alignment, but on translation with more linguistic information incorporated
in the models. Phrase-based SMT (Koehn et al.,2003) uses units larger than words, whereas Hiero (Chiang, 2005) used a kind of sentence structure. Various other studies tried incorporating
additional linguistic knowledge such as syntactic
trees (Chiang, 2010), dependency trees (Menezes
and Quirk, 2008), or packed-forests (Tu et al.,2010) in their translation models. Note that allthese works are based on the word sequentialalignment models.
However, for distant language pairs such as
English-Japanese or Chinese-Japanese, the word
sequential model is quite inadequate (about 20 to
30 % AER), and therefore it is important to improve the alignment accuracy itself. The differences between languages can be seen in Figure
1, which shows an example of English-Japanese.
The word or phrase order is quite different forthese languages. Another important point is that
there are often many-to-one or many-to-many correspondences. For example, the Japanese nounphrase “受 光 素子” is composed of three words,
whereas the corresponding English phrase consistsof only one word “photodetector”, and the English
function word “for” corresponds to two Japanesefunction words “に は”. In addition, there are basically no counterparts for the English articles (a,an, the). Figure 2 shows the alignment results frombi-directional GIZA++ together with a combination heuristic called grow-diag-final-and1 for thesame sentence pair given in Figure 1. The systemfailed to align some words in the Japanese noun

Word sequential alignment models work
well for similar language pairs, but they
are quite inadequate for distant language
pairs. It is difficult to align words orphrases of distant languages with high accuracy without structural information of
the sentences. In this paper, we pro- pose a
Bayesian subtree alignment model that incorporates dependency relations be- tween
subtrees in dependency tree struc- tures
on both sides. The dependency re- lation model is a kind of tree-based re- ordering model, and can handle non-local
reorderings, which sequential word-basedmodels often cannot handle properly. The
model is also capable of handling multilevel structures, making it possible to findmany-to-many correspondences automatically without any heuristic rules. The
size of the structures is controlled by nonparametric Bayesian priors. Experimental alignment results show that our model
achieves 3.5 points better alignment error
rate for English-Japanese than the word
sequential alignment model, thereby verifying that the use of dependency information is effective for structurally different
language pairs.

1

Introduction

Alignment accuracy is crucial for providing highquality corpus-based machine translation systems
because translation knowledge is acquired froman aligned training corpus. For similar language
pairs, alignment accuracy is high, and the state-ofthe-art word alignment tool GIZA++ has a smaller
than 10% alignment error rate (AER) for FrenchEnglish. GIZA++ is an implementation of thealignment models called the IBM models (Brown

1

This is trained on the same corpus used in Section 4.

794
Proceedings of the 5th International Joint Conference on Natural Language Processing, pages 794–802,
Chiang Mai, Thailand, November 8 – 13, 2011. c 2011 AFNLP

phrase, and incorrectly aligned “the ↔ は “. The
word sequential model is prone to many such errors even for short simple sentences of a distantlanguage pair.
Even if the word order differs greatly between
languages, phrase dependencies tend to hold between languages. This is also true in Figure 1.
Therefore, incorporating dependency analysis into
the alignment model is useful for distant language
pairs. Cherry and Lin (2003) proposed a modelthat uses a source side dependency tree structure
and constructs a discriminative model. However,the drawback is that the alignment unit is the word,
and thus, it can only find one-to-one alignments.
The capability of generating many-to-many correspondences is also important because one or more
words often correspond to more than one word on
the other side.
Nakazawa and Kurohashi (2009) also proposeda model focusing on dependency relations. Theymodeled phrase dependency relations in dependency trees on both sides. The model is also capable of estimating many-to-many correspondences
automatically without any heuristics through maximum likelihood estimation. One serious drawback of their model is that it tends to acquire incorrect larger subtrees. For models that can handle multiple levels (or sizes) of structures, larger
structures always defeat smaller ones in maximum
likelihood estimation, and the best solution is toalign one sentence as a structure with the otherfor all sentence pairs. Although Denero et al.
(2008) solved this degeneracy by placing a Dirichlet process prior over the parameters that can control the size of phrases properly, their Bayesianmodel again only handles sentences as sequencesof words. In this paper, we take advantage of thetwo studies by Nakazawa et al. and Denero et al.,and propose a Bayesian subtree alignment model
based on dependency trees to improve alignment
accuracy for distant language pairs.

2ཷ(accept)ගA(light)⣲Ꮚ

photogate(device)

䛻

is

(ni)

䛿

used

(ha)

䝣䜷䝖

for

(photo)䝀䞊䝖(gate)

䜢thephotodetector

(wo)

⏝䛔䛯
(used)

Figure 1: Example of dependency trees and alignment of subtrees. The root of the tree is placed at
the extreme left and words are placed from top tobottom.

Figure 2: Alignment results from bi-directional
GIZA++. Black boxes depict the system output,
while dark (Sure) and light (Possible) gray cells
denote gold-standard alignments.

as a sequence of words works adequately. This
does not hold for distant language pairs such as
English-Japanese or Chinese-Japanese, in whichword orders differ greatly. We incorporate dependency relations of words into the alignment
model and define the reorderings on the word dependency trees. Figure 1 shows an example of thedependency trees for Japanese and English.
2.1 Generative Story Description

Dependency Tree-based Alignment
Model

Similar to the previous works (Marcu and Wong,
2002; DeNero et al., 2008), we first describe thegenerative story for the joint alignment model.

Our model is an extension of the one proposed by
Denero et al. (2008). Two main drawbacks of theprevious model are the lack of structural information and a naive distortion model. For similar language pairs such as French-English (Marcu andWong, 2002) or Spanish-English (DeNero et al.,2008), even a simple model that handles sentences

1. Generate ` concepts from which subtree pairs
are generated independently.
2. Combine the subtrees in each language so as
to create parallel sentences.

795

Here, subtrees are equivalent to phrases in the previous works. One subtree in a concept can be
NULL, which represents an unaligned subtree. We
restrict the unaligned subtrees to be composed ofexactly one word, because of our model simplicity(NULL-alignment restriction).
The number of concepts ` is parameterized using a geometric distribution:
P (`) = pc · (1 − pc )`−1 .

where PW A is the IBM model1 likelihood (Brown
et al., 1993), and nf and ne are the numbers ofword types in each language. θA gives a non-zeroweight to aligned subtree pairs only.
Unaligned subtrees are generated from anotherunknown probability distribution θN :(1)

P ({he, f i}, D) = P (`) · P (D|{he, f i}) ·he,f i

Instead of the naive reordering model in the previous work, our model considers dependency relations between subtrees and assigns a weight toeach relation. Suppose subtree fj depends on
subtree fk (parent subtree), which means (j →k) ∈ DF , and both fj and fk are aligned subtrees. Their counterparts, ej and ek respectively,
are somewhere on the dependency tree of the otherside. We can assume that ej tends to depend on ek
because the dependencies between concepts hold
across languages. The dependency relation probability reflects this tendency.
Formally,
weextractatuple(N (fj ), rel(fj , fj 0 )) for subtree fj , and assign the dependency relation probability to thattuple. For unaligned subtrees, the dependency
relation probability is not taken into consideration.
If the parent subtree is an unaligned subtree, we
ascend the dependency tree to the root node until
an aligned subtree is found. We call the nearestaligned subtree a pseudo parent. The pseudoparent for subtree fj is denoted as fj 0 , and thenumber of unaligned subtrees from fj to fj 0 isdenoted as N (fj ). We consider an imaginary
root node as a pseudo parent for the root subtree.
For example, the parent subtree of “フォト ゲー
ト (photogate)” is “を (accusative)” which isunaligned in Figure 1. The pseudo parent is “
用いた (used)” and the number of unaligned
subtrees N = 1. Japanese function words areoften unaligned, similar to this example, but thedependency relations between subtrees stepping
over the function words are assumed to hold on(2)

When generating subtrees, we first decide whether
to generate an unaligned subtree (with probability pφ ) or an aligned subtree pair (with probability
1 − pφ ). DeNero et al. (2008) used pφ = 10−10
to strongly discourage NULL alignment, but thisis not reasonable for some language pairs. Taking Japanese and English as an example, English
determiners (a, an, the) and Japanese case markers (ha, ga, wo, etc.) rarely have counterparts. In
addition, if the corpus is less clean and sentencepairs often contain a different amount of information, the strict restriction may lead to alignment
errors. Therefore, we use pφ = 0.33.
Aligned subtree pairs are generated from an unknown probability distribution θA , which obeys
the Dirichlet process (DP):(3)

where MA is the base distribution and αA is a concentration parameter. The base distribution is defined as:=Pf (f )=Pe (e)==

2.3 Dependency Relation Probability

2.2 Subtree Generation

MA (he, f i)

MN (he, f i)

DP (MN , αN ){PW A (e|NULL) if f = NULL.
PW A (f |NULL) if e = NULL
(5)

θT (he, f i) = pφ θN (he, f i) + (1 − pφ )θA (he, f i).
(6)θT (he, f i).

θA (he, f i) ∼ DP (MA , αA ),∼θN gives a non-zero weight to unaligned subtrees
only. Note that unaligned subtrees are always
composed of only one word in our model. Finally,
θT can be decomposed as:

Each concept ci generates a subtree pair hei , fi ifrom an unknown distribution θT , and then they
are combined in each language. We denote the
combinations of subtrees in English as DE ={(j → k)}, where (j → k) denotes that subtree ejdepends on subtree ek , and in the foreign language
as DF . D refers to DE and DF as a whole.
With these notations, the joint probability for asentence pair is defined as:∏

θN (he, f i)

1

[Pf (f )PW A (e|f ) · Pe (e)PW A (f |e)] 2( )|f |
pt · (1 − pt )|f |−1 · n1f( )|e|
pt · (1 − pt )|e|−1 · n1e
,
(4)

796

the other side. Therefore we introduce a pseudoparent to capture the relations.
Function rel(fj , fj 0 )) returns a dependency relation between the counterparts of the two arguments. Note that the counterparts of fj and fj 0
are ej and ej 0 , respectively. We express a dependency relation as the shortest path from one subtree to another. For simplicity, we indicate thepath with a pair of non-negative integers, where
the first is the number of steps going up (U p) the
dependency tree and the other is the number going
down (Down). It also requires one additional stepfor going through unaligned subtrees. For example, in Figure 1, traveling from “A photogate” to“photodetector” requires 1 step going up (to reach“is used”) and 2 steps going down (via “for”), so
the dependency relation is (U p, Down) = (1, 2).
Consequently, the tuple is represented as a tripletof non-negative integers Rf = (N, U p, Down).
The dependency relation probabilities for theforeign language side are drawn from an unknown
probability distribution θf e and for the English
side from θef , with both obeying the DP:
θf e (Rf )Mf e (Rf )θef (Re )Mef (Re )sults of the standard word alignment tool GIZA++.
Many machine translation studies use heuristics tocombine the two alignment results, one of whichis called grow-diag-final-and (Koehn et al., 2007).
Our heuristic is similar to this, but the differenceis that we combine the two results based on dependency trees, and not on word sequences. The
initialization is carried out by the following steps:
1. Take the intersection of the two results.
2. Add alignment points connected to at least
one accepted point in terms of the dependency tree (corresponds to grow-diag).
3. Add alignment points between two unaligned
words (corresponds to final-and).
Initial boundaries of subtrees and their alignments,
and also the counts of subtree pairs and dependency relations are thus acquired.
3.2 Sampling Operators
Our sampler uses three operators repeatedly togenerate samples. The operators are illustrated in
Figure 3. A solid circle represents a single word,while a subtree is depicted as the part surrounded
by a dotted line. Alignment links between subtrees
are represented by broken lines.
Each application of an operator generates one
new sample, and of course we could use all thegenerated samples. However, successive samples
are almost the same, except for one local part. It
is no use keeping all the samples, so we keep only
one sample, which is the final outcome after applying all the operators to all the possible points inall the sentence pairs in the training corpus.

∼
=
∼
=

DP (Mf e , αf e )pf e · (1 − pf e )N +U p+Down−1
DP (Mef , αef )pef · (1 − pef )N +U p+Down−1 .
(7)
Using the notations and definitions above,the dependency tree-based reordering model
P (D|{he, f i}) is decomposed as:∏
P (D|{he, f i}) =θf e (Rf ) · θef (Re ). (8)he,f i

3 Model Training

We train the model by means of a collapsed Gibbs
sampling, which has been used in some recent
NLP works (DeNero et al., 2008). In a Gibbs sampling, we first need to initialize the states of the
training data, such as the boundaries between subtrees and their alignments, and also initialize thelatent variables according to the initial states ofthe data. Starting with the initial state, we generate many samples in order from the last stateby changing a small local point. Normalizing thecounts in the samples yields the parameter estimations.

SWAP
The SWAP operator exchanges the counterparts of
two subtrees with each other. Boundaries between
subtrees and the number of aligned subtrees in thesentence pair are fixed. There are two cases for
SWAP:
1. Both of the subtrees are aligned (SWAP-1).
2. One of the two subtrees is unaligned and theother is composed of only one word (SWAP2).

3.1 Initialization
We initialize the states of the training data byheuristically merging bi-directional alignment re-

An illustration of the result of the SWAP operator
is shown at the top of Figure 3.

797

node has more than one child node inside the subtree, it cannot exclude the root node, because thesubtree will be divided into two subtrees by theexclusion, and it is impossible to return to the previous state. Operators in a Gibbs sampler must beable to return the same status by immediately reapplying the same operator to the same point. An
illustration of the EXPAND operation is shown in
Figure 3.

SWAP-1

SWAP-2NULL

NULL

TOGGLE
NULL

3.3 Computational Complexity and Parallel
Sampling

NULL

The distortion model of the previous work does
not consider any relations to neighboring phrases,
so any operation does not affect the distortions ofneighboring phrases. On the contrary, our proposed model considers the relations, and this leads
to an increase in the computational complexity for
one operation. For example, swapping two aligned
subtree pairs requires re-calculation of the dependency relation probabilities for not only the four
focused subtrees, but also subtrees whose pseudoparent is one of the focused subtrees. This is thesame for the TOGGLE operation.
To make matters worse, the EXPAND operator requires much more. All the subtrees that traverse the locally changed subtree, 1) in finding a
pseudo parent, and 2) in finding the dependency
relations, need re-calculation of the dependency
relation probabilities, because the number of steps(N , U p and Down) will change.
This increase in computational complexity
makes the training time much longer, so that it is
impossible to train using a single CPU. To alleviate this problem somewhat, we divide the training data into several parts and execute samplingin parallel. The overall flow of model training issummarized as follows:

EXPAND-1
NULL

EXPAND-2

NULL

Figure 3: Illustration of the operators.
TOGGLEThe TOGGLE operator adds or removes an alignment. If fj and ek are both unaligned subtrees,
TOGGLE links these two subtrees. Alternatively,
if fj and ej are aligned, TOGGLE cuts the link andmakes each of the subtrees unaligned. Because of
the NULL-alignment restriction, TOGGLE doesnothing if fj or ej is composed of more than one
word. Boundaries between subtrees are fixed. An
illustration of the TOGGLE operation is shown inthe middle of Figure 3.
EXPANDThe EXPAND operator expands or contracts analigned subtree. If an unaligned subtree is next
to an aligned one, EXPAND tries to merge the unaligned and aligned subtrees. It also tries to exclude a marginal node from a subtree, and to makethe excluded node unaligned. There are two cases
for EXPAND:

1. Initialize the training corpus and current
counts of subtree pairs and dependency relations, and divide the corpus into several sections.

1. A node is added to a subtree as a new leaf
node, or a leaf node of a subtree is excluded(EXPAND-1).

2. Start sampling in parallel using the same current counts, and generate one sample fromeach section. A sample is the final state of
the section.

2. A node is added to a subtree as the new root
node, or the root node of a subtree is excluded(EXPAND-2).

3. Gather samples and update the current counts
by counting subtree pairs and dependency relations in the samples.

EXPAND-1 does not have any restrictions on its
operation. However, for EXPAND-2, if the root798

4. Go back to step 2.

4# of sentences# of words
ave. sent. length

Alignment Experiments

We conducted alignment experiments on EnglishJapanese and Chinese-Japanese corpora to show
the effectiveness of the proposed model.

En-Ja
Zh-Ja

For English-Japanese, the JST2 paper abstract corpus was used. This corpus was created by NICT3
from JST’s 2M English-Japanese paper abstract
corpus using the method of Utiyama and Isahara(2007). For Chinese-Japanese, we used the paper abstract corpus provided by JST and NICT.
This corpus was developed during a project inJapan called the “Development and Research of
Chinese-Japanese Natural Language Processing
Technology”. The statistics of these corpora areshown in Table 4.1. Unfortunately, these two corpora are not freely available now, but they will become available to everyone in near future.
As gold-standard data, we used 479 sentencepairs of English-Japanese and 510 sentence pairsof Chinese-Japanese. These were annotated byhand using two types of annotations: sure (S)alignments and possible (P ) alignments (Och andNey, 2003). The unit of evaluation was the word
for all the languages. We used precision, recall,and alignment error rate (AER) as evaluation criteria. All the experiments were run on the original forms of words. The hyper parameters for ourmodel used in the experiments are summarized inTable 4.1.
Japanese sentences were converted into dependency structures using the morphological analyzer
JUMAN (Kurohashi et al., 1994), and the dependency analyzer KNP (Kawahara and Kurohashi,2006). For English sentences, Charniak’s nlparser
was used to convert them into phrase structures(Charniak and Johnson, 2005), and then they weretransformed into dependency structures by rules
defining head words for phrases. Chinese sentences were converted into dependency trees using the word segmentation and POS-tagging tool
by Canasai et al. (2009) and the dependency analyzer CNP (Chen et al., 2008).
For comparison, we used GIZA++ (Och andNey, 2003) which implements the prominent sequential word-based statistical alignment model
3

Zh-Ja
Zh
Ja
680K
18.8M 22.3M
27.7 32.9

Table 1: Statistics of the training corpus.

4.1 Settings

2

En-Ja
En
Ja
996K
24.7M 27.5M
24.8 27.6

αA
100
10

αN
100
100

pt
0.8
0.8

αf e , αef
100100

pf e , pef
0.5
0.5

Table 2: Hyper parameters used in experiments.
of the IBM Models. We conducted word alignment bidirectionally with the default parametersand merged them using the grow-diag-final-andheuristic (Koehn et al., 2003). Furthermore, weused the BerkeleyAligner4 (DeNero and Klein,2007) with default settings for unsupervised training. Experimental results for English-Japaneseare shown in Table 4.1, and those for ChineseJapanese are shown in Table 4.1. The alignment
accuracy of the initialization described in Section
3.1 is indicated as “Initialization”, while the accuracy after conducting Gibbs sampling is indicatedas “Proposed”.
4.2 Discussion
For English-Japanese, our proposed model
achieved reasonably high alignment accuracy
compared with that of GIZA++ and the BerkeleyAligner. Using tree structures combined withthe bi-directional alignment results leads to better
accuracy than the original sequential heuristic(indicated as Initialization). We also give thealignment accuracy obtained by Nakazawa andKurohashi (2009) (indicated as Nakazawa+ in
Table 4.1, and applicable only to the EnglishJapanese corpus)5 . Their model suffered froma degeneracy in acquiring larger phrases caused
by maximum likelihood estimation, and this led
to low precision and high recall. Compared with
their model, our proposed model overcomes thedegeneracy and outperforms in terms of both precision and recall. Figure 4 shows an example ofthe improvement in alignment. GIZA++ aligned
function words incorrectly because of the lackof structural information. For example, GIZA++aligned the English “of” and the Japanese “の”4

http://code.google.com/p/berkeleyaligner/
They used 475 sentence pairs instead of 479 sentencepairs of ours. The difference comes from the inconsistencyof word segmentations of Japanese, but it is negligibly small.
5

http://www.jst.go.jp/
http://www.nict.go.jp/799

grow-diag-final-and
BerkeleyAligner
Nakazawa+
Initialization
Proposed

Pre.
81.17
85.00
80.28
82.39
85.93

Rec.
62.19
53.82
63.85
61.82
64.71

AER
29.25
33.72
28.67
28.99
25.73

Table 3: Results of English-Japanese alignment
experiments.

grow-diag-final-and
BerkeleyAligner
Initialization
Proposed

Pre.
83.77
88.43
84.71
85.52

Rec.
75.38
69.77
75.46
74.71

GIZA++

AER
20.39
21.60
19.90
19.89

Table 4: Results of Chinese-Japanese alignment
experiments.
in the third word. This was incorrectly derived
from the combination heuristic: English posterior
word “other” and Japanese prior word “その他” are aligned by intersection, and thus, “of↔ の” is also aligned through the grow-diagheuristic. This could be avoided by introducing
dependency trees: the English words “of” and“other” are not contiguous in the dependency tree.
In addition, there is no correspondence between“に ついて の ↔ of”. This is a rare translation
for “of”, which is most frequently translated
as “の”, so GIZA++ aligned “の ↔ of” only.
A nonparametric Bayesian model is capable offinding the correct alignment with the support ofoccurrences of the subtree pair elsewhere in the
training corpus.
The reasons for recall being significantly lower
than precision in all the models are summarized
in the two points. One is the separation between
gold-standard criteria and system output. In Figure 4, “are described” and “を 取りまとめた” arealigned in their entirety, but the system found oneto-one alignments, which are also acceptable. The
other is that it is sometimes hard to align part ofa sentence in a smaller unit for distant language
pairs, because the expressions are quite different.
In such cases, the system is obliged to align expressions enmasse, which leads to low recall.
For Chinese-Japanese, we failed to improvealignment accuracy greatly. A major cause of thisundesirable result could be the accuracy of theChinese parser. Both the English and Japanese

Proposed

Figure 4: Alignment results from bi-directional
GIZA++ (top) and proposed model (bottom).

parsers used in the experiments can analyze sentences with over 90% accuracy, whereas the accuracy of the Chinese parser is less than 80% despite it being state-of-the-art in the world (Chenet al., 2008). The parsing accuracy reported inthis paper was obtained from an experiment using gold-standard word segmentation and POStags. Starting with raw sentences results in about
77.4% accuracy. This information was obtained
from communication with the authors. Fundamental NLP technologies in each language must be improved in the long term, and sophisticated models,
which use deeper analysis of sentences like ourmodel, should become effective in the near future.
One possible short-term solution for the parsing
problem is to use the n-best parsing results in themodel. Another kind of solution was proposed by
Burkett et al. (2010), who described a joint parsing and alignment model that can exchange useful
information between the parser and aligner.
However, even in the case of Chinese-Japanesealignment, we achieved higher precision than
GIZA++. For translation, precision is more im-800

grow-diag-final-and
Initialization
Proposed

BLEU
24.59
25.33
24.50

for distant language pairs. The model incorporates
the tree-based reordering model. It also solves thedegeneracy of the maximum likelihood estimation
for models capable of handling multiple levels of
structures by placing a Dirichlet process prior overparameters. Experimental results show that a word
sequential model does not work well for distantlanguage pairs, but that this can be addressed byusing syntactic information. Our proposed model
achieved a lower AER by about 3.5 points compared with GIZA++.
To support allegation that syntactic information
is important for distant language pairs, it is necessary to compare our model with the original word
sequential study (DeNero et al., 2008), which wasconsulted often. It is also important to apply ourmodel not only to other distant language pairs, butalso to similar language pairs, and to investigate
the results. We are planning to use standard data
set such as NIST or IWSLT. Also, we could use
the n-best parsing results in our model to alleviate
the error propagation from parsing, especially for
Chinese.

Table 5: BLEU results for Japanese-to-English
translation experiments.
portant than recall. The BerkeleyAligner showedmuch higher precision than GIZA++ and, in
Chinese-Japanese alignment, than our model aswell. However, recall was quite low comparedwith all the other models. Lower recall results ina large translation table because the phrase extraction heuristics ’grow’ over each unaligned word.

5

Translation Experiments

We conducted Japanese-to-English translation experiments on the same corpus used in the alignment experiment. We translated 500 paper abstract sentences from the JST corpus. Note thatthese sentences were not included in the training
corpus. We used the state-of-the-art phrase-based
SMT toolkit Moses(Koehn et al., 2007) with default options, except for the distortion limit (6 →20). It was tuned by MERT using another 500 development sentence pairs.
Table 5 shows the BLEU scores for the translations. Although the difference in alignment accuracy between grow-diag-final-and and Initialization is small, the BLEU score was improved by
0.74 point. This is because syntactic information
reduced incorrect alignment points and the quality of translation table becomes better. This result
provided evidence that syntactic knowledge is useful for distant language pairs. However, the BLEU
score decreased after iterations of our alignment
model. The main reason is that the alignment result of our model is not compatible with Phrasebased SMT. Our model often output sequentially
discontiguous alignments which are harmful for
PSMT to create fine-grained phrase table. We
need to use other decoders which is compatible
with our alignment model (Nakazawa and Kurohashi, 2010), and we believe that our model leads
to better translation quality.

6

References
Peter F. Brown, Stephen A. Della Pietra, Vincent
J. Della Pietra, and Robert L. Mercer. 1993. The
mathematics of statistical machine translation: Parameter estimation. Association for Computational
Linguistics, 19(2):263–312.
David Burkett, John Blitzer, and Dan Klein. 2010.
Joint parsing and alignment with weakly synchronized grammars. In Human Language Technologies: The 2010 Annual Conference of the North
American Chapter of the Association for Computational Linguistics, pages 127–135, Los Angeles, California, June. Association for Computational
Linguistics.
Eugene Charniak and Mark Johnson. 2005. Coarseto-fine n-best parsing and maxent discriminative
reranking. In Proceedings of the 43rd Annual Meeting of the Association for Computational Linguistics(ACL’05), pages 173–180.
Wenliang Chen, Daisuke Kawahara, Kiyotaka Uchimoto, Yujie Zhang, and Hitoshi Isahara. 2008. Dependency parsing with short dependency relations in
unlabeled data. In In Proceedings of the 3rd International Joint Conference on Natural Language Processing (IJCNLP-08), pages 88–94.

Conclusion

Colin Cherry and Dekang Lin. 2003. A probability
model to improve word alignment. In Proceedingsof the 41st Annual Meeting of the Association ofComputational Linguistics, pages 88–95.

In this paper, we proposed a linguisticallymotivated nonparametric Bayesian subtree alignment model based on dependency tree structures801

David Chiang. 2005. A hierarchical phrase-basedmodel for statistical machine translation. In Proceedings of the 43rd Annual Meeting of the Association for Computational Linguistics (ACL’05), pages
263–270.

Daniel Marcu and Daniel Wong. 2002. A phrasebased,joint probability model for statistical machinetranslation. In Proceedings of the 2002 Conferenceon Empirical Methods in Natural Language Processing, pages 133–139. Association for Computational Linguistics, July.

David Chiang. 2010. Learning to translate with source
and target syntax. In Proceedings of the 48th Annual
Meeting of the Association for Computational Linguistics, pages 1443–1452, Uppsala, Sweden, July.
Association for Computational Linguistics.

Arul Menezes and Chris Quirk. 2008. Syntactic models for structural word insertion and deletion during translation. In Proceedings of the 2008 Conference on Empirical Methods in Natural Language
Processing, pages 734–743, Honolulu, Hawaii, October. Association for Computational Linguistics.

John DeNero and Dan Klein. 2007. Tailoring wordalignments to syntactic machine translation. In Proceedings of the 45th Annual Meeting of the Association of Computational Linguistics, pages 17–24,
Prague, Czech Republic, June. Association for Computational Linguistics.

Toshiaki Nakazawa and Sadao Kurohashi. 2009. Statistical phrase alignment model using dependency
relation probability. In In Proceedings of the third
Workshop on Syntax and Structure in Statistical
Translation (SSST-3), pages 10–18, Boulder, Colorado, June.

John DeNero, Alexandre Bouchard-Côté, and Dan
Klein. 2008. Sampling alignment structure under a Bayesian translation model. In Proceedingsof the 2008 Conference on Empirical Methods in
Natural Language Processing, pages 314–323, Honolulu, Hawaii, October. Association for Computational Linguistics.

Toshiaki Nakazawa and Sadao Kurohashi. 2010. Fully
syntactic ebmt system of kyoto team in ntcir-8. In
In Proceedings of the 8th NTCIR Workshop Meetingon Evaluation of Information Access Technologies(NTCIR-8), pages 403–410.
Franz Josef Och and Hermann Ney. 2003. A systematic comparison of various statistical alignment
models. Association for Computational Linguistics,
29(1):19–51.

Daisuke Kawahara and Sadao Kurohashi. 2006. A
fully-lexicalized probabilistic model for japanesesyntactic and case structure analysis. In Proceedingsof the Human Language Technology Conference of
the NAACL, Main Conference, pages 176–183, NewYork City, USA, June. Association for Computational Linguistics.

Zhaopeng Tu, Yang Liu, Young-Sook Hwang, Qun
Liu, and Shouxun Lin. 2010. Dependency forest for statistical machine translation. In Proceedings of the 23rd International Conference on Computational Linguistics (Coling 2010), pages 1092–
1100, Beijing, China, August. Coling 2010 Organizing Committee.

Philipp Koehn, Franz J. Och, and Daniel Marcu. 2003.
Statistical phrase-based translation. In HLT-NAACL
2003: Main Proceedings, pages 127–133.

Masao Utiyama and Hitoshi Isahara. 2007. Ajapanese-english patent parallel corpus. In MT summit XI, pages 475–482.

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
Annual Meeting of the Association for Computational Linguistics (ACL), demonstration session.
Canasai Kruengkrai, Kiyotaka Uchimoto, Jun’ichi
Kazama, Yiou Wang, Kentaro Torisawa, and Hitoshi
Isahara. 2009. An error-driven word-character hybrid model for joint chinese word segmentation andpos tagging. In Proceedings of the Joint Conference of the 47th Annual Meeting of the ACL and the
4th International Joint Conference on Natural Language Processing of the AFNLP, pages 513–521,
Suntec, Singapore, August. Association for Computational Linguistics.
Sadao Kurohashi, Toshihisa Nakamura, Yuji Matsumoto, and Makoto Nagao. 1994. Improvements of Japanese morphological analyzer JUMAN.
In Proceedings of The International Workshop on
Sharable Natural Language, pages 22–28.

802