輪講発表資料

平成 18 年 4 月 14 日

統計的枠組みを統合した木構造アラインメント
A Probabilistic Framework for Structure-based Alignment
黒橋研究室

Abstract
In this paper, we propose a new method for alignment
using correspondence pattern score (CP-score). Thismethod is a hybrid one combining structural preference,
which is a characteristic of EBMT, and statistical formalism, which is a characteristic of SMT. We conduct experiments on travel domain corpus, and achieve an F-measure
improvement of 2.6% over a baseline system.

1

Introduction
In machine translation tasks, how to align the training

parallel corpus with high accuracy is a big problem, andthus a number of studies have been done. The alignment
methods can be categorized into two groups: one is probabilistic methods and the other is heuristic methods withstructural information.

電子情報学専攻 56430 中澤 敏明

morphological analyzer and a syntactic analyzer, to grasp
characteristics of language pairs with large difference inlinguistic structure.
[9] proposed a kind of tree structure called “LogicalForm”, which is an unordered graph representing the relations among the most meaningful elements of a sentence.
With this structure they proposed a “best-first” alignment
method. This method starts from the nodes with the tightest lexical correspondence and then goes to close nodes
from the first nodes. [5] used parsed tree structure of theoriginal sentence, and then aligned the trees with someheuristic rules which constrain the order of alignment.
Although these structure-based methods utilize profound knowledge of NLP and achieve high accuracy, themanner of alignment is still heuristic, which is often not

Probabilistic methods are mainly used in Statisticalgeneral-purpose. To resolve this issue, [4] proposed aprobabilistic tree-based alignment between Korean andEnglish. They use some cloning operations to calculate

Machine Translation (SMT) systems [11]. The main
issue is how to decompose the alignment probabilities

the probability, so they make the structure more complicated. Moreover, it is not apparent that the same opera-

P r(A|S, T) reasonably to make good use of some approximations, where A represents an alignment, S represents a source sentence, and T represents a target sen-tions are effective and fit for different language pairs.

tence.

the SMT’s statistical alignment and EBMT’s deep useof structural preference by decomposing the alignment

The simplest statistical method is based on word levelalignment, in which the IBM Model [2] is mostly used as
the baseline method. Recently, more sophisticated methods have been proposed by [12] and [13], which handle
not only a word but a larger block which is usually a multiple word or a phrase. However, even if these methods
are oriented to use larger block or structure, data sparseness problem is still a big problem on its way. For thisreason, it is not easy to achieve high performance for the
language pair whose linguistic structures are quite different from each other.

In this paper, we introduce a probabilistic frameworkfor structure-based alignment. This is an integration ofprobability P r(A|S, T).
For one of the decompositions, we propose correspondence pattern score (CP-score), which can evaluate therelations between all the pair of correspondences. We
define correspondence pattern (CP) as the positional relationship between correspondences, and CP-score as theprobability of each CP. Experimental results prove thatalignment performance is improved with this new criterion.

On the other hand, heuristic structural methods are

In the following section, we briefly introduce the basic
structure-based alignment module in our machine trans-

usually used in Example Based Machine Translation(EBMT) systems. They use heuristic rules in alignment

lation system. In Section 3, the CP-score as a decomposition of the alignment probability is defined, and the dis-

procedure, and can easily use NLP resources, such as aambiguation method of correspondences using CP-score

is introduced. Moreover, in Section 4, we propose how
to use the CP-score in a more precise way by the modification of English dependency structure. In addition,
we further decompose the alignment probability into several feature functions and integrate them by means of the
maximum entropy method. We performed some experiments to evaluate our proposal, and it is reported in Section 5. At last, we give a short conclusion and introduce
our future work.

2

Basic Structure-based Alignment
MethodIn this section, we briefly introduce our alignment

module of a machine translation system. This alignment
module is used as a baseline method in the experiments,and from the alignment results, we calculate the CP-scorestated in Section 3.2.
Our machine translation system works mainly forJapanese-English, and the alignment is achieved by thefollowing steps, using a Japanese parser, an English
parser, and a bilingual dictionary.
1. Dependency analysis of Japanese and English sentences.
2. Detection of word/phrase correspondences.
3. Disambiguation of correspondences.
4. Handling of remaining words.

2.2

Detection of Word/Phrase Correspondences

Correspondences between Japanese word/phrase andEnglish word/phrase are detected by a Japanese-English
dictionary.
At this moment, the dictionary is not probabilistic. By
looking up the whole pair of Japanese words and English
words in the dictionary, correspondences are detected deterministically.
In addition to the dictionary, we also handle transliteration. For possible person names and place names
suggested by the morphological analyzer and Katakana
words (Katakana is a Japanese alphabet usually used forloan words), their possible transliterations are produced
and their similarity with words in the English sentence iscalculated based on the edit distance. If there are similar
word pairs whose edit distance exceeds a threshold, they
are handled as a correspondence.

2.3 Disambiguation of Correspondences
There are sometimes two types of correspondence ambiguities. One is that there are the same words in thesentence, the other is that one word has some different
meanings.
We resolve these ambiguities with some harmonious
criteria. Suppose there is a correspondence X with ambiguity, and there is an unambiguous correspondence Y
with the distance n in the Japanese dependency tree andthe distance m in the English dependency tree, we givea score 1/n + 1/m to the correspondence X. Here we

2.1

Dependency Analysis of Japanese andEnglish Sentences

Japanese sentences are converted into dependency
structures using the morphological analyzer, JUMAN [7],and the dependency analyzer, KNP [6]. Japanese depen-

define the distance of correspondences as the number oftraversing nodes in a dependency tree.
Then, we hold a assumption that the closer Y is to X,
the more strongly Y supports X. Consequently, we accept
the ambiguous correspondence with the highest score andreject the others conflicting with the accepted one. Thisdency structure consists of nodes which correspond with
content words. Function words such as postpositions, af-

calculation is repeated until all the ambiguous correspondences are resolved.

fixes, and auxiliary verbs are included in content words’
nodes.

Figure 1 is an example of correspondence disambigua-

For English sentences, Charniak’s nlparser is used toconvert them into phrase structures [3], and then they aretransformed into dependency structures by rules defining
head words for phrases. In the same way as Japanese,each node in this dependency tree consists of a content
word and related function words.

tion. The root of a tree is placed at the extreme left andphrases are placed from top to bottom, and the correspondences of circled words were detected by a bilingual dictionary.
There is only one determined correspondence “日本(Japan) ↔ Japan” in the example. Considering this correspondence as a clue, the scores are calculated, and the

ᣣᧄ 䈪

you

଻㒾

will haveળ␠ 䈮

to fileኻ䈚䈩੤Ꮕinsurance଻㒾⺧᳞䈱insurance↳䈚┙䈩 䈏

with the office
1/2 + 1/1

came

⓭ὼ

an claimน⢻䈪䈜 䉋

the car

ὐ䈪䇮

at me

䈅䈱

from the sideゞ䈏㘧䈶಴䈚䈩 ᧪䈢 䈱䈪䈜 䇯at the intersectionin JapanFigure 2: Example of extend.

Figure 1: Example of disambiguation.

correspondence “申し 立て (allegation) ↔ file” with thehighest score is adopted. At the same time, the conflicting correspondence “申し 立て (allegation) ↔ claim” isrejected. After that, the correspondence “請求 (claim) ↔
claim” is unambiguous so that it is adopted.
This strategy is effective but heuristic, and what isworse, sometimes the same scores are given to ambiguous correspondences. In this case, the ambiguities cannot
be resolved.

2.4

Handling of Remaining Words

3

Statistical Structure-based Alignment

Our previous alignment module uses some heuristic
rules so that it cannot handle all the ambiguous correspondences. To solve this problem, we introduce a probabilistic framework which combines the statistical information from the whole parallel corpus into our previousalignment module. To do this, it is necessary to decompose the alignment probability P r(A|S, T) in a reasonable way. For one of the decomposed components, we
propose correspondence pattern score (CP-score).

The alignment procedure so far found some correspondences in parallel sentences. Then, we merge the remaining nodes into existing correspondences.

3.1 Correspondence Pattern (CP)CP is defined as a positional pattern of a pair of corre-First, the root nodes of the dependency trees are handled as follows. In the given training data, we suppose

spondences based on the tree structure. Figure 3 is an abstract example of dependency tree structure. Circles rep-that all parallel sentences have appropriate translation relation. Accordingly, if neither of the root nodes (of theJapanese dependency tree and the English dependency

resent nodes (they are actually phrases) and the numbers
represent the correspondences: same numbered nodes arecorrespondent with each other, and blank nodes have notree) is included in any correspondences, the new correspondence between the two root nodes is generated. If

correspondence (means aligned to NULL).
3either root node is remaining, it is merged into the correspondence of the other root node.
Then, for both Japanese remaining node and English
remaining node, if it is within a base NP and another nodein the NP is in a correspondence, it is merged into the correspondence. At last, other remaining nodes are merged
into correspondences of their parent (or ancestor) nodes.
For example in Figure 2, “あの (that)” is merged into
the correspondence “車 (car) ↔ the car”, since it is within

3
1
2
2
1
SourceTargetFigure 3: Example of dependency tree structure.
The nodes connected by broken lines represent corre-an NP. “突然 (suddenly)”, “at me” and “from the side” aremerged into their parent correspondence, “飛び出して来spondences between source and target language (Figure3). CP is defined as a relation between two correspon-

たのです (rush out) ↔ came”.

dences. In Figure 3, there are three correspondences (1,2 and 3), and so there are three combinations of correspondences (1-2, 1-3 and 2-3) as shown in Figure 4. CP

CPs extracted from Figure 5. The CP for the first example is (0, 2, 1, 2) and for the second is (0, 2, 2, 1). Note

will be extracted from each combinations in the following
steps.

that the two CPs are different from each other and thescore is also different even though the tree structures are
the same. This difference can be held by the constraint of

3

3

3

3

numeral order for target language.

1

1

2

2

2

2

X

1

1

Combination of 1-2

Y

Combination of 1-3
3

3

X

1

Y

2

CP = (0, 2, 1, 2)
2
1

Combination of 2-3

YY

Figure 4: Combinations of correspondences.

X

As for the source language tree structure, there are twokinds of relation between aligned nodes: lineal relationand collateral relation (Figure 5). In Figure 5, X andY nodes are the focused aligned nodes and the gradated
nodes are the common parent node from each aligned
node.

X
Y

(0, 2)
linealFigure 6: Examples of CP.

3.2

Calculation of CP-score

We assign a score to each CP, which is calculated bycounting the frequency of each CP from the aligned par-

X
Y

X

X
CP = (0, 2, 2, 1)

Y(1, 2)(1, 1)
collateralallel corpus by the method introduced in the previous section, and then divide them by the total frequency of allCPs.
We calculate the CP-score by the aligned parallel corpus which is made by our original alignment module.

Figure 5: Two types of relation.
All the relations are distinguished by the distance: forlineal relations, we use distance between two nodes, andfor collateral relations, we use two distances to the common parent node. For example, the relations in Figure 5
can be represented with two numerals: (0, 2) for the first,(1, 2) for the second, and (1, 1) for the last. The numerals
are written in ascending order because what is importantis the pair of numerals, and we treat (0, 2) and (2, 0) as
the same relation.
It is the same for the target language, but there is one
thing that we have to care, which is that the order of numerals for target language should correspond to that ofsource language. Then, CP is represented as a combination of the two relations of focused correspondences between source and target language, which means that CPs
are distinguished by four numerals. Figure 6 shows some

The corpus is a travel domain corpus (BTEC) used fora training data set in IWSLT20051 , which contains 20k
Japanese-English parallel sentences2 .

3.3

Alignment Disambiguation with CPscore

Ambiguous correspondences can be resolved with CPscore. In case there is one or more ambiguous correspondences, we generate all the possible alignment candidates. And then, the alignment score for each of thepossible alignments is calculated by means of CP-score.
Finally, we adopt the best alignment which gets the highest score.
We define the alignment score (AS) as the product of
1 http://www.is.cs.cmu.edu/iwslt2005/
2 It is worth trying to calculate the CP-score in an unsupervised way
like the EM algorithm. According to our preliminary experiment, it is
not very effective to use iterative estimation for CP-score.

2

2
Amb1

?
1

?
1

?
Amb2

2

2

(1, 2, 1, 1)

2

2(1, 2, 2, 1)(0, 2, 0, 1)(0, 1, 0, 1)

3(0, 2, 0, 1)

3
1

1

3
1

1

(0, 1, 0, 2)

3

Figure 7: Example of disambiguation.
CP-scores between all pairs of correspondences:
AS =

M
−1
Y

M
Y

CP -scorei,jon the Japanese dependency trees, and try to modify only
(1)i=1 j=i+1

where M is the number of correspondences in the sentence pair.
Figure 7 is an example of disambiguation. There are
two ambiguous correspondences, and from that, two possible alignments are generated. At last, we adopt thealignment with higher AS.

4

Consideration and Optimizationof Dependency Structure Possibilities

4.1

Modification of Dependency Structure

Automatic syntactic analysis inevitably contains someerrors, such as word segmentation errors and parsing errors. These errors may decrease the accuracy of structurebased alignment.
As for English, parsing is particularly difficult, because of the following characteristics: one word can havevarious parts-of-speech and meanings, and there is PPattachment ambiguity. These problems cause parse errors, and sometimes make the alignment accuracy worse.

the English dependency trees in this paper. This is performed by applying n-best dependency structures to ouralignment module. After the alignment of each dependency structure, the AS can be calculated as a productof all the CP-scores as given in Equation (1). Then, wechoose the alignment with the highest AS, and the best
dependency structure is acquired simultaneously.

4.2

Combination of Various Scores Using
Maximum Entropy Method

Although we consider only AS so far, the score of eachEnglish structure is also useful. The problem arising hereis that we do not know how to combine the CP-score andthe structure score. Taking this problem into consideration, parameters that weigh the various scores appropriately are necessary. To find the parameters, we employ
the maximum entropy (ME) method [1].
Alignment methods with ME are reported in [10] and[8]. Following these methods, we define alignment probability P r(A|S, T) as follows:
P r(A|S, T) =
exp

£ PM

¤

m=1 λm hm (A, S, T)
£ PM
¤
P
0
A0 expm=1 λm hm (A , S, T)

On the other hand, the head of a Japanese sentence iswhere hm (A, S, T) are feature functions, and λm aremodel parameters.

always put at the end of the sentence. Therefore, it iseasier to parse Japanese sentences and to get correct de-

In addition to the AS and the parse score, we introduce
some other feature functions which are thought to be ef-

pendency trees. Consequently, we give great confidence

fective.

AS: The AS of the sentence.

Y

English parse score: The Charniak’s parse score output itself.
Depth pattern score (DP-score): The score of the pattern of depth from head node of the sentence. Depth
pattern (DP) is represented with four numerals, and DP-

Y
X

Y
X

X

of the word alignment tool GIZA++ by [11]. In case ofmultiple word correspondences in one phrase correspondence, the one which has the largest probability is chosen as a representation. We use both source-to-target andtarget-to-source alignment probabilities independently.
Coverage of the correspondences:

The ratio ofaligned nodes compared to the total number of nodes.
This is calculated in both source and target sentence independently.
Average size of the correspondences: Our alignment
method can handle not only one-to-one node alignment
but one-to-many or many-to-many nodes alignment. Furthermore, variations of dependency structure occasionally merge some phrases into one phrase. For these reasons, the average size of the correspondence can affectthe alignment. This is calculated in both source and target sentence independently.
Training data set for ME is automatically generated
from the Charniak’s n-best output. Moreover, if there
are some ambiguous correspondences, we can also generate alignment candidates in the way shown in section
3.3. All of them are compared to the gold-standard alignment, which is created in Section 5, then, the one best
candidate based on F-measure is marked correct and theothers marked incorrect.

5

Experimental Results and Discussion

5.1

Experiments and Results

We selected 500 moderately long sentences from the
BTEC corpus of IWSLT2005 training data set and manually annotated phrase-to-phrase alignment to them. ThisY
(0, 2, 1, 1)(0, 1, 0, 1)
Frequent CP

X

score is calculated in the same way of CP-score.
Probability of the lexicon: The product of all the
probabilities of the lexicon which is included in each correspondence. For lexical probability, we use the output

XYX(0, 1, 2, 2)
Infrequent CPY

Figure 8: Examples of frequent and infrequent CP.
• Merge function words into content words.
• Remove all punctuation marks.
• Omitted subjects or objects are merged into headverb phrase.
We conducted 5-fold cross validation, in which 400
sentences are used for ME training and 100 sentences fortesting. CP-score and DP-score are calculated from thebase alignment results of the IWSLT2005 training corpus. Figure 8 shows examples of frequent and infrequentCPs, and we can see that CPs whose relation of source
language is similar to that of target language occur more
frequently.
The evaluation results are shown in Table 1. “Baseline”
is the heuristic method introduced in Section 2. “CPscore” is the disambiguation of correspondence with CPscore introduced in section 3. “ES Modification”, which
is an abbreviation of English Structure Modification, utilizes n-best parse results. “ME” is the integration methodof nine feature functions by ME. For “ES Modification”
and “ME”, we use 3-best Charniak’s parse results.
There are three evaluations. The first one is the result of whole 500 sentences and evaluated with all thefunction words. “CP-score” performed better than the“Baseline”. “ES Modification” was a little worse than“CP-score” and only the result of “ME” is the statistically significant compared to that of the baseline method(p < 0.05).
The second evaluation was done also on 500 sentences,
but all the function words are eliminated for the appro-

is because our alignment module is based on tree structure composed of phrases. A part of the criteria for anno-

priate comparison with the statistical alignment method,
GIZA++. Function words make the alignment accu-

tation are listed below:racy of GIZA++ worse because GIZA++ is a word-based

Table 1: Evaluation results.
MethodAll sentences
w/ function words

All sentences
w/o function words

Ambiguous sentences
w/ function words

Baseline

63.86

65.14

60.43

+ CP-score+ ES Modification
+ ME

64.21
64.20
64.58

65.54
65.47
66.03

61.60
61.61
63.00

GIZA

22.14

52.85

23.76

rious alignment errors.
Table 2: Effect of the number of parse candidates.
ES ModificationME

3-best

64.20

64.58

5-best10-best

63.99
63.94

64.47
64.38

alignment tool and our gold-standard data is based onphrases.
GIZA++ was trained using whole 20k sentences of
IWSLT2005 training corpus, in which function words areleft, and all the words are lowercased and converted tobase forms. The alignment was performed in one direction (Japanese to English). Because we have an advantage of using the dictionary, we can see that our method
achieved much higher accuracy.
In the third evaluation, we selected 142 sentences outof 500, which have ambiguous correspondences, and all
the function words are included. From this evaluation, we
can see the improvement measurably: 1.2% improvementfor “CP-score”, and 2.6% for “ME” over the “Baseline”.
The improvements of all of our methods are statisticallysignificant (p < 0.05).

5.2

Discussion

We discuss the following five points derived form theexperimental results.
Disambiguation with CP-score: If two correspondences are in the same clause of the source sentence, they

ES Modification: The accuracy of “ES Modification”
was worse than that of “CP-score”. This is because we do
not care the Charniak’s parse scores, and CP-score sometimes tends to choose incorrect parse results. However,this problem was solved by the ME integration. Table 2
shows the effect of the number of parse candidates, which
are the Charniak’s n-best. As the number of candidates
increases, the accuracy falls off, but the degree of the decrease of “ME” is smaller than that of “ES Modification”.
Sentence complexity: One of the reasons of small improvement of the results comes from the complexity ofthe sentences. Our proposed method works effectively
for long and complex sentences in particular. The BTEC
corpus’ sentences are short, and come from spoken language, and so it is difficult to find correspondences using
a dictionary. We will test our method in other corpus suchas newspaper and patent in the future.
Preciseness of dictionary: The dictionary we used is
not precise nor concise. If there is an erroneous correspondence by the dictionary, it makes bad effects onalignment. On the other hand, if the number of entries
is small, it becomes hard to align accurately. Preparing aprecise and concise dictionary is also our future work.
Parse error of Japanese: Not only English parse results but Japanese parse results are sometimes wrong, andthis leads to alignment errors. The Japanese dependency
analyzer KNP can produce n-best parse results, and so in
the future, we will consider parse results of both Japaneseand English.

are mostly in the same clause of the target sentence. We
do not distinguish a main clause and a subordinate clauseon the tree structure now. Therefore, even if there is an

6

ambiguous correspondence which crosses the clause, we
do not impose any penalties. We need to resolve thisWe have proposed a probabilistic framework to improve structure-based alignment. As one of the decom-

problem because disambiguation errors cause further se-

positions of alignment probability P r(A|S, T), we pro-Conclusionposed new criteria CP-score for evaluating alignment.
With the CP-score we succeed to utilized probabilities for[6] Sadao Kurohashi and Makoto Nagao. A syntactic
analysis method of long Japanese sentences based

structure-based alignment and achieved higher alignment
accuracy.

on the detection of conjunctive structures. Computational Linguistics, 20(4):507–534, 1994.

We also integrated the ME model into our alignment
approach. We utilized nine feature functions, which made[7] Sadao Kurohashi, Toshihisa Nakamura, Yuji Mat-

it possible to modify the dependency tree structure andlead to much higher alignment accuracy.
What we need to do in the future is to sophisticate the
CP and CP-score, one way is to consider the clause, andto select the feature functions to improve our ME model,
and moreover, we will test our method on other corpora
which consist of long sentences.

Publications• IJCNLP 2005
• IWSLT 2005

• COLING-ACL 2006 (Under audition)

References[1] Adam Berger, Stephen Della Pietra, and Vincent Della Pietra. A maximum entropy approachsumoto, and Makoto Nagao. Improvements ofJapanese morphological analyzer JUMAN. In
Proceedings of The International Workshop on
Sharable Natural Language, pages 22–28, 1994.
[8] Yang Liu, Qun Liu, and Shouxun Lin. Log-linear
models for word alignment. In Proceedings of the
43rd Annual Meeting of the Association for Computational Linguistics, pages 459–466, 2005.
[9] Arul Menezes and Stephen D. Richardson. 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 Data-Driven Machine Translation, pages 39–46,
2001.

to natural language processing. Computational Linguistics, 22(1):39–71, 1996.

[10] Franz Josef Och and Hermann Ney. Discriminative training and maximum entropy models for sta-

[2] Peter F. Brown, Stephen A. Della Pietra, Vincent
J. Della Pietra, and Robert L. Mercer. The mathe-tistical machine translation. In Proceedings of the40th Annual Meeting of the Association for Computational Linguistics, pages 295–302, 2002.

matics of statistical machine translation: Parameter
estimation. Association for Computational Linguistics, 19(2):263–312, 1993.

[11] Franz Josef Och and Hermann Ney. A systematiccomparison of various statistical alignment mod-[3] Eugene Charniak and Mark Johnson. Coarse-to-fineels. Association for Computational Linguistics,
29(1):19–51, 2003.

n-best parsing and maxent discriminative reranking. In Proceedings of the 43rd Annual Meetingof the Association for Computational Linguistics(ACL’05), pages 173–180, Ann Arbor, Michigan,
June 2005.
[4] Daniel Gildea. Loosely tree-based alignment formachine translation. In Proceedings of the 41st
Annual Meeting on Association for Computational
Linguistics, pages 80–87, 2003.
[5] Declan Groves, Mary Hearne, and Andy Way. Robust sub-sentential alignment of phrase-structure
trees. In Proceedings of the 20th International Conference on Computational Linguistics, pages 1072–
1078, 2004.

[12] Taro Watanabe, Kenji Imamura, and Eiichiro
Sumita. Statistical machine translation based on hierarchical phrase alignment. In 9th International
Conference on Theoretical and Methodological Issues in Machine Translation, pages 188–197, 2002.
[13] Ying Zhang and Stephan Vogel.

An efficientphrase-to-phrase alignment model for arbitrarily
long phrase and long corpora. In European Association for Machine Translation 2005 Conference
Proceedings, pages 294–301, 2005.