Breaking Down the Language Barrier with Statistical Machine Translation

Breaking down the Language Barrier with
Statistical Machine Translation:2) Alignment/Phrase Extraction
http://www.phontron.com/class/sentan2014
Advanced Research Seminar I/III
Graham Neubig
2014-1-30

1Breaking Down the Language Barrier with Statistical Machine Translation

How does machine translation work?
●

Divide sentence into translatable patterns, reorder,
combineToday I will give a lecture on machine translation .
Today
I will give
今日は、 を行います

Today
今日は、

a lecture onの講義

machine translation
機械翻訳

machine translation
機械翻訳

a lecture onの講義

I will give
を行います

.
。

.
。

今日は、機械翻訳の講義を行います。
2

Breaking Down the Language Barrier with Statistical Machine Translation

Problem●

There are millions of possible translations!
花子 が 太郎 に 会った
Hanako met Taro
Hanako met to Taro
Hanako ran in to Taro
Taro met Hanako
The Hanako met the Taro●How do we tell which is better?
3

Breaking Down the Language Barrier with Statistical Machine Translation

Statistical Machine Translation●

Translation model:P(“ 今日” |“today”) = highP(“ 今日 は 、” |“today”) = medium

P(“ 昨日” |“today”) = lowP(●

Reordering Model:

鶏がchicken eats
●

鶏

食べる

)=high

P(

を

eats

食べる

鶏

)=highchicken

P(

が

eats

食べる

)=low

chickenLanguage Model:P( “Taro met Hanako” )=highP( “the Taro met the Hanako” )=low
4

Breaking Down the Language Barrier with Statistical Machine Translation

Alignment●

Find the correspondences between words

太郎 が 花子 を 訪問 した 。

太郎 が 花子 を 訪問 した 。

taro visited hanako .

taro visited hanako .

●Unsupervised probabilistic models are most common
日本語
日本語
日本語
日本語
日本語
日本語
日本語
日本語
日本語
日本語
日本語
日本語
EnglishEnglishEnglishEnglishEnglishEnglishEnglishEnglishEnglishEnglishEnglishEnglishP( 花子 |hanako) = 0.99
P( 太郎 |taro) = 0.97
P(visited| 訪問 ) = 0.46
P(visited| した ) = 0.04
P( 花子 |taro) = 0.0001

5

Breaking Down the Language Barrier with Statistical Machine Translation

Assignment●

I have given you code that:
1: Calculates the Dice coefficient for each pair of words● 2: Decides the alignment in each direction using Dicecoefficient statistics and the Max Score criterion● 3: Combines these two alignments using the“intersection” heuristic● 4: Measures alignment F-measure●●

You should
1: Measure the alignment accuracy on the provided
data● 2: Make one change that improves the accuracy●

6Breaking Down the Language Barrier with Statistical Machine Translation

Heuristic Alignment

Breaking Down the Language Barrier with Statistical Machine Translation

How Do we Learn Alignments?
●

For example, we go to an Italian restaurant w/
Japanese menu
チーズムースMousse di formaggi
タリアテッレ ４種のチーズソース
Tagliatelle al 4 formaggi
本日の鮮魚
Pesce del giorno
鮮魚のソテー お米とグリーンピース添え
Filetto di pesce su “Risi e Bisi”
ドルチェとチーズ
Dolce e Formaggi●

Try to find the patterns!

8Breaking Down the Language Barrier with Statistical Machine Translation

How Do we Learn Alignments?
●

For example, we go to an Italian restaurant w/
Japanese menu
チーズムースMousse di formaggi
タリアテッレ ４種のチーズソース
Tagliatelle al 4 formaggi
本日の鮮魚
Pesce del giorno
鮮魚のソテー お米とグリーンピース添え
Filetto di pesce su “Risi e Bisi”
ドルチェとチーズ
Dolce e Formaggi●

Try to find the patterns!

9Breaking Down the Language Barrier with Statistical Machine Translation

Co-occurrence●

Simplest measure of correlation: co-occurrence

チーズ ムース
Mousse di formaggi
タリアテッレ ４ 種 の チーズ ソース
Tagliatelle al 4 formaggi
本日 の 鮮魚
Pesce del giorno
鮮魚 の ソテー お 米 と グリーンピース 添え
Filetto di pesce su “Risi e Bisi”
ドルチェ と チーズ
Dolce e Formaggi

Occurrencec( チーズ ) = 3c( の ) = 3c( と ) = 2…

c(formaggi) = 3c(pesce) = 2
c(e) = 2...

Co-occurrencec( チーズ , formaggi) = 3
c( チーズ , mousse) = 1
c( チーズ , di) = 1
c( チーズ , tagliatelle) = 1…

Breaking Down the Language Barrier with Statistical Machine Translation

Problem with Co-occurrence●

Co-occurrence favors frequent words

the banker met a tall man
銀行 員 が 背 の 高い 男 に 会った
a man ran out of the room
男 が 部屋 から 飛び出た
the young boy is good at soccer
あの 男 の 子 は サッカー が 上手 だ
the statue of liberty
自由 の 女神
he enjoys the olympics
彼 は オリンピック が 大好き だ

Co-occurrencec(the, 男 ) = 3
c(man, 男 ) = 2

Breaking Down the Language Barrier with Statistical Machine Translation

Dice Coefficient●

The dice coefficient penalizes highly frequent words

2∗c (e , f )dice(e , f )=c (e )+ c( f )the banker met a tall man
銀行 員 が 背 の 高い 男 に 会った
a man ran out of the room
男 が 部屋 から 飛び出た
the young boy is good at soccer
あの 男 の 子 は サッカー が 上手 だ
the statue of liberty
自由 の 女神
he enjoys the olympics
彼 は オリンピック が 大好き だ

Dice Coefficientdice(the, 男 ) =(2 * 3) / (5 + 3) = 0.75
dice(man, 男 ) =(2 * 2) / (2 + 3) = 0.80

Breaking Down the Language Barrier with Statistical Machine Translation

Scores → Alignments●

Now, we need a way to change dice coefficients toalignments
historicalhistoricalcoldoutbreaks

歴代

0.596

0.018

0.250

歴代

の

0.002

0.003

0.000

の

風邪

0.020

0.909

0.037

風邪

大

0.007

0.002

0.085

大

流行

0.025

0.010

0.240

流行

cold

outbreaks

●
●
●
●
●

Breaking Down the Language Barrier with Statistical Machine Translation

Max-Score●

Choose the best target word for each source

historicalcoldoutbreaks

歴代

0.596

0.018

0.250

の

0.002

0.003

0.000

風邪

0.020

0.909

0.037

大

0.007

0.002

0.085

流行

0.025

0.010

0.240

historical
cold
cold
outbreaks
outbreaks

Breaking Down the Language Barrier with Statistical Machine Translation

Threshold●Choose a threshold, align all words over thresholdhistoricalcoldoutbreaks

歴代

0.596

0.018

0.250

の

0.002

0.003

0.000

風邪

0.020

0.909

0.037

大

0.007

0.002

0.085

流行

0.025

0.010

0.240

t > 0.1

Breaking Down the Language Barrier with Statistical Machine Translation

Competitive Linking●

Pick the highest scored alignment in order, but do notallow the same word be aligned to others
historicalcoldoutbreaks

歴代

0.596

0.018

0.250

の

0.002

0.003

0.000

風邪

0.020

0.909

0.037

大

0.007

0.002

0.085

流行

0.025

0.010

0.240

1. 風邪 → cold
2. 歴代 → historical
3. 流行 → outbreaks

Breaking Down the Language Barrier with Statistical Machine Translation

Probabilistic Alignment:
IBM Model 1

Breaking Down the Language Barrier with Statistical Machine Translation

Probabilistic Alignment●

Create probabilistic model of two sentences
F= チーズ ムース
E= mousse di formaggi●

P(F | E; M)

The model M has some parameters (e.g. probabilities)
P(f= チーズ | e=formaggi) = 0.92
P(f= チーズ | e=di) = 0.001
P(f= チーズ | e=mousse) = 0.02
P(f= ムース | e=formaggi) = 0.07
P(f= ムース | e=di) = 0.002
P(f= ムース | e=mousse) = 0.89●

Probabilities are easier to understand (can make morerefined models), easier to integrate

Breaking Down the Language Barrier with Statistical Machine Translation

IBM Model One Idea●

Generate each word fj in F according to
Pick one word index aj at random (P(aj) = 1/(|E|+1)),
including special “NULL” word for unaligned words● Pick the word f according to P(f | e )jaj●

Generate two words

チーズ

ムース

Choose: チーズ ( P(f|e) = 0.92 )Choose: ムース ( P(f|e) = 0.89 )Choose: a1 = 3 ( P(a1=3) = 0.25 )Choose: a2 = 1 ( P(a2=1) = 0.25 )moussediformaggi

NULL

Breaking Down the Language Barrier with Statistical Machine Translation

IBM Model 1 Equation●

If we guess the alignment and output words,
probability is

1
P (F , A∣E)=∏ j=1
P ( f j∣e a )
I +1
J

j

Alignment●

Word translation

We can also sum over all alignments

1
P ( F∣E )=∑ A ∏ j =1
P ( f j∣e a )
I +1
J
I +1
1
=∏ j =1
P ( f j∣e i)
∑
i=1
I +1
J

j

Breaking Down the Language Barrier with Statistical Machine Translation

Training Model 1●●

We need to estimate our model parameters
The most natural way to do so is with maximum
likelihood

̂ =argmax P ( F∣E )M
M●

How do we calculate the parameters to maximize
likelihood?

Breaking Down the Language Barrier with Statistical Machine Translation

EM Algorithm●●

IBM models trained using the EM (ExpectationMaximization) algorithm
Idea:
E Step: Based on the model, estimate how many times
each word e is translated into f● M Step: Based on the estimated counts, re-calculate
the model parameters●●

Every iteration, we increase the likelihood of the model

22

Breaking Down the Language Barrier with Statistical Machine Translation

EM Example●

Initialize: Simply count co-occurrence

チーズ ムース
Mousse di formaggi
本日 の 鮮魚
Pesce del giorno
本日 の チーズ
Formaggi del giorno
ドルチェ と チーズ
Dolce e Formaggi

23

Breaking Down the Language Barrier with Statistical Machine Translation

EM Example●

M Step: Update the probabilities

チーズ ムースP( チーズ |formaggi) =P( ムース |formaggi) =P( 本日 |formaggi) =P( の |formaggi) =P( ドルチェ |formaggi) =P( と |formaggi) =

0.375
0.125
0.125
0.125
0.125
0.125

ドルチェ と チーズ

P( 本日 |giorno) =P( の |giorno) =P( 鮮魚 |giorno) =P( チーズ |giorno) =

0.33
0.33
0.16
0.16

Dolce e Formaggi...

Mousse di formaggi
本日 の 鮮魚
Pesce del giorno
本日 の チーズ
Formaggi del giorno

24

Breaking Down the Language Barrier with Statistical Machine Translation

EM Example●

E Step: Calculate connections between words

チーズ ムースP( チーズ |formaggi) =P( ムース |formaggi) =P( 本日 |formaggi) =P( の |formaggi) =P( ドルチェ |formaggi) =P( と |formaggi) =

0.375
0.125
0.125
0.125
0.125
0.125

ドルチェ と チーズ

P( 本日 |giorno) =P( の |giorno) =P( 鮮魚 |giorno) =P( チーズ |giorno) =

0.33
0.33
0.16
0.16

Dolce e Formaggi...

Mousse di formaggi
本日 の 鮮魚
Pesce del giorno
本日 の チーズ
Formaggi del giorno

25

Breaking Down the Language Barrier with Statistical Machine Translation

EM Example●

M Step: Update the probabilities

チーズ ムースP( チーズ |formaggi) =P( ムース |formaggi) =P( 本日 |formaggi) =P( の |formaggi) =P( ドルチェ |formaggi) =P( と |formaggi) =

0.9
0.02
0.02
0.02
0.02
0.02

ドルチェ と チーズ

P( 本日 |giorno) =P( の |giorno) =P( 鮮魚 |giorno) =P( チーズ |giorno) =

0.48
0.48
0.02
0.02

Dolce e Formaggi...

Mousse di formaggi
本日 の 鮮魚
Pesce del giorno
本日 の チーズ
Formaggi del giorno

26

Breaking Down the Language Barrier with Statistical Machine Translation

EM Example●

E Step: Calculate connections between words

チーズ ムースP( チーズ |formaggi) =P( ムース |formaggi) =P( 本日 |formaggi) =P( の |formaggi) =P( ドルチェ |formaggi) =P( と |formaggi) =

0.9
0.02
0.02
0.02
0.02
0.02

ドルチェ と チーズ

P( 本日 |giorno) =P( の |giorno) =P( 鮮魚 |giorno) =P( チーズ |giorno) =

0.48
0.48
0.02
0.02

Dolce e Formaggi...

Mousse di formaggi
本日 の 鮮魚
Pesce del giorno
本日 の チーズ
Formaggi del giorno

27

Breaking Down the Language Barrier with Statistical Machine Translation

Initialization in Equations/Words●

Define our expected counts of two words x and ybeing aligned asq (e =x , f = y )●Initialize this to the co-occurrence countsq (e =x , f = y )=c (e= x , f = y )28

Breaking Down the Language Barrier with Statistical Machine Translation

M Step in Equations/Words●

M Step: Calculate the model parameters●

Simply calculate the maximum likelihood estimate of theconditional probabilityq (e= x , f = y )P ( f = y∣e= x)=q (e= x )where

q (e =x )=∑ y q (e= x , f = y )29

Breaking Down the Language Barrier with Statistical Machine Translation

E Step in Equations/Words●

E Step: Calculate expectations with model fixed●

One sentence, probability of aj=i given model is:

I +1
1
1
P (a j =i∣F , E , M )=P ( f j∣e i ) / ∑ ̃i =1
P ( f j∣e ̃i )
I +1
I +1
Current word

All words

I +1

P ( a j =i∣F , E , M )= P ( f j∣e i) / ∑̃i =1 P ( f j∣e ̃i )●Given this, calculate the expected count of translations(δ = Kronecker's delta, 1 when true, 0 otherwise)
I +1

J

q (e =x , f = y )=∑ E , F ∑i=1 ∑ j =1 P (a j =i∣F , E , M )δ (e i =x , f j = y)30

Breaking Down the Language Barrier with Statistical Machine Translation

Probabilistic Alignment:
IBM Models 2-5/HMM

Breaking Down the Language Barrier with Statistical Machine Translation

Model 1 Problem●

Model 1 cannot handle word order!
big oranges and big apples
大きな オレンジ と 大きな りんご●

Many new models proposed, all to handle this problem

Breaking Down the Language Barrier with Statistical Machine Translation

Model 2 Idea●

“Words in both languages should be in about the sameorder”
bigorangesandbigapples大きな オレンジ と 大きな りんご●

But, in most languages this is not true

Breaking Down the Language Barrier with Statistical Machine Translation

HMM Idea●“Words that were previously aligned should give an
idea about the next word”
bigorangesandbigappleslast

大きな オレンジ と 大きな りんご●

More effective than 2

Breaking Down the Language Barrier with Statistical Machine Translation

HMM Graph

Breaking Down the Language Barrier with Statistical Machine Translation

IBM Models 3-5●

Remaining IBM models are based on “fertility”●“Given this word, how many words will it produce?”

Fertility 1

Fertility 3.5

I

adopted私僕
俺

採用 され た養子 に なっ たBreaking Down the Language Barrier with Statistical Machine Translation

Combining Alignments

Breaking Down the Language Barrier with Statistical Machine Translation

Combining 1-to-many Alignments
ホテル の 受付X
the hotel front desk

the hotel front deskX
ホテル の 受付

combination

the hotel front desk
ホテル の 受付●

Various heuristics for combination

38

Breaking Down the Language Barrier with Statistical Machine Translation

Union
●

Union: Take allalignments ineither direction

ホ
テ 受
ルの付
the
hotel
front
desk

ホ
テ 受
ルの付
the
hotel
front
desk
ホ
テ 受
ルの付

the
hotel
front
desk

39

Breaking Down the Language Barrier with Statistical Machine Translation

Intersection●

Intersection:
Only takealignments in
one direction

ホ
テ 受
ルの付
the
hotel
front
desk

ホ
テ 受
ルの付
the
hotel
front
desk
ホ
テ 受
ルの付

the
hotel
front
desk

40

Breaking Down the Language Barrier with Statistical Machine Translation

Grow/Diag●●

Grow: Use intersection, but add corner pieces
included in the union

Diag: Use intersection, but add corners

41

Breaking Down the Language Barrier with Statistical Machine Translation

Evaluating Alignments

42

Breaking Down the Language Barrier with Statistical Machine Translation

How Good are Our Alignments?
●

Let's say we have two systems, which is better?
Reference

System A

ホ
テ 受
ルの付
the
hotel
front
desk

System B

ホ
テ 受
ルの付
the
hotel
front
desk

ホ
テ 受
ルの付
the
hotel
front
desk

43

Breaking Down the Language Barrier with Statistical Machine Translation

Precision/Recall/F-Measure●

Precision: ratio of system alignments correct●

Recall: ratio of reference alignments correct●

F-measure: geometric mean of precision and recall

Reference (Handmade)

System A

ホ
テ 受
ルの付
the
hotel
front
desk

System B

ホ
テ 受
ルの付
the
hotel
front
desk

P=1.0
R=0.75F=2*1.0*0.75/(1.0+0.75)=0.85

ホ
テ 受
ルの付
the
hotel
front
desk

P=0.8
R=1.0
44
F=2*0.8*1.0/(0.8+1.0)=0.88

Breaking Down the Language Barrier with Statistical Machine Translation

Advanced Topics

45Breaking Down the Language Barrier with Statistical Machine Translation

Inversion Transduction Grammar (ITG)●

A context-free grammar over two languages
non-terminal “regular (reg)” and “inverted (inv)”● one pre-terminal 「 term 」● terminals represent a phrase pair
●

reg

inv

term

term

term

term

7/7

kilos/ キロ

Mr./ さん Smith/ スミス

English7 kilos

Japanese
7 キロ

EnglishJapanese
Mr. Smith スミス さん
46

Breaking Down the Language Barrier with Statistical Machine Translation

Parsing with ITGs●

Define a probability over non-terminals/pre-terminals
Px , define another over terminals Pt
Mrs.

Smith

's

スミス

さん

の

Px(inv)Px(term)red
赤いPx(reg)Px(term)

cookbook
料理本

Px(reg)Px(term)Px(reg)Px(term)Pt(Mrs./ さん )●Pt(Smith/ スミス )Px(term)Pt('s/ の ) Pt(red/ 赤い ) Pt(cookbook/ 料理 本 )Can use a variant of the CKY algorithm (standard
algorithm for parsing context-free grammars)

47

Breaking Down the Language Barrier with Statistical Machine Translation

Advantages/Disadvantages of ITGs●

Advantage:
Simple model, no heuristics● Can handle many-to-many alignments in polynomial(O(n6)) time●●

Disadvantage:●

Compared to other models, this is slow, especially for
longer sentences48

Breaking Down the Language Barrier with Statistical Machine Translation

Supervised Alignment●●

Prepare a hand-made training corpus
Use this corpus to train a model to “fix” unsupervisedalignment
Reference

thisis a pen

Unsupervised

thisis a pen

これ は ペン です

これ は ペン ですc(is, です )++c(is, は )-c(a, です )-49

Breaking Down the Language Barrier with Statistical Machine Translation

Class-Based Alignment●

Classes can be used to smooth the probability
distribution
this10

is a pen
5 9 2010 8 20 5
これ は ペン です

●

this
10

is a pencil
5 9 2010 8 20 5
これ は 鉛筆 です

Classes are learned automatically over bothlanguages
50Breaking Down the Language Barrier with Statistical Machine Translation

Phrase Extraction/ScoringBreaking Down the Language Barrier with Statistical Machine Translation

What is a “Phrase”●●

In linguistics a “phrase” has a special meaning (“nounphrase, verb phrase”)
In translation, it generally just means a string of words

Today
I will give
今日は、 を行います

Today
今日は、

a lecture onの講義

machine translation
機械翻訳

machine translation
機械翻訳

a lecture onの講義

I will give
を行います

.
。

.
。

Breaking Down the Language Barrier with Statistical Machine Translation

Phrase Extraction●

We extract bilingual phrases from data

ホ
テ 受
ルの付
the
hotel
front
desk
●

●

ホテル の → hotel
ホテル の → the hotel
受付 → front desk
ホテルの受付 → hotel front desk
ホテルの受付 → the hotel front desk

Check all bilingual phrase pairs
Extract only ones that have at least one goodalignment, and no conflicts

Breaking Down the Language Barrier with Statistical Machine Translation

Phrase Scoring●

We calculate probabilities for the phrases to measure
how good a translation it is●Phrase translation probability (in both directions)
P(f|e) = c(f,e)/c(e)P(e|f) = c(f,e)/c(f)e.g.: c( ホテル の , the hotel) / c(the hotel)● Lexical probabilities
Calculate phrase probabilities using IBM model 1
probabilities, and the words contained within– Helps relieve sparsity problems–

P(f|e) = Πf 1/|e| ∑e P(f|e)
e.g.:(P( ホテル |the)+P( ホテル |hotel))/2 * (P( の |the)+P( の |hotel))/2

Breaking Down the Language Barrier with Statistical Machine Translation

Reordering Varieties●

Probability of monotone, swap, discontinuous
細太 訪しい男が郎を問た

the
thin
man
visitedTaromono

細い → the thinhigh monotone probability

disc.

swap

太郎 を → Tarohigh swap probability

Breaking Down the Language Barrier with Statistical Machine Translation

Reordering Probabilities●●

Calculate reordering probabilities from data, liketranslation
Condition on previous, next phrase
細
い男が

the
thin
man

c(after, the thin → 細い , mono) ++c(before, man → 男 が , mono) ++mono

Breaking Down the Language Barrier with Statistical Machine Translation

Assignment

57

Breaking Down the Language Barrier with Statistical Machine Translation

Assignment●

I have given you code that:
1: Calculates the Dice coefficient for each pair of words● 2: Decides the alignment in each direction using Dicecoefficient statistics and the Max Score criterion● 3: Combines these two alignments using the“intersection” heuristic● 4: Measures alignment F-measure●●

You should
1: Measure the alignment accuracy on the provided
data● 2: Make one change that improves the accuracy●

58

Breaking Down the Language Barrier with Statistical Machine Translation

Assignment Details●●

Download the exercise from the web
You can find a list of commands to run in runalignment.sh
This is currently using smaller data (kyoto-tunesmall)● You can use larger data (kyoto-tunetrain) if you have apowerul computer (4GB memory, 5 minutes)●●

Send your code, alignment f-measure before/after, ashort description of the change, and a “username”
Due date: February 5th, 23:59● Address: neubig@is.naist.jp●

59