NLP Programming Tutorial 1 – Unigram Language Model

NLP Programming Tutorial 1 Unigram Language Models

Graham Neubig
Nara Institute of Science and Technology (NAIST)1NLP Programming Tutorial 1 – Unigram Language Model

Language Model Basics

2

NLP Programming Tutorial 1 – Unigram Language Model

Why Language Models?
●We have an English speech recognition system, whichanswer is better?

SpeechW1 = speech recognition
systemW2 = speech cognition
systemW3 = speck podcast
histamine
W4 = スピーチ が 救出 ストン

3

NLP Programming Tutorial 1 – Unigram Language Model

Why Language Models?
●

We have an English speech recognition system, whichanswer is better?

Speech●W1 = speech recognition
systemW2 = speech cognition
systemW3 = speck podcast
histamine
W4 = スピーチ が 救出 ストン

Language models tell us the answer!
4

NLP Programming Tutorial 1 – Unigram Language Model

Probabilistic Language Models●

Language models assign a probability to eachsentence

W1 = speech recognition
systemW2 = speech cognition
systemW3 = speck podcast
histamine
W4 = スピーチ が 救出 ストン●

P(W1) = 4.021 * 10-3
P(W2) = 8.932 * 10-4
P(W3) = 2.432 * 10-7
P(W4) = 9.124 * 10-23

We want P(W1) > P(W2) > P(W3) > P(W4)●(or P(W4) > P(W1), P(W2), P(W3) for Japanese?)

5

NLP Programming Tutorial 1 – Unigram Language Model

Calculating Sentence Probabilities●

We want the probability of
W = speech recognition system●

Represent this mathematically as:
P(|W| = 3, w1=”speech”, w2=”recognition”, w3=”system”)

6

NLP Programming Tutorial 1 – Unigram Language Model

Calculating Sentence Probabilities●We want the probability of
W = speech recognition system●Represent this mathematically as (using chain rule):

P(|W| = 3, w1=”speech”, w2=”recognition”, w3=”system”) =P(w1=“speech” | w0 = “
”)* P(w2=”recognition” | w0 = “
”, w1=“speech”)* P(w3=”system” | w0 = “
”, w1=“speech”, w2=”recognition”)* P(w4=”
” | w0 = “
”, w1=“speech”, w2=”recognition”, w3=”system”)

NOTE:
sentence start 
 and end 
 symbol

NOTE:
P(w0 = 
) = 17

NLP Programming Tutorial 1 – Unigram Language Model

Incremental Computation●Previous equation can be written:∣W ∣+ 1P(W )=∏i =1 P(wi∣w 0 … wi−1 )●How do we decide probability?

P( wi∣w 0 … wi−1 )8NLP Programming Tutorial 1 – Unigram Language Model

Maximum Likelihood Estimation●

Calculate word strings in corpus, take fractionc (w1 … wi )P( wi∣w 1 …w i−1)=c (w 1 …w i−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

9NLP Programming Tutorial 1 – Unigram Language Model

Problem 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 . 
) = 010

NLP Programming Tutorial 1 – Unigram Language Model

Unigram Model●Do not use history:c (wi )P( wi∣w 1 …w i−1)≈ P( 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-711

NLP Programming Tutorial 1 – Unigram Language Model

Be Careful of Integers!
●

Divide two integers, you get an integer (rounded down)$ ./my-program.py
0●

Convert one integer to a float, and you will be OK$ ./my-program.py
0.5

12NLP Programming Tutorial 1 – Unigram Language Model

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)
N
13

NLP Programming Tutorial 1 – Unigram Language Model

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
14NLP Programming Tutorial 1 – Unigram Language Model

Evaluating Language Models

15

NLP Programming Tutorial 1 – Unigram Language Model

Experimental Setup●Use training and test sets

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

Train
Model

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

Model

Test
Model
Model Accuracy
Likelihood
Log Likelihood
Entropy
Perplexity 16

NLP Programming Tutorial 1 – Unigram Language ModelLikelihood●Likelihood is the probability of some observed data(the test set Wtest), given the model M

P(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-73
17

NLP Programming Tutorial 1 – Unigram Language Model

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.58

log P(w=”i am a student”|M) =-18.45++log P(w=”my classes are hard”|M) = -33.67=-72.60
18

NLP Programming Tutorial 1 – Unigram Language Model

Calculating Logs●

Python's math package has a function for logs

$ ./my-program.py
4.60517018599
2.019

NLP Programming Tutorial 1 – Unigram Language Model

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)=( 68.43i am a student

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

61.32

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

NLP Programming Tutorial 1 – Unigram Language ModelPerplexity●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=521

NLP Programming Tutorial 1 – Unigram Language Model

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/722

NLP Programming Tutorial 1 – Unigram Language Model

Exercise23

NLP Programming Tutorial 1 – Unigram Language Model

Exercise●Write two programs
train-unigram: Creates a unigram model● test-unigram: Reads a unigram model and calculates
entropy and coverage for the test set●●

Test them test/01-train-input.txt test/01-test-input.txt●

Train the model on data/wiki-en-train.word●●Calculate entropy and coverage on data/wiki-entest.word
Report your scores next week
24

NLP Programming Tutorial 1 – Unigram Language Modeltrain-unigram Pseudo-Codecreate a map counts
create a variable total_count = 0for each line in the training_file
split line into an array of words
append “
” to the end of words
for each word in words
add 1 to counts[word]
add 1 to total_countopen the model_file for writingfor each word, count in counts
probability = counts[word]/total_countprint word, probability to model_file25

NLP Programming Tutorial 1 – Unigram Language Model

test-unigram Pseudo-Code
λ1 = 0.95, λunk = 1-λ1, V = 1000000, W = 0, H = 0

Load Modelcreate a map probabilities
for each line in model_file
split line into w and P
set probabilities[w] = P

Test and Print
for each line in test_file
split line into an array of words
append “
” to the end of words
for each w in words
add 1 to W
set P = λunk / V
if probabilities[w] exists
set P += λ1 * probabilities[w]else
add 1 to unk
add -log2 P to H
print “entropy = ”+H/W
print “coverage = ” + (W-unk)/W26

NLP Programming Tutorial 1 – Unigram Language Model

Thank You!

27