Breaking Down the Language Barrier with Statistical Machine Translation

Breaking down the Language Barrier with
Statistical Machine Translation:1) Language Models

http://www.phontron.com/class/sentan2014
Advanced Research Seminar I/III
Graham Neubig
2014-1-28

1Breaking Down the Language Barrier with Statistical Machine Translation

Machine Translation●●

Automatically translate between languages
SourceTarget

太郎が花子を訪問した。

Taro
visitedHanako.

Real products/services being created!
ChronusSimultaneousTranslation
System2

Breaking Down the Language Barrier with Statistical Machine Translation

How does machine translation work?

Today I will give a lecture on machine translation .

3

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を行います.
。

.
。

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

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?
5

Breaking Down the Language Barrier with Statistical Machine Translation

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

P(“ 昨日” |“today”) = low

P(●Reordering Model:

鶏がchicken eats
●鶏食べる)=highP(をeats食べる鶏)=highchicken

P(がeats食べる)=lowchicken

Language Model:P( “Taro met Hanako” )=highP( “the Taro met the Hanako” )=low6

Breaking Down the Language Barrier with Statistical Machine Translation

Creating a Machine Translation System●Learn patterns from documents
Documents

ModelsTranslation Model

太郎が花子を訪問した。
Taro visited Hanako.
花子にプレセントを渡した。
He gave Hanako a present.
...

Reordering Model
Language Model7

Breaking Down the Language Barrier with Statistical Machine Translation

Easier Saidthan Done!

Flow-chart fortraining an MT system →8Breaking Down the Language Barrier with Statistical Machine Translation

Lecture Plan

9

Breaking Down the Language Barrier with Statistical Machine Translation

Lecture Plan
1) Language models
2) Word alignment / Translation modeling3) Kana-kanji conversion / Phrase-based translation
4) Machine translation evaluation / Optimization

10Breaking Down the Language Barrier with Statistical Machine Translation

Assignments●●●

All assignments will require simple programmingA “baseline” system will be prepared for you(in Python)
Improve the system's accuracy, turn in your code, anda short description of what you changed and why●You may work in teams of up to 3 people●I will keep a scoreboard

11

Breaking Down the Language Barrier with Statistical Machine Translation

Today's Assignment●I have given you code to train and test a language
model using bigrams and linear interpolation●Make a change to the code to improve its entropy●

Due date: Monday, February 3rd, 23:59●

Address: neubig@is.naist.jp

12Breaking Down the Language Barrier with Statistical Machine Translation

Unigram Language Models

13

Breaking Down the Language Barrier with Statistical Machine Translation

Why Language Models?
●When performing Japanese-English translation, whichis correct?
W1 = Taro visited Hanako

太郎は花子を訪問した

W2 = the Taro visited the Hanako
W3 = fat visit ro flower childW4 = 太郎 は 花子 を 訪問 した

14

Breaking Down the Language Barrier with Statistical Machine Translation

Why Language Models?
●

When performing Japanese-English translation, whichis correct?
W1 = Taro visited Hanako

太郎は花子を訪問した

W2 = the Taro visited the Hanako
W3 = fat visit ro flower childW4 = 太郎 は 花子 を 訪問 した●The language model tells you which is most likely
15

Breaking Down the Language Barrier with Statistical Machine TranslationProbabilistic Language Models●Language models assign a probability to eachsentence

W1 = taro visited hanako

P(W1) = 4.021 * 10-3

W2 = the taro visited the hanako

P(W2) = 8.932 * 10-4

W3 = fat visit ro flower childP(W3) = 2.432 * 10-7

W4 = 太郎 は 花子 を 訪問 した

P(W4) = 9.124 * 10-23●

P(W1) > P(W2) > P(W3) > P(W4) is best(in Japanese P(W4) > P(W1), P(W2), P(W3) ？ )16

Breaking Down the Language Barrier with Statistical Machine Translation

Calculating Sentence Probabilities●

We want the probability of
W = taro visited hanako●

Represent this mathematically as:
P(|W| = 3, w1=”taro”, w2=”visited”, w3=”hanako”)

17Breaking Down the Language Barrier with Statistical Machine Translation

Calculating Sentence Probabilities●

We want the probability of
W = taro visited hanako●

Represent this mathematically as (using chain rule):

P(|W| = 3, w1=”taro”, w2=”visited”, w3=”hanako”) =P(w1=“taro” | w0 = “
”)* P(w2=”visited” | w0 = “
”, w1=“taro”)* P(w3=”hanako” | w0 = “
”, w1=“taro”, w2=”visited”)* P(w4=”
” | w0 = “
”, w1=“taro”, w2=”visited”, w3=”hanako”)

NOTE:
sentence start 
 and end 
 symbol

NOTE:
P(w0 = 
) = 1

18

Breaking Down the Language Barrier with Statistical Machine Translation

Incremental Computation●

Previous equation can be written:∣W ∣+1

P(W )=∏i =1 P (w i∣w0 …w i−1)
●How do we decide probability?

P( wi∣w 0 … wi−1 )19Breaking Down the Language Barrier with Statistical Machine Translation

Maximum Likelihood Estimation●Calculate word strings in corpus, take fractionc (w 0 … wi )P( wi∣w 0 … wi−1 )=c (w0 … wi −1)
i live in osaka . 
i am a graduate student . 

my school is in nara . 
P(live | 
 i) = c(
 i live)/c(
 i) = 1 / 2 = 0.5
P(am | 
 i) = c(
 i am)/c(
 i) = 1 / 2 = 0.5

20Breaking Down the Language Barrier with Statistical Machine TranslationProblem With Full Estimation●

Weak when counts are low:

Training:

i live in osaka . 
i am a graduate student . 

my school is in nara . 

 i live in nara . 


Test:

P(nara|
 i live in) = 0/1 = 0
P(W=
 i live in nara . 
) = 021

Breaking Down the Language Barrier with Statistical Machine Translation

Unigram Model●

Do not use history:P( wi∣w 0 … wi−1 )≈P (w i)=c (wi )̃∑w̃ c ( w)P(nara) = 1/20 = 0.05
i live in osaka . 

= 2/20 = 0.1
i am a graduate student . 
 P(i)my school is in nara . 

P(
) = 3/20 = 0.15
P(W=i live in nara . 
) =0.1 * 0.05 * 0.1 * 0.05 * 0.15 * 0.15 = 5.625 * 10 -7
22

Breaking Down the Language Barrier with Statistical Machine Translation

What about Unknown Words?!
●Simple ML estimation doesn't work
i live in osaka . 
i am a graduate student . 

my school is in nara . 
P(nara) = 1/20 = 0.05
P(i)= 2/20 = 0.1
P(kyoto) = 0/20 = 0●

Often, unknown words are ignored (ASR)●Better way to solve●

Save some probability for unknown words (λunk = 1-λ1)●

Guess total vocabulary size (N), including unknowns

1P( wi )=λ1 P ML ( wi )+ (1−λ 1)N23Breaking Down the Language Barrier with Statistical Machine Translation

Unknown Word Example●

Total vocabulary size: N=106●

Unknown word probability: λunk=0.05 (λ1 = 0.95)

1P( wi )=λ1 P ML ( wi )+ (1−λ 1)NP(nara) = 0.95*0.05 + 0.05*(1/106) = 0.04750005
P(i)= 0.95*0.10 + 0.05*(1/106) = 0.09500005

P(kyoto) = 0.95*0.00 + 0.05*(1/106) = 0.00000005
24

Breaking Down the Language Barrier with Statistical Machine Translation

Bigram Language Models

25

Breaking Down the Language Barrier with Statistical Machine Translation

Unigram Models Ignore Word Order!
●

Ignoring context, probabilities are the same:

Puni(w=speech recognition system) =P(w=speech) * P(w=recognition) * P(w=system) * P(w=
)=Puni(w=system recognition speech ) =P(w=speech) * P(w=recognition) * P(w=system) * P(w=
)26Breaking Down the Language Barrier with Statistical Machine Translation

Unigram Models Ignore Agreement!
●Good sentences (words agree):Puni(w=i am) =P(w=i) * P(w=am) * P(w=
)●Puni(w=we are) =P(w=we) * P(w=are) * P(w=
)

Bad sentences (words don't agree)

Puni(w=we am) =Puni(w=i are) =P(w=we) * P(w=am) * P(w=
)P(w=i) * P(w=are) * P(w=
)

But no penalty because probabilities are independent!
27

Breaking Down the Language Barrier with Statistical Machine Translation

Solution: Add More Context!
●

Unigram model ignored context:P( wi∣w 0 … wi−1 )≈P (w i)●

Bigram model adds one word of context

P( wi∣w 0 … wi−1 )≈P (w i∣wi−1 )●Trigram model adds two words of context

P( wi∣w 0 … wi−1 )≈P (w i∣wi− 2 w i−1)●

Four-gram, five-gram, six-gram, etc...

28

Breaking Down the Language Barrier with Statistical Machine Translation

Maximum Likelihood Estimationof n-gram Probabilities●

Calculate counts of n word and n-1 word stringsc (w i−n+ 1 … wi )P( wi∣w i−n+ 1 … wi−1 )=c ( wi− n+ 1 … wi−1)
i live in osaka . 
i am a graduate student . 

my school is in nara . 
P(osaka | in) = c(in osaka)/c(in) = 1 / 2 = 0.5
n=2 →P(nara | in) = c(in nara)/c(in) = 1 / 2 = 0.529Breaking Down the Language Barrier with Statistical Machine Translation

Still Problems of Sparsity●

When n-gram frequency is 0, probability is 0P(osaka | in)P(nara | in)= c(i osaka)/c(in) = 1 / 2 = 0.5= c(i nara)/c(in) = 1 / 2 = 0.5

P(school | in) = c(in school)/c(in) = 0 / 2 = 0!!
●

Like unigram model, we can use linear interpolation

Bigram:Unigram:P( wi∣w i−1)=λ 2 P ML (w i∣wi −1)+ (1−λ 2) P( wi )1
P( wi )=λ1 P ML ( wi )+ (1−λ 1)N30Breaking Down the Language Barrier with Statistical Machine Translation

Choosing Values of λ: Grid Search●One method to choose λ2, λ1: try many values

λ 2=0.95, λ1 =0.95
λ 2=0.95, λ1 =0.90
λ 2=0.95, λ1 =0.85…
λ 2=0.95, λ1 =0.05
λ 2=0.90, λ1 =0.95
λ 2=0.90, λ1 =0.90…
λ 2=0.05, λ1 =0.10
λ 2=0.05, λ1 =0.05

Problems:
Too many options→ Choosing takes time!
Using same λ for all n-grams→ There is a smarter way!

31

Breaking Down the Language Barrier with Statistical Machine Translation

Evaluating Language Models

32

Breaking Down the Language Barrier with Statistical Machine Translation

Experimental Setup●Use training and test sets

Training Datai live in osaka
i am a graduate student
my school is in nara
...

Train
ModelTesting Datai live in narai am a student
i have lots of homework…

ModelTest
Model
Model Accuracy
Likelihood
Log Likelihood
Entropy
Perplexity 33

Breaking Down the Language Barrier with Statistical Machine Translation

Likelihood●Likelihood is the probability of some observed data(the test set Wtest), given the model MP(W test∣M )=∏ w∈ W P ( w∣M )test

i live in naraP(w=”i live in nara”|M) =2.52*10-21

i am a student

P(w=”i am a student”|M) =3.48*10-19

P(w=”my classes are hard”|M) =2.15*10-34

my classes are hardxx=
1.89*10-7334

Breaking Down the Language Barrier with Statistical Machine Translation

Log Likelihood●Likelihood uses very small numbers=underflow●

Taking the log resolves this problem

log P(W test∣M )=∑ w∈W log P( w∣M )test

i live in narai am a student
my classes are hard

log P(w=”i live in nara”|M) =-20.58log P(w=”i am a student”|M) =-18.45++log P(w=”my classes are hard”|M) = -33.67=-72.60
35

Breaking Down the Language Barrier with Statistical Machine Translation

Entropy●Entropy H is average negative log2 likelihood per word

1H (W test∣M )=−log 2 P (w∣M )∑w∈W| W test |test

i live in naralog2 P(w=”i live in nara”|M)=i am a student

log2 P(w=”i am a student”|M)=

my classes are hard

( )68.43+61.32+log2 P(w=”my classes are hard”|M)= 111.84# of words=/12=20.13* note, we can also count 
 in # of words (in which case it is 15)

36

Breaking Down the Language Barrier with Statistical Machine Translation

Entropy and Compression●Entropy H is also the average number of bits needed
to encode information (Shannon's information theory)1
H=∑|W test | w ∈W

wtest−log 2 P( w∣M )a bird a cat a dog a 


Encodingabirdcatdog


→1
→ 000
→ 001
→ 010
→ 011

1000100110101011

P(w= “a”) = 0.5-log2 0.5 = 1
P(w= “bird”) = 0.125 -log2 0.125 = 3P(w= “cat”) = 0.125 -log2 0.125 = 3P(w= “dog”) = 0.125 -log2 0.125 = 3P(w= “
”) = 0.125 -log2 0.125 = 337

Breaking Down the Language Barrier with Statistical Machine Translation

Perplexity●

Equal to two to the power of per-word entropy

PPL=2
●

●

H(Mainly because it makes more impressive numbers)
For uniform distributions, equal to the size ofvocabulary

V =51
H=−log 25H

PPL=2 =2−log 21
5=2log2 5=538

Breaking Down the Language Barrier with Statistical Machine Translation

Coverage●The percentage of known words in the corpus
a bird a cat a dog a 
“dog” is an unknown word
Coverage: 7/8 ** often omit the sentence-final symbol → 6/7

39

Breaking Down the Language Barrier with Statistical Machine Translation

Smoothing40

Breaking Down the Language Barrier with Statistical Machine Translation

Context Dependent Smoothing
High frequency word: “Tokyo”

Low frequency word: “Tottori”

c(Tokyo city) = 40c(Tokyo is) = 35c(Tokyo was) = 24c(Tokyo tower) = 15c(Tokyo port) = 10…

c(Tottori is) = 2c(Tottori city) = 1c(Tottori was) = 0

Most 2-grams already exist→ Large λ is better!

Many 2-grams will be missing→ Small λ is better!

●Make the interpolation depend on the context

P( wi∣w i−1)=λ w P ML (w i∣wi−1 )+ (1−λ w ) P( wi )i−1i−141

Breaking Down the Language Barrier with Statistical Machine Translation

Witten-Bell Smoothing●One of the many ways to choose λ w i−1u( wi−1 )λ w =1−u( wi−1 )+ c ( wi −1)u( wi −1) = number of unique words after wi-1i−1●For example:c(Tottori is) = 2 c(Tottori city) = 1c(Tottori) = 3u(Tottori) = 2c(Tokyo city) = 40 c(Tokyo is) = 35 ...
c(Tokyo) = 270u(Tokyo) = 30

2
λ Tottori=1−=0.62+ 330
λ Tokyo =1−=0.930+ 270
42Breaking Down the Language Barrier with Statistical Machine Translation

Absolute Discounting●Reduce a little bit (d) from each countc ' ( wi−1 , wi )=c (w i−1 , wi )−dc ' (w i−1 , wi )P( wi∣w i−1)=c (w i−1)
●For example:

d=0.5c(Tottori is) = 2c(Tottori city) = 1c'(Tottori is) = 1.5c'(Tottori city) = 0.5u(Tottori) = 2

1.5 2∗0.5
P( wi=is∣w i−1=Tottori)=+P( wi =is)33P( wi=city∣wi −1=Tottori)=

1.5 2∗0.5+P (w i=city)3343

Breaking Down the Language Barrier with Statistical Machine Translation

Kneser-Ney Smoothing●

Currently standard smoothing method●

Similar to abolute discounting, but change P( wi )●Basic idea:
Unigram distribution is used as fall-back for bigram● Unigram should mainly give probability to words that willoccur in new contexts● Count contexts
x (w i) that the new word appears in:●c(Barack Obama) = 50c(President Obama) = 20x(Obama) = 2 c(Obama) = 70c(John Smith) = 7c(Mary Smith) = 4c(Fred Smith) = 3...
x(Smith) = 20 c(Smith) = 50

44

Breaking Down the Language Barrier with Statistical Machine Translation

Advanced Techniques

45

Breaking Down the Language Barrier with Statistical Machine Translation

Class-based Language Models●Group words into classes●Predict the class before predicting words∣W ∣+1P(W )=∏i =1 P (c i∣c i−1) P( wi∣c i )




●taro

methanako

201520
Classes are learned automatically●Brown clustering most famous method

46

Breaking Down the Language Barrier with Statistical Machine Translation

Continuous-Space Language Models●Represent each state as a vector of numbers
taro

met

hanako
 {20.4, 30.2} {15.9, 12.5} {32.1, 9.2} 
●

Generally learned using neural networks●Can learn more complicated information47

Breaking Down the Language Barrier with Statistical Machine Translation

Discriminative Language Models●

Use actual machine translation output and rerankusing n-gramsc(visited Hanako)++c(Taro visited)++MT

W1 = Taro visited Hanako

Good!

W2 = the Taro visited the HanakoBad!

c(Taro visited)-- c(the Hanako)-c(the Taro)-c(visited the)--c(visited Hanako) = 1c(the Taro) = -1 c(visited the) = -1c(the Hanako) = -148

Breaking Down the Language Barrier with Statistical Machine Translation

Assignment

49

Breaking Down the Language Barrier with Statistical Machine Translation

Today's Assignment●Code to train and test an LM (on the website)
cd sentan-01
script/train-bigram.py data/kyoto-train.en > model/bigram.en
script/test-bigram.py model/bigram.en data/kyoto-dev.en●Make a change to the code to improve its entropy●

Any change is OK, EXCEPT:
Adding the testing data to the training data
● Adjusting the number of unknown words V●●

Send your code, entropy before/after, a short
description of the change, and a “username”
Due date: February 3rd, 23:59● Address: neubig@is.naist.jp●50

Breaking Down the Language Barrier with Statistical Machine Translation

References51