Alignment by Bilingual Generation and
Monolingual Derivation
Toshiaki N akazawa

Sadao Kur ohashi

Graduate School of Informatics, Kyoto University
Yoshida-honmachi, Sakyo-ku
Kyoto, 606-8501, Japannakazawa@nlp.ist.i.kyoto-u.ac.jp, kuro@i.kyoto-u.ac.jp

ABSTRACTOne of the main issues in a word alignment task is the difficulty of handling function words that
do not have direct translations which we call unique function words. They are often aligned
to some words in the other language incorrectly. This is prominent in language pairs with very
different sentence structures. In this paper, we propose a novel approach for handling uniquefunction words. The proposed model monolingually derives unique function words from bilingually generated treelet pairs. The monolingual derivation prevents incorrect alignments forunique function words. The derivation probabilities are estimated from a large monolingual
corpus, which is much easier to acquire than a parallel corpus. Also, the proposed alignment
model uses semantic-head dependency trees where dependency relations between words become similar in each language. Experimental results on an English-Japanese corpus showthat the proposed model achieves better alignment and translation quality compared with thebaseline models.

TITLE AND ABSTRACT IN JAPANESE

二言語の生成と単言語の派生によるアライメント
単語アライメントタスクにおける主な問題の一つは、機能語の中でも相手言語に対応する語が存在しない機能語の扱いの困難さである。我々はこのような語を孤立機能語と呼ぶ。孤立機能語は、相手言語の何らかの単語に不適切に対応付けられることが多く、これは特に文構造が大きく異なる言語対において顕著である。本論文では、孤立機能語を扱うための新しい手法を提案する。提案モデルは、二言語で生成された部分木ペアから、孤立機能語をそれぞれ単言語で派生することにより、孤立機能語が誤って対応付けられることを防ぐ。派生確率
は、対訳コーパスに比べて入手が容易である大規模単言語コーパスから推定する。また提案
モデルは、単語同士の依存関係が各言語で近くなるように、意味主辞依存構造木を用いる。
英日コーパスでの実験結果から、提案モデルはベースラインモデルと比べてより良いアライ
メントおよび翻訳精度を実現した。

KEYWORDS: monolingual derivation, semantic-head dependency tree, treelet alignment.
KEYWORDS IN JAPANESE: 単言語の派生, 意味主辞依存構造木, 木構造アライメント.

Proceedings of COLING 2012: Technical Papers, pages 1963–1978,
COLING 2012, Mumbai, December 2012.

1963

1

Introduction

Alignment accuracy is crucial for providing high quality corpus-based machine translation systems because translation knowledge is acquired from an aligned training corpus. For similar
language pairs, alignment accuracy is high. Less than 10% alignment error rate (AER) for
French-English has been achieved by the conventional word alignment tool GIZA++, an implementation of the alignment models called the IBM models (Brown et al., 1993), with someheuristic symmetrization rules. However, for distant language pairs such as English-Japanese,the conventional alignment method is quite inadequate (achieving an AER of about 20%).
There are two main issues in a word alignment task for distant language pairs: one is theword order difference, while the other relates to function words. The word order issue
has to some extent been solved by using word dependency trees in the alignment model(Nakazawa and Kurohashi, 2011). Most of the remaining alignment errors are related to function words such as English articles and Japanese case markers (Wu et al., 2011) because they
do not have counterparts in the other language. As an example, most of the errors in Figure 1
are related to function words: “has” and “は (topic-marker)” in example (A), and “although”,“は (topic-marker)”, “を (ACC)” and “が (but)” in example (B).
Several previous works focused on alignment errors of function words. Isozaki et al. (2010)
inserted pseudo nodes in English sentences for Japanese function words. Wu et al. (2011)
removed the alignment of some function words to effectively acquire translation rules using
the underlying word alignment by GIZA++. Nevertheless, these methods for dealing withfunction words are ad-hoc and based on hand-crafted rules.
In this paper, we propose a novel approach for handling function words. If there is a directtranslation for a function word, these words should be aligned with each other. For function
words that do not have any counterparts, the conventional model is supposed to align themto NULL, but it does not always work well. They are often aligned to some words incorrectly.
In contrast with the conventional model, our model derives such function words from content
words in their own language. The derivation probabilities used in our proposed model are
estimated from a large monolingual corpus for each language. Thus, we do not require alarge parallel corpus. With this derivation model, we can reduce alignment errors for function
words, which leads to a better translation resources such as a phrase table, which is acquired
from a word-aligned parallel corpus. In the remainder of this paper, we use English-Japanese
language pairs for explanation. However, it should be noted that the proposed model is completely language independent.

2

Semantic-head dependency tree

The proposed model utilizes word dependency trees on both the source and target
sides. Dependency trees are effective for language pairs with very different word orders,such as English-Japanese, to achieve high quality alignment by absorbing the difference(Nakazawa and Kurohashi, 2011). There are two types of word dependency trees: syntactichead and semantic-head. Our model adopts the latter. This section discusses the difference
between syntactic-head and semantic-head, and the reason why we choose the semantic-headdependency tree.
The syntactic-head dependency tree has two main drawbacks. One is that distances between
content words are excessively large for agglutinative languages such as Japanese. The otheris that dependency relations differ because of the difference in head word definitions in each

1964

!

!
!
!

!

!
!
!

"""!

!"#$%&!'()*!

!"#$%&!'(+*!

Figure 1: Alignment results of Nakazawa and Kurohashi (2011). Black boxes depict the system
output, while dark blue (Sure) and light blue (Possible) cells denote gold-standard alignments.
Cells demarcated by dotted lines are alignment errors related to function words.
language. On the other hand, in semantic-head dependency trees, function words giving additional information to content words are placed as children of the content words, thus itpreserves the dependency relations between words over languages. In the semantic-head dependency tree (on the right of Figure 2), “medical treatment ↔ 治療”, “may ↔ かも しれない”, “not ↔ ない” and “weight ↔ 体重” are all children of “change ↔ 変化”, while therelations are not preserved in the syntactic-head dependency tree (on the left of Figure 2).
Because of these advantages, our model uses semantic-head dependency trees.
In this paper, English sentences are first parsed by nlparser (Charniak and Johnson, 2005)
which outputs phrase structures that are then converted into word dependency trees by defining the head word for phrases. The conversion rules follow Collins’ head percolation table(Collins, 1999) with some modifications for acquiring semantic-head dependency trees. The
following head-specifying rules are examples in which the syntactic head (underlined) and thesemantic head (double underlined) is different.
• VP → MD• VP → VBZ

VB (ex. "may change" in Figure 2)
JJ (ex. "is large")

Japanese sentences are usually parsed based on a unit called a basic phrase, which consistsof one content word followed by zero or more function words. In syntactic-head word dependency trees, on the left of Figure 2, the head word is the last function word (or thecontent word if there is no function word in a basic phrase), and other words depend on
their following words (Hajič et al., 2009). In semantic-head dependency trees, while function words showing a relationship between content words such as case markers are placed asparents of content words, other function words are placed as children. We obtain semantichead dependency trees by modifying the rule file of the Japanese dependency analyzer KNP(Kawahara and Kurohashi, 2006b).

1965

5+%#
'%3.*&4##$%&#'%(##
'&)#

!"!#
/!"#$%&'()*+)0#
$#
01!#
%#
/010#
&'#
()!#

(6##
*+&(,%#*"/,$-.!&/+)00##+%#+,#-%.,+##
-.#
12##
*/#
333"
+,"

5+%#
'%3.*&4##$%&#'%(##
'&)#
(6##
*+&(,%##+%#-%.,+##
12##
333"

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

2"
333"

2"
333"
Figure 2: Examples of syntactic-head (left) and semantic-head (right) dependency trees. The
root of the tree is at the extreme left and words are placed from top to bottom. Japanesecontent words are indicated by “*”.
Several related studies use the semantic-head dependency trees in machine translation(Hong et al., 2009; Xu et al., 2009). They use English-side semantic-head dependency trees
for pre-reordering of English sentences in order to make the word order closer to that of
Subject-Object-Verb language sentences. The closer the word order is, the easier it is to train
the model. However, certain hand-crafted rules are needed for reordering, and pseudo words
are used to take care of function words. Compared with these studies, our proposed model uses
semantic-head dependency trees on both sides and does not reorder sentences, and therefore
it does not require any hand-crafted rules or pseudo words.

3

Handling function words

Although each language has a closed set of function words, the variety of function words differs
between languages. For example, in Figure 2, some function words have direct translations in
the other language (“may ↔ かも しれ ない”, “not ↔ ない” and “but ↔ が”), while others donot (“the”, “は (topic marker)” and “に より (by)”). The first case is less problematic, and anyalignment model can correctly detect the link. The second case represents the issue addressedin this paper. We call function words that do not have direct translations unique function words.
One solution, adopted by almost all the existing alignment models, is to align unique function
words to NULL. However, it is difficult to judge whether a unique function word has to be
NULL-aligned or not, and often causes alignment errors as shown in Figure 1. Also, the NULLaligned words behave as gaps between aligned words, making it harder to capture relations
between aligned words. In Figure 2, “に より (by)” is a gap between “治療 (medical treatment)”
and “変化 し (change)” whereas counterparts have a direct parent-child relation.
Another solution is to enhance the alignment model so as to handle a larger unit than a word,
and include the unique function words in neighboring alignments. For example, “weight ↔
体重” can include the Japanese “は (topic marker)” and become “weight ↔ 体重 は”. However, this solution can lead to a less appropriate parameter estimation for an alignment model
because “weight ↔ 体重” and “weight ↔ 体重 は” are treated as different alignment patterns

1966while the two patterns have essentially no difference.
The novel solution to this problem proposed in this paper is to derive unique function words
from neighboring words monolingually. In the monolingual derivation model, “は (topic
marker)” can be derived from “体重 (weight)” without changing the original treelet pair “weight↔ 体重”, and therefore the model achieves good estimation of parameters. Note that it is also
possible to derive “は (topic marker)” from “変化 し (change)” because they are contiguousin the tree structure. Another advantage of the monolingual derivation model is that it can
reduce the gaps between alignments, and preserve the dependency relations between treelets
over languages. For example, the model can derive “に より (by)” from “変化 し (change)” or “治療 (medical treatment)” and let the dependency relation between “変化 し (change)” and “治療 (medical treatment)” be direct parent-child like their English counterparts. This is effective
for estimating the dependency relation probability described in Section 4.3.

4Model overview

The proposed model is an extension of that proposed by Nakazawa and Kurohashi (2011). This
earlier model was overcoming the long-distance reordering issue by incorporating dependency
trees. However, it was suffering from alignment errors for function words, which our newmodel solves by incorporating a monolingual derivation model. First we describe the generative
story for the joint alignment model in the same manner as in previous work (Marcu and Wong,
2002; DeNero et al., 2008; Nakazawa and Kurohashi, 2011).
1. Generate ℓ concepts from which bilingual treelet pairs are generated independently.
2. For each treelet pair, derive zero or more treelets monolingually from each treelet in thetreelet pair.
3. Combine the treelets in each language so as to create parallel sentences.
The number of concepts ℓ (> 0) is parameterized using a geometric distribution
P(ℓ) = p$ · (1 − p$ )ℓ−1(1)where p$ is a constant. Each concept generates a bilingual treelet pair from an unknown
distribution θ T . We call the treelet pair the core alignment denoting it as 〈eC , f C 〉. Either oneof the treelets in a treelet pair can be NULL, which represents an unaligned treelet. Unaligned
treelets must be composed of exactly one word (NULL-alignment restriction).
Each treelet eC and f C derives sets of treelets {deC } and {d fC } monolingually which basicallyconsist of unique function words. The numbers of monolingual derivations |{deC }| and |{d fC }|(≥ 0) are parameterized using a geometric distribution
P(|{deC }|) = pd · (1 − pd )|{deC }| ,P(|{d fC }|) = pd · (1 − pd )|{d fC }|(2)

where pd is a constant. Each derivation is drawn from a known multinomial distribution ϕeC
and ϕ fC , as explained in Section 4.2. We use the notation e to represent the combination of eCand {deC }, and f for f C and {d fC }. Thus 〈e, f 〉 contains 〈eC , f C 〉, {deC } and {d fC }.

Finally, the treelet pairs are combined in each language. We denote the relation of treelets on
the e-side as D E = {( j → k)}, where ( j → k) denotes that treelet e j depends on treelet ek ,and on the f -side as D F . D refers to D E and D F as a whole. With these notations, the joint

1967

6/$#
#$%&'()#*+$(*#$,*#
#(-#
,.*#
'/(,0$#*/$#
1$&0/*"
9:*#
777"

2!/01$&0/*3"!"12"4"5-#%./*/*/$234"5!"/$2#
2!/0#$%&'()"*+$(*#$,*3"%&124"
5"#$%&'()*+#'*"#,*/6/$2#
2!/0'/(,0$3"*+12"4"
5*+/'3()234"5*+/,2#
2!/0,.*3"-45612#
2!/0#(-3"483,93-.12#!"!#$#7*23%&)"'+4#+8#
%&!#
'#
7018#
()#
*+!"
,#7(%./*)5#+08#
-.#
48#
,9#
-."

:"
777"

2!/09:*3":12#

Figure 3: Example showing the calculation of the bilingual generation probability and monolingual derivation probability.

probability for an aligned sentence pair is defined as:P(ℓ, {〈e, f 〉}, D) = P(ℓ)·P(D|{〈e, f 〉})·



∏
∏
∏

θ
(〈e
,
f
〉)
·
P(|{d
}|)
·
ϕ
(d
)
·
P(|{d
}|)
·
ϕ
(d
)
 T C C
eC
eC
eC
fC
f
fC  .
deC〈e, f 〉d fC

(3)

In Figure 3, we show an example of the calculation of bilingual generation probability andmonolingual derivation probability for each treelet pair (ignoring P(|{deC }|) and P(|{d f C }|) forease of understanding). For the core alignment 〈not, ない 〉, there is no derivation, and only
bilingual generation probability θ T (〈not, なかった 〉) is used. For 〈change, 変化 〉, there are
two derivations from “変化 (change)”; “に より (by)” and “し (light verb)”. Therefore, we needto calculate two monolingual derivation probabilities in addition to the bilingual generation
probability.
The remainder of this section gives the details of the bilingual generation probability θ T , monolingual derivation probability ϕ and dependency relation probability P(D).

4.1 Bilingual generation probability
When generating bilingual treelets, we first need to decide whether to generate an unaligned
treelet (with probability pN ) or an aligned treelet pair (with probability 1− pN ). Aligned treelet
pairs are generated from an unknown probability distribution θA, which obeys the Dirichlet
process (DP):θA(〈eC , f C 〉)

∼

1968

DP(MA, αA),(4)where MA is the base distribution and αA is a concentration parameter. The base distribution
is defined as:
1

MA(〈eC , f C 〉) = [Pe (eC )PW A( f C |eC ) · P f ( f C )PWA(eC | f C )] 2
 1 |eC | 1 | f C |Pe (eC ) = p t · (1 − p t )|e|−1 ·P f ( f C ) = p t · (1 − p t )| f |−1 ·
,
ne
nf

(5)

where PWA is the translation probability computed by IBM model1 (Brown et al., 1993), andne and n f are the numbers of word types in each language. θA does not give a weight to an
unaligned treelet.
Unaligned treelets are generated from another unknown probability distribution θN :
θN (〈eC , f C 〉)MN (〈eC , f C 〉)∼=DP(MN , αN )¨
PWA(eC |NULL)
PWA( f C |NULL)

if f C = NULL.
if eC = NULL

(6)

θN does not give a weight to an aligned treelet pair. Note that an unaligned treelet is always
composed of only one word in our model. Finally, θ T can be decomposed as:θ T (〈eC , f C 〉) = pN θN (〈eC , f C 〉) + (1 − pN )θA(〈eC , f C 〉).

(7)

The earlier study (Nakazawa and Kurohashi, 2011) only considered treelets as alignment
units. However, this is inadequate for semantic-head dependency trees, since a set of sibling function words is often considered as an alignment unit. In Figure 2, for example, sibling“かも しれ ない (may)” in Japanese should be aligned to the English “may”. Therefore, ourmodel allows siblings to be a core alignment unit when the siblings are contiguous in the word
sequence. We suppose the term “treelet” includes siblings in this paper.

4.2 Monolingual derivation probability
We only explain the e-side derivations in this section, since the f -side is the same. We calculate
the monolingual derivation probability using a large monolingual corpus. Derivations deC are
conditioned on the treelet eC from which they were derived:ϕe (deC ) = p(deC |eC ).

(8)

For example, ϕmed ical t r eat ment (the) = p(the|medical treatment). However, using a treelet asa condition is vulnerable to the data sparseness problem. We use an anchor word in eC as
the condition instead of eC . The derivation is connected to the anchor word in the word
dependency tree:p(deC |eC ) ≈ p(deC |A(eC , deC )).
(9)
The function A(eC , deC ) returns the anchor word in eC for deC .
A(medical treatment, the) is “treatment”.

For example,p(deC |A(eC , deC )) are calculated as follows:

C ount(deC , A(eC , deC )).
p(deC |A(eC , deC )) = ∑d C ount(d, A(eC , deC ))

1969

(10)

Anchor Derivations
theP:treatment, P:treatment change
medical P:treatment, P:treatment change
treatment L:the, L:medical, P:changemay
P:changenotP:changechange L:treatment, L:the treatment, L:medical
treatment, L:the medical treatment, L:may,
L:not, R:weight, R: the weightthe
P:weight, P: change weightweightP:change, L: theAnchor Derivations
体重P:は, P:は 変化
はL:体重, P:変化
治療
P:に, P:に より, P:に より 変化にL:治療, P:より, P:より 変化
より
L:に, L:治療 に, P:変化
L:は, L:体重 は, L:より, L:に変化
より, L:治療 に より, R:し, R:
ない, R:かも, R:しれ, R:ない
し
P:変化
ない
P:変化

Table 1: The English derivations (left) and Japanese derivations (right) acquired from thesentences in Figure 3. ’P’, ’L’ and ’R’ denote, respectively, Parent, pre-child (dependent fromthe Left), and post-child (dependent from the Right).
C ount(deC , A(eC , deC )) denotes the frequency with which deC is connected to A(eC , deC ) in themonolingual corpus. Taking each sentence in Figure 3 as an example sentence in the monolingual corpus, we can enumerate the derivations shown in Table 1 from the sentences. A
derivation must be contiguous as a tree, and we do not consider sibling derivations. We distinguish three types of derivations: parent, pre-child (dependent from the left) and post-child(dependent from the right).
This lexicalized derivation is excessively specific. For example, the highest probability derivations from “Ph.D.” acquired from the English Web corpus (Kawahara and Kurohashi, 2006a)are “a”, “student”, “thesis” in order. Consequently, using only lexicalized derivation can cause
many derivation errors. We consider not only the lexicalized derivation probability, but also
another probability using part-of-speech (POS) is used as the condition. Using the notation
A pos (eC , deC ) for the POS of the anchor word, the monolingual derivation probability is defined
as:
1
(11)
p(deC |eC ) = [p(deC |A(eC , deC )) · p(deC |A pos (eC , deC ))] 2 .

p(deC |A pos (eC , deC )) is also acquired from the large monolingual corpus in the same manner asp(deC |A(eC , deC )). We take the geometric mean of the two probabilities because this eliminates
noisy derivations of lexicalized probabilities while keeping the derivation preferences for each
word.
Note that we do not need to discriminate between content words and function words in theenumeration of derivations and the calculation of derivation probabilities. Generally, theneighboring words of function words are content words. The vocabulary size of content words
is much larger than that of function words. Therefore, the number of derivation patterns fromfunction words is quite large, causing their probabilities to be very small. The probabilities naturally prefer deriving function words from content words than deriving content words fromfunction words.

4.3 Dependency Relation Probability
Our model considers dependency relations between treelets and assigns a weight to each relation following the previous work (Nakazawa and Kurohashi, 2011). Here, each treelet includes both core and derivation treelets, and treelets in a treelet pair have the same index, forexample, the counterpart of e j is f j .

1970

The dependency relations are considered on each e and f side in the same manner, thus
we only explain the e-side. First, we find the nearest aligned parent treelet, which we callrelational parent, for each treelet in e-side. The relational parent is searched by ascending thedependency tree to the root node until an aligned treelet is found. The number of unaligned
treelets on the path to relational parent from e j is denoted as N (e j ). N (e j ) = 0 if the relational
parent is the direct parent of e j . We consider an imaginary root as the relational parent for theroot treelet of a sentence.
Suppose the relational parent treelet of e j is ek . Then, we consider where their counterparts,
f j and f k respectively, are on the dependency tree of the other side. We can assume that f j
tends to depend on f k because the dependencies between concepts hold across languages. The
dependency relation probability reflects this tendency. We define the function r el(e j , ek ) which
returns a dependency relation between the counterparts of the two arguments, in other words,
dependency relation between f j and f k . We express a dependency relation as the shortest pathfrom f j to f k . For simplicity, we indicate the path 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). For example, in Figure 3, traveling from “medical treatment” to “weight”
requires 1 step going up (to reach “change”) and 1 step going down, so the dependency relationis (U p, Down) = (1, 1).
Finally, we assign the dependency relation probability to a triplet of non-negative integers
R f = (N , U p, Down). The dependency relation probabilities for the e-side are drawn from an
unknown probability distribution θe f and for the f -side from θ f e , with both obeying the DP:
θe f (R e )θ f e (R f )∼∼DP(Me f , αe f )DP(M f e , α f e )Me f (R e )M f e (R f )==pe f · (1 − pe f )N +U p+Down−1
p f e · (1 − p f e )N +U p+Down−1 .

(12)Using the notations and definitions above, the dependency tree-based reordering modelP(D|{〈e, f 〉}) is decomposed as:∏
P(D|{〈e, f 〉}) =θe f (R e ) · θ f e (R f ).
(13)〈e, f 〉

5

Model training

We train the model by means of a collapsed Gibbs sampling, which has been used in somerecent NLP works (Nakazawa and Kurohashi, 2011; DeNero et al., 2008). In a Gibbs sampling,
we first need to initialize the states of the training data, such as the boundaries between treelets
and their alignments, and also initialize the latent variables according to the initial states of thedata. Starting with the initial state, we generate many samples sequentially from the last stateby changing a small local point. Normalizing the counts in the samples yields the parameter
estimations.

5.1 Initialization
We initialize the states of the training data by heuristically merging bi-directional alignment
results of the standard word alignment tool GIZA++. Many machine translation studies use
heuristics to combine the two alignment results, one of which is called grow-diag-final-and(Koehn et al., 2007). Our heuristic is similar to this, but the difference is that we combine
the two results based on dependency trees, and not on word sequences. The initialization iscarried out by the following steps:

1971

3,"!0&24"

!!
!"

!!
!"

!!
!"

!!
!"

$%&'()"$%&'(*"+2&!$5,21"

!!
!"

!!
!"

!"##"

!"##"

./'&!0"+,--#."

!"##"
!"##"

!"##"

1.2-."

Figure 4: Illustration of the sampling operators. A solid circle represents a single word, whilea treelet is depicted surrounded by a broken line. A gray treelet represents a derivation. A
link directly connected to a word denotes that the treelet must consist of exactly one word,
whereas other treelets can consist of one or more words including derivations.
1. Take the intersection of the two results.
2. In the union of the two results, accept alignment points connected to at least one accepted point in terms of the dependency tree (corresponds to grow-diag).
3. In the union of the two results, accept alignment points between two unaligned words(corresponds to final-and).
Initial boundaries of treelets and their alignments, and also the counts of treelet pairs anddependency relations are thus acquired. Note that there is no derivations after the initialization
step.

5.2 Sampling operators
Our sampler repeatedly uses the six operators illustrated in Figure 4, to generate samples.
Each application of an operator generates one new sample. We could, of course, use all thegenerated samples. However, since successive samples are almost the same, except for one
local part, it is futile keeping all the samples. Thus, for each iteration, 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.
SWAP
The SWAP operator exchanges the counterparts of two treelets, which may have derivations.
There are two cases: [SWAP-1] both treelets are aligned, and [SWAP-2] one of the two treelets
is unaligned and the other consists of exactly one word.
TOGGLEThe TOGGLE operator adds or removes an alignment. If f j and ek are both unaligned treelets,
TOGGLE links the two treelets. Alternatively, if f j and e j are aligned, TOGGLE cuts the link1972

and makes each of the treelets unaligned. Because of the NULL-alignment restriction, f j ande j must consist of exactly one word.
MERGE
The MERGE operator combines a one-to-one alignment with the neighboring alignment asderivations from each treelet, or separates derivations from each treelet as an independentalignment.
BOUNDARY
The BOUNDARY operator moves the boundary between two treelets by one word. This operator does not change the type (core or derivation) of the boundary word.
TRANSFORM
The TRANSFORM operator changes the type of a word from core to derivation or vice versa.
EXPANDThe EXPAND operator expands or contracts an aligned treelet. If an unaligned treelet is next
to an aligned one, EXPAND merges the unaligned and aligned treelets, either as a part of coretreelet or derivation treelet. As the opposite direction, it excludes a marginal node from atreelet, and to make the excluded node unaligned.

6

Alignment experiments

We conducted alignment experiments on the English-Japanese corpus to show the effectivenessof the proposed model.

6.1 Settings
For the experiments, we used the JST1 paper abstract corpus. This corpus was created by NICT2 from JST’s 2M English-Japanese paper abstract corpus using the method of
Utiyama and Isahara (2007). This corpus consists of 996K parallel sentences: 24.7M words in
English and 27.5M words in Japanese. Unfortunately, this corpus is not publicly available now,
but they will become available in the near future.
As gold-standard data, 500 sentence pairs were annotated by hand using two types of annotations: sure (S) alignments and possible (P) alignments (Och and Ney, 2003). The unitof evaluation was the word. 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 our model used in the experiments are as follows: p$ = 0.1, pd = 0.9, pN = 0.1,
p t = 0.8, αA = 100, αN = 100, α f e = 100, αe f = 100, p f e = 0.5, pe f = 0.5. They are borrowed
from the previous work (DeNero et al., 2008; Nakazawa and Kurohashi, 2011) and changed
a little. The training time was about 1 day using 200 CPU cores. It is much slower than
the word-sequence-based models because considering tree structures is computationally more
complex.
The derivation probabilities were calculated from English and Japanese Web corpora eachconsisting of 550M sentences (Kawahara and Kurohashi, 2006a). We limited the maximum
size of a derivation treelet to three words. We only consider top-20 frequent derivations foreach word and POS.
1
2

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

1973English sentences were converted into phrase structures using Charniak’s nlparser(Charniak and Johnson, 2005), and then they were transformed into dependency structuresby rules defining head words for phrases (Collins, 1999). Japanese sentences were converted
into dependency structures using the morphological analyzer JUMAN (Kurohashi et al., 1994)
and the dependency analyzer KNP (Kawahara and Kurohashi, 2006b).
For comparison, we used GIZA++ (Och and Ney, 2003), which implements the well-known
word-based statistical alignment model of the IBM Models. We conducted word alignment
bidirectionally with the default parameters and merged them using the grow-diag-final-andheuristics (Koehn et al., 2003). We also tested the BerkeleyAligner3 (DeNero and Klein, 2007)
in the unsupervised training mode with default settings.

6.2 Experimental result and discussion
The experimental results are given in Table 2. “Syntactic-head” is the alignment accuracy of thebaseline system by Nakazawa and Kurohashi (2011), while “Semantic-head w/o derivation”
is the result of using the baseline model on semantic-head dependency trees. The results ofincorporating the monolingual derivation are given in the bottom two rows, where “all” meansthat we evaluated all the alignments including derivations, while “core” means that we only
evaluated the core alignments.
As mentioned in Section 1, the baseline model has already shown much better alignment
accuracy than the conventional models, GIZA++ and BerkeleyAligner. There was a slight
improvement using semantic-head dependency trees (0.36% absolute AER reduction).
The proposed model further improved the alignment accuracy. Compared with the baselinemodel, we achieved 0.6% and 1.34% improvement in absolute AER by evaluating all the alignments and only the core alignments respectively. The relative error reduction in AER is about
10% for the core alignment, which can be considered as a significant improvement. The reasonof the further AER decrease when using only the core alignments is as follows: although themonolingual derivation can prevent from incorrect alignments for unique function words, it
sometimes causes over derivations. This is discussed in detail later.
Figure 5 shows the alignment results by the proposed model for sentences in Figure 1. The
proposed model reduced the alignment errors for unique function words by deriving themmonolingually, and found correct alignments which the baseline system failed to find.
There are two main causes of alignment errors in the proposed model. One is the granularityof the derivation probability. We used the product of the two probabilities, lexicalized andPOS-based, to take advantage of them, but this is insufficient. For example, in the sentence
fragment “the possibility that ...”, the proposed model failed to derive the unique word “that”
from “possibility”. In another fragment “the patient who ...”, the proposed model failed toderive “who” from “patient”. The reason for these failures is the low probability in the POSbased derivation. The possible solution for the granularity problem is to use word classes
where each word class contains the words which have similar derivation distribution. For
example, some abstract nouns such as “possibility” and “fact” tend to derive appositive “that”,
and person-category nouns tend to derive a relative “who”.
The other cause of alignment errors is the over derivation typically created by the noise ina parallel sentence and parsing error. On the left of Figure 6, the fragment of the Japanese3

http://code.google.com/p/berkeleyaligner/

1974

Alignment model
GIZA++ & grow-diag-final-and
BerkeleyAligner
Syntactic-head (baseline)
Semantic-head w/o derivation
Semantic-head w/ derivation (all)Semantic-head w/ derivation (core)

Pre.
83.00
85.69
88.59
88.82
87.83
90.51

Rec.
83.01
74.13
83.78
84.28
85.81
84.49

AER
16.99
20.32
13.66
13.30
13.06
12.32

Table 2: Results of English-Japanese alignment experiments.

"

!
!
!

"

!
!
!

!!!"

Figure 5: Alignment results by the proposed model. The solid and open squares depict corealignments and derivations, respectively.
sentence “音 列 の (of tone sequence)” has no corresponding part in the English sentence. “音列 (tone sequence)” is correctly aligned to NULL, but the function word “の (of)” is incorrectly
derived from “法 (method)”. On the right of Figure 6, the Japanese “HDMI は” should notdepend on “異なる (different)”, but on “使用 (use)”. Because of this parsing error, the topic
marker “は” is incorrectly derived from “異なる (different)”. One possible short-term solution
for the parsing problem is to use the n-best parsing results in the model. An alternative solution
was proposed by Burkett et al. (2010), who described a joint parsing and alignment model thatexchanges useful information between the parser and aligner.

7

Translation experiments

We conducted English-to-Japanese and Japanese-to-English translation experiments on thesame corpus used in the alignment experiments. We translated 500 paper abstract sentencesfrom the JST corpus. Note that these sentences were not included in the training corpus. We
use Joshua4 , a Java-based opensource implementation of the hierarchical decoder, version 4.0(Ganitkevitch et al., 2012) with default settings. It was tuned using another 500 development
sentence pairs.
Table 3 shows the BLEU (Papineni et al., 2002) scores for the translations. The proposed4

http://joshua-decoder.org

1975

!

!
!
!

"""!

Figure 6: Alignment errors of the proposed model caused by a NULL part (left) and a parsing
error (right).
Alignment model
En → Ja Ja → En
GIZA++ & grow-diag-final-and
23.84
17.75
Syntactic-head (baseline)
24.16
17.83
Semantic-head w/o derivation
24.11
18.06
Semantic-head w/ derivation (all)24.55†
18.46†‡
24.45
17.76
Semantic-head w/ derivation (core)
Table 3: BLEU scores for English-to-Japanese and Japanese-to-English translation experiments.
† and ‡ marks indicate significant difference by bootstrap resampling (Koehn, 2004) from thedecoder using GIZA++ & grow-diag-final-and alignment and baseline alignment respectively(p < 0.05).
model using all the alignments including derivations achieved the best translation quality. We
believe this improvement is due to the reduction in function word alignment errors. The BLEU
score decreased when only core alignments were used. This is because the exclusion of thederivations increased the ambiguity of the translation rules.

Conclusion and future work
In this paper, we proposed a novel approach for handling unique function words based on
semantic-head dependency trees. The proposed model monolingually derives unique function
words from bilingually generated treelet pairs. The derivation probabilities are acquired froma large monolingual corpus for each language. We showed that semantic-head dependency
trees are more effective than syntactic-head dependency trees for high quality alignment, andthat the treelet derivation model can reduce alignment errors for function words resulting in
better translation quality.
To further validate the effectiveness of the proposed model, we need to apply our model toother language pairs, including the Korean language, which is also an agglutinative language.
In addition, we need to resolve the issues discussed in Section 6.2.

Acknowledgments
This work was partially supported by Yahoo Japan Corporation.

1976

References
Brown, P. F., Pietra, S. A. D., Pietra, V. J. D., and Mercer, R. L. (1993). The mathematics of statistical machine translation: Parameter estimation. Association for Computational Linguistics,
19(2):263–312.
Burkett, D., Blitzer, J., and Klein, D. (2010). Joint parsing and alignment with weakly synchronized grammars. In Human Language Technologies: The 2010 Annual Conference of theNorth American Chapter of the Association for Computational Linguistics, pages 127–135, Los
Angeles, California. Association for Computational Linguistics.
Charniak, E. and Johnson, M. (2005). Coarse-to-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.
Collins, M. (1999). Head-Driven Statistical Models for Natural Language Parsing. PhD thesis,
University of Pennsylvania.
DeNero, J., Bouchard-Côté, A., and Klein, D. (2008). Sampling alignment structure undera Bayesian translation model. In Proceedings of the 2008 Conference on Empirical Methods
in Natural Language Processing, pages 314–323, Honolulu, Hawaii. Association for Computational Linguistics.
DeNero, J. and Klein, D. (2007). Tailoring word alignments to syntactic machine translation.
In Proceedings of the 45th Annual Meeting of the Association of Computational Linguistics, pages
17–24, Prague, Czech Republic. Association for Computational Linguistics.
Ganitkevitch, J., Cao, Y., Weese, J., Post, M., and Callison-Burch, C. (2012). Joshua 4.0:
Packing, pro, and paraphrases. In Proceedings of the Seventh Workshop on Statistical MachineTranslation, pages 283–291, Montréal, Canada. Association for Computational Linguistics.
Hajič, J., Ciaramita, M., Johansson, R., Kawahara, D., Martı́, M. A., Màrquez, L., Meyers, A.,
Nivre, J., Padó, S., Štěpánek, J., Straňák, P., Surdeanu, M., Xue, N., and Zhang, Y. (2009).
The conll-2009 shared task: Syntactic and semantic dependencies in multiple languages. In
Proceedings of the Thirteenth Conference on Computational Natural Language Learning (CoNLL
2009): Shared Task, pages 1–18, Boulder, Colorado. Association for Computational Linguistics.
Hong, G., Lee, S.-W., and Rim, H.-C. (2009). Bridging morpho-syntactic gap between source
and target sentences for english-korean statistical machine translation. In Proceedings of the
ACL-IJCNLP 2009 Conference Short Papers, pages 233–236, Suntec, Singapore. Association for
Computational Linguistics.
Isozaki, H., Sudoh, K., Tsukada, H., and Duh, K. (2010). Head finalization: A simple reordering rule for sov languages. In Proceedings of the Joint Fifth Workshop on Statistical MachineTranslation and MetricsMATR, pages 244–251, Uppsala, Sweden. Association for Computational Linguistics.
Kawahara, D. and Kurohashi, S. (2006a). Case frame compilation from the web using highperformance computing. In the 5th International Conference on Language Resources and Evaluation (LREC2006).

1977

Kawahara, D. and Kurohashi, S. (2006b). A fully-lexicalized probabilistic model for japanesesyntactic and case structure analysis. In Proceedings of the Human Language Technology Conference of the NAACL, Main Conference, pages 176–183, New York City, USA. Association for
Computational Linguistics.
Koehn, P. (2004). Statistical significance tests for machine translation evaluation. In Lin, D.
and Wu, D., editors, Proceedings of EMNLP 2004, pages 388–395, Barcelona, Spain. Association for Computational Linguistics.
Koehn, P., Hoang, H., Birch, A., Callison-Burch, C., Federico, M., Bertoldi, N., Cowan, B.,
Shen, W., Moran, C., Zens, R., Dyer, C., Bojar, O., Constantin, A., and Herbst, E. (2007).
Moses: Open source toolkit for statistical machine translation. In Annual Meeting of the
Association for Computational Linguistics (ACL), demonstration session.
Koehn, P., Och, F. J., and Marcu, D. (2003). Statistical phrase-based translation. In HLT-NAACL
2003: Main Proceedings, pages 127–133.
Kurohashi, S., Nakamura, T., Matsumoto, Y., and Nagao, M. (1994). Improvements ofJapanese morphological analyzer JUMAN. In Proceedings of The International Workshop on
Sharable Natural Language, pages 22–28.
Marcu, D. and Wong, D. (2002). A phrase-based,joint probability model for statistical machine translation. In Proceedings of the 2002 Conference on Empirical Methods in Natural
Language Processing, pages 133–139. Association for Computational Linguistics.
Nakazawa, T. and Kurohashi, S. (2011). Bayesian subtree alignment model based on dependency trees. In Proceedings of the 5th International Joint Conference on Natural Language
Processing (IJCNLP2011), pages 794–802, Chiang Mai, Thailand. Asian Federation of Natural
Language Processing.
Och, F. J. and Ney, H. (2003). A systematic comparison of various statistical alignment models. Association for Computational Linguistics, 29(1):19–51.
Papineni, K., Roukos, S., Ward, T., and Zhu, W.-J. (2002). Bleu: a method for automatic
evaluation of machine translation. In ACL, pages 311–318.
Utiyama, M. and Isahara, H. (2007). A japanese-english patent parallel corpus. In MT summit
XI, pages 475–482.
Wu, X., Matsuzaki, T., and Tsujii, J. (2011). Effective use of function words for rule generalization in forest-based translation. In Proceedings of the 49th Annual Meeting of the Association
for Computational Linguistics: Human Language Technologies, pages 22–31, Portland, Oregon,
USA. Association for Computational Linguistics.
Xu, P., Kang, J., Ringgaard, M., and Och, F. (2009). Using a dependency parser to improve
smt for subject-object-verb languages. In Proceedings of Human Language Technologies: The
2009 Annual Conference of the North American Chapter of the Association for Computational
Linguistics, pages 245–253, Boulder, Colorado. Association for Computational Linguistics.

1978