NLP Programming Tutorial 2 – Bigram Language Model

NLP Programming Tutorial 2 Bigram Language Models

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

Review:
Calculating Sentence Probabilities●

We want the probability ofW = speech recognition system●

Represent this mathematically as:

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 = 
) = 12

NLP Programming Tutorial 2 – Bigram Language Model

Incremental Computation●

Previous equation can be written:∣W ∣+ 1P(W )=∏i =1 P( wi∣w 0 … wi−1 )●Unigram model ignored context:P( wi∣w 0 … wi−1 )≈P (w i)3

NLP Programming Tutorial 2 – Bigram Language Model

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=
)

4NLP Programming Tutorial 2 – Bigram Language Model

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

NLP Programming Tutorial 2 – Bigram Language Model

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

6

NLP Programming Tutorial 2 – Bigram Language ModelMaximum 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.5
7NLP Programming Tutorial 2 – Bigram Language Model

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 )1P( wi )=λ1 P ML ( wi )+ (1−λ 1)
N8

NLP Programming Tutorial 2 – Bigram Language Model

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!

9NLP Programming Tutorial 2 – Bigram Language ModelContext 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−1

10

NLP Programming Tutorial 2 – Bigram Language Model

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
11NLP Programming Tutorial 2 – Bigram Language Model

Programming Techniques

12

NLP Programming Tutorial 2 – Bigram Language Model

Inserting into Arrays●

To calculate n-grams easily, you may want to:
my_words = [“this”, “is”, “a”, “pen”]
my_words = [“
”, “this”, “is”, “a”, “pen”, “
”]●

This can be done with:
my_words.append(“
”) # Add to the end
my_words.insert(0, “
”) # Add to the beginning

13

NLP Programming Tutorial 2 – Bigram Language Model

Removing from Arrays●●Given an n-gram with wi-n+1 … wi, we may want thecontext wi-n+1 … wi-1
This can be done with:

my_ngram = “tokyo tower”
my_words = my_ngram.split(“ “) # Change into [“tokyo”, “tower”]
my_words.pop()# Remove the last element (“tower”)
my_context = “ “.join(my_words) # Join the array back together
print my_context

14

NLP Programming Tutorial 2 – Bigram Language Model

Exercise

15

NLP Programming Tutorial 2 – Bigram Language Model

Exercise●Write two programs
train-bigram: Creates a bigram model● test-bigram: Reads a bigram model and calculates
entropy on the test set●●

Test train-bigram on test/02-train-input.txt●

Train the model on data/wiki-en-train.word●●

Calculate entropy on data/wiki-en-test.word (if linear
interpolation, test different values of λ2)
Challenge:●●

Use Witten-Bell smoothing (Linear interpolation is easier)Create a program that works with any n (not just bi-gram)

16

NLP Programming Tutorial 2 – Bigram Language Modeltrain-bigram (Linear Interpolation)
create map counts, context_counts
for each line in the training_filesplit line into an array of words
append “
” to the end and “
” to the beginning of words
for each i in 1 to length(words)-1 # Note: starting at 1, after 
counts[“wi-1 wi”] += 1
# Add bigram and bigram context
context_counts[“wi-1”] += 1
counts[“wi”] += 1
# Add unigram and unigram context
context_counts[“”] += 1
open the model_file for writingfor each ngram, count in counts
split ngram into an array of words # “wi-1 wi” → {“wi-1”, “wi”}
remove the last element of words # {“wi-1”, “wi”} → {“wi-1”}
join words into context# {“wi-1”} → “wi-1”
probability = counts[ngram]/context_counts[context]
print ngram, probability to model_file17

NLP Programming Tutorial 2 – Bigram Language Model

test-bigram (Linear Interpolation)
λ1 = ???, λ2 = ???, V = 1000000, W = 0, H = 0
load model into probs
for each line in test_file
split line into an array of words
append “
” to the end and “
” to the beginning of words
for each i in 1 to length(words)-1# Note: starting at 1, after 

P1 = λ1 probs[“wi”] + (1 – λ1) / V# Smoothed unigram probability
P2 = λ2 probs[“wi-1 wi”] + (1 – λ2) * P1 # Smoothed bigram probability
H += -log2(P2)W += 1
print “entropy = ”+H/W
18

NLP Programming Tutorial 2 – Bigram Language Model

Thank You!

19