Effective Phrase Translation Extraction from Alignment Models
Ashish Venugopal
Language Technologies Institute
Carnegie Mellon University
Pittsburgh, PA 15213
ashishv@cs.cmu.edu
Stephan Vogel
Language Technologies Institute
Carnegie Mellon University
Pittsburgh, PA 15213
vogel+@cs.cmu.edu
Alex Waibel
Language Technologies Institute
Carnegie Mellon University
Pittsburgh, PA 15213
ahw@cs.cmu.edu
Abstract
Phrase level translation models are ef-
fective in improving translation qual-
ity by addressing the problem of local
re-ordering across language boundaries.
Methods that attempt to fundamentally
modify the traditional IBM translation
model to incorporate phrases typically do
so at a prohibitive computational cost. We
present a technique that begins with im-
proved IBM models to create phrase level
knowledge sources that effectively repre-
sent local as well as global phrasal con-
text. Our method is robust to noisy align-
ments at both the sentence and corpus
level, delivering high quality phrase level
translation pairs that contribute to signif-
icant improvements in translation quality
(as measured by the BLEU metric) over
word based lexica as well as a competing
alignment based method.
1 Introduction
Statistical Machine Translation defines the task
of translating a source language sentence a0a2a1a4a3
a1a6a5a8a7a9a7a9a7a10a1a12a11a12a13 into a target language sentence a0a15a14a16a3
a14a5 a7a9a7a9a7a17a14a19a18a20a13 . The traditional framework presented in
(Brown et al., 1993) assumes a generative process
where the source sentence is passed through a noisy
stochastic process to produce the target sentence.
The task can be formally stated as finding the a21a14
s.t a21a14 = a22a24a23a26a25a28a27a29a22a24a30a32a31 a0a15a14a9a33a1a34a13 where the search compo-
nent is commonly referred to as the decoding step
(Wang and Waibel, 1998). Within the generative
model, the Bayes reformulation is used to estimate
a31
a0a15a14a35a33a1a26a13a37a36
a31
a0a15a14a19a13
a31
a0a2a1a38a33a14a39a13 where
a31
a0a15a14a39a13 is considered the lan-
guage model, and a31 a0a2a1a38a33a14a19a13 is the translation model;
the IBM (Brown et al., 1993) models being the de
facto standard. Direct translation approaches (Fos-
ter, 2000) consider estimating a31 a0a15a14a9a33a1a34a13 directly, and
work by (Och and Ney, 2002) show that similar
or improved results are achieved by replacinga31 a0a2a1a20a33a14a39a13
in the optimization witha31 a0a15a14a35a33a1a26a13 , at the cost of devi-
ating from the Bayesian framework. Regardless of
the approach, the question of accurately estimating
a model of translation from a large parallel or com-
parable corpus is one of the defining components
within statistical machine translation.
Re-ordering effects across languages have been
modeled in several ways, including word-based
(Brown et al., 1993), template-based (Och et al.,
1999) and syntax-based (Yamada, Knight, 2001).
Analyzing these models from a generative mind-
set, they all assume that the atomic unit of lexi-
cal content is the word, and re-ordering effects are
applied above that level. (Marcu, Wong, 2002) il-
lustrate the effects of assuming that lexical corre-
spondence can only be modeled at the word level,
and motivate a joint probability model that explic-
itly generates phrase level lexical content across
both languages. (Wu, 1995) presents a bracketing
method that models re-ordering at the sentence level.
Both (Marcu, Wong, 2002; Wu, 1995) model the re-
ordering phenomenon effectively, but at significant
computational expense, and tend to be difficult to
scale to long sentences. Reasons to introduce phrase
level translation knowledge sources have been ade-
quately shown and confirmed by (Och, Ney, 2000),
and we focus on methods to build these sources from
existing, mature components within the translation
process.
This paper presents a method of phrase extraction
from alignment data generated by IBM Models. By
working directly from alignment data with appro-
priate measures taken to extract accurate translation
pairs, we try to avoid the computational complex-
ity that can result from methods that try to create
globally consistent alignment model phrase segmen-
tations.
We first describe the information available within
alignment data, and go on to describe a method
for extracting high quality phrase translation pairs
from such data. We then discuss the implications of
adding phrasal translation pairs to the decoding pro-
cess, and present evaluation results that show sig-
nificant improvements when applying the described
extraction technique. We end with a discussion of
strengths and weaknesses of this method and the po-
tential for future work.
2 Motivation
Alignment models associate words and their transla-
tions at the sentence level creating a translation lexi-
con across the language pair. For each sentence pair,
the model also presents the maximally likely associ-
ation between each source and target word across the
sentence pair, forming an alignment map for each
sentence pair in the training corpus. The most likely
alignment pattern between a source and target sen-
tence under the trained alignment model will be re-
ferred to as the maximum approximation, which un-
der HMM alignment (Vogel et al., 1996) model cor-
responds to the Viterbi path. A set of words in the
source sentence associated with a set of words in
the target sentence is considered a phrasal pair and
forms a partition within the alignment map. Fig-
ure a40 . shows a source and target sentence pair with
points indicating alignment points.
A phrasal translation pair within a sentence
pair can be represented as the 4-tuple hypothesis
a41a43a42 a0a15a44a39a45a39a46a15a47a35a45a49a48a6a45a39a46a51a50a52a13 representing an index a0a15a44a39a45a49a48a24a13 and length
a0a53a46a54a47a35a45a39a46a51a50a55a13 within the source and the target sentence pair
a31 , respectively. The phrasal extraction task involves
selecting phrasal hypotheses based on the alignment
Figure 1: Sample source a56a58a57 and target a59a8a57 aligment
map. Partitions/Potential translations for source
phrase s2s3 are shown by rounded boxes.
model (both the translation lexicon as well as the
maximal approximation). The maximal approxima-
tion captures context at the sentence level, while
the lexicon provides a corpus level translation esti-
mate, motivating the alignment model as a starting
point for phrasal extraction. The extraction tech-
nique must be able to handle alignments that are
only partially correct, as well as cases where the sen-
tence pairs have been incorrectly matched as parallel
translations within the corpus. Accommodating for
the noisy corpus is an increasingly important com-
ponent of the translation process, especially when
considering languages where no manually aligned
parallel corpus is available.
Building a phrasal lexicon involves Generation,
Scoring, and Pruning steps, corresponding to gen-
erating a set of candidate translation pairs, scoring
them based on the translation model, and pruning
them to account for noise within the data as well as
the extraction process.
3 Generation
The generation step refers to the process of identify-
ing source phrases that require translations and then
extracting translations from the alignment model
data. We begin by identifying all source language n-
grams upto somea60 within the training corpus. When
the test sentences that require translation are known,
we can simply extract those n-grams that appear in
the test sentences. For each of these n-grams, we
create a set of candidate translations extracted from
the corpus. The primary motivation to restrict the
identification step to the test sentence n-grams is
savings in computational expense, and the result is
a phrasal translation source that extracts translation
pairs limited to the test sentences. For each source
language n-gram within the pool, we have to find a
set of candidate translations. The generation task is
formally defined as finding a21a41a62a61 in Equation (1)
a21
a41 a61 a1a6a63a64a14a58a65 a41a43a42 a0a15a44a39a45a39a46a54a47a12a45a49a48a66a45a39a46a67a50a68a13a70a69
a21
a41 a45
a31a71a57
a7a9a7a9a7
a31 a57a51a72a8a73a75a74
a3
a25 (1)
where a25 is the source n-gram for which we are ex-
tracting translations, a21a41 is the set of all partitions,
anda31a76a57 refers to the word at position a44 in the source
sentence a31 . a21a41 a61 is then the set of all translations
for source n-gram a25 , and a77 is a specific translation
hypothesis within this set. When considering only
those hypothesis translation extracted from a partic-
ular sentence paira31 , we use a21a41 a61 a0a31 a13 .
We extract these candidates from the alignment
map by examining each sentence pair where the
source n-gram occurs, and extracting all possible tar-
get phrase translations using a sliding window ap-
proach. We extract candidate translations of phrase
length a40 to a78 , starting at offseta79 toa78a81a80a82a40 . Figure 1.
shows circular boxes indicating each potential parti-
tion region. One particular partition is indicated by
the shading.
Over all occurrences of the n-gram within the sen-
tences as well as across sentences, a sizeable can-
didate pool is generated that attempts the cover the
translated usage of the source n-gram a25 within the
corpus. This set is large, and contains several spuri-
ous translations, and does not consider other source
side n-grams within each sentence. The deliberate
choice to avoid creating a consistent partitioning of
the sentence pairs across n-grams reflects the abil-
ity to model partially correct alignments within sen-
tences. This sliding window can be restricted to ex-
clude word-word translations, ie a46a54a47a84a83a3 a40 , a46a51a50a85a83a3 a40 if
other sources are available that are known to be more
accurate. Now that the candidate pool has been gen-
erated, it needs to be scored and pruned to reflect rel-
ative confidence between candidate translations and
to remove spurious translations due to the sliding
window approach.
4 Scoring
The candidate translations for the source n-gram
now need to be scored and ranked according to some
measure of confidence. Each candidate translation
pair defines a partition within the sentence map,
and this partitioning can be scored for confidence
in translation quality. We estimate translation con-
fidence by measures from three models; the estima-
tion from the maximum approximation (alignment
map), estimation from the word based translation
lexicon, and language specific measures. Each of
the scoring methods discussed below contributes to
the final score under (2)
a86 a44
a60a87a22
a46
a56a89a88a91a90a26a23a6a92
a0
a77
a69
a21
a41 a61a13a93a3a95a94
a57
a0
a56a89a88a91a90a96a23a6a92a35a57
a0
a77
a69
a21
a41 a61a13a19a13a55a97a71a98
(2)
where a99
a57a101a100
a57 = a40 and a77 refers to a translation hy-
pothesis for a given source n-grama25 . From now on
we will refer to aa56a89a88a91a90a26a23a6a92 with regard to a particulara25
implicitly.
4.1 Alignment Map
We define two kinds of scores, within sentence con-
sistency and across sentence consistency from the
alignment map, in order to represent local and global
context effects.
4.2 Within Sentence
The partition defined by each candidate translation
pair imposes constraints over the maximum approx-
imation hypothesis for sentences in which it occurs.
We evaluate the partition by examining its consis-
tency with the maximum approximation hypothe-
sis by considering the alignment hypothesis points
within the sentence. An alignment point a102 a42 a0a30 a45a19a103a104a13
(source, target) is said to be consistent if it occurs
within the partition defined by a41 a42 a0a15a44a39a45a39a46a47a45a49a48a6a45a39a46a50a13 . a102a106a105a34a107a108
is considered inconsistent in two cases.
a44a84a109
a30
a109a16a44a58a110a111a46a54a47 anda0a76a103a113a112a70a48 ora103a115a114a70a48a116a110a111a46a51a50a49a13 (3)
a48a117a109a16a103a113a109a118a48a119a110a32a46a67a50 and a0
a30
a112a120a44 or
a30
a114a111a44a58a110a32a46a15a47a17a13 (4)
Each a41a43a42 a0a15a44a39a45a39a46a54a47a12a45a49a48a66a45a39a46a67a50a52a13 in a21a41 a61 a0a31 a13 ( a44a115a7a9a7a9a7a121a44 +a46a15a47 defines
a25 ) determines a set of consistent and inconsistent
points. Figure 1. shows inconsistent points with re-
spect to the shaded partition by drawing an X over
the alignment point. The within sentence consis-
tency scoring metric is defined in Equation (5).
a56a89a88a91a90a26a23a6a92
a97
a47a12a0a41a43a42 a0a15a44a39a45a39a46a15a47a35a45a49a48a6a45a39a46a51a50a52a13a19a13a101a3 a122 a88a91a90a26a60
a1
a122
a44
a60a87a88a91a90a26a60
a1a121a110
a122 a88a91a90a96a60
a1
(5)
This measure represents consistency of
a41a43a42 a0a15a44a39a45a39a46a15a47a35a45a49a48a6a45a39a46a51a50a52a13 within the maximal approxima-
tion alignment for sentence paira31 .
4.3 Across Sentence
Several hypothesis within a21a41 a61 a0a31 a13 are similar or iden-
tical to those in a21a41 a61 a0a53a123a6a13 where a31 a83a3a124a123 . We want to
score hypothesis that are consistent across sentences
higher than those that occur rarely, as the former are
assumed to be the correct translations in context. We
want to account for different contexts across sen-
tences; therefore we want to highlight similar trans-
lations, not simply exact matches. We use a word
level Levenstein distance to compare the target side
hypotheses within a21a41 a61 . Each element a77 within a21a41 a61
(the complete candidate translation list for a25 ) is as-
signed the average Levenstein distance with all other
elements as its across sentence consistence score; ef-
fectively performing a single pass average link clus-
tering to identify the correct translations.
a56a89a88a91a90a26a23a6a92a35a125
a47a96a0
a77
a13a126a3 a40
a5
a127
a99a129a128
a130a34a131a34a132a134a133a101a135
a0
a77
a45a71a136
a77
a13 (6)
where a133a101a135 calculates the Levenshein distance be-
tween the target phrases within two hypothesisa77 and
a136
a77 ,a137 is the number of elements in a21
a41 a61 .
The higher the a56a89a88a91a90a26a23a66a92a12a125a47 , the more likely the hy-
pothesis pair is a correct translation. The clustering
approach accounts for noise due to incorrect sen-
tence alignment, as well as the different contexts
in which a particular source n-gram can be used.
As predicted by the formulation of this method,
preference is given towards shorter target transla-
tions. This effect can be countered by introducing a
phrase length model to approximate the difference in
phrases lengths across the language boundary. This
will be discussed further as a language specific scor-
ing method.
4.4 Alignment Lexicon
The methods presented above used the maximum
approximation to score candidate translation hy-
potheses. The translation lexicon generated by the
IBM models provides translation estimates at the
word level built on the complete training corpus.
These corpus level estimates can be integrated into
our scoring paradigm to balance the sentence level
estimates from the alignment map methods.
The translation lexicon provides a conditional
probability estimatea31 a0a2a1a105 a33a14a108a13 for each a102 a42 a0a30 a45a19a103a104a13 (a1a105
refers to the word at positiona30 in sentencea31 ) within
the maximum approximation. Depending on the
direction in which the traditional IBM models are
trained, we can either condition on the source or tar-
get side, while joint probability models can give us a
bidirectional estimate. These translation probability
estimates are used to weight thea102 a42 a0a30 a45a19a103a104a13 within the
methods described above. Instead of simply count-
ing the number of consistent/inconsistent a102
a42 a0
a30
a45a19a103a138a13 ,
we sum the probability estimatesa31 a0a2a1a105 a33a14a108a13 for each
a102
a42 a0
a30
a45a19a103a104a13 . So far we have only considered the points
within the partition where alignment points are pre-
dicted by the maximal approximation. The transla-
tion lexicon provides estimates at the word level, so
we can construct a scoring measure for the complete
region within a41a43a42 a0a15a44a39a45a39a46a15a47a35a45a49a48a6a45a39a46a51a50a52a13 that models the com-
plete probability of the partition. The lexical scoring
equation below models this effect.
a56a139a88a10a90a26a23a6a92a73a141a140a105
a0a41a43a42 a0a15a44a39a45a39a46a15a47a35a45a49a48a6a45a39a46a51a50a52a13a19a13a101a3 a94
a57a15a142 a105a142a76a73a75a74
a143
a144
a142 a108a142a76a73a146a145
a31
a0a2a1
a105
a33a14
a108
a13
(7)
This method prefers longer target side phrases due
to the sum over the target words within the parti-
tion. Although it would also prefer short source side
phrases, we are only concerned with comparing hy-
pothesis partitions for a given source n-grama25 .
4.5 Language Specific
The nature of the phrasal association between lan-
guages varies depending on the level of inflexion,
morphology as well as other factors. The predomi-
nant language specific correction to the scoring tech-
niques discussed above models differences in phrase
lengths across languages. For example, when com-
paring English and Chinese translations, we see that
on average, the English sentence is approximately
1.3 times longer (under our current segmentation
in the small data track). To model these language
specific effects, we introduce a phrase length scor-
ing component that is based on the ratio of sen-
tence length between languages. We build a sen-
tence length model based on the DiffRatio statis-
tic defined as a135 a44a55a147a37a147a8a148 a22 a14a52a44a90 a3
a11a91a149 a18
a18 where I is the
source sentence length and J is the target sentence
length. Let a150a152a151a139a153 be the average a135 a44a55a147a37a147a8a148 a22
a14a52a44
a90 over
the sentences in the corpus, and a154a37a155
a151a139a153
be the vari-
ance; thereby defining a normal distribution over the
DiffRatio statistic. Using the standard Z normaliza-
tion technique under a normal distribution param-
eterized by a150 a151a139a153 a45a154 a155
a151a139a153
, we can estimate the proba-
bility that a new DiffRatio calculated on the phrasal
pair can be generated by the model, giving us the
scoring estimate below.
a56a89a88a91a90a26a23a66a92a73a146a140a55a156
a0a41a43a42 a0a15a44a157a45a39a46a54a47a12a45a49a48a66a45a39a46a51a50a68a13a19a13a158a3a160a159a161a0a53a46a15a47a9a45a39a46a51a50a17a33a146a162
a150a152a151a139a153
a45
a154 a155a151a139a153a158a163
a13
(8)
To improve the model we might consider exam-
ining known phrase translation pairs if this data is
available. We explore the language specific differ-
ence further by noting that English phrases contain
several function words that typically align to the
empty Chinese word. We accounted for this effect
within the scoring process by treating all target lan-
guage (English) phrases that only differed by the
function words on the phrase boundary as the same
translation. The burden of selecting the appropriate
hypothesis within the decoding process is moved to-
wards the language model under this corrective strat-
egy.
5 Pruning
The list of candidate translations for each source n-
gram a25 is large, and must be pruned to select the
most likely set of translations. This pruning is re-
quired to ensure that the decoding process remains
computationally tractable. Simple threshold meth-
ods that rank hypotheses by their final score and
only save the top a137 hypotheses will not work here,
since phrases differ in the number of possible correct
translations they could have when used in different
contexts. Given the score ordered set of candidate
phrases a21a41 a61 , we would like to label some subset as
incorrect translations and remove them from the set.
We approach this task as a density estimation prob-
lem where we need to separate the distribution of
the incorrectly translated hypothesis from the dis-
tribution of the likely translations. Instead of using
the maximum likelihood criteria, we use the maxi-
mal separation criteria ie. selecting a splitting point
within the scores to maximize the difference of the
mean score between distributions as shown below.
a56a58a31
a46a15a44a164a14
a56a139a88a10a90a26a23a6a92
a3
a22a28a23a26a25a28a27a29a22a24a30
a42 a0
a150
a130a34a165
a42
a80a166a150
a130a66a167
a42 a13 (9)
where a150 a130a34a165 a42 is the mean score of those hypothesis
with a score less thana31 , anda150 a130a34a167 a42 is the mean score
of those hypothesis with a greater than or equal to
a31 . Once pruning is completed, we convert the scores
into a probability measure conditioned on the source
n-gram a25 and assign the probability estimate as the
translation probability for the hypothesisa77 as shown
below.
a31
a0a15a14a168a69
a77
a33a1a119a169
a25
a13a158a3
a86 a44
a60a87a22
a46
a56a89a88a91a90a26a23a66a92
a0
a77
a13
a99 a128
a130a26a131a171a170a132a152a172
a86 a44
a60a87a22
a46
a56a89a88a91a90a26a23a66a92
a0 a136
a77
a13
(10)
(10) calculates direct translation probabilities, ie
a31
a0a15a14a35a33a1a26a13 . As mentioned earlier, (Och and Ney, 2002),
show that using direction translation estimates in
the decoding process as compared with calculating
a31
a0a2a1a38a33a14a19a13 as prescribed by the Bayesian framework does
not reduce translation quality. Our results corrob-
orate these findings and we use (10) as the phrase
level translation model estimate within our decoder.
6 Integration
Phrase translation pairs that are generated by the
method described in this paper are finally scored
with estimates of translation probability, which can
be conditioned on the target language if necessary.
These estimates fit cleanly into the decoding pro-
cess, except for the issue of phrase length. Tra-
ditional word lexicons propose translations for one
source word, while with phrase translations, a single
hypothesis pair can span several words in the source
or target language. Comparing between a path that
uses a phrase compared to one that uses multiple
words (even if the constituent words are the same)
is difficult. The word level pathway involves the
product of several probabilities, whereas the phrasal
path is represented by one probability score. Po-
tential solutions are to introduce translation length
models or to learn scaling factors for phrases of dif-
ferent lengths. Results in this paper have been gener-
ated by empirically determining a scaling factor that
was inversely proportional to the lenth of the phrase,
causing each translation to have a score compara-
ble to the product of the word to word translations
within the phrase.
7 HMM Phrase Extraction
In order to compare our method to a well under-
stood phrase baseline, we present a method that ex-
a137a134a22a24a27a85a92
a159
a22
a44
a23
a1 a173
a77
a44
a60a152a92
a1
a92 a174a43a60a8a25
a46a54a44a52a1
a77
Small 3540 90K 115K
Large 77558 2.46M 2.69M
Testing 993 27K NA
Table 1: Corpus figures indicating no. of sentence
pairs, no. of Chinese and English words
tracts phrases by harvesting the Viterbi path from an
HMM alignment model (Vogel et al., 1996). The
HMM alignment model is computationally feasible
even for very long sentences, and the phrase ex-
traction method does not have limits on the length
of extracted target side phrase. For each source
phrase ranging from positions a44a19a5 to a44
a155
the target
phrase is given by a48a35a175 a57a176a156 a3 a27 a44a60a37a57a162a17a48a177a3 a22 a0a15a44a52a13a163 and
a48a9a175
a125a105
a3
a27a29a22a24a30a76a57
a162a17a48a84a3
a22
a0a15a44a52a13
a163
, where a44a178a3a179a44a19a5a35a63a180a63a180a63a64a44
a155
anda48
refers to an index in the target sentence pair. We cal-
culate phrase translation probabilities (the scores for
each extracted phrase) based on a statistical lexicon
for the constituent words in the phrase. As the IBM1
alignment model gives the global optimum for the
lexical probabilities, this is the natural choice. This
leads to the phrase translation probability
a31
a0a17a181a1a20a33
a181
a14a19a13a158a3 a40
a182
a11
a94
a57
a143
a144
a31
a0a2a1
a57
a33a14
a144
a13 (11)
where a182 and a78 denotes the length of the target
phrase
a181
a14 , source phrase a181a1 , and the word probabil-
ities a31 a0a2a1a57a33a14a144a13 are estimated using the IBM1 word
alignment model. The phrases extracted from this
method can be used directly within our in-house
decoder without the significant changes that other
phrase based methods could require.
8 Experimentation
IBM alignment models were trained up to model
4 using GIZA (Al Onaizan et al., 1999) from Chi-
nese to English and Chinese to English on two
tracks of data. Figures describing the characteris-
tics of each track as well as the test sentences are
shown in Table (1). All the data were extracted
from a newswire source. We applied our in house
segmentation toolkit on the Chinese data and per-
formed basic preprocessing which included; lower-
casing, tagging dates, times and numbers on both
languages. Translation quality is evaluated by two
metrics, (MTEval, 2002) and BLEU (Papeneni et
al., 2001), both of which measure n-gram matches
between the translated text and the reference trans-
lations. NIST is more sensitive to unigram precision
due to its emphasis toward high perplexity words.
Four reference translations were available for each
test sentence. We first compare against a system
built using word level lexica only to reiterate the im-
pact of phrase translation, and then show gains by
our method over a system that utilizes phrase ex-
tracted from the HMM method. The word level sys-
tem consisted of a hand crafted (Linguistics Data
Consortium) bilingual dictionary and a statistical
lexicon derived from training IBM model 1. In our
experiments we found that although training higher
order IBM models does yield lower alignment error
rates when measured against manually aligned sen-
tences, the highest translation quality is achieved by
using a lexicon extracted from the Model 1 align-
ment. Experiments were run with a language model
(LM) built on a 20 million word news source corpus
using our in house decoder which performs a mono-
tone decoding without reordering. To implement our
phrase extraction technique, the maximum approx-
imation alignments were combined with the union
operation as described in (Och et al., 1999), result-
ing in a dense but inaccurate alignment map as mea-
sured against a human aligned gold standard. Since
bi-directional translation models are available, scor-
ing was performed in both directions, using IBM
Model 1 lexica for the within sentence scoring. The
final phrase level scores computed in each direction
were combined by a weighted average before the
pruning step. Source side phrases were restricted
to be of length 2 or higher since word lexica were
available. Weights for each scoring metric were de-
termined empirically against a validation set (align-
ment map scores were assigned the highest weight-
ing). Table (2) shows results on the small data
track, while Table (3) shows results on the large data
track. The technique described in this paper is la-
belleda159 a77a138a23a66a22 a1a92a1 in the tables. The results show that
the phrase extraction method described in this paper
contribute to statistically significant improvements
over the baseline word and phrase level(HMM) sys-
tems. When compared against the HMM phrases,
our technique show statistically significant improve-
ments. Statistical significance is evaluated by con-
a183
a92
a14
a77a104a90a34a184 a185
a133
a174a62a186 a137a187a78a20a56a188a59
Baseline-Word 0.135 6.19
Baseline-Word+Phrases 0.167 6.71
Baseline-HMM 0.166 6.49
Baseline-HMM+Phrases 0.174 6.71
Table 2: Small track results
a183
a92
a14
a77a104a90a34a184 a185
a133
a174a62a186 a137a187a78a20a56a188a59
Baseline-Word 0.147 6.62
Baseline-Word+Phrases 0.190 7.48
Baseline-HMM 0.187 7.42
Baseline-HMM+Phrases 0.197 7.60
Table 3: Large track results
sidering deviations in sentence level NIST scores
over the 993 sentence test set with a NIST improve-
ment of 0.05 being statistically significant at the 0.01
alpha level. In combination with the HMM method,
our technique delivers further gains, providing evi-
dence that different kinds of phrases have been learnt
by each method. The improvements caused by our
methods is more apparent in the NIST score rather
than the BLEU score. We predict that this effect is
due to the language specific correction that treats tar-
get phrases with function words at the boundaries as
the same phrase. This correction cause the burden
to be placed on the language model to select the cor-
rect phrase instance from several possible transla-
tions. Correctly translating function words dramati-
cally boosts the NIST measure as it places emphasis
on high perplexity words ie. those with diverse con-
texts.
9 Conclusions
We have presented a method to efficiently ex-
tract phrase relationships from IBM word alignment
models by leveraging the maximum approximation
as well as the word lexicon. Our method is signifi-
cantly less computationally expensive than methods
that attempt to explicitly model phrase level inter-
actions within alignment models, and recovers well
from noisy alignments at the sentence and corpus
level. The significant improvements above the base-
line carry through when this method is combined
with other phrasal and word level methods. Further
experimentation is required to fully appreciate the
robustness of this technique, especially when con-
sidering a comparable, but not parallel, corpus. The
language specific scoring methods have a significant
impact on translation quality, and further work to ex-
tend these methods to represent specific characteris-
tics of each language, promises to deliver further im-
provements. Although the method performs well, it
lacks an explanatory framework through the extrac-
tion process; instead it leverages the well understood
fundamentals of the traditional IBM models.
Combining phrase level knowledge sources
within a decoder in an effective manner is currently
our primary research interest, specifically integrat-
ing knowledge sources of varying reliability. Our
method has shown to be an effective contributing
component within the translation framework and we
expect to continue to improve the state of the art
within machine translation by improving phrasal ex-
traction and integration.
References
Peter F. Brown, Stephen A. Della Pietra, Vincent J. Della
Pietra, and Robert L. Mercer 1993. The Mathematics
of Statistical Machine Translation: Parameter Estima-
tion, Computational Linguisics vol 19(2) 1993
George Foster 2000. A Maximum Entropy Minimum Di-
vergence Translation Model, Proc. of the 38th Annual
Meeting of the Association for Computational Lin-
guistics
Daniel Marcu and William Wong 2002. A Phrase-Based,
Joint Probability Model for Statistical Machine Trans-
lation, Proc. of the Conference on Empirical Methods
in Natural Language Processing , Philadelphia, PA
NIST 2002. MT Evaluation Kit Version 9,
www.nist.gov/speech/tests/mt/
Franz Josef Och, Hermann Ney 2002. Discriminative
Training and Maximum Entropy Models for Statistical
Machine Translation, Proc. North American Associa-
tion for Computational Linguistics
Franz Josef Och and Hermann Ney 200. A Comparison
of Alignment Models for Statistical Machine Transla-
tion, Proc. of the 18th International Conference on
Computational Linguistics. Saarbrucken, Germany
Franz Josef Och, Christoph Tillmann, Hermann Ney
1999. Improved Alignment Models for Statistical Ma-
chine Translation, Proc. of the Joint Conference of
Empirical Methods in Natural Language Processing,
p20-28, MD.
Al’ Onaizan, Jan Curin, Michael Jahr, Kevin Knight,
John Lafferty, Dan Melamed, Franz-Josef Och, David
Purdy, Noah H. Smith and David Yarowsky 1999.
Statistical Machine Translation, Final Report, JHU
Summer Workshop
Kishore Papeneni, Salim Roukos, Todd Ward 2001.
BLEU: A Method for Automatic Evaluation of Ma-
chine Translation, IBM Research Report, RC22176
Stephan Vogel, Hermann Ney, and Christoph Tillmann
1996. HMM-based Word Alignment in Statistical
Translation, Proc. of COLING ’96: The 16th Interna-
tional Conference on Computational Linguistics, pp.
836-841. Copenhagen, Denmark
Yeyi Wang, Alex Waibel 1998. Fast Decoding for Statis-
tical Machine Translation, Proc. of the International
Conference in Spoken Language Processing
Dekai Wu 1995. Stochastic Inversion Transduction
Grammars, with Application to Segmentation, Brack-
eting, and Alignment of Parallel Corpora, Proceed-
ings of the 14th International Joint Conference on Ar-
tificial Intelligence (IJCAI-95), pp. 1328-1335. Mon-
treal
Kenji Yamada and Kevin Knight 2001. A syntax-based
statistical translation model, Proc. of the 39th An-
nual Meeting of the Association for Computational
Linguistics, France
