Statistical Machine Translation

​

​

​

​

Slides from Ray Mooney

Human Language Technologies

Dipartimento di Informatica

Università di Pisa

What makes a good translation

• Translators often talk about two factors we want to maximize:
• Faithfulness or fidelity
• How close is the meaning of the translation to the meaning of the original
• Even better: does the translation cause the reader to draw the same inferences as the original would have
• Fluency or naturalness
• How natural the translation is, just considering its fluency in the target language

Statistical MT: Faithfulness and Fluency formalized!

• Best-translation of a source sentence S:

​

​

• Developed by researchers originally in speech recognition at IBM
• Called the IBM model

​

The IBM model

• Those two factors might look familiar…

​

​

• Yup, it’s Bayes rule:

​

More formally

• Assume we are translating from a foreign language sentence F to an English sentence E:

F = f₁, f₂, f₃,…, f_m

• We want to find the best English sentence

Ē = e₁, e₂, e₃,…, e_n

Ē = argmax_E P(E|F)

= argmax_E P(F|E)P(E)/P(F)

= argmax_E P(F|E)P(E)

Translation Model

Language Model

The noisy channel model for MT

Fluency: P(T)

• How to measure that this sentence

That car was almost crash onto me

• is less fluent than this one:

That car almost hit me

• Answer: language models (N-grams, Neural)
• For example P(hit|almost) > P(was|almost)
• But can use any other more sophisticated model of grammar
• Advantage: this is monolingual knowledge!

Faithfulness: P(S|T)

• French: ça me plait [that me pleases]
• English:

that pleases me - most fluent

I like it

I’ll take that one

• How to quantify this?
• Intuition: degree to which words in one sentence are plausible translations of words in other sentence
• Product of probabilities that each word in target sentence would generate each word in source sentence.

​

​

Faithfulness P(S|T)

• Need to know, for every target language word, probability of it mapping to every source language word.
• How do we learn these probabilities?
• Parallel texts!
• Lots of times we have two texts that are translations of each other
• If we knew which word in Source text mapped to each word in Target text, we could just count!

Faithfulness P(S|T)

• Sentence alignment:
• Figuring out which source language sentence maps to which target language sentence
• Word alignment
• Figuring out which source language word maps to which target language word

Big Point about Faithfulness and Fluency

• Job of the faithfulness model P(S|T) is just to model “bag of words”; which words come from, say, English to Italian
• P(S|T) doesn’t have to worry about internal facts about target word order: that’s the job of P(T)
• P(T) can do bag generation: put the following words in order (from Kevin Knight)
• have programming a seen never I language better
• actual the hashing is since not collision-free usually the is less perfectly the of somewhat capacity table

​

P(T) and bag generation: the answer

“Usually the actual capacity of the table is somewhat less, since the hashing is not prefectly collision-free”

​

• How about:
• loves Mary John

Three Problems for Statistical MT

Language model

• Given an English string e, assigns P(e) by a formula s.t.
• good English string -> high P(e)
• random word sequence -> low P(e)

​

Translation model

• Given a pair of strings <f, e>, assigns P(f | e) by a formula s.t.
• <f,e> look like translations -> high P(f | e)
• <f,e> don’t look like translations -> low P(f | e)

​

Decoding algorithm

• Given a language model, a translation model, and a new sentence f … find translation e maximizing P(e) P(f | e)

Slide from Kevin Knight

The Classic Language Model: Word N-Grams

• Goal of the language model -- choose among:

​

• He is on the soccer field
• He is in the soccer field

​

• Is table the on cup the
• The cup is on the table

​

• Rice shrine
• American shrine
• Rice company
• American company

Slide from Kevin Knight

Language Model

• Use a language model for P(E)
• Classical n-gram model
• Neural (transformer) model
• Can be trained on a large, unsupervised mono-lingual corpus for the target language E.
• To capture long-distance dependencies:
• use a more sophisticated PCFG language model
• LSTM neural model
• Terabytes of web data have been used to build large 5-gram models or autoregressive models like GPT-3.

​

​

Slide from Ray Mooney

Phrase Based Machine Translation

Intuition of phrase-based translation (Koehn et al. 2003)

​

​

​

​

​

Three steps

• Group words into phrases
• Translate each phrase
• Move the phrases around

​

Slide from Ray Mooney

Phrase-Based Translation Model

P(F | E) is modeled by translating phrases in E to phrases in F.

1. First segment E into a sequence of phrases ē₁,…,ē_I
2. Then translate each phrase ē_i, into f_i, based on translation probability φ(f_i | ē_i)
3. Then reorder translated phrases based on distortion probability d(i) for the i-th phrase. (distortion = how far the phrase moved)

Slide from Ray Mooney

Translation Probabilities

• Assuming a phrase aligned parallel corpus is available or constructed that shows matching between phrases in E and F.
• Then compute (MLE) estimate of φ based on simple frequency counts:

Slide from Ray Mooney

Distortion Probability

• The probability that a phrase in position X in the original sentence moves to position Y in the translation
• Distortion: a measure of distance between positions of corresponding phrases in the 2 languages.
• distortion of phrase i as the distance between the start of the foreign phrase generated by ē_i, (a_i) and the end of the foreign phrase generated by the previous phrase ē_i-1, (b_i-1).
• Typically assume the probability of a distortion decreases exponentially with the distance of the movement.

Slide from Ray Mooney

Set 0<α<1 based on fit to phrase-aligned training data

Then set c to normalize d(i) so it sums to 1.

Sample Translation Model

Slide from Ray Mooney

verde - la

bruja - verde

Phrase-based MT

• Language model P(E)
• Translation model P(F|E)
• Model
• How to train the model
• Decoder: finding the sentence E that is most probable

Training P(F|E)

• What we mainly need to train is φ(f_j|e_i)
• Suppose we had a large bilingual training corpus
• A bitext
• In which each English sentence is paired with a Spanish sentence
• And suppose we knew exactly which phrase in Spanish was the translation of which phrase in the English
• We call this a phrase alignment
• If we had this, we could just count-and-divide:

​

​

But we don’t have phrase alignments

What we have instead are word alignments:

​

​

​

​

​

​

​

​

​

​

(actually the word alignments we have are more restricted than this, as we’ll see in two slides)

Getting phrase alignments

To get phrase alignments:

• We first get word alignments
• Then we “symmetrize” the word alignments into phrase alignments

How to Represent Word Alignments

• Word alignment: a mapping between the source words and the target words in a set of parallel sentences.
• Restriction: each foreign word comes from exactly one English word

​

​

​

​

​

• Advantage: represent an alignment by the index of the English word that the French word comes from
• Alignment above is thus 2,3,4,5,6,6,6

​

One addition: spurious words

• A word in the foreign sentence that does not align with any word in the English sentence is called a spurious word.
• We model these by pretending they are generated by an English word e₀:

More sophisticated models of alignment

One to Many Alignment

• To simplify the problem, typically assume each word in F aligns to 1 word in E (but assume each word in E may generate more than one word in F).
• Some words in F may be generated by the NULL element of E.
• Therefore, alignment can be specified by a vector A giving, for each word in F, the index of the word in E which generated it.

NULL Mary didn’t slap the green witch.

​

Maria no dió una bofetada a la bruja verde.

0 1 2 3 4 5 6

1 2 3 3 3 0 4 6 5

Computing word alignments: IBM Model 1

• For phrase-based machine translation:
• We need a word-alignment to extract a set of phrases
• A word alignment model gives us P(F,E)
• We want this to train our phrase probabilities φ(f_j|e_i) as part of P(F|E)
• A word-alignment model allows to compute the translation probability P(F|E) by summing the probabilities of all possible (l +1)^m ‘hidden’ alignments A between F and E:

​

IBM Model 1

Slide from Ray Mooney

Sample IBM Model 1 Generation

verde.

1 2 3 3 3 0 4 6 5

NULL Mary didn’t slap the green witch.

0 1 2 3 4 5 6

Maria

no

dió

una

bofetada

a

la

bruja

Slide from Ray Mooney

J

alignment

Computing P(F|E) in IBM Model 1

• Assume some length distribution P(J | E)
• Assume all alignments are equally likely. Since there are (I + 1)^J possible alignments:

• Assume t(f_x,e_y) is the probability of translating e_y as f_x, therefore:

• Determine P(F | E) by summing over all alignments:

Decoding for IBM Model 1

Goal is to find the most probable alignment given a parameterized model.

Since translation choice for each position j is independent,

the product is maximized by maximizing each term:

Training alignment probabilities

Step 1: get a parallel corpus

• Europarl
• Hansards
• Canadian parliamentary proceedings, in French and English
• Hong Kong Hansards: English and Chinese

Step 2: sentence alignment

Step 3: use EM (Expectation Maximization) to train word alignments

Step 1: Parallel corpora

Example from DE-News (8/1/1996)

​

Slide from Christof Monz

Step 2: Sentence Alignment

The old man is happy. He has fished many times. His wife talks to him. The fish are jumping. The sharks await.

​

​

Intuition:

• use length in words or chars
• together with dynamic programming
• or use a simpler MT model

El viejo está feliz porque ha pescado muchos veces. Su mujer habla con él. Los tiburones esperan.

Slide from Kevin Knight

Sentence Alignment

1. The old man is happy.
2. He has fished many times.
3. His wife talks to him.
4. The fish are jumping.
5. The sharks await.

El viejo está feliz porque ha pescado muchos veces.

Su mujer habla con él.

​

Los tiburones esperan.

Slide from Kevin Knight

Sentence Alignment

1. The old man is happy.
2. He has fished many times.
3. His wife talks to him.
4. The fish are jumping.

​

• The sharks await.

El viejo está feliz porque ha pescado muchos veces.

​

​

Su mujer habla con él.

​

​

Los tiburones esperan.

Slide from Kevin Knight

Sentence Alignment

1. The old man is happy. He has fished many times.
2. His wife talks to him.
3. The sharks await.

El viejo está feliz porque ha pescado muchos veces.

​

Su mujer habla con él.

Los tiburones esperan.

Note that unaligned sentences are thrown out, and

sentences are merged in n-to-m alignments (n, m > 0).

Slide from Kevin Knight

Step 3: word alignments

We can bootstrap alignments from a sentence-aligned bilingual corpus

using the Expectation-Maximization (EM) algorithm

​

P(A|E, F) is the probability of the alignment A given a translated pair of sentences E and F

EM for training alignment probs

… la maison … la maison bleue … la fleur …

​

​

… the house … the blue house … the flower …

All word alignments equally likely

​

All P(french-word | english-word) equally likely

Slide from Kevin Knight

EM for training alignment probs

… la maison … la maison bleue … la fleur …

​

​

… the house … the blue house … the flower …

“la” and “the” observed to co-occur frequently,

so P(la | the) is increased.

Slide from Kevin Knight

EM for training alignment probs

… la maison … la maison bleue … la fleur …

​

​

… the house … the blue house … the flower …

“house” co-occurs with both “la” and “maison”, but

P(maison | house) can be raised without limit,

while P(la | house) is limited because

“la” may align also to “the”

​

(pigeonhole principle)

Slide from Kevin Knight

EM for training alignment probs

… la maison … la maison bleue … la fleur …

​

​

… the house … the blue house … the flower …

settling down after another iteration

Slide from Kevin Knight

EM for training alignment probs

… la maison … la maison bleue … la fleur …

​

​

… the house … the blue house … the flower …

Inherent hidden structure revealed by EM training!

Slide from Kevin Knight

EM Algorithm for Word Alignment

Slide from Ray Mooney

Randomly set model parameters.

(making sure they represent legal distributions)

Until converge (i.e. parameters no longer change) do:

E Step: Compute the probability of all possible

alignments of the training data using the current model.

M Step: Use these alignment probability estimates to

re-estimate values for all of the parameters.

Note: Use dynamic programming (as in Baum-Welch)

to avoid explicitly enumerating all possible alignments

IBM Model 1 and EM

Sample EM Trace for Alignment

green house

casa verde

the house

la casa

Training

Corpus

Translation

Probabilities

Assume uniform

initial probabilities

Compute

Alignment

Probabilities

P(a, f | e)

1/3 x 1/3 = 1/9

1/3 x 1/3 = 1/9

1/3 x 1/3 = 1/9

1/3 x 1/3 = 1/9

Normalize

to get

P(a, f | e)

Slide from Ray Mooney

2/9

2/9

Example cont.

1/2

1/2

1/2

1/2

Compute

weighted

translation

counts

Normalize

rows to sum

to one to

estimate P(f | e)

Slide from Ray Mooney

Example cont.

1/2 x 1/4=1/8

Recompute

Alignment

Probabilities

P(a, f | e)

1/2 x 1/2=1/4

1/2 x 1/2=1/4

1/2 x 1/4=1/8

Normalize

to get

P(a, f | e)

Continue EM iterations until translation

parameters converge

Translation

Probabilities

Slide from Ray Mooney

1/8 + 1/4=3/8

1/4 + 1/8=3/8

IBM Model 1 and EM Algorithm

initialize t(e|f) uniformly

repeat

set count(e|f) to 0 for all e, f

set total(f) to 0 for all f

for all sentence pairs (e_s, f_s)

for all words e in e_s

total_s = 0

for all words f in f_s

total_s += t(e|f)

for all words e in e_s

for all words f in f_s

count(e|f) += t(e|f) / total_s

total(f) += t(e|f) / total_s

for all f where total(f) != 0

for all e in count(e|f)

t(e|f) = count(e|f) / total(f)

until convergence

Higher IBM Models

• Only IBM Model 1 has global maximum
• training of a higher IBM model builds on previous model
• Computationally biggest change in Model 3
• exhaustive count collection becomes computationally too expensive
• sampling over high probability alignments is used instead

Phrase-based Translation Model

Phrase-based Translation Model

Benefits of PBMT

• Many-to-many translation can handle non-compositional phrases
• Use of local context in translation
• The more data, the longer phrases can be learned

Phrase Translation Table

Phrase translations for den Vorschlag

Phrase Alignment

Phrase Alignments from Word Alignments

• Alignment algorithms produce one to many word translations
• We know that words do not map one-to-one in translations
• Better to map ‘phrases’, i.e. sequences of words, to phrases and probabilistically reorder them in translation
• Combine E→F and F →E word alignments to produce a phrase alignment

Phrase Alignment Example

Spanish to English

Slide from Ray Mooney

Phrase Alignment Example

English to Spanish

Slide from Ray Mooney

Phrase Alignment Example

Intersection

Slide from Ray Mooney

Symmetrizing

Add alignments from union to intersection

to produce a consistent phrase alignment

Slide from Ray Mooney

Consistent with word alignment

Word Alignment Induced Phrases

(Maria no, Mary did not), (no dio una bofetada, did not slap), (dio una bofetada a la, slap the), (bruja verde, green witch)

(Maria no dio una bofetada, Mary did not), (no dio una bofetada a la, did not slap the), (a la bruja verde, the green witch)

Phrase Translation Table

Sample phrase table from Moses (en-it)

f e φ(f|e) lex(f|e) φ(e|f) lex(e|f) Alignments (F-E)

! it definitively correct that ||| , che conferma ||| 0.0136986 5.6952e-07 1 4.68166e-17 ||| 0-0 4-1 1-2 ||| 73 1

! it depends ||| sono solo ||| 0.00107991 2.85796e-05 1 5.63319e-11 ||| 1-0 2-1 ||| 926 1

! it does not bode at all ||| , che non lascia presagire nulla di ||| 1 2.58282e-09 0.5 1.60281e-13 ||| 0-0 1-1 2-2 3-2 4-3 4-4 4-5 5-5 6-5 ||| 1 2

! it does not bode at all ||| , che non lascia presagire nulla ||| 1 2.20735e-08 0.5 1.60281e-13 ||| 0-0 1-1 2-2 3-2 4-3 4-4 4-5 5-5 6-5 ||| 1 2

! it does not ||| , che non ||| 0.000334448 0.000259527 1 1.16381e-08 ||| 0-0 1-1 2-2 3-2 ||| 2990 1

! it has become a ||| , che è diventata una ||| 0.2 6.20953e-07 1 3.72893e-08 ||| 0-0 1-1 1-2 2-2 3-3 4-4 ||| 5 1

! it has become ||| , che è diventata ||| 0.0588235 2.67744e-06 1 7.12714e-08 ||| 0-0 1-1 1-2 2-2 3-3 ||| 17 1

! it has not been implemented yet ||| e non è ancora stato applicato ||| 1 3.69476e-07 1 1.233e-10 ||| 0-0 3-1 1-2 2-2 6-3 4-4 5-5 ||| 1 1

! it has not ||| e non è ||| 0.000823045 0.000251293 1 4.8038e-08 ||| 0-0 3-1 1-2 2-2 ||| 1215 1

! it has ||| ! ||| 5.86751e-05 0.755472 0.5 1.82129e-05 ||| 0-0 ||| 17043 2

! it has ||| , che è ||| 0.000127307 7.00774e-05 0.5 1.41342e-07 ||| 0-0 1-1 1-2 2-2 ||| 7855 2

' access to cheap medicines ||| di accedere a farmaci a basso prezzo ||| 1 2.18888e-07 1 5.95807e-07 ||| 0-0 2-0 1-1 2-2 4-3 3-4 3-5 3-6 ||| 1 1

' access to credit ||| l' accesso al credito da parte ||| 1 5.13669e-09 0.333333 2.9826e-05 ||| 0-0 1-0 1-1 2-2 3-3 ||| 1 3

' access to credit ||| l' accesso al credito da ||| 1 2.01676e-06 0.333333 2.9826e-05 ||| 0-0 1-0 1-1 2-2 3-3 ||| 1 3

' access to credit ||| l' accesso al credito ||| 0.030303 0.000396314 0.333333 2.9826e-05 ||| 0-0 1-0 1-1 2-2 3-3 ||| 33 3

' access to satellite TV , ||| canali censurati ||| 0.166667 2.4734e-10 0.5 1.35061e-17 ||| 0-1 ||| 6 2

​

​

​

Decoding

Translation model for PBMT

Let’s look at a simple example with no distortion

Translation Options

Look up possible phrase translations

• many different ways to segment words into phrases
• many different ways to translate each phrase

Hypothesis Expansion

Start with empty hypothesis

• e: no English words
• f: no foreign words covered
• p: probability 1

e:

f: ---

p: 1

Hypothesis Expansion

Pick translation option

Create hypothesis

• e: add English phrase Mary
• f: first foreign word covered
• p: 0.534

e:

f: ---------

p: 1

e: Mary

f: *--------

p: .534

Hypothesis Expansion

Add another hypothesis

e:

f: ---------

p: 1

e: witch

f: -------*-

p: .182

e: Mary

f: *--------

p: .534

Hypothesis Expansion

Add further hypothesis

e:

f: ---------

p: 1

e: witch

f: -------*-

p: .182

e: Mary

f: *--------

p: .534

e: slap

f: *-**----

p: .043

Hypothesis Expansion

... until all foreign words covered

• and best hypothesis that covers all foreign words
• backtrack to read translation

e:

f: ---------

p: 1

e: witch

f: -------*-

p: .182

e: Mary

f: *--------

p: .534

e: slap

f: *-**----

p: .043

e: did not

f: **------

p: .043

e: slap

f: *****--

p: .015

e: the

f: ******--

p: .0942

e: green witch

f: ********

p: .0027

Hypothesis Expansion

Adding more hypothesis

Explosion of search space

e:

f: ---------

p: 1

e: witch

f: -------*-

p: .182

e: Mary

f: *--------

p: .534

e: slap

f: *-**----

p: .043

e: did not

f: **------

p: .043

e: slap

f: *****--

p: .015

e: the

f: ******--

p: .0942

e: green witch

f: ********

p: .0027

Explosion of search space

• Number of hypotheses is exponential with respect to sentence length
• Decoding is NP-complete [Knight, 1999]
• Need to reduce search space
• risk free: hypothesis recombination
• risky: histogram/threshold pruning

Hypothesis Recombination

Different paths to the same translation

Hypothesis Recombination

Different paths to the same partial translation

Combine paths

• drop weaker path
• keep pointer from weaker path (for lattice generation)

Hypothesis Recombination

Recombined hypotheses do not have to match completely

No matter what is added, weaker path can be dropped, if:

• last two English words match (matters for language model)
• foreign word coverage vectors match (affects future path)

Hypothesis Recombination

• Recombined hypotheses do not have to match completely
• No matter what is added, weaker path can be dropped, if:
• last two English words match (matters for language model)
• foreign word coverage vectors match (affects future path)
• Combine paths

Pruning

• Hypothesis recombination is not sufficient
• Heuristically discard weak hypotheses early
• Organize Hypothesis in stacks, e.g. by
• same foreign words covered
• same number of foreign words covered
• same number of English words produced
• Compare hypotheses in stacks, discard bad ones
• histogram pruning: keep top n hypotheses in each stack (e.g., n=100)
• threshold pruning: keep hypotheses that are at most times the cost of best hypothesis in stack (e.g., = 0.001)

Hypothesis Stack

Organization of hypothesis into stacks

• here: based on number of foreign words translated
• during translation all hypotheses from one stack are expanded
• expanded Hypotheses are placed into stacks

Comparing Hypothesis

Comparing hypotheses with same number of foreign words covered

​

​

​

​

​

​

​

Hypothesis that covers easy part of sentence is preferred

Need to consider future cost of uncovered parts

Future Cost Estimation: Step 2

Estimate cost to translate remaining part of input

Step 1: estimate future cost for each translation option

• look up translation model cost
• estimate language model cost (no prior context)
• ignore reordering model cost

→ LM * TM = p(to) * p(the|to) * p(to the|a la)

a la

to the

Future Cost Estimation: Step 2

Step 2: find cheapest cost among translation options

a la

to the

to

the

cost: 0.0372

cost: 0.0299

cost: 0.0354

Future Cost Estimation: Step 3

Step 3: find cheapest future cost path for each span

• can be done efficiently by dynamic programming
• future cost for every span can be pre-computed

Application

Use future cost estimates when pruning hypotheses

For each uncovered contiguous span:

• look up future costs for each maximal contiguous uncovered span
• add to actually accumulated cost for translation option for pruning

Limits on Reordering

• Reordering may be limited
• Monotone Translation: No reordering at all
• Only phrase movements of at most n words
• Reordering limits speed up search (polynomial instead of exponential)
• Current reordering models are weak, so limits improve translation quality

Sample N-Best List

Translation ||| Reordering LM TM WordPenalty ||| Score

this is a small house ||| 0 -27.0908 -1.83258 -5 ||| -28.9234

this is a little house ||| 0 -28.1791 -1.83258 -5 ||| -30.0117

it is a small house ||| 0 -27.108 -3.21888 -5 ||| -30.3268

it is a little house ||| 0 -28.1963 -3.21888 -5 ||| -31.4152

this is an small house ||| 0 -31.7294 -1.83258 -5 ||| -33.562

it is an small house ||| 0 -32.3094 -3.21888 -5 ||| -35.5283

this is an little house ||| 0 -33.7639 -1.83258 -5 ||| -35.5965

this is a house small ||| -3 -31.4851 -1.83258 -5 ||| -36.3176

this is a house little ||| -3 -31.5689 -1.83258 -5 ||| -36.4015

it is an little house ||| 0 -34.3439 -3.21888 -5 ||| -37.5628

it is a house small ||| -3 -31.5022 -3.21888 -5 ||| -37.7211

this is an house small ||| -3 -32.8999 -1.83258 -5 ||| -37.7325

it is a house little ||| -3 -31.586 -3.21888 -5 ||| -37.8049

this is an house little ||| -3 -32.9837 -1.83258 -5 ||| -37.8163

the house is a little ||| -7 -28.5107 -2.52573 -5 ||| -38.0364

the is a small house ||| 0 -35.6899 -2.52573 -5 ||| -38.2156

Evaluation

Evaluating MT

• Human subjective evaluation is the best but is time-consuming and expensive.
• Automated evaluation comparing the output to multiple human reference translations is cheaper and correlates with human judgements.

Slide from Ray Mooney

Human Evaluation of MT

Ask humans to estimate MT output on several dimensions.

• Fluency: Is the result grammatical, understandable, and readable in the target language.
• Fidelity: Does the result correctly convey the information in the original source language.
• Adequacy: Human judgment on a fixed scale.
• Bilingual judges given source and target language.
• Monolingual judges given reference translation and MT result.
• Informativeness: Monolingual judges must answer questions about the source sentence given only the MT translation (task-based evaluation).

Slide from Ray Mooney

Computer-Aided Translation Evaluation

Edit cost: Measure the number of changes that a human translator must make to correct the MT output.

• Number of words changed
• Amount of time taken to edit
• Number of keystrokes needed to edit

Slide from Ray Mooney

Automatic Evaluation of MT

Collect one or more human reference translations of the source.

Compare MT output to these reference translations.

Score result based on similarity to the reference translations.

• BLEU
• NIST
• TER
• METEOR

Slide from Ray Mooney

BLEU (Bilingual Evaluation Understudy)

Determine number of n-grams of various sizes that the MT output shares with the reference translations.

Compute a modified precision measure of the n-grams in MT result.

​

https://en.wikipedia.org/wiki/BLEU

Slide from Ray Mooney

Multiple Reference Translations

Slide from Bonnie Dorr

BLEU Example

Cand 1: Mary no slap the witch green

Cand 2: Mary did not give a smack to a green witch.

Ref 1: Mary did not slap the green witch.

Ref 2: Mary did not smack the green witch.

Ref 3: Mary did not hit a green sorceress.

Cand 1 Unigram Precision: 5/6

Slide from Ray Mooney

BLEU Example

Cand 1 Bigram Precision: 1/5

Cand 1: Mary no slap the witch green.

Cand 2: Mary did not give a smack to a green witch.

Ref 1: Mary did not slap the green witch.

Ref 2: Mary did not smack the green witch.

Ref 3: Mary did not hit a green sorceress.

Slide from Ray Mooney

BLEU Example

Clip match count of each n-gram to maximum

count of the n-gram in any single reference

translation

Ref 1: Mary did not slap the green witch.

Ref 2: Mary did not smack the green witch.

Ref 3: Mary did not hit a green sorceress.

Cand 1: Mary no slap the witch green.

Cand 2: Mary did not give a smack to a green witch.

Cand 2 Unigram Precision: 7/10

Slide from Ray Mooney

BLEU Example

Ref 1: Mary did not slap the green witch.

Ref 2: Mary did not smack the green witch.

Ref 3: Mary did not hit a green sorceress.

Cand 2 Bigram Precision: 3/9 =1/3

Cand 1: Mary no slap the witch green.

Cand 2: Mary did not give a smack to a green witch.

Slide from Ray Mooney

Modified N-Gram Precision

Average n-gram precision over all n-grams up to size N (typically 4) using geometric mean.

Cand 1:

Cand 2:

Slide from Ray Mooney

Brevity Penalty

• Not easy to compute recall to complement precision since there are multiple alternative gold-standard references and don’t need to match all of them.
• Instead, use a penalty for translations that are shorter than the reference translations.
• Define effective reference length, r, for each sentence as the length of the reference sentence with the largest number of n-gram matches. Let c be the candidate sentence length.

Slide from Ray Mooney

BLEU Score

• Final BLEU Score: BLEU = BP × p

Cand 1: Mary no slap the witch green.

Best Ref: Mary did not slap the green witch.

​

​

​

Cand 2: Mary did not give a smack to a green witch.

Best Ref: Mary did not smack the green witch.

Slide from Ray Mooney

BLEU Score Issues

• BLEU has been shown to correlate with human evaluation when comparing outputs from different SMT systems.
• However, it does not correlate with human judgments when comparing SMT systems with manually developed MT (Systran) or MT with human translations.
• Other MT evaluation metrics have been proposed that claim to overcome some of the limitations of BLEU.

Slide from Ray Mooney

BLEU Tends to Predict Human Judgments

slide from G. Doddington

(variant of BLEU)

Syntax-Based Statistical Machine Translation

• SMT methods adopting a syntactic transfer approach.
• Improved results demonstrated for translating between more distant language pairs, e.g. Chinese/English.

Slide from Ray Mooney

Synchronous Grammar

• Multiple parse trees in a single derivation.
• Used by (Chiang, 2005; Galley et al., 2006).
• Describes the hierarchical structures of a sentence and its translation, and also the correspondence between their sub-parts.

Slide from Ray Mooney

Synchronous Productions

• Has two RHSs, one for each language

X 🡪 X 是甚麼 / What is X

Chinese:

English:

Slide from Ray Mooney

Syntax-Based MT Example

Input: 俄亥俄州的首府是甚麼？

Slide from Ray Mooney

Syntax-Based MT Example

X

X

Input: 俄亥俄州的首府是甚麼？

Slide from Ray Mooney

Syntax-Based MT Example

What is X

X

X

X 是甚麼

Input: 俄亥俄州的首府是甚麼？

X 🡪 X 是甚麼 / What is X

Slide from Ray Mooney

Syntax-Based MT Example

X 首府

What is X

the capital X

X

X

X 是甚麼

Input: 俄亥俄州的首府是甚麼？

X 🡪 X 首府 / the capital X

Slide from Ray Mooney

Syntax-Based MT Example

X 首府

What is X

the capital X

of X

X

X

X 是甚麼

X 的

Input: 俄亥俄州的首府是甚麼？

X 🡪 X 的 / of X

Slide from Ray Mooney

Syntax-Based MT Example

X 首府

What is X

the capital X

of X

Ohio

X

俄亥俄州

X

X 是甚麼

X 的

Input: 俄亥俄州的首府是甚麼？

X 🡪 俄亥俄州 / Ohio

Slide from Ray Mooney

Syntax-Based MT Example

X 首府

What is X

the capital X

of X

Ohio

X

俄亥俄州

X

X 是甚麼

X 的

Input: 俄亥俄州的首府是甚麼？

Output: What is the capital of Ohio?

Slide from Ray Mooney

Synchronous Derivations and Translation Model

Slide from Ray Mooney

Use of Dependency parsing

• Restrict phrases to those corresponding to parse subtrees
• Use parse trees to learn reordering of source language to make it more similar to target language and train a PBMT system on the rearranged parallel corpus.
• Attardi and Micheli-Barone. 2013. https://www.aclweb.org/anthology/W13-2220.pdf
• Visweswariah et al., 2011

MERT

Minimum Error Rate Training

• No longer use the noisy channel model
• Noisy channel model is not trained to directly minimize the final MT evaluation metric, e.g. BLEU.
• MERT: train a logistic regression classifier to directly minimize the final evaluation metric on the training corpus by using various features of a translation.
• Language model: P(E)
• Translation mode: P(F | E)
• Reverse translation model: P(E | F)

Slide from Ray Mooney

Conclusions

• Statistical PBMT
• Phrase table: derived by symmetrizing word alignments on a sentence-aligned parallel corpus
• Statistical phrase translation model P(F | E)
• Language model P(E)
• All these combined in a logistic regression classifier trained to minimize error rate.
• Research on: syntax based SMT
• Next: Neural Machine Translation

Slide from Ray Mooney