A Survey of Statistical Machine Translation
Masao Utiyama
Lecture slides, Kyoto University, August 2006

Contents• Main components in SMT• Publicly available SMT system• Word-based models: IBM models• Automatic evaluation: BLEU
• Phrase-based SMT

1

Contents (cont.)• Decoding• Log-linear model• Minimum error rate training• Reranking• Discriminative SMT

2Contents (cont.)• Formally syntax-based SMT• Formally and linguistically syntax-based SMT• Dependency-based SMT• Word alignment• Parallel corpora• Next topics in SMT (in my opinion)
3

Main components in SMT• Parallel corpora• SMT engine• Automatic evaluation

4

Publicly available SMT system
http://www.statmt.org/wmt06/shared-task/
Philipp Koehn and Christof Monz. (2006) Manual and Automatic Evaluation of MachineTranslation between European Languages. HLT-NAACL workshop on Statistical MachineTranslation.

• parallel corpora• word alignment program• decorder• minimum error rate training package
5Performance of baseline system• speed: a few seconds per sentence• accuracy: comparable to SYSTRAN?
• languages: any language pair with a large parallel corpus
Accuracy depends on the language pairs.

6IBM models
Peter F. Brown, Stephen A. Della Pietra, Vincent J. Della Pietra and Robert L. Mercer. (1993)
The Mathematics of Statistical Machine Translation: Parameter Estimation. Computational
Linguistics, 19:2, 263–311.

• Translate a French sentence f into an English sentence e

Pr(e|f ) =Pr(e) Pr(f |e)Pr(f )ê = arg max Pr(e) Pr(f |e)e7

Three components in SMTê = arg maxe Pr(e) Pr(f |e)• Language model: Pr(e)Responsible for ﬂuency• Translation model: Pr(f |e)Responsible for adequacy• Search or decoding: arg maxe
Responsible for candidate selection
8

Word alignment a• Le1 programme2 a3 été4 mis5 en6 application7• And(0) the(1) program(2) has(3) been(4) implemented(5,6,7)• J’1 applaudis2 á3 la4 décision5• e0(3) I(1) applaud(2) the(4) decision(5)9Translation model as sum of alignments

Pr(f |e) =Pr(f , a|e)a• e = el1 = e1e2 . . . el (ei is i-th English word)• f = f1m = f1f2 . . . fm (fj is j-th French word)• am
1 = a1 a2 . . . am (aj = i if j-th French position is connected to i-th English
position. aj = 0 if fj is not connected to any English word)10Sequence modelPr(f , a|e) = (Choose the length of f )m×(Choose where to connect j-th French word)
j=1

× (Choose j-th French word)
m

j−1
j
j−1
= Pr(m|e)Pr(aj |aj−1
,
f
,
m,
e)
Pr(f
|a
,
f
, m, e)
j
1
1
1 1
j=1

11

Model 1• Pr(m|e) =  (a constant independent of m and e)
j−1
1
,
f
, m, e) = l+1(depends only on l, the length of e)• Pr(aj |aj−1
11• Pr(fj |aj1, f1j−1, m, e) = t(fj |eaj ) (translation probability of fj given eaj )t(fj |eaj ) is estimated by EM.

12

HMM-based word alignment
Stephan Vogel, Hermann Ney, and Cristoph Tillmann. (1996) HMM-Based Word Alignment in
Statistical Translation. COLING-96.
j−1• Pr(aj |aj−1,f, m, e) = Pr(aj |aj−1, l) (depends only on the previous
1
1alignment aj−1 and the length of e)• Probability depends on the relative positions(aj − aj−1)
Pr(aj |aj−1, l) = li=1 s(i − aj−1 ){s(·)} is a set of non-negative parameters. The empty word is not considered.
13

Fertility model
φi = fertility of i-th English word (no. of French words to which ei is connected)
τik = k-th (1 ≤ k ≤ φi) French words to which ei is connected
πik = position in f of τik
Pr(f , a|e) =Pr(τ, π|e)(τ,π)∈f ,a• Given an English sentence, e• Decide the fertility of each English word,• Choose a list of French words (τ ) to connect to each English word,• Choose a position of each French word (π)
14Pr(τ, π)

=

l


i−1

Pr(φi|φ1 , e)(Choose fertility of each non-empty word ei )

i=1

×
×

l

Pr(φ0|φ1 , e)(Choose fertility of the empty word e0)
φi
l 


k−1
Pr(τik |τi1
, τ0i−1, φl0, e)(Choose k-th French word for ei )i=0 k=1

×

φi
l 


k−1
Pr(πik |πi1
, π1i−1, τ0l , φl0, e)

i=1 k=1(position of each French word τik connecting to non-empty word ei )

×

φ0


k−1

l

l

l

Pr(π0k |π01 , π1 , τ0, φ0 , e)k=1

(position of each French word connecting to the empty word)15

Model 3• n(φ|ei) = Pr(φi|φi−1
1 , e) (fertility probability for non-empty words)
k−1 i−1, τ0 , φl0, e) (translation probability for all words)• t(f |ei) = Pr(Tik = f |τi1
k−1
, π1i−1, τ0l , φl0, e) (distortion probability for non• d(j|i, m, l) = Pr(Πik = j|πi1
empty words)

•

φ0

k−1
l
l
l
k=1 Pr(π0k |π01 , π1, τ0 , φ0 , e)1
= φ10! = φ0(φ0−1)(φ.
0 −2)···
positions to go. τ02 has φ0 − 1 positions, and so on)• Pr(φ0|φl1, e) =φ1 + φ2 + · · · + φl
φ0(τ01 has φ0

φ +φ2 +···+φl −φ0 φ0
p1

p0 1

16

IBM models summary
Automatic construction of a machine translation system is feasible given a parallel
corpus.

17

Automatic evaluation: BLEU
Kishore Papineni, Salim Roukos, Todd Ward and Wei-Jing Zhu. (2002) BLEU: a Method forAutomatic Evaluation of Machine Translation. ACL-02.

The closer a machine translation is to a professional human translation, the better
it is.
Essential ingredients:• a numerical “translation closeness” metric• a corpus of good quality human reference translations

18

BLEU

BLEU = BP × exp(

N

1

N
n=1

log pn)• BP: brevity penalty (punish short translations)clipped number of shared n-grams• pn = ngram precision = number of ngrams in translations

19

Evaluating BLEU

• 5 Chinese-to-English MT (S1,S2,S3,H1,H2) were evaluated• 250 Chinese sentences were translated• monolingual and bilingual groups evaluated translations

20

Relationship between BLEU and human evaluations
3.5
3

HUMAN

2.5
2
1.5
1
0.5
’bleu.txt’’human.txt’
0
0

0.05

0.1

0.15

0.2

0.25

0.3

BLEU

21

BLEU summary• BLEU correlates highly with human evaluation• BLEU is used in all SMT papers these days

22

BLEU limitations
Chris Callison-Burch, Miles Osborne and Philipp Koehn. (2006) Re-evaluating the Role of BLEU
in Machine Translation Research. EACL-06.

appropriate use of BLEU
• Comparing systems with similar translation strategy• Parameter optimization
inappropriate use of BLEU
• Comparing systems with diﬀerent translation strategy (SMT vs rule-based MT)• Trying to detect improvements not modelled well by BLEU
23

Phrase-based models
Franz Josef Och and Hermann Ney. (2004) The Alignment Template Approach to Statistical
Machine Translation. Computational Linguistics, 30:4, 417–449.
Philipp Koehn, Franz Josef Och, and Daniel Marcu. (2003) Statistical Phrase-Based Translation.
HLT-NAACL-2003

Phrase refers to a consecutive sequence of words occurring in text.

24

Phrase-based translation
MorgenfliegeTomorrowIichwill flynach Kanada

zur Konferenz

to the conferencein Canadafrom Koehn et al. 2005.

25

Phrase-based model by Koehn, Och and Marcu 2003
• f is segmented into a sequence of I phrases f1I• Each fi is translated into an English phrase ei• Phrase translation probabilty is φ(fi|ei)• Reordering of the English output phrases is modeled by a relative distortion
probability distribution d(ai − bi−1)• ai is the start position of fi• bi−1 is the end position of fi−1
26

Phrase-based model (cont.)ê = arg max Pr(e) Pr(f |e)ω length(e)ePr(f |e) =Iφ(fi|ei)d(ai − bi−1)i• d(ai − bi−1) is trained using a joint probablity model• d(ai − bi−1) = α|ai−bi−1| is used in the Pharaoh decoder
27

Research issues in phrase-based models• How to extract phrases?
• How to estimate φ(f |e)?
(f |e)
φ(f |e) = count
count(f |e)f• How to estimate the distortion or reordering probability distribution d(·)?
Kohen et al.’s model is very simple. Much recent work focuses on reordering.

28

Phrase extraction
Philipp Koehn, Amittai Axelrod, Alexandra Birch Mayne, Chris Callison-Burch, Miles Osborneand David Talbot. (2005) Edinburgh System Description for the 2005 IWSLT Speech Translation
Evaluation. IWSLT-2005.

• Align the words bidirectionally by GIZA++• Intersection: high precision alignment• Union: high recall alignment• Extract phrase paris that are consistent with the word alignment
29

Phrase extraction
Maria
Mary

did
not

slap
the
green

no

daba

una

botefada a

la

bruja

verde

Mary
did
did not
Mary did not
slap
slap
slap
slap
slap
...

Maria
no
no
Maria nodaba
una
botefada
daba unadaba una botefada

witch

30

Phrase-based SMT summary• Currently, best performing SMT.
• A phrase translation pair incorporates local reordering• Heuristic phrase extraction works well
• Global reordering is a research issue
Phrase-based models are constructed on top of the word-based IBM models.

31

Theoretical issues in phrase-based models• Phrase-based models are constructed on top of the word-based IBM models.
• A generative phrase-based model is inferior to heuristic models.
Daniel Marcu and William Wong. (2002) A phrase-based, joint probability model for statisticalmachine translation. EMNLP-02.

32

Decoding or SearchDiﬀerent models require diﬀerent decoders. Basic algorithms are borrowed fromspeech recognition or parsing.
• Beam searchFranz Josef Och and Hermann Ney (2004)• Weighted ﬁnite state transducer
Kevin Knight and Yaser Al-Onaizan. (1998) Translation with Finite-State Devices. 4th AMTA

• CYK
Syntax-based SMT
33

Log-linear modelFranz Josef Och.
ACL-2003.

(2003) Minimum Error Rate Training in Statistical Machine Translation.

ê = arg max Pr(e|f )eexp( m λmhm(e, f ))= arg max ee exp(m λm hm (e , f ))
λmhm(e, f ))= arg max exp(em

• λm = weight of feature m• hm(e, f ) = value of feature m
34

Research issues in log-linear models• Modeling problem
Developing suitable feature functions that capture the relevant properties of
the translation task
• Training problem
obtaining suitable feature weights

35

Example of features• language model probability: Pr(e)• phrase translation probability: φ(e|f ), φ(f |e)• lexical translation probability: t(ei|fj ), t(fi|ej )• word and phrase penalty (prefer long or short sentences)36

Minimum error rate training
Optimize the weights of features λ1. running the decorder with a currently best weight setting
2. extracting an n-bset list of possible translations
3. ﬁnding a better weight setting that re-ranks the n-best-list, so that a bettertranslation score is obtained.
4. goto 1

37

Minimum Bayes-risk decoding
Ashish Venugopal, Andreas Zollmann and Alex Waibel. (2005) Training and Evaluating Error
Minimization Rules for Statistical Machine Translation. ACL Workshop on Building and Using
Parallel Texts.

ê = arg

mine∈Gen(f )

Loss(e, e) Pr(e|f )e ∈Gen(f )ê is regarded as the centroid of Gen(f ) if we regard Loss(e,e) as the distance
between e and e. In other word, ê is the representative translation of Gen(f ).

38Comparison of performance
Minimum Bayes risk (MBR) >(slighly) MAP with Minimum error training
1. MAP returns the top ranked translation
2. MBR examines the n-best list for the best translation

39

N-best reranking
Franz Josef Och, Daniel Glidea, Sanjeev Khudanpur, Anoop Sarkar, Kenji Yamada, Alex Fraser,
Shankar Kumar, Libin Shen, David Smith, Katherine Eng, Viren Jain, Zhen Jin, and Dragomir
Radev. (2004) A Smorgasbord of Features for Statistical Machine Translation. HLT-NAACL2004.
Libin Shen, Anoop Sarkar, and Franz Josef Och. (2004) Discriminative Reranking for MachineTranslation. HLT-NAACL-2004.

Reranks the n-best list of translation candidates.

40

N-best reranking (cont.)• Easy to incorporate various features including global features that are diﬃcult
to handle in decoding• Currently, improvement with reranking is modest• This is because the translations contained in an n-best list are quite limited
compared to the vast search space41

Log-linear model summary• Log-linear model is one of the best practices in the current SMT

42

Discriminative SMT
Percy Liang, Alexandre Bouchard-Cote, Dan Klein, and Ben Taskar. (2006) An End-to-End
Discriminative Approach to Machine Translation. ACL-2006.

• Formuate SMT as structured classiﬁcation• Represent a translation candidate as a feature vector• Estimate a weight vector from a large training corpus, in contrast to minimum
error training that uses a small development corpus

43

Translation as structured classiﬁcationê = arg max w · Φ(f , e, h)e, h• ê is the English translation• f is the input foreign language sentence• e is a candidate translation• h is a hidden structure• w is a weight vector• Φ(f , e, h) is a feature vector representing (f , e, h)
44w · Φ(f , e, h)• A candidate e is represented by a feature vector Φ(f , e, h)• Its score is w · Φ(f , e, h)• Score calculation and candidate generation is done by a decoder.
• w is updated for each (fi, ei)
Once you can represent a translation candidate as a feature vector, you can tune
a weight vector to search better translations.

45Perceptron-based training
Update rule on an example (fi, ei)w ← w + Φ(fi, et, ht) − Φ(fi, ep, hp)• ep, hp are the predicted translation and hidden structure, i.e., the besttranslation obtained by a decorder.
• et, ht are the target translation and hidden structure.
• To obtain et, generate an n-bset list using the current parameters. Then selectthe highest BLEU score translation in the n-best list wrt ei
46

Discriminative SMT summary• A large number of feature weights can be tuned• Use all training data for tuning weights

47

Reordering for phrase-based SMT
Kazuteru Ohashi, Kazuhide Yamamoto, Kuniko Saito, and Masaaki Nagata. (2005) NUT-NTT
Statistical Machine Translation System for IWSLT 2005.

Pr(f |e) =Iφ(fi|ei)d(ai − bi−1)i• Reordering in phrase-based SMT is very weak.
• Simply to penalize nonmonotonic phrase alignment• Can’t represent the general tendency of global phrase reordering
48

Phrase distortion modelp(d|ei−1, ei, f i−1, f i)
• ei−1, ei are adjacent target phrases• f i−1, f i are source phrases aligned• d is the relative distance between fi−1 - fi
Slightly improvements in accuracy.

49

Discriminative reordering modelRichard Zens and Hermann Ney. (2006) Discriminative Reordering Models for Statistical MachineTranslation. HLT-NAACL-2006 Workshop on Statistical Machine Translation.

p(o|ei−1, ei, f i−1, f i)
• o = orientation (left/right)• o is left if the start position of f i is to the left of f i−150Training• Maximum entropy modeling• Word alignment corpora were used for training corpora• Words and word classes were used as features

51

Formally syntax-based SMT
Dekai Wu. (1997) Stochastic Inversion Transduction Grammars and Bilingual Parsing of Parallel
Corpora. Computational Linguistics, 23:3, 377–403.
David Chiang. (2005) A Hierarchical Phrase-Based Model for Statistical Machine Translation.
ACL-2005.

Learn a synchronous context-free grammer from a bitext without any syntactic
information.

52

Hierarchical phrases［オーストラリア］ ［ 是］ ［［［与 ［ 北朝鮮］1 有 ［ 外交］2 ］ 的 ［ 少数国家］3 ］ 之一］［ Australia ］［ is ］［ one of ［ the ［ few countries ］3 that ［ have ［ diplomatic relations ］2 with
［ North Korea ］1 ］］］• 是=is, 与=with, 有=have, 的=that, 之一=one of• 与 X1 有 X2, have X2 with X1• X1 = 北朝鮮, North Korea• X2 = 外交, diplomatic relations
53

Hierarchical phrases (cont.)［オーストラリア］ ［ 是］ ［［［与 ［ 北朝鮮］1 有 ［ 外交］2 ］ 的 ［ 少数国家］3 ］ 之一］［ Australia ］［ is ］［ one of ［ the ［ few countries ］3 that ［ have ［ diplomatic relations ］2 with
［ North Korea ］1 ］］］• X1 的 X2, the X2 that X1• X1 = 与 北朝鮮 有 外交， have diplomatic relations• X2 = 少数国家, few countries

54

Hierarchical phrases (cont.)［オーストラリア］ ［ 是］ ［［［与 ［ 北朝鮮］1 有 ［ 外交］2 ］ 的 ［ 少数国家］3 ］ 之一］［ Australia ］［ is ］［ one of ［ the ［ few countries ］3 that ［ have ［ diplomatic relations ］2 with
［ North Korea ］1 ］］］• X1 之一, one of X1• X1 = 与 北朝鮮 有 外交 的 少数国家, the few countries that have diplomatic
relations with North Korea

55

Parsing = translation

オーストラリア -------------------------------------------(Australia)X--S-+
是 --------------------------------------------------------------(is)X----+-S---+与 -----------------+|
北朝鮮 -(N. Korea)X1+|
有 -----------------+-(have X2 with X1)X1-+|
外交 -(dipl. rel.)X2+||
的 ---------------------------------------+--(the X2 that X1)X1--+|
少数国家 ----(few countries)X2 -----------+||之一 ------------------------------------------------------------+-- one of X1 -+- S

56

Rule acquisition

1. If < f , e > is an initial phrase pair, then
X →< f , e >is a rule.
2. If r = X →< γ, α > is a rule and < f , e > is an initial phrase pair such thatγ = γ1f γ2 and α = α1eα2 then
X →< γ1X1γ2, α1X1α2 >is a rule. (Replace initial phrases with variables)

57

Linguistically and formally syntax-based SMT

Kenji Yamada and Kevin Knight. (2001) A Syntax-Based Statistical Translation Model. ACL2001.

Kenji Yamada and Kevin Knight. (2002) A Decoder for Syntax-based Statistical MT. ACL-2002.

Parse a foreign sentence as an English sentence when translating f to e.

• training corpus = parsed English sentences and raw foreign sentences
58

VB

Reorder

PRP VB1

VB2

He adores
VB

VB
PRP

VB2

VB1

He
TO

adoresTO

VB

listeninglistening

TO

NN

to

music

NN

TO

music

to

• reordering
nodes

InsertVB
PRP

Translate
VB2

kare hasuki desu

TO

NN

VB1

VB ga
kiku
TO

ongaku wo

VB
PRP
He

no

VB2

ha

Three
kinds
of
operations are appliedon each node:

VB1

child

• inserting an extra
word to the left or
right of the node
• translating leaf words

adores desu
Reverse
VB ga

TO

listening no
NN

TO

music

to

operations
are performed whentranslating f into e

59

Rule acquisition
Michel Galley, Mark Hopkins, Kevin Knight and Daniel Marcu. (2004) What’s in a Translation
Rule? NAACL-HLT-2004.
S
NP

INPUT
ne VB pas

VP

PRP

AUX

RB

VB

he

does

not

go

il

ne

va

pas

Transformation
rules
are extracted fromalignment graphs

OUTPUT
VP
AUX

RB

does

not

VB

60

Dependency-based SMT
Chris Quirk, Arul Menezes, and Colin Cherry.
Syntactically Informed Phrasal SMT. ACL-2005.

(2005) Dependency Treelet Translation:

Yuan Ding and Martha Palmer. (2005) Machine Translation Using Probabilistic Synchronous
Dependency Insertion Grammars. ACL-2005.
David A. Smith and Jason Eisner. (2006) Quasi-Synchronous Grammars: Alignment by SOft
Projection of Syntactic Dependencies. HLT-NAACL-2006 Workshop on Statistical MachineTranslation.

61

Dependency Treelet Translation

1. Align a parallel corpus
2. Project the source dependency parse onto the target sentence
3. Extract dependency treelet translation pairs
4. Train a tree-based ordering model62

Projecting dependency trees
1. Dependency projection (English dependency -> French dependency)+-[0]startup+-[1]properties[2]and+-[3]options

de demarrage[0]-+proprietes[1]-+et[2]options[3]-+2. Reattachment (to correct the word order in the French sentence)+-[0]startup+-[1]properties[2]and+-[3]options

proprietes[1]--------+
et[2]options[3] --+de demarrage[0] -+63

Translation modelPr(order(t)|t, s) Pr(t|s)

t,s• Treelet s collectively covers the source dependency tree
• t is the translation of s
• order(t) is the order of the constituent of t
• order(t) is learned by a decision tree64Advantage of dependency translation• Discontiguous phrases• Reordering based on syntax• Dependency is better suited to lexicalized models compared with constituency
analysis

65Phrase cohesion
Heidi J. Fox. (2002) Phrasal Cohesion and Statistical Machine Translation. EMNLP-2002.

Explore how well phrases cohere across two languages, speciﬁcally English andFrench.
crossing• eji = ei . . . ej
• span(eij ) = fmin(ai,...,aj ), . . . , fmax(ai,...,aj )If phrase cohere perfectly across languages, the span of one phrase will neveroverlap the span of another. If two spans do overlap, we call this a crossing.
66Phrase cohesion (cont.)
Head-modiﬁer crossing#crossing per sentence
constituency analysis 2.252
dependency analysis 1.88
Modiﬁer-modiﬁer crossing#crossing per sentence
constituency analysis 0.86
dependency analysis 1.498
Reordering words by phrasal movement is a reasonable strategy
The highest degree of cohesion is present in dependency structures67

Word alignment
Franz Josef Och and Hermann Ney. (2003) A Systematic Comparison of Various Statistical
Alignment Models. Computational Linguistics, 29:1, 19–51.
Robert C. Moore (2005) A Discriminative Framework for Bilingual Word Alignment. HLT-NAACL2005.

68

Systematic comparison of alignment models• Statistical alignment models outperform the simple Dice coeﬃcient• The best results are obtained with Model-6 (log-linear interpolation of Model-4
and HMM-model)• Smoothing and symmetrization have a signiﬁcant eﬀect on the alignment
quality69

Discriminative word alignmentâ = arg maxa

λifi(a, e, f )ifeatures• Association score• Nonmonotonicity features• one-to-many feature• unlinked word feature70Parameter optimization
A modiﬁed version of averaged perceptron learningλi ← λi + η(fi(aref, e, f ) − fi(ahypo, e, f ))• aref = reference alignment between e and f• ahypo = best alingment obtained by a beam searchComparable performance with IBM Model 4.

71

Language model
Eugene Charniak, Kevin Knight and Kenji Yamada. Syntax-based Language Models for Statistical
Machine Translation

Syntax-based language models improve the syntactic quality of SMT.
Almut Silja Hildebrand, Matthias Eck, Stephan Vogel and Alex Waibel. (2005) Adaptation of
the Translation Model for Statistical Machine Translation based on Information Retrieval. EAMT
2005.

Select part of a training parallel corpus that are similar to the test sentences.
Bing Zhao, Mathias Eck and Stephan Vogel. Language Model Adaptation for Statistidcal MachineTranslation with Structured Query Models.

Select part of a target monolingual corpus that are searched by CLIR techniques.
72Construction of parallel corpora
Masao Utiyama and Hitoshi Isahara. (2003) Reliable Measures for Aligning Japanese-English
News Articles and Sentences. ACL-2003
Dragos Stefan Munteanu and Daniel Marcu. (2006) Improving Machine Translation Performance
by Exploiting Non-Parallel Corpora. Computational Linguistics 31:4, 477–504.
Matthias Eck, Stephan Vogel and Alex Waibel. (2005) Low Cost Portability for Statistical
Machine Translation based on N-gram Frequency and TF-IDF. IWSLT-2005.

73

Other topics
Evgeny Matusov, Nicota Ueﬃng and Hermann Ney. (2006) Computing Consensus Translationfrom Multiple Machine Translation Systems Using Enhanced Hypotheses Alignment. EACL-2006.
Chris Callison-Burch, Philipp Koehn and Miles Osborne. (2006) Improved Statistical MachineTranslation Using Paraphrases.
Franz Josef Och and Hermann Ney.
Recognition?

What Can Machine Translation Learn from Speech74

Next topics in SMT (in my opinion)• SMT from comparable corpora• Reliable human evaluation• Automatic error analysis• Language modeling• SMT between non-English languages• Minimum error rate phrase extraction
75

SMT from comparable corpora• Current phrase-based translation models are based on phrase tables.
• Thus, if we can construct phrase tables from comparable corpora, we can makea statistical machine translation system from comparable corpora.
• We can assume a small development parallel corpora for tuning parameters.
cf. (Dragos Stefan Munteanu and Daniel Marcu 2006)

76

Reliable human evaluation• Judgments on adequacy and ﬂuency are unstable (Koehn and Monz 2006)• More reliable human judgments are needed.
• Candidates:– paired comparison analysis– ranking77

Automatic error analysis• BLEU is useful for ranking systems• However, we want to spot the type of errors• Better evaluation is needed.
• The ﬁrst step is large scale (automatic) evaluation• Then, we can classify test sentences into good and bad translations• We can extract characteristic error patterns in bad translations
Identifying what can do and what can not do.
78

Language modeling• Very large scale n-gram model (20 billion?)• Maximum entropy modeling• Discriminative language modeling• Rich features

79

SMT between non-English languages
Parallel corpus• There are a large amount of English-Chinese parallel corpora• There are a large amount of English-Arabic parallel corpora• However, Chinese-Arabic parallel corpora are few if exist at all
Pivot translation is promising for the time being.

80

SMT between non-English languages (cont.)• Morphology• Reordering
A language universal approach is needed which can be applied to all language
pairs.

81

Minimum error rate phrase extraction• Phrases have large impact on MT performance• Connecting phrase extraction and decoding is needed.
Cf. (Nagata et. al 2006)

82

Diﬃcult problems• Better modeling• Better evaluation• Publicly available large scale multilingual corpora83

ACL-2006
Incomplete notes taken while ACL-2006

84

Arabic-to-English SMT
Fatiha Sadat and Nizar Habash. Combination of Arabic Preprocessing Schemes for Statistical
Machine. Translation.

Arabic Linguistic Issues• Rich morphology• Spelling ambiguity• Segmentation Ambiguity
Preprocessing can improve MT quality.
85

Word alignment error
Necip Fazil Ayan and Bonnie J. Dorr. Going Beyond AER: An Extensive Analysis of Word
Alignments and Their Impact on MT• AER and BLEU are not correlated very much
• Precision-oriented alignments is better than recall-oriented alignments inphrase-based SMT

86

Word alignment with CRF
Phil Blunsom and Trevor Cohn. Discriminative Word Alignment with Conditional Random Fields.

• Conditional random ﬁelds based on the HMM alignment model• HMM alignment model is a sequential model• Alignment as tagging.
• For each source word, assign a position in the target sentence87Phrase extraction from comparable corpora
Dragos Stefan Munteanu and Daniel Marcu. Extracting Parallel Sub-Sentential Fragments from
Non-Parallel Corpora.

• Begin with a word alignment sentence pair
• Detect fragments (phrases) that are translation with each other• Alignment score of a fragment is the average of word alignment scores in awindow88

Word alignment
Robert C. Moore, Wen-tau Yih and Andreas Bode. Improved Discriminative Bilingual Word
Alignment

Two stage approach:Stage 1 aligns words then Stage 2 uses the resultsof stage 1 to align words. Stage1 features are association score, jump distancediﬀerences, etc. Stage2 features are conditional link cluster odds, ....
New features had a large impact on performance
perceptron learning < Joachims’ SV M struct (note!)89

Reordering
Deyi Xiong, Qun Liu and Shouxun Lin. Maximum Entropy Based Phrase Reordering Model for
Statistical Machine Translation

Pr(o|P1, P2)
P1 and P2 are phrases. o is either straight or inverted.
• Translation model is built upon BTG.
• CYK-style decoder
90

Reordering
Distortion Models for Statistical Machine Translation Yaser Al-Onaizan and Kishore Papineni

Reordering scrambled English• Input: English written in foreign language order• Task: Recover English order.
• N-gram (3 ≤ N ≤ 5) language model is not suﬃcient to address word orderissue in SMT
Distortion modelPr(distance between fi and fj |fi, fj )91

Syntax-based SMT
Tree-to-String Alignment Template for Statistical Machine Translation Yang Liu, Qun Liu andShouxun Lin

Tree-string-alignment (TSA): bilingual phrase with tree over the source string
Corporation between phrases (n-grams) and syntactic constituents are not easy.

92

Reordering
Masaaki Nagata, Kuniko Saito, Kazuhide Yamamoto and Kazuteru Ohashi. A Clustered Global
Phrase Reordering Model for Statistical Machine Translationp(d|ei−1, ei, f i−1, f i)
• d = monotone ajacent, monotone gap, reverse adjacent, reverse gap• mkcls was used to cluster phrases• Jointly segmenting and aligning phrases performs better than grow-diag-ﬁnal.
(note!)

93

Discriminative SMT
Christoph Tillmann and Tong Zhang. A Discriminative Global Training Algorithm for Statistical
MT.

Block bigram model: (b1, N,) , (b2, L, b1), ...
feature: f (bi, o, bi−1)
nn n
sw (b1 , o1 ) = i=1 wT · f (bi, oi, bi−1)
arg max sw (bn1 , on1 )94

Discriminative SMT
Percy Liang, Alexandre Bouchard-Cote, Dan Klein and Ben Taskar. An End-to-End Discriminative
Approach to Machine Translation.

95

Word alignment and SMT performance
Alexander Fraser and Daniel Marcu. Semi-Supervised Training for Statistical Word Alignment.

• The AER metric is broken. Use F-measure instead• AER is not a good indicator of MT performance• F-measure is a good indicator of MT performance• Discriminatively train parameters to maximize unbalanced F-measure96Decoding
Taro Watanabe, Hajime Tsukada and Hideki Isozaki.
Hierarchical Phrase-Based Translation.

Left-to-Right Target Generation for

97

Syntax-based SMT
Michel Galley, Jonathan Graehl, Kevin Knight, Daniel Marcu, Steve DeNeefe, Wei Wang andIgnacio Thayer. Scalable Inference and Training of Context-Rich Syntactic Translation Models.

• Bigger rules are better than minimal rules.
• Incorporating phrases

98Word clustering
David Talbot and Miles Osborne. Modelling Lexical Redundancy for Machine Translation.

Clustering of source words

99

Word alignment
Benjamin Wellington, Sonjia Waxmonsky and I. Dan Melamed. Empirical Lower Bounds on the
Complexity of Translational Equivalence• Translation equivalence without gap is relatively small• Using discontinuous constituents leads to higher coverage• Many sentendce pairs cannot be hierarchically aligned without discontinuities

100

EBMT incorporating SMT techniques• End-to-End discriminative approach
The key technique is representing a candidate translation as a feature vector.
cf. (Liang et.al 2006)
perceptron, structured SVM, ... Searn might be good if we can formulate
EBMT as a sequence of classiﬁcation• Word, phrase, or dependency alignment directly connected to decoding.
For example, use alignments that are used in N-best translation candidates indiscriminative training.
cf. (Alexander Fraser 2006, Nagata et.al 2006)
101