Phrase-Based Models
Philipp Koehn
12 September 2023
Philipp Koehn Machine Translation: Phrase-Based Models 12 September 2023
1Motivation
• Word-Based Models translate words as atomic units
• Phrase-Based Models translate phrases as atomic units
• Advantages:
– many-to-many translation can handle non-compositional phrases
– use of local context in translation
– the more data, the longer phrases can be learned
• ”Standard Model”, used by Google Translate and others until about 2017
Philipp Koehn Machine Translation: Phrase-Based Models 12 September 2023
2Phrase-Based Model
• Foreign input is segmented in phrases
• Each phrase is translated into English
• Phrases are reordered
Philipp Koehn Machine Translation: Phrase-Based Models 12 September 2023
3Phrase Translation Table
• Main knowledge source: table with phrase translations and their probabilities
• Example: phrase translations for natuerlich
Translation Probability φ(¯e| ¯f)
of course 0.5
naturally 0.3
of course , 0.15
, of course , 0.05
Philipp Koehn Machine Translation: Phrase-Based Models 12 September 2023
4Real Example
• Phrase translations for den Vorschlag learned from the Europarl corpus:
English φ(¯e| ¯f) English φ(¯e| ¯f)
the proposal 0.6227 the suggestions 0.0114
’s proposal 0.1068 the proposed 0.0114
a proposal 0.0341 the motion 0.0091
the idea 0.0250 the idea of 0.0091
this proposal 0.0227 the proposal , 0.0068
proposal 0.0205 its proposal 0.0068
of the proposal 0.0159 it 0.0068
the proposals 0.0159 ... ...
– lexical variation (proposal vs suggestions)
– morphological variation (proposal vs proposals)
– included function words (the, a, ...)
– noise (it)
Philipp Koehn Machine Translation: Phrase-Based Models 12 September 2023
5Linguistic Phrases?
• Model is not limited to linguistic phrases
(noun phrases, verb phrases, prepositional phrases, ...)
• Example non-linguistic phrase pair
spass am → fun with the
• Prior noun often helps with translation of preposition
• Experiments show that limitation to linguistic phrases hurts quality
Philipp Koehn Machine Translation: Phrase-Based Models 12 September 2023
6
modeling
Philipp Koehn Machine Translation: Phrase-Based Models 12 September 2023
7Noisy Channel Model
• We would like to integrate a language model
• Bayes rule
argmaxe p(e|f) = argmaxe
p(f|e) p(e)
p(f)
= argmaxe p(f|e) p(e)
Philipp Koehn Machine Translation: Phrase-Based Models 12 September 2023
8Noisy Channel Model
• Applying Bayes rule also called noisy channel model
– we observe a distorted message R (here: a foreign string f)
– we have a model on how the message is distorted (here: translation model)
– we have a model on what messages are probably (here: language model)
– we want to recover the original message S (here: an English string e)
Philipp Koehn Machine Translation: Phrase-Based Models 12 September 2023
9More Detail
• Bayes rule
ebest = argmaxe p(e|f)
= argmaxe p(f|e) pLM(e)
– translation model p(f|e)
– language model pLM(e)
• Decomposition of the translation model
p( ¯fI
1 |¯eI
1) =
I
i=1
φ( ¯fi|¯ei) d(starti − endi−1 − 1)
– phrase translation probability φ
– reordering probability d
Philipp Koehn Machine Translation: Phrase-Based Models 12 September 2023
10Distance-Based Reordering
1 2 3 4 5 6 7
d=0
d=-3
d=2
d=1
foreign
English
phrase translates movement distance
1 1–3 start at beginning 0
2 6 skip over 4–5 +2
3 4–5 move back over 4–6 -3
4 7 skip over 6 +1
Scoring function: d(x) = α|x|
— exponential with distance
Philipp Koehn Machine Translation: Phrase-Based Models 12 September 2023
11
training
Philipp Koehn Machine Translation: Phrase-Based Models 12 September 2023
12Learning a Phrase Translation Table
• Task: learn the model from a parallel corpus
• Three stages:
– word alignment: using IBM models or other method
– extraction of phrase pairs
– scoring phrase pairs
Philipp Koehn Machine Translation: Phrase-Based Models 12 September 2023
13Word Alignment
house
the
in
stay
will
he
that
assumes
michael
michael
geht
davon
aus
dass
er
im
haus
bleibt
,
Philipp Koehn Machine Translation: Phrase-Based Models 12 September 2023
14Extracting Phrase Pairs
house
the
in
stay
will
he
that
assumes
michael
michael
geht
davon
aus
dass
er
im
haus
bleibt
,
extract phrase pair consistent with word alignment:
assumes that / geht davon aus , dass
Philipp Koehn Machine Translation: Phrase-Based Models 12 September 2023
15Consistent
ok violated ok
one
alignment
point outside
unaligned
word is fine
All words of the phrase pair have to align to each other.
Philipp Koehn Machine Translation: Phrase-Based Models 12 September 2023
16Consistent
Phrase pair (¯e, ¯f) consistent with an alignment A, if all words f1, ..., fn in ¯f that
have alignment points in A have these with words e1, ..., en in ¯e and vice versa:
(¯e, ¯f) consistent with A ⇔
∀ei ∈ ¯e : (ei, fj) ∈ A → fj ∈ ¯f
AND ∀fj ∈ ¯f : (ei, fj) ∈ A → ei ∈ ¯e
AND ∃ei ∈ ¯e, fj ∈ ¯f : (ei, fj) ∈ A
Philipp Koehn Machine Translation: Phrase-Based Models 12 September 2023
17Phrase Pair Extraction
house
the
in
stay
will
he
that
assumes
michael
michael
geht
davon
aus
dass
er
im
haus
bleibt
,
Smallest phrase pairs:
michael — michael
assumes — geht davon aus / geht davon aus ,
that — dass / , dass
he — er
will stay — bleibt
in the — im
house — haus
unaligned words (here: German comma) lead to multiple translations
Philipp Koehn Machine Translation: Phrase-Based Models 12 September 2023
18Larger Phrase Pairs
house
the
in
stay
will
he
that
assumes
michael
michael
geht
davon
aus
dass
er
im
haus
bleibt
,
michael assumes — michael geht davon aus / michael geht davon aus ,
assumes that — geht davon aus , dass ; assumes that he — geht davon aus , dass er
that he — dass er / , dass er ; in the house — im haus
michael assumes that — michael geht davon aus , dass
michael assumes that he — michael geht davon aus , dass er
michael assumes that he will stay in the house — michael geht davon aus , dass er im haus bleibt
assumes that he will stay in the house — geht davon aus , dass er im haus bleibt
that he will stay in the house — dass er im haus bleibt ; dass er im haus bleibt ,
he will stay in the house — er im haus bleibt ; will stay in the house — im haus bleibt
Philipp Koehn Machine Translation: Phrase-Based Models 12 September 2023
19Scoring Phrase Translations
• Phrase pair extraction: collect all phrase pairs from the data
• Phrase pair scoring: assign probabilities to phrase translations
• Score by relative frequency:
φ( ¯f|¯e) =
count(¯e, ¯f)
¯fi
count(¯e, ¯fi)
Philipp Koehn Machine Translation: Phrase-Based Models 12 September 2023
20EM Training of the Phrase Model
• We presented a heuristic set-up to build phrase translation table
(word alignment, phrase extraction, phrase scoring)
• Alternative: align phrase pairs directly with EM algorithm
– initialization: uniform model, all φ(¯e, ¯f) are the same
– expectation step:
∗ estimate likelihood of all possible phrase alignments for all sentence pairs
– maximization step:
∗ collect counts for phrase pairs (¯e, ¯f), weighted by alignment probability
∗ update phrase translation probabilties p(¯e, ¯f)
• However: method easily overfits
(learns very large phrase pairs, spanning entire sentences)
Philipp Koehn Machine Translation: Phrase-Based Models 12 September 2023
21Size of the Phrase Table
• Phrase translation table typically bigger than corpus
... even with limits on phrase lengths (e.g., max 7 words)
→ Too big to store in memory?
• Solution for training
– extract to disk, sort, construct for one source phrase at a time
• Solutions for decoding
– on-disk data structures with index for quick look-ups
– suffix arrays to create phrase pairs on demand
Philipp Koehn Machine Translation: Phrase-Based Models 12 September 2023
22
advanced modeling
Philipp Koehn Machine Translation: Phrase-Based Models 12 September 2023
23Weighted Model
• Described standard model consists of three sub-models
– phrase translation model φ( ¯f|¯e)
– reordering model d
– language model pLM(e)
ebest = argmaxe
I
i=1
φ( ¯fi|¯ei) d(starti − endi−1 − 1)
|e|
i=1
pLM(ei|e1...ei−1)
• Some sub-models may be more important than others
• Add weights λφ, λd, λLM
ebest = argmaxe
I
i=1
φ( ¯fi|¯ei)λφ d(starti − endi−1 − 1)λd
|e|
i=1
pLM(ei|e1...ei−1)λLM
Philipp Koehn Machine Translation: Phrase-Based Models 12 September 2023
24Log-Linear Model
• Such a weighted model is a log-linear model:
p(x) = exp
n
i=1
λihi(x)
• Our feature functions
– number of feature function n = 3
– random variable x = (e, f, start, end)
– feature function h1 = log φ
– feature function h2 = log d
– feature function h3 = log pLM
Philipp Koehn Machine Translation: Phrase-Based Models 12 September 2023
25Weighted Model as Log-Linear Model
p(e, a|f) = exp(λφ
I
i=1
log φ( ¯fi|¯ei)+
λd
I
i=1
log d(ai − bi−1 − 1)+
λLM
|e|
i=1
log pLM(ei|e1...ei−1))
Philipp Koehn Machine Translation: Phrase-Based Models 12 September 2023
26More Feature Functions
• Bidirectional alignment probabilities: φ(¯e| ¯f) and φ( ¯f|¯e)
• Rare phrase pairs have unreliable phrase translation probability estimates
→ lexical weighting with word translation probabilities
does
geht
nicht
davon
not
assume
aus
NULL
lex(¯e| ¯f, a) =
length(¯e)
i=1
1
|{j|(i, j) ∈ a}|
∀(i,j)∈a
w(ei|fj)
Philipp Koehn Machine Translation: Phrase-Based Models 12 September 2023
27More Feature Functions
• Language model has a bias towards short translations
→ word count: wc(e) = log |e|ω
• We may prefer finer or coarser segmentation
→ phrase count pc(e) = log |I|ρ
• Multiple language models
• Multiple translation models
• Other knowledge sources
Philipp Koehn Machine Translation: Phrase-Based Models 12 September 2023
28
reordering
Philipp Koehn Machine Translation: Phrase-Based Models 12 September 2023
29Lexicalized Reordering
• Distance-based reordering model is weak
→ learn reordering preference for each phrase pair
• Three orientations types: (m) monotone, (s) swap, (d) discontinuous
orientation ∈ {m, s, d}
po(orientation| ¯f, ¯e)
Philipp Koehn Machine Translation: Phrase-Based Models 12 September 2023
30Learning Lexicalized Reordering
? ?
• Collect orientation information during phrase pair extraction
– if word alignment point to the top left exists → monotone
– if a word alignment point to the top right exists→ swap
– if neither a word alignment point to top left nor to the top right exists
→ neither monotone nor swap → discontinuous
Philipp Koehn Machine Translation: Phrase-Based Models 12 September 2023
31Learning Lexicalized Reordering
• Estimation by relative frequency
po(orientation) =
¯f ¯e count(orientation, ¯e, ¯f)
o ¯f ¯e count(o, ¯e, ¯f)
• Smoothing with unlexicalized orientation model p(orientation) to avoid zero
probabilities for unseen orientations
po(orientation| ¯f, ¯e) =
σ p(orientation) + count(orientation, ¯e, ¯f)
σ + o count(o, ¯e, ¯f)
Philipp Koehn Machine Translation: Phrase-Based Models 12 September 2023
39Summary
• Phrase Model
• Training the model
– word alignment
– phrase pair extraction
– phrase pair scoring
– EM training of the phrase model
• Log linear model
– sub-models as feature functions
– lexical weighting
– word and phrase count features
• Lexicalized reordering model
• Operation sequence model
Philipp Koehn Machine Translation: Phrase-Based Models 12 September 2023