Machine Translation

W266: Natural Language Processing

The plan...

• Announcements
• Classical MT
• Noisy-Channel model
• Word-based MT / IBM models
• Phrase-based MT
• MT Evaluation
• Neural MT
• Word alignments beyond MT

Back in the old days...

Classical MT

1. Direct translation model
1. Some local reordering included
2. i.e. I am eating the apple. -> Je mange la pomme.
2. Transfer model
• Transform the parse tree
• i.e. English to Spanish; NP -> Adjective Noun to NP -> Noun Adjective
• i.e. The green witch -> La bruja verde
3. Interlingua model
• Extract meaning
• Event-based representation

Vauquois Triangle

(Vauquois, 1968)

MT is *really* hard

• Why?

MT is *really* hard

• Division of words (i.e. Eskimo)
• Syntax differences
• SVO (like English) vs. SOV (like Japanese)
• Placement of adjectives
• Head marking
• The man's house vs. "the man house-his" (in Hungarian)
• Referential density
• Lack of vs presence of pronouns
• Homonyms
• bass (the fish? the instrument?)

MT is *really* hard

• Polysemy
• I know vs. Je connais or Je sais (in French)
• Gender
• La pomme
• Lack of similar context
• Brother vs "older/younger brother" (in Chinese/Japanese)

Which one seems best?

• Japanese: "fukaku hansei shite orimasu"
• English:
• "I'm sorry"
• "We are deeply reflecting (on our past behavior, and what we did wrong, and how to avoid the problem next time)"
• Hebrew: "adonai roi" (the Lord is my shepherd)
• Suppose a culture has no sheep...
• "the Lord will look after me"
• "the Lord is for me like somebody who looks after animals with cotton-like hair"
• Faithfulness vs. Fluency

​

Statistical MT

​

End goal: evaluate P(hello | bonjour)

The Noisy Channel Model

For Machine Translation, translate f → e

P(e) : source (language model)

P(f|e) : channel (translation model)

​

“...one naturally wonders if the problem of translation could conceivably be treated as a problem in cryptography. When I look at an article in Russian, I say: ‘This is really written in English, but it has been coded in some strange symbols. I will now proceed to decode.’ ”

• Warren Weaver, 1947

​

​

IBM Alignment Models

Generative process e → f with P(f | e)

Latent variable model for P(f | e)

• P(f | e) = P(f | a, e) P(a | e)
• Hidden variable: alignment a_i
• Parameters: t(f | e_ai)

Use Bayes’ rule to compute P(e | f)

​

​

Decode using beam search over P(f | e) P(e)

p(a | e)

t(f | e)

Generation

(never used)

IBM Alignment Models: Inference

Generative process e → f with P(f | e)

Latent variable model for P(f | e)

• P(f | e) = P(f | a, e) P(a | e)
• Hidden variable: alignment a_i
• Parameters: t(f | e_ai)

Use Bayes’ rule to compute P(e | f)

​

​

Decode using beam search over P(f | e) P(e)

Generation

(never used)

Inference

p(a | e)

t(f | e)

What is P(f | e) ?

IBM Model 1

Noisy-channel translation f → e

Model: generative process e → f with P(f | e)

1. Sample a length m ∼ Q(m)
• Distribution Q(m) doesn’t matter!
2. Sample an alignment {a_i} for i = 1,...,m
3. Sample a word f_i from t(f | e_ai)

m = 3

IBM Model 1

Noisy-channel translation f → e

Model: generative process e → f with P(f | e)

• Sample a length m ∼ Q(m)
• Distribution Q(m) doesn’t matter!
• Sample an alignment {a_i} for i = 1,...,m
• a_i ∼ Uniform(0, ℓ + 1)
• a_i independent
• Sample a word f_i from t(f | e_ai)

m = 3

a₁ = 1

IBM Model 1

Noisy-channel translation f → e

Model: generative process e → f with P(f | e)

• Sample a length m ∼ Q(m)
• Distribution Q(m) doesn’t matter!
• Sample an alignment {a_i} for i = 1,...,m
• a_i ∼ Uniform(0, ℓ + 1)
• a_i independent
• Sample a word f_i from t(f | e_ai)

m = 3

a₁ = 1

a₂ = 3

IBM Model 1

Noisy-channel translation f → e

Model: generative process e → f with P(f | e)

• Sample a length m ∼ Q(m)
• Distribution Q(m) doesn’t matter!
• Sample an alignment {a_i} for i = 1,...,m
• a_i ∼ Uniform(0, ℓ + 1)
• a_i independent
• Sample a word f_i from t(f | e_ai)

m = 3

a₁ = 1

a₂ = 3

a₃ = 2

IBM Model 1

Noisy-channel translation f → e

Model: generative process e → f with P(f | e)

• Sample a length m ∼ Q(m)
• Distribution Q(m) doesn’t matter!
• Sample an alignment {a_i} for i = 1,...,m
• a_i ∼ Uniform(0, ℓ + 1)
• a_i independent
• Sample a word f_i from t(f | e_ai)
• t(f | e) tabulated

m = 3

t(la | the)

IBM Model 1

Noisy-channel translation f → e

Model: generative process e → f with P(f | e)

• Sample a length m ∼ Q(m)
• Distribution Q(m) doesn’t matter!
• Sample an alignment {a_i} for i = 1,...,m
• a_i ∼ Uniform(0, ℓ + 1)
• a_i independent
• Sample a word f_i from t(f | e_ai)
• t(f | e) tabulated

m = 3

t(maison | house)

IBM Model 1

Noisy-channel translation f → e

Model: generative process e → f with P(f | e)

• Sample a length m ∼ Q(m)
• Distribution Q(m) doesn’t matter!
• Sample an alignment {a_i} for i = 1,...,m
• a_i ∼ Uniform(0, ℓ + 1)
• a_i independent
• Sample a word f_i from t(f | e_ai)
• t(f | e) tabulated

m = 3

t(bleue | blue)

IBM Model 1

Noisy-channel translation f → e

Model: generative process e → f with P(f | e)

• Sample a length m ∼ Q(m)
• Distribution Q(m) doesn’t matter!
• Sample an alignment {a_i} for i = 1,...,m
• a_i ∼ Uniform(0, ℓ + 1)
• a_i independent
• Sample a word f_i from t(f | e_ai)
• t(f | e) tabulated

IBM Model 1

Noisy-channel translation f → e

Model: generative process e → f with P(f | e)

• Sample a length m ∼ Q(m)
• Distribution Q(m) doesn’t matter!
• Marginalize alignment {a_i} for i = 1,...,m
• a_i ∼ Uniform(0, ℓ + 1)
• a_i independent
• Sample a word f_i from t(f | e_ai)
• t(f | e) tabulated

IBM Model 1: Inference

Noisy-channel translation f → e

Model: generative process e → f with P(f | e)

• Closed-form expression for P(f | e)
• As long as t(f | e) known
• Alignments are implicit (summed out)

Use Bayes’ rule to compute P(e | f)

​

​

Decode using beam search over P(f | e) P(e)

Training Model 1

IBM Alignment Models: Training

Generative process e → f with P(f | e)

Latent variable model for P(f | e)

• P(f | e) = P(f | a, e) P(a | e)
• Hidden variable: alignment a_i
• Parameters: t(f | e_ai)

Observe (f, e). Need to infer parameters!

But, a_i unobserved: use EM

• E-step: infer p(a_i | f, e)
• M-step: estimate t(f | e_ai)

Generation

(never used)

Training

p(a | e)

t(f | e)

IBM Model 1: Training

Observe (f, e). Need to infer parameters!

But, a_i unobserved: use EM

• E-step: infer p(a_i | f, e)
• M-step: estimate t(f | e_ai)

​

​

IBM Model 1: Training

Observe (f, e). Need to infer parameters!

But, a_i unobserved: use EM

• E-step: infer p(a_i | f, e)
• M-step: estimate t(f | e_ai)

​

​

IBM Model 1: Training

Observe (f, e). Need to infer parameters!

But, a_i unobserved: use EM

• E-step: infer p(a_i | f, e)
• M-step: estimate t(f | e_ai)

​

​

​

​

t(w_f | w_e) = count(w_f, w_e) / count(w_e)

​

​

Better models?

Model 1 Limitations

Bag-of-words model! (yuck)

• P(f | e) doesn’t depend sequence e
• Thus, P(e | f) relies on LM P(e) for fluency
• Problems?

Alignments all independent

No many-to-one alignments, or many-to-many

• Problems?

Word-factored - problems?

​

Model 1 vs. Model 2

Model 1: “bag of words”

Generative process e → f with P(f | e)

1. Sample a length m ∼ Q(m)
• Distribution Q(m) doesn’t matter!
2. Sample an alignment {a_i} for i = 1,...,m
• a_i ∼ Uniform(0, ℓ + 1)
• a_i independent
3. Sample a word f_i from t(f | e_ai)
• t(f | e) tabulated

Model 2: distortion probabilities

Generative process e → f with P(f | e)

1. Sample a length m ∼ Q(m)
• Distribution Q(m) doesn’t matter!
2. Sample an alignment {a_i} for i = 1,...,m
• a_i ∼ a(a_i| i, ℓ, m)
• a_i independent
3. Sample a word f_i from t(f | e_ai)
• t(f | e) tabulated

HMM Model

HMM: sequence model over alignments

Generative process e → f with P(f | e)

1. Sample a length m ∼ Q(m)
• Distribution Q(m) doesn’t matter!
2. Sample an alignment {a_i} for i = 1,...,m
• a_i ∼ a(a_i| a_i-1)
• a_i form Markov chain
3. Sample a word f_i from t(f | e_ai)
• t(f | e) tabulated

Model 2: distortion probabilities

Generative process e → f with P(f | e)

• Sample a length m ∼ Q(m)
• Distribution Q(m) doesn’t matter!
• Sample an alignment {a_i} for i = 1,...,m
• a_i ∼ a(a_i| i, ℓ, m)
• a_i independent
• Sample a word f_i from t(f | e_ai)
• t(f | e) tabulated

Phrase-Based MT

Problem: words are not independent!

• Common patterns: [eat apples] ↔ [manger des pommes]
• Idiomatic or non-compositional: [kick the bucket] ↔ [casser sa pipe]

Idea: translate in larger chunks - phrase units

• Pre-segment input(s)
• Translate each segment
• (inference) beam decode

Phrase-Based MT

Generate phrases by heuristics or ML

​

​

​

​

​

• Variable length
• No linguistic constraints

Koehn (2009) Statistical Machine Translation

Evaluation Metrics: BLEU

BLEU motivation

​

Why is an automated eval important for machine translation?

What makes automated evaluation hard?

What makes us think that evaluation is possible?

BLEU motivation

Why is an automated eval important for machine translation?

• Quick turn around
• Cheap
• Consistency

What makes automated evaluation hard?

What makes us think that evaluation is possible?

Evaluation seems possible!

BLEU: http://aclweb.org/anthology/P/P02/P02-1040.pdf (IBM, 2002)

BLEU formulation

Idea #1: Precision

How many of the words in the candidate translation occur in a reference?

​

BLEU formulation

Idea #1: Precision

How many of the words in the candidate translation occur in a reference?

​

Problem:

Candidate: the the the

Reference: the cow jumped over the moon

Precision?

BLEU formulation

Idea #2: Max credit

How many of the words in the candidate translation occur in a reference?

(Cap numerator of precision by # of times word seen in reference.)

Better:

Candidate: the the the the the the

Reference: the cow jumped over the moon

Precision?

BLEU formulation

Idea #3: Unigrams are too small of a unit

How many of the words in the candidate translation occur in a reference?

(Cap numerator of precision by # of times word seen in reference.)

(<= 4-grams)

​

Smaller n-grams stop correlating with monolingual judgements on fluency.

BLEU formulation

Idea #4: Brevity Penalty

How many of the words in the candidate translation occur in a reference?

(Cap numerator of precision by # of times word seen in reference.)

(<= 4-grams)

(Trivial translations are likely bad)

Penalty = e^(min(0, 1 - ref_len / mt_len))

BLEU formulation

Extensions:

• Corpus level
• Multiple reference sentences

​

How long to optimize for?

• Compare references against one another is a good measure of benchmark usefulness

Evaluation seems possible!

BLEU: http://aclweb.org/anthology/P/P02/P02-1040.pdf (IBM, 2002)

The Future: Neural MT

Or maybe the present?

Google’s GNMT system serves 16 language pairs: https://translate.google.com/

End-to-End Sequence-to-Sequence models:

• Input: source language sentence
• Output: target language sentence

​

​

la

maison

bleue

</s>

<s>

the

blue

the

blue

house

house

</s>

Attention Models

Problem: fixed-length vector representation

• Bad for long sentences!

Idea: allow model to look back at input sequence during decoding

• Acts as a sort of “memory”
• Cognitively plausible?
• Bonus: get alignments! (or something like them)

Image by Chris Olah and Shan Carter

Attention Models: Example

Attention Demo

-> go here

Convolutional Neural Networks

https://developer.apple.com/library/content/documentation/Performance/Conceptual/vImage/ConvolutionOperations/ConvolutionOperations.html

ByteNet: Convolution over characters

Neural Machine Translation in Linear* Time, Kalchbrenner et al, March 2017

ByteNet: Language Model

ByteNet: Translation Model

Word Alignments: Cross-Lingual Parsing

Cross-Lingual Parsing

Neural MT doesn’t need explicit alignment model.

But: alignments useful for domain transfer!

Input: English parser

Input: parallel sentences (f, e)

Output: parsed foreign sentences

Source: “Bootstrapping Parsers via Syntactic Projection across Parallel Texts” (Hwa et al. 2005)

​

Cross-Lingual Parsing

(almost) Equivalent to matrix multiplication:

​

​

​

​

If interested in typed edges, can treat E as 3rd-rank tensor

Normalize columns of E^t, then DMST to decode

​

Source: Multilingual Projection for Parsing Truly Low-Resource Languages (Agic, et al. 2016)