Statistical Phrase Alignment Model
Using Dependency Relation Probability
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
When aligning very different language pairs,
the most important needs are the use of structural information and the capability of generating one-to-many or many-to-many correspondences. In this paper, we propose anovel phrase alignment method which models
word or phrase dependency relations in dependency tree structures of source and target languages. The dependency relation model is akind of tree-based reordering model, and canhandle non-local reorderings which sequential word-based models often cannot handle
properly. The model is also capable of estimating phrase correspondences automaticallywithout any heuristic rules. Experimental results of alignment show that our model could
achieve F-measure 1.7 points higher than theconventional word alignment model with symmetrization algorithms.

1

Introduction

We consider that there are two important needs inaligning parallel sentences written in very different languages such as Japanese and English. One
is to adopt structural or dependency analysis into
the alignment process to overcome the difference inword order. The other is that the method needs tohave the capability of generating phrase correspondences, that is, one-to-many or many-to-many wordcorrespondences. Most existing alignment methods
simply consider a sentence as a sequence of words(Brown et al., 1993), and generate phrase correspondences using heuristic rules (Koehn et al., 2003).
Some studies incorporate structural information into
the alignment process after this simple word align-

ment (Quirk et al., 2005; Cowan et al., 2006). However, this is not sufficient because the basic wordalignment itself is not good.
On the other hand, a few models have been proposed which use structural information from the beginning of the alignment process. Watanabe et al.
(2000) and Menezes and Richardson (2001) proposed a structural alignment methods. These methods use heuristic rules when resolving correspondence ambiguities. Yamada and Knight (2001) and
Gildea (2003) proposed a tree-based probabilisticalignment methods. These methods reorder, insert
or delete sub-trees on one side to reproduce the otherside, but the constraints of using syntactic information is often too rigid. Yamada and Knight flattened the trees by collapsing nodes. Gildea cloned
sub-trees to deal with the problem. Cherry and Lin(2003) proposed a model which uses a source side
dependency tree structure and constructs a discriminative model. However, there is the defect that itsalignment unit is a word, so it can only find oneto-one alignments. Nakazawa and Kurohashi (2008)
also proposed a model focusing on the dependency
relations. Their model has the constraint that content
words can only correspond to content words on theother side, and the same applies for function words.
This sometimes leads to an incorrect alignment. We
have removed this constraint to make more flexible alignments possible. Moreover, in their model,
some function words are brought together, and thus
they cannot handle the situation where each function word corresponds to a different part. The smallest unit of our model is a single word, which shouldsolve this problem.

In this paper, we propose a novel phrase alignment method which models word or phrase dependency relations in dependency tree structures ofsource and target languages. For a pair of correspondences which has a parent-child relation on one side,
the dependency relation on the other side is definedas the relation between the two correspondences.
It is a kind of tree-based reordering model, andcan capture non-local reorderings which sequential
word-based models often cannot handle properly.
The model is also capable of estimating phrase correspondences automatically without heuristic rules.
The model is trained in two steps: Step 1 estimates
word translation probabilities, and Step 2 estimatesphrase translation probabilities and dependency relation probabilities. Both Step 1 and Step 2 are performed iteratively by the EM algorithm. During theStep 2 iterations, word correspondences are growninto phrase correspondences.

2

Proposed Model

We suppose that Japanese is the source language andEnglish is the target language in the description of
our model. Note that the model is not specialized
for this language pair, and it can be applied to any
language pair.
Because our model uses dependency tree structures, both source and target sentences are parsed
beforehand. Japanese sentences are converted into
dependency structures using the morphological analyzer JUMAN (Kurohashi et al., 1994), and the dependency analyzer KNP (Kawahara and Kurohashi,2006). MSTparser (McDonald et al., 2005) is used
to convert English sentences. Figure 1 shows an example of dependency structures. The root of a tree isplaced at the extreme left and words are placed from
top to bottom.
2.1 Overview
This section outlines our proposed model in comparison to the IBM models, which are the conventional
statistical alignment models.
In the IBM models (Brown et al., 1993), the bestalignment â between a given source sentence f andits target sentence e is acquired by the following
equation:â = argmax p(f , a|e)a= argmax p(f |e, a) · p(a|e)
a

(1)

ཷ
(accept)ගA(light)⣲Ꮚ

photogate(device)

䛻

is

(ni)

䛿

used

(ha)

䝣䜷䝖

for

(photo)䝀䞊䝖

the(gate)

䜢photodetector

(wo)

⏝䛔䛯

.

(used)

䚹

Figure 1: An example of a dependency tree and its alignment.

where p(f |e, a) is called lexicon probability andp(a|e) is called alignment probability.
Suppose f consists of n words f1 , f2 , ..., fn , and econsists of m words e1 , e2 , ..., em and a NULL word(e0 ). The alignment mapping a consists of associations j → i = aj from source position j to target
position i = aj . The two probabilities above arebroken down as:
J∏(2)p(f |e, a) =p(fj |eaj )j=1

p(a|e) =I∏

p(∆j|ei )

(3)

i=1

where ∆j is a relative position of words in thesource side which corresponds to ei . Equation 2 isthe product of the word translation probabilities, andEquation 3 is the product of relative position probabilities.
In the proposed model, we refine the IBM models
in three ways. First, as for Equation 2, we consider
phrases instead of words. Second, as for Equation 3,
we consider dependencies of words instead of theirpositions in a sentence.
Finally, the proposed model can find the bestalignment â by not using f -to-e alone, but simultaneously with e-to-f . That is, Equation 1 is modified
as follows:â = argmax p(f |e, a) · p(a|e) ·ap(e|f , a) · p(a|f )(4)

Since our model regards a phrase as a basic unit,
the above formula is calculated in a straightforward
way. In contrast, the IBM models can consider
a many-to-one alignment by combining one-to-one

alignments, but they cannot consider a one-to-manyor many-to-many alignment.
The models are estimated by EM-like algorithm
which is very similar to (Liang et al., 2006). The
important difference is that we are using tree structures.
We maximize the data likelihood:∑max(log pef (f , e; θef ) + log pf e (f , e; θf e ))
θef ,θf e

f ,e

(5)
In the E-step, we compute the posterior distributionof the alignments with the current parameter θ:q(a; f , e) := pef (a|f , e; θef ) · pf e (a|f , e; θf e ) (6)In the M-step, we update the parameter θ:θ0 := argmaxθ∑q(a; f , e) log pef (a, f , e; θef )a,f ,e+∑q(a; f , e) log pf e (a, f , e; θf e )a,f ,e= argmaxθ∑q(a; f , e) log p(e) · pef (a, f |e; θef )a,f ,e+∑q(a; f , e) log p(f ) · pf e (a, e|f ; θf e )a,f ,e(7)Note that p(e) and p(f ) have no effect on maximization, and pef (a, f |e; θef ) and pf e (a, e|f ; θf e )appeared in Equation 1 or Equation 4.
In the following sections, we decompose the lexicon probability and alignment probability.
2.2 Phrase Translation Probability
Suppose f consists of N phrases F1 , F2 , ..., FN , ande consists of M phrases E1 , E2 , ..., EM . The alignment mapping a consists of associations j → i =Aj from source phrase j to target phrase i = Aj .
We consider phrase translation probabilityp(Fj |Ei ) instead of word translation probability.
There is one restriction: that phrases composed ofmore than one word cannot be aligned to NULL.
Only a single word can be aligned to NULL.
We denote a phrase which the word fj belongs to
as Fs(j) , and a phrase which the word ei belongs to
as Et(i) . With these notations, we refine Equation 2
as follows:J∏p(f |e, a) =p(Fs(j) |EAs(j) )(8)
j=1

Suppose phrase Fj and Ei are aligned where thenumber of words in Fj is denoted by |Fj | and that
number in Ei is |Ei |, the probability mass related tothis alignment in Equation 8 is as follows:p(Fj |Ei )|Fj | · p(Ei |Fj )|Ei |(9)

We call this probability for the link between Fj andEi phrase alignment probability. The upper part ofTable 1 shows phrase alignment probabilities for thealignment in Figure 1.
2.3 Dependency Relation Probability
The reordering model in the IBM Models is definedon the relative position between an alignment andits previous alignment, as shown in Equation 3. Ourmodel, on the other hand, considers dependencies ofwords instead of positional relations.
We start with a dependency relation where fc depends on fp in the source sentence. In a possiblealignment, fc belongs to Fs(c) , fp belongs to Fs(p) ,and Fs(c) depends on Fs(p) . In this situation, we consider the relation between EAs(p) and EAs(c) . Even
if two languages have different word order, their dependency structures are similar in many cases, andEAs(c) tends to depend on EAs(p) . Our model takes
this tendency into consideration. In order to denote the relationship between phrases, we introduce
rel(EAs(p) , EAs(c) ). This is defined as the path from
EAs(p) to EAs(c) . It is represented by applying thenotations below:• ’c’ if going down to the child node
• ’p’ if going down to the parent node
For example, in Figure 1, the path from “for” to“photodetector” is ’c’, from “the” to “for” is ’p;p’
because it travels across two nodes. All the phrases
are considered as a single node, so the path from“photogate” to “the” is ’p;c;c;c’ with the alignment
in Figure 1.
We refine Equation 3 using rel as follows:∏p(a|e) =pt (rel(EAs(p) , EAs(c) )|pc)(p,c)∈Ds-pc(10)
where Ds-pc denotes a set of parent-childword pairs in the source sentence.
We callpt (rel(EAs(p) , EAs(c) )|pc) target side dependency
relation probability. pt is a kind of tree-based
reordering model.

Source
受 光 素子にはフォト ゲートを 用いた
NULL

Table 1: A probability calculation example.
TargetPhrase alignment probability
photodetector p(受 光 素子 |photodetector)3 · p(photodetector| 受 光 素子)
forp(に は |for)2 · p(for| に は )photogatep(フォト ゲート |a photogate)2 · p(a photogate| フォト ゲート )2
is usedp(を 用いた |is used)2 · p(is used| を 用いた)2thep(the|NULL)

Source
c

p

受
光
素子
に
は
フォト
ゲート
を

光
素子
に
は
用いた
ゲート
を
用いた

Target dependency
relation probabilitypt (SAME|pc)
pt (SAME|pc)
pt (c|pc)
pt (SAME|pc)
pt (c|pc)
pt (SAME|pc)
pt (c|pc)
pt (SAME|pc)

TargetcAphotogate
used
for
the
photodetector

There are some special cases for rel. When Fs(c)and Fs(p) are the same, that is, fc and fp belong
to the same phrase, rel is represented as ’SAME’.
When fp is aligned to NULL, fc is aligned to NULL,
and both of them are aligned to NULL, rel is represented as ’NULL p’, ’NULL c’, and ’NULL b’, respectively. The lower part of Table 1 shows dependency relation probabilities corresponding to Figure
1.
Actually, we extend the dependency relation
probability to consider a wider relation, i.e, thegrandparent-child∏relation, as follows:p(a|e) =pt (rel(EAs(p) , EAs(c) )|pc) ·(p,c)∈Ds-pc∏

Source dependency
relation probability
ps (SAME|pc)
ps (c|pc)
ps (SAME|pc)
ps (c|pc)
ps (NULL c|pc)
ps (c|pc)

exactly the same way as in IBM Model 1.
In this process, the alignment unit is a word.
When we consider f -to-e alignment, each word on
the source side fj can correspond to a word on thetarget side ei or a NULL word, independently ofother source words. The probability of one possiblealignment a is calculated as follows:J∏
p(a, f |e) =p(fj |eaj )
(12)
j=1

By considering all possible alignments, p(f |e) is
calculated as:∑p(f |e) =p(a, f |e)(13)apt (rel(EAs(g) , EAs(c) )|gc)(g,c)∈Ds-gc(11)
where Ds-gc denotes a set of grandparent-child wordpairs in the source sentence.

3p
photogate
is
is
used
photodetector
forModel Training

Our model is trained in two steps. In Step 1, wordtranslation probability is estimated. Then, in Step 2,
possible phrases are acquired, and both phrase translation probability and dependency relation probability are estimated. In both steps, parameter estimation is done with the EM algorithm.
3.1 Step 1
In Step 1, word translation probability in each direction is estimated independently. This is done in

As initial parameters of p(f |e), we use uniform
probabilities. Then, after calculating Equation 12|e)
and 13, we give the fractional count p(a,fp(f |e) to allword alignments in a, and we estimate p(f |e) by
MLE. We perform this estimation iteratively.
The inverse model e-to-f can be calculated in thesame manner.
3.2 Step 2
Both phrase translation probability and dependency
relation probability are estimated, and one undirected alignment is found using the e-to-f and f -to-eprobabilities simultaneously in this step. In contrast
to Step 1, it is impossible to enumerate all the possible alignments. To find the best alignment, we firstcreate an initial alignment based on phrase translation probability only, and then gradually revise it

by considering the dependency relation probability
with a hill-climbing algorithm.
The initial parameters of Step 2 are calculated
as follows. The dependency relation probability is
calculated using the final alignment result of Step
1, and we use the word translation probability estimated in Step 1 as the initial phrase translation probability.
3.2.1 Initial Alignment
We first create an initial alignment based on thephrase translation probability without considering
the dependency relation probabilities.
For all the combinations of possible phrases(including NULL), phrase alignment probabilities
are calculated (equation 9). Correspondences are
adopted one by one in descending order of geometric mean of the phrase alignment probabilities. All
the words should be aligned only once, that is, thecorrespondences are adopted exclusively. Generation of possible phrases is explained in Section 3.2.3.
3.2.2 Hill-climbing
To find better alignments, the initial alignment isgradually revised with a hill-climbing algorithm. We
use four kinds of revising operations:
Swap: Focusing on any two correspondences, thepartners are swapped. In the first step in
Figure2, the correspondences “光 ↔ photogate” and “フォト ゲート ↔ photodetector” areswapped to “光 ↔ photodetector” and “フォトゲート ↔ photogate”.
Extend: Focusing on one correspondence, thesource or target phrase is extended to include
its neighboring (parent or child) NULL-aligned
word.
Add: A new correspondence is added between asource word and a target word both of which
are aligned to NULL.
Reject: A correspondence is rejected and the source
and target phrase are aligned to NULL.
Figure 2 shows an illustrative example of hill
climbing. The alignment is revised only if the alignment probability gets increased. It is repeated until no operation can improve the alignment probability, and the final state is the best approximate alignment. As a by-product of hill-climbing, pseudo nbest alignment can be acquired. It is used in collecting fractional counts.

3.2.3 Phrase Generation
If there is a word which is aligned to NULL in thebest approximate alignment, a new possible phrase
is generated by merging the word into a neighboring phrase which is not aligned to NULL. In the lastalignment result in Figure 2, for example, “素子”
is treated as being included in the correspondence
between “受 光” and “photodetector” and the correspondence between “に ” and “for”. As a result,
we consider the correspondence between “受 光 素子” and “photodetector” and the correspondence between “素子 に ” and “for” existing in parallel sentences. The new possible phrase is taken into consideration from the next iteration.
3.2.4 Model Estimation
Collecting all the alignment results, we estimate
phrase alignment probabilities and dependency relation probabilities.
One way of estimating parameters of phrasealignment probabilities is using the following equations:C(Fj , Ei )p(Fj |Ei ) = ∑k C(Fk , Ei )C(Fj , Ei )p(Ei |Fj ) = ∑(14)
k C(Ek , Fj )where C(Fj , Ei ) is a frequency of Fj and Ei isaligned.
However, if we use this in our model, the phrasetranslation probability of the new possible phrase
can become extremely high (often it becomes 1).
To avoid this problem, we use the equations below
for the estimation of phrase translation probability
in place of Equation 14:
C(Fj , Ei )C(Fj , Ei ), p(Ei |Fj ) =p(Fj |Ei ) =(15)
C(Ei )
C(Fj )
C(Ei ) is the frequency of the phrase Ei in the training corpus which can be pre-counted. This definition
can resolve the problem where the phrase translation
probability of the new possible phrase becomes too
high.
As for the NULL, we use Equation 14 because wecannot pre-count the frequency of NULL.
Using the estimated phrase alignment probabilities and dependency relation probabilities, we goback to the initial alignment described in Section
3.2.1 iteratively.

Ini al alignment
ཷ
ග
⣲Ꮚ
䛻

(light)Swapphotogate(device)

⣲Ꮚ

is

⏝䛔䛯
䚹

.

䚹

ཷ
ග
䛻

is
䝣䜷䝖

is
used
䝣䜷䝖

photodetector
.

䚹

for

䝀䞊䝖

the

䜢

photogate

䛿

for

䝀䞊䝖

A

⣲Ꮚ

Extendphotogate
used

⏝䛔䛯

photodetector

⏝䛔䛯

.

A

⣲Ꮚ
䛻

the

䜢

photodetector

ཷ
ග

䛿

for

䝀䞊䝖

the

䚹

Add

used
䝣䜷䝖

for

⏝䛔䛯

.

(used)

photogate
is

䛿

used

䜢

photodetector

(wo)

is

䝀䞊䝖

the

(gate)

A

⣲Ꮚ
䛻

䝣䜷䝖

for

(photo)Rejectphotogate

䛿

used

ග

A

䛻

䝣䜷䝖
䝀䞊䝖

䜢

ග

A

(ni)

䛿
(ha)

ཷ

ཷ

(accept)

the

䜢
⏝䛔䛯

photodetector.

䚹Figure 2: An example of hill-climbing.

4

Experimental Results

We conducted alignment experiments. A JST1
Japanese-English paper abstract corpus consistingof 1M parallel sentences was used for the modeltraining. This corpus was constructed from a 2M
Japanese-English paper abstract corpus by NICT2
using the method of Uchiyama and Isahara (2007).
As gold-standard data, we used 475 sentence pairs
which were annotated by hand. The annotations
were only sure (S) alignments (there were no possible (P ) alignments) (Och and Ney, 2003). The unitof evaluation was word-base for both Japanese andEnglish. We used precision, recall, and F-measure
as evaluation criteria.
We conducted two experiments to reveal 1) thecontribution of our proposed model compared to theexisting models, and 2) the effectiveness of using
dependency tree structure and phrases, which arelarger alignment units than words. Trainings wererun on the original forms of words for both the proposed model and the models used for comparison.
4.1 Comparison with Word Sequential Model
For comparison, we used GIZA++ (Och and Ney,
2003) which implements the prominent sequential
word-base statistical alignment model of IBM Models. We conducted word alignment bidirectionallywith its default parameters and merged them using
three types of symmetrization heuristics (Koehn etal., 2003). The results are shown in Table 2.
12

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

The result of ’Step 1’ uses parameters estimatedafter 5 iterations of Step 1. The alignment is obtained by the method of initial alignment shown in
Section 3.2.1. In ’Step 2-1’, the phrase translation
probabilities are the same as those in ’Step 1’. In addition, dependency relation probabilities estimatedfrom the ’Step 1’ alignment result are used. By comparing ’Step 1’ and ’Step 2-1’, we can see the effectiveness of dependency relation probability. We
performed 5 iterations for Step 2 and calculated thealignment accuracy each time. As a result, the proposed model could achieve a higher F-measure by
1.7 points compared to the sequential model. ’Intersection’ achieved best Precision, but its Recall isquite low. ’grow-diag-final-and’ achieved best Recall, but its Precision is lower than our best result
where the Recall is almost same. Thus, we can say
our result is better than sequential word alignment
models.
4.2 Effectiveness of Dependency Trees andPhrases
To confirm the effectiveness of dependency trees andphrases, we conducted alignment experiments on thefollowing four conditions:• Using both dependency trees and phrases (referred to as ’proposed’).
• Using dependency trees only.
• Using phrases only.
• Not using dependency trees or phrases (referred
to as ’none’)For the conditions which do not use dependency
trees, we used positional relations of a sentence asTable 3: Effectiveness of dependency trees and phrases(results after 5 iterations in Step 2.)
Precision Recall
F
proposed
85.54
51.00 63.90
dependency tree only
89.77
39.47 54.83
phrase only
84.41
47.33 60.65
none
85.07
38.06 52.59

5

Discussion

Table 2 shows that our proposed model could
achieve reasonably high accuracy of alignment, andis better than sequential word-base models. As
an example, alignment results of a word sequential model are shown in Figure 3. The gray colored cells are the gold-standard alignments, and theblack boxes are the outputs of the sequential model.
The model failed to resolve the correspondence ambiguities between “非 (not) 去勢 (castrated) マウ
ス (mice)”, and “去勢 マウス”; and “non-castrated
mice”, and “castrated mice” respectively. This isbecause these words are placed close to each otherand are also close to the correspondence “同様に↔ as” which can be a clue to the word order. Using the tree structure in Figure 4, these words werecorrectly aligned. This is because in the English
tree, the phrase “castrated mice” does not depend
on “as”, and “non-castrated mice” does. Similarlyin the Japanese tree, “非 去勢 マウス” depends on “同様に ” and “去勢 マウス” does not.
As mentioned in Section 1, sequential statistical

䕔䕔
䕔
䕔
䕔
䕔䕔
䕔
䕔
䕔
䕔
䕔
䕔
䕔䕔
䕔
䕔
䕔
㠀ཤ䝬 䛸 ྠཤ䝬 䛾⭘䛾ᡂ䛻 ᑐᙉᢚຠ 䜢 ♧
ໃ䜴
ᵝໃ䜴
䜘
㛗
䛧 䛔 ไᯝ
䛧䝇䛻䝇䛖䛯Figure 3: An alignment example of the word sequential
model (grow-diag-final-and).
䞉䞉䞉
exhibitedؒ ‫ؐ؜‬aؒ ‫ؐج‬strongؒ ‫ؐج‬inhibitory‫ؐج‬effect‫ؐج‬onؒ ؒ ‫ؐ؜‬tumorؒ ‫ؐؤ‬growth‫ؐج‬inؒ ؒ ‫ؐ؜‬theؒ ؒ ‫ؐج‬castratedؒ ‫ؐؤ‬mice‫ؐؤ‬as‫ؐؤ‬inؒ ‫ؐ؜‬theؒ ‫ؐج‬non-castrated‫ؐؤ‬mice

䕔䕔
䕔
䕔
䕔
䕔
䕔
䕔
䕔
䕔
䕔
䕔
䕔䕔
࣭࣭࣭

a sequence of words instead of dependency tree relations. The results are shown in Table 3. All the
results are the alignment accuracy after 5 iterationsof Step 2.

䞉䞉䞉exhibitedastronginhibitory
effecton
tumor
growthinthecastrated
mice
as
in
the
non-castrated
mice

࣭࣭࣭

Table 2: Results of alignment experiment.
Precision Recall
F
Step 1
77.55
33.92 47.20
Step 2-1
83.46
40.03 54.11
Step 2-2
87.74
45.37 59.81
Step 2-3
87.62
48.92 62.79
86.87
50.42 63.81
Step 2-4
Step 2-585.90
50.75 63.80
Step 2-6
85.54
51.00 63.90
Step 2-7
85.18
50.87 63.70
Step 2-8
84.66
50.75 63.46
intersection
90.34
34.28 49.71
grow-final-and
81.32
48.85 61.04
79.39
51.15 62.22
grow-diag-final-and䕔ؐؐؐؐ‫♧ؼؐؐؐؼؐؐؐؐؐؐؐؼ‬
ؒ
ؒ
ؒ 䛧
‫ྠ؜‬
‫؜‬ᑐ
‫ ؜‬䜢 䛯ؒᵝؒ 䛧ؒ‫ ؜‬䛸 䛻
‫؜‬䛻
‫ؼ؜‬ຠ
ؒ
ؒ
ؒؒᯝ
‫؜‬䝬
‫؜‬ᡂ
ᙉᢚ
ؒ䜴
ؒ㛗
䛔 ไ
‫؜‬ཤ䝇
‫؜‬䛾
ؒໃ
ؒ
㠀
‫⭘؜‬
ؒ 䜘
‫؜‬䛾 䛖
ؒ
‫؜‬䝬
ؒ䜴
ཤ䝇
ໃ

Figure 4: An alignment example of the proposed model.

methods, which regard a sentence as a sequence ofwords, work well for language pairs that are not too
different in their language structure. Japanese andEnglish have significantly different structures. Oneof the issues is that Japanese sentences have a SOV
word order, but in English, the word order is SVO, so
the dependency relations are often turned over. For
language pairs such as Japanese and English, deeper
sentence analysis using NLP resources is necessary
and useful. Our method is therefore suitable for suchlanguage pairs.
As another example of an alignment failure by
the sequential model, Figure 5 shows the phrase correspondence “受 光 素子 ↔ photodetector”, which
was correctly found as shown in Figure 6. The pro-A
photogate
is
used
for
the
photodetector

䕔䕔
䕔
䕔
䕔
䕔
䕔
ཷග⣲ 䛻䛿 䝣 䝀 䜢 ⏝
Ꮚ
䜷 䞊
䛔
䝖 䝖
䛯

Figure 5: An unsuccessful example of phrase detection in
the sequential model (grow-diag-final-and).
‫ؐ؜‬A䕔䕔‫ؐ؜‬photogate䕔䕔is䕔䕔‫ؐؤ‬used䕔䕔‫ؐؤ‬for䕔䕔ؒ ‫ؐ؜‬the‫ؐؤ‬photodetector 䕔 䕔 䕔‫⏝ؼؐؐ؜‬ؒؒ 䛔‫؜‬䛿‫ ؜‬䜢 䛯
ؒ
ؒ
‫ ؜‬䛻
‫ ؜‬䝀
ؒ
ؒ 䞊
‫؜‬⣲
䝣 䝖
ؒᏊ
䜷
‫؜‬ග
䝖
ؒ
ཷ

Figure 6: An example of phrase detection in the proposedmodel.

posed method of generating possible phrases during
iterations works well and improves alignment.
From the result of our second experiment, we cansee the following points:
1. Phrasal alignment improves the recall, but lowers the precision.
2. By using dependency trees, precision can be
improved.
3. We can find a balance point by using bothphrasal alignment and dependency trees.
The causes of alignment errors in our model canbe summarized into categories. The biggest one isparsing errors. Since our model is highly dependent
on the parsing result, the alignments would easily
turn out wrong if the parsing result was incorrect.
Sometimes the hill-climbing algorithm could notrevise the initial alignment. Most of these cases
would happen when one word occurred several
times on one side, but some of those occurrenceswere omitted on the other side. Let’s suppose there
are two identical words on the source side, but thetarget side has only one corresponding word. Initialalignment is created without considering the dependencies at all, so it cannot judge which source word
should be aligned to the corresponding target word.
In this case, the best alignment searching sometimes
gets the local solution. This problem could be resolved by considering local dependencies for ambiguous words.
One difficulty is how to handle function words.
Function words often do not have exactly corresponding words in the opposite language. Japanesecase markers such as “は (ha)”, “が (ga)” (subjective case), “を (wo)” (objective case) and so on, andEnglish articles are typical examples of words, that
do not have corresponding parts. There is a difference between alignment criteria for function wordsof gold-standard and our outputs, and it is somewhat
difficult to improve alignment accuracy.

6 Conclusion
In this paper, we have proposed a linguisticallymotivated probabilistic phrase alignment model
based on dependency tree structures. The model incorporates the tree-based reordering model. Experimental results show that the word sequential model
does not work well for linguistically different language pairs, and this can be resolved by using syntactic information. We have conducted the experiments only on Japanese-English corpora. To firmly
support our claim that syntactic information is important, it is necessary to do more investigation onother language pairs.
Most frequent alignment errors are derived fromparsing errors. Because our method depends heavily
on structural information, parsing errors easily makethe alignment accuracy worse. Although the parsing
accuracy is high in general for both Japanese andEnglish, it sometimes outputs incorrect dependency
structures because technical or unknown words often appears in scientific papers. This problem could
be resolved by introducing parsing probabilities into
our model using parsing tools which can output nbest parsing with their parsing probabilities. This
will not only improve the alignment accuracy, it willallow revision of the parsing result. Moreover, weneed to investigate the contribution of our alignment
result to the translation quality.

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.
Colin Cherry and Dekang Lin. 2003. A probability
model to improve word alignment. In Proceedings ofthe 41st Annual Meeting of the Association of Computational Linguistics, pages 88–95.
Brooke Cowan, Ivona Kuc̆erová, and Michael Collins.
2006. A discriminative model for tree-to-tree translation. In Proceedings of the 2006 Conference on
EMNLP, pages 232–241, Sydney, Australia, July. Association for Computational Linguistics.
Daniel Gildea. 2003. Loosely tree-based alignment formachine translation. In Proceedings of the 41st Annual Meeting on ACL, pages 80–87.
Daisuke Kawahara and Sadao Kurohashi. 2006. A fullylexicalized probabilistic model for japanese syntactic
and case structure analysis. In Proceedings of the Human Language Technology Conference of the NAACL,
Main Conference, pages 176–183, New York City,
USA, June. Association for Computational Linguistics.
Philipp Koehn, Franz J. Och, and Daniel Marcu. 2003.
Statistical phrase-based translation. In HLT-NAACL
2003: Main Proceedings, pages 127–133.
Sadao Kurohashi, Toshihisa Nakamura, Yuji Matsumoto,and Makoto Nagao. 1994. Improvements of Japanesemorphological analyzer JUMAN. In Proceedings of
The International Workshop on Sharable Natural Language, pages 22–28.
Percy Liang, Ben Taskar, and Dan Klein. 2006. Alignment by agreement. In Proceedings of the Human
Language Technology Conference of the NAACL, Main
Conference, pages 104–111, New York City, USA,
June. Association for Computational Linguistics.
Ryan McDonald, Fernando Pereira, Kiril Ribarov, andJan Hajic. 2005. Non-projective dependency parsing using spanning tree algorithms. In Proceedings of
Human Language Technology Conference and Conference on Empirical Methods in Natural Language Processing, pages 523–530, Vancouver, British Columbia,
Canada, October. Association for Computational Linguistics.
Arul Menezes and Stephen D. Richardson. 2001. A bestfirst alignment algorithm for automatic extraction oftransfer mappings from bilingual corpora. In Proceedings of the 39th Annual Meeting of the Association for
Computational Linguistics (ACL) Workshop on DataDriven Machine Translation, pages 39–46.

Toshiaki Nakazawa and Sadao Kurohashi.
2008.
Linguistically-motivated tree-based probabilisticphrase alignment. In In Proceedings of the Eighth
Conference of the Association for Machine Translationin the Americas (AMTA2008).
Franz Josef Och and Hermann Ney. 2003. A systematiccomparison of various statistical alignment models.
Association for Computational Linguistics, 29(1):19–51.
Chris Quirk, Arul Menezes, and Colin Cherry. 2005. Dependency treelet translation: Syntactically informed
phrasal SMT. In Proceedings of the 43rd Annual
Meeting of the Association for Computational Linguistics (ACL’05), pages 271–279.
Masao Utiyama and Hitoshi Isahara. 2007. A japaneseenglish patent parallel corpus. In MT summit XI, pages
475–482.
Hideo Watanabe, Sadao Kurohashi, and Eiji Aramaki.
2000. Finding structural correspondences from bilingual parsed corpus for corpus-based translation. In
Proceedings of the 18th International Conference on
Computational Linguistics, pages 906–912.
Kenji Yamada and Kevin Knight. 2001. A syntax-based
statistical translation model. In Proceedings of 39th
Annual Meeting of the ACL, pages 523–530.