言語処理学会 第21回年次大会 発表論文集 (2015年3月)

Word Alignment Model with Longer Contexts
Hitoshi Otsuki Masahiro Araki Taro Watanabe
Kyoto Institute of TechnologyNICT
otsuki@ii.is.kit.ac.jp,araki@kit.jp,taro.watanabe@nict.go.jp

1Introduction

Word alignment is a crucial component in MT and
its quality directly aﬀects the end-to-end MT performance in most cases. The generative word alignment
model, i.e. IBM Model[1], is learned in an unsupervised fashion, and considers limited history, i.e. apair of source and target word. Previous studies incorporated longer histories but little gains were observed mainly due to sparsity issues[5]. To address
this issue, we introduce two models; n-gram based
context model and skip-gram based context model,
both of them take into account longer contexts for
disambiguating translations. The sparsity issue incurred by richer contexts are resolved by KneserNey(KN) smoothing on fractional counts[10], oneof the state-of-the-art performing smoothing techniques. Experimental results on French-English andChinese-English pairs for word alignment and translations tasks were, to our surprise, negative in anycases.

2Related Work

2.1

IBM Model

IBM Model is an instance of noisy channel modelin which the task of translation is modeled as a
generative process[1]. Given a source string f =f1 · · · fj · · · fJ and a target string e = e1 · · · ei · · · eI ,we want to ﬁnd ê which maximizes P r(e|f ). Here,by using Bayes’ theorem, the model is split into twoterms,
ê = argmax P r(e|f ) = argmax P r(e)P r(f |e)e(1)eThe former is called language model, and the latter is called translation model. Now we introduce a
hidden variable a which is a representation of wordalignment:∑P r(f , a|e)(2)
P r(f |e) =a

An example of word alignment is presented in Figure 1. The maximum likely word alignment givena pair of sentences f and e is computed by replacing the summation in equation 2 with maximization

Figure 1: word alignment; aj is the index of a target
word a source word at index j is aligned to .
which is called Viterbi alignment. IBM Model has
deﬁned several models by varying the richness andcomplexity in representation, and we will concentrateon two simpler models, Model 1 and 2 in particular.
P r(f , a|e) in Equation 2 is divided into several components as follows:
P r(f , a|e)
= P r(J|e)

J
∏

j−1
P r(aj |aj−1, J, e)P r(fj |aj1 , f1j−1 , J, e)
1 , f1j=1(3)
It is assumed that the length model P r(J|e) is independent of e and that P r(fj |aj1 , f1j−1 , J, e), called
lexicon model, depends only on fj and eaj which wedenote as t(fj |eaj ). Under Model 1, the alignment
j−1
model P r(aj |aj−1, J, e) is assumed to be uni1 , f1
1
form I+1 whereas the model is dependent on just a
few variables under Model 2 via a(aj |i, I, J). In thiswork, we employ a variant of Model 2 which strongly
prefers alignments to be close to the diagonal[4]. As
an extension of IBM model 1, triplet lexicon model
consider two words in the target side, ei and ek , inthe lexicon model as a way to disambiguate translations by exploring additional contexts[5].
Training of these models are performed iteratively
using EM algorithm, in which posterior probability
P (a|f , e; θ(t) ) for each sentence pair is computed using the current parameters θ(t) , and optimal parameters θ(t+1) is obtained by maximizing the expectation of joint probabilities of f and a given e overP (a|f , e; θ(t) )[1],θ(t+1) = argmax― 1024 ―θ∑ ∑P (a|f , e; θ(t) ) log P (f , a|e; θ)<f ,e> a(4)Copyright(C) 2015 The Association for Natural Language Processing.
All Rights Reserved.

2.2

Smoothing

Smoothing is a popular technique in machine learning and used for estimating parameters even for unseen event and for avoiding overﬁtting to a training data. One of the popular choice of smoothing isregularization which directly prevents from overﬁtting toward training data, for instance by using ℓ0prior[9].
Another form of smoothing is backoﬀ smoothing primarily used in n-gram language models in whichcounts are discounted and the subtracted counts arereserved for unseen data. More formally, given an ngram uw with its frequency c(uw) and a certain discounted amount D(uw), the probability of observing
w given contexts u is represented as follows:·c(uw) − D(uw)p(w|u) =+ α(u)p(w|u′ )
c(u )

(5)

where α(u) is used to ensure the probability sum
to 1. In absolute discounting and KN smoothing[2]D(uw) is a constant. The probability p(w|u′ ) is alower order probability which truncate u to u′ . Under KN smoothing, the probability is taken to satisfy
marginal constraint, leading to:′p(w|u ) =···

n1+ ( u′ w)
n1+ ( u′ )(6)·Recursive smoothing further smooths n1+ ( u′ w) tolower order. Uniform distribution |V1 | is taken to end
the recursion, where |V | denotes the size of vocabulary. Modiﬁed KN, which is reported to be one of thebest performing smoothing technique[2], use three
diﬀerent discounts D1 ,D2 and D3+ , that are applied
to n-gram with one, two, three or more counts.
The original (Modiﬁed) KN smoothing is only applicable to integer counts. In EM algorithm, however, collected counts are fractional, which makes
KN smoothing inapplicable. KN smoothing on expected counts[10] extended KN smoothing to fractional counts by incorporating count distributionp(c(uw) = r) which is the pobability that n-gram
uw appears r times.

3Alignment Model with Long
Contexts

One of the drawback of IBM Model is the limited
context represented in lexicon model. As a way to
disambiguate correspondences between source andtarget words, we present two models to consider
longer contexts in the target side, namely n-grambased model and skip-gram based model. However,longer contexts directly represented in lexicon models incur severe sparsity problems. Thus, we introduce modiﬁed KN smoothing for fractional count as

Figure 2: triplet lexicon model: source word fj isaligned to ei , ek

a way to backoﬀ to shorter contexts during the estimation of parameters in M-step.

3.1

n-gram based modeln-gram based model extends the lexicon model byconsidering previous n − 1 consecutive words in thetarget side as follows:p(f |e) =pt (fj |NULL, . . . , NULL)p0 +(1 − p0 )J ∑I∏

pt (f |ei−n · · · , ei−1 , ei ) · a(i|j, I, J)

j=1 i=1(7)where p0 is null alignment probability and a(i|j, I, J)
is an alignment model which favors diagonal alignment points. Note that the n-gram based model isa very simple extension of IBM Model and exactly
the same EM algorithm can be used to estimate theparameters despites the growth of parameters of thelexicon model.

3.2

skip-gram based model

Skip-gram based model is triplet lexicon model[5]combined with alignment model which favors diagonal alignment points. In this model, each element inword alignment a is a pair of indices in target sentence, aj = (i, k), where i < k with the ﬁrst element
used as a primary index for alignment link and thesecond element used as secondary index to represent
context, as shown in Figure 2. Like the original paper of triplet lexicon model, we deﬁne pall (fj , eI1 ),the probability of a source word fj given the wholetarget sentence eI1 as follows1 :pall (fj |eI1 ) = pt (fj |NULL, NULL) · p0 +(1 − p0 )II+1∑∑
i=1 k=i+1

1pt (fj |ei , ek ) · a(i|j, I, J)
I +1−i(8)where p0 is null alignment probability. In skip-grambased model, Viterbi alignment is obtained as fol-― 1025 ―1eI+1 denotes an end-of-sentence character

Copyright(C) 2015 The Association for Natural Language Processing.
All Rights Reserved.

lows:
aj = argmax pt (fj |NULL, NULL) · p0 · δ(i = 0)+0≤i≤I(1 − p0 )

I+1∑
k=i+1

1pt (fj |ei , ek ) · a(i|j, I, J) · δ(i ̸= 0)
I +1−i(9)where δ(·) evaluates to 1 if the condition · holds; otherwise evaluates to 0.
EM algorithm is similar to that of IBM Model, except that we need to check secondary index k whichis larger than primary index i. Sum over k is taken
to properly obtain Viterbi alignment.

4Experiments

4.1

Setting

We carried out experiments on two tasks for two
language pairs: French-English and Chinese-English.
First task is to measure the quality of word alignment, for which we used Hansards2 , French-English
corpus, consisting of 1.1M parallel sentences pairs as
training data and 447 word-aligned sentence pairs forevaluation. Second task is to measure the translation
quality. For this, we used Europarl+news commentary, another French-English corpus, from wmt12translation task3 , consisting of 2M+137K of parallel
corpus as training data, 3003 sentence as development data and 2489 sentences for evaluation. Also
we used FBIS corpus, Chinese-English corpus, which
includes 138K parallel sentences as training data, 878
sentences for development data and 919 sentences fortest data with 4 references each.
The aligners are modiﬁed version of fast align4of cdec[4] with giza-kn5 for the code base for KN
smoothing on fractional counts[10]. For all tasks, wetrained both n-gram based aligner, n ranging from 1
to 3 or 4, and skip-gram based aligner. For each corpus, we conducted experiments on diﬀerent corpus
sizes. For Hansards, a 1/10, 1/5, 1/2 and all of corpus were used for the experiments. For FBIS, 1/5,1/2 and all of the corpus were used for the experiment. And for Europarl+news commentary, a 1/10,1/5, 1/2 of the corpus were used. Due to memory
and time constraint, 5 iterations was used for training with Hansards and Europarl+news commentaryand 10 iterations for FBIS, and window size was set
to 5 in skip-gram based aligner.
We aligned on both directions of a language pairand then symmetrized them using grow-diag-ﬁnaland method. Word alignment qualities for Hansards
2 http://www.isi.edu/naturallanguage/download/hansard/
3 http://www.statmt.org/wmt12/translation-task.html
4 https://github.com/redpony/cdec/word-aligner
5 https://github.com/hznlp/giza-kn

were measured by AER[7]. For the other data set,
we measured translation qualities by BLEU[8] using a phrase-based MT of Moses[6] tuned by batchMIRA[3].

4.2

Results

Our experimental results showed that adding context degraded AER and BLEU scores. Experimental results on word alignment qualities measured by
AER are summarized in Table 1. For n-gram basedaligner, AER basically got worse as the number ofcontexts increases in both KN and maximum likelihood estimate(ML). While almost no diﬀerenceswere observed for 2-gram and above, AER drops
signiﬁcantly when a context is added to the 1-grammodel. The drop is even more signiﬁcant in ML thanKN, demonstrating up to 15% degradation. Skipgram base aligner scored better than 2-gram aligner,
5% better in KN and 8% in ML at least. We also observe that Kneser ney smoothing surpress the worsening of the results compared to ML. The results fortranslation qualities are presented in Table 2. We cansee that skip-gram aligner performed poorer than 2gram aligner in FBIS, up to 0.69 diﬀerence in BLEU
score when KN is used, and up to 0.65 diﬀerence
when ML is used. On the other hand, skip-grambased model outperformed 2-gram model in Europarl+ news commentary, though it falls behind 1-grammodel. Like AER in Table 1, BLEU generally drops
as the number of context increases.

4.3

Discussion

We observed that additional contexts had negative
impact for the AER and BLEU score. Figure 3
shows an example of word alignment results from1-gram aligner and 2-gram aligner under Hansard.
In this example, “threat” is aligned to “menace”,
which is the correct alignment, when 1-gram aligner
is used, and is aligned to “pour” when 1-gram aligner
is used. We extracted the translation table produced
after training 2-gram aligner with Hansard corpus in
Table 3. Table 3 shows that the probability that“menace pour” is linked to “threat” is very high,even though we want the lexical translation model
to link “menace pour” to “to” or “for” in almost
all cases, not “threat”. We conﬁrmed that “pour”
is most likely be translated to “to” or “for” in 1gram aligner. This implies that adding context tolexical translation model incurs more parameters tobe estimated to the extent KN smoothing can’t handle. Therefore, if a n-gram appears only a few times
in a training data, relatively low probability is assigned to the parameter even if a word consisting
the n-gram appears frequently, as in “serieuse menace” → “threat”. Indeed, “menace pour” appeared― 1026 ―Copyright(C) 2015 The Association for Natural Language Processing.
All Rights Reserved.

Table 1: AER of n-gram aligner and skip-gram aligner, trained on Hansards corpus with 5 EM iterations
Kneser Ney
Maximum Likelihood
model
1/10
1/5
1/2
all
1/10
1/5
1/2
all
1-gram 15.09 14.56 14.06 13.90 15.76 14.92 14.20 14.06
2-gram
22.59
23.28
24.00
24.89
29.73
29.43
29.28
28.77
3-gram
23.43
24.16
25.09
26.29
32.12
32.85
32.96
32.79
4-gram
23.30
23.95
24.76
26.08
33.43
33.03
32.16
32.74
skip
17.22
17.34
17.54
17.52
21.70
21.26
20.44
20.01
Table 2: BLEU of n-gram aligner and skip-gram aligner, trained on FBIS corpus with 10 EM iterations andEuroparl + news commentary with 5 EM iterations
FBIS
Europarl + news commentary
Kneser Ney
Maximum Likelihood
Kneser Ney
Maximum Likelihood
model
1/5
1/2
all
1/5
1/2
all
1/10
1/5
1/2
1/10
1/5
1/2
1-gram22.1 26.05 28.11 20.80 24.46 26.89 23.01 23.69 24.17 22.87 23.58 24.07
2-gram 19.77 23.62
26.22
14.69
18.34
20.7
22.42
23.00
23.55
20.58
21.28
22.14
3-gram 17.87 21.63
24.37
13.85
17.39
19.63
22.14
22.69
23.21
19.63
20.56
21.46
4-gram 17.94 20.94
23.16
13.5
17.30
19.28
skip
19.33 22.9325.99
14.38
17.69
20.56
22.69
23.52
23.86
21.09
22.17
23.12

Figure 3: Alignment points between a English sentence and a French sentence; dashed line is the alignmentsfrom 2-gram aligner, and normal line is the alignments by 1-gram aligner

Table 3: translation table of hansard corpus, learnedby 2-gram aligner
fei−1 , eit(f |ei−1 , ei )tomenace pour
0.476080
threatmenace pour
0.298240
threat serieuse menace
0.121866

more than 100 times in the training corpus, while“serieuce menace” appeared only 3 times.

5References[1]

Peter F Brown, Vincent J Della Pietra, Stephen A Della Pietra, andRobert L Mercer. The mathematics of statistical machine translation:
Parameter estimation. Computational linguistics, 19(2):263–311, 1993.

[2]

Stanley F Chen and Joshua Goodman. An empirical study of smoothing
techniques for language modeling. In Proceedings of the 34th annual meetingon Association for Computational Linguistics, pages 310–318. Association for
Computational Linguistics, 1996.

[3]

Colin Cherry and George Foster. Batch tuning strategies for statisticalmachine translation. In Proceedings of the 2012 Conference of the North American Chapter of the Association for Computational Linguistics: Human LanguageTechnologies, pages 427–436. Association for Computational Linguistics,
2012.

[4]

Chris Dyer, Victor Chahuneau, and Noah A Smith. A simple, fast,and effective reparameterization of ibm model 2. In HLT-NAACL, pages
644–648. Citeseer, 2013.

[5]

Saša Hasan, Juri Ganitkevitch, Hermann Ney, and Jesús Andrés-Ferrer.
Triplet lexicon models for statistical machine translation. In Proceedingsof the Conference on Empirical Methods in Natural Language Processing, pages
372–381. Association for Computational Linguistics, 2008.

[6]

Philipp Koehn, Hieu Hoang, Alexandra Birch, Chris Callison-Burch,
Marcello Federico, Nicola Bertoldi, Brooke Cowan, Wade Shen, Christine Moran, Richard Zens, Chris Dyer, Ondřej Bojar, Alexandra Constantin, and Evan Herbst. Moses: Open source toolkit for statisticalmachine translation. In Proceedings of the 45th Annual Meeting of the ACL
on Interactive Poster and Demonstration Sessions, ACL ’07, pages 177–180,
Stroudsburg, PA, USA, 2007. Association for Computational Linguistics.

[7]

Franz Josef Och and Hermann Ney. Improved statistical alignment models. In Proceedings of the 38th Annual Meeting on Association for ComputationalLinguistics, pages 440–447. Association for Computational Linguistics,
2000.

[8]

Kishore Papineni, Salim Roukos, Todd Ward, and Wei-Jing Zhu. Bleu:a method for automatic evaluation of machine translation. In Proceedingsof the 40th annual meeting on association for computational linguistics, pages
311–318. Association for Computational Linguistics, 2002.

[9]

Ashish Vaswani, Liang Huang, and David Chiang. Smaller alignment
models for better translations: unsupervised word alignment with the l0-norm. In Proceedings of the 50th Annual Meeting of the Association for Computational Linguistics: Long Papers-Volume 1, pages 311–319. Association for
Computational Linguistics, 2012.

[10]

Hui Zhang and David Chiang.
counts.

Conclusion

We introduced two translation model, n-gram basedmodel and skip-gram based model. n-gram basedmodel considers previous context in the lexicontranslation model where as skip-gram based model
considers words not only from local context but also
from global context. Our experiments showed that
adding contexts has negative impact on both of thealignment quality and translation quality, thoughprevious studies insisted on positive results undermore simpler triplet lexicon model. The extra contexts might cause huge data sparsity issue than wehave expected which cannot be handled by simply
introducing a state-of-the-art backoﬀ smoothing of
KN on expected counts. In the future, we would
like to investigate the issue using more sophisticatedmethod, such as non-parametric Bayesian to properly handle longer contexts.

― 1027 ―Kneser-ney smoothing on expected

Copyright(C) 2015 The Association for Natural Language Processing.
All Rights Reserved.