N-gram Language Models

Natural Language Processing 1

 Statistical Language Processing
• In the solution of many problems in the natural language processing, statistical
language processing techniques can be also used.
– optical character recognition
– spelling correction
– speech recognition
– machine translation
– part of speech tagging
– parsing
• Statistical techniques can be used to disambiguate the input.
• They can be used to select the most probable solution.
• Statistical techniques depend on the probability theory.
• To able to use statistical techniques, we will need corpora to collect statistics.
• Corpora should be big enough to capture the required knowledge.

Natural Language Processing 2

 Basic Probability
• Probability Theory: predicting how likely it is that something will happen.
• Probabilities: numbers between 0 and 1.
• Probability Function:
– P(A) means that how likely the event A happens.
– P(A) is a number between 0 and 1
– P(A)=1 => a certain event
– P(A)=0 => an impossible event
• Example: a coin is tossed three times. What is the probability of 3 heads?
– 1/8
– uniform distribution

Natural Language Processing 3

 Probability Spaces
• There is a sample space and the subsets of this sample space describe the events.
• Ω is a sample space.
– Ω is the certain event
– the empty set is the impossible event.

P(A) is between 0 and 1

P(Ω) = 1

Natural Language Processing 4

 Unconditional and Conditional Probability
• Unconditional Probability or Prior Probability
– P(A)
– the probability of the event A does not depend on other events.
• Conditional Probability -- Posterior Probability -- Likelihood
– P(A|B)
– this is read as the probability of A given that we know B.
Example:
– P(put) is the probability of to see the word put in a text
– P(on|put) is the probability of to see the word on after seeing the word put.

• Joint Probability
– P(A∩B) or P(A,B)
– the probability of the events A and B occur together

Natural Language Processing 5

Unconditional and Conditional Probability

P(A|B) = P(A∩B) / P(B)

P(B|A) = P(A∩B) / P(A)

Natural Language Processing 6

 Bayes’ Theorem
• Bayes’ theorem is used to calculate P(A|B) from given P(B|A).
• We know that:
P(A∩B) = P(A|B) P(B)
P(A∩B) = P(B|A) P(A)

• So, we will have:

𝐏 𝐁 𝐀 𝐏(𝐀) 𝐏 𝐀 𝐁 𝐏(𝐁)
𝐏𝐀𝐁 = 𝐏𝐁𝐀 =
𝐏𝐁 𝐏𝐀

Natural Language Processing 7

 Language Model
• Models that assign probabilities to sequences of words are called language models
(LMs).
• The simplest language model that assigns probabilities to sentences and
sequences of words is n-gram language model.
• An n-gram is a sequence of N words:
– A 1-gram (unigram) is a single word sequence of words like “please” or “ turn”.
– A 2-gram (bigram) is a two-word sequence of words like “please turn”, “turn your”, or
”your homework”.
– A 3-gram (trigram) is a three-word sequence of words like “please turn your”, or “turn your
homework”.
• We can use n-gram models to estimate the probability of the last word of an
n-gram given the previous words, and also to assign probabilities to entire word
sequences.

Natural Language Processing 8

 Probabilistic Language Models
• Probabilistic language models can be used to assign a probability to a sentence in
many NLP tasks.
– In many NLP applications, we can use the probability as a way to choose a better sentence
or word over a less-appropriate one.

• Machine Translation:
– P(high winds tonight) > P(large winds tonight)

• Spell Correction:
– Thek office is about ten minutes from here
– P(The office is) > P(Then office is)

• Speech Recognition:
– P(I saw a van) >> P(eyes awe of an)

• Summarization, question-answering, …

Natural Language Processing 9

 Probabilistic Language Models
• Our goal is to compute the probability of a sentence or sequence of words
W (=w1,w2,…,wn):
P(W) = P(w1,w2,…,wn)

• What is the probability of an upcoming word?:

– P(w5|w1,w2,w3,w4)

• A model that computes either of these:

– P(W) or P(wn|w1,w2…wn-1) is called a language model.

Natural Language Processing 10

 Chain Rule of Probability
• How can we compute probabilities of entire word sequences like w1,w2,…,wn?
– The probability of the word sequence w1,w2,…,wn is P(w1,w2,…,wn).
• We can use the chain rule of the probability to decompose this probability:
P(w1n) = P(w1) P(w2|w1) P(w3|w12) … P(wn|w1n-1)
𝐧

= 𝖦 𝐏 𝐰𝐤 𝐤−𝟏
𝐰𝟏 )
𝐤=𝟏

Example:
P(the man from jupiter) =
P(the) P(man|the) P(from|the man) P(jupiter|the man from)

Natural Language Processing 11

 Chain Rule of Probability
and Conditional Probabilities
• The chain rule shows the link between computing the joint probability of a sequence
and computing the conditional probability of a word given previous words.

• Definition of Conditional Probabilities:

P(B|A) = P(A,B) / P(A) P(A,B) = P(A) P(B|A)

• Conditional Probabilities with More Variables:

P(A,B,C,D) = P(A) P(B|A) P(C|A,B) P(D|A,B,C)

• Chain Rule:
P(w1… wn) = P(w1) P(w2|w1) P(w3|w1w2) … P(wn|w1…wn-1)

Natural Language Processing 12

 Computing Conditional Probabilities
• To compute the exact probability of a word given a long sequence of preceding
words is difficult (sometimes impossible).
• We are trying to compute P(wn|w1…wn-1) which is the probability of seeing wn after
seeing w1n-1.
• We may try to compute P(wn|w1…wn-1) exactly as follows:

P(wn|w1…wn-1) = count(w1…wn-1wn) / count(w1…wn-1)

• Too many possible sentences and we may never see enough data for estimating these
probability values.
• So, we need to compute P(wn|w1…wn-1) approximately.

Natural Language Processing 13

 N-Grams
• The intuition of the n-gram model (simplifying assumption):
– instead of computing the probability of a word given its entire history, we
can
approximate the history by just the last few words.
P(wn|w1…wn-1) ≈ P(wn) Unigram - no history is used
P(wn|w1…wn-1) ≈ P(wn|wn-1) bigram – one word history
P(wn|w1…wn-1) ≈ P(wn|wn-1wn-2) trigram – two words history
P(wn|w1…wn-1) ≈ P(wn|wn-1wn-2wn-3) 4-gram – Three words history
P(wn|w1…wn-1) ≈ P(wn|wn-1wn-2wn-3wn-4) 5-gram – Four words history

• In general, N-Gram is
P(wn|w …w
1 ) ≈ 𝐏(w |𝐰n𝐧−𝟏 )
𝐧−𝐍+𝟏
n-1

Natural Language Processing 14

 N-Grams
computing probabilities of word sequences

Unigrams -- P(w )
P(w1n) ≈ k k
Π
=1

Bigrams -- P(w | wk −1
P(w1n) ≈ k k
)
Π
=1

Trigrams -- P(w |w w
P(w1n) ≈ k k −1 k −2
Π
=1
k
)
n
P(wk | w
4-grams -- P(w1n) ≈ Π
k
w
k −1 k −2
w
k −3
=1
)
Natural Language Processing 15
 N-Grams
computing probabilities of word sequences (Sentences)
Unigram
P(<s> the man from jupiter came </s>) ≈
P(the) P(man) P(from) P(jupiter) P(came)

Bigram
P(<s> the man from jupiter came </s>) ≈
P(the|<s>) P(man|the) P(from|man) P(jupiter|from) P(came|jupiter) P(</s>|came)

Trigram
P(<s> the man from jupiter came </s>) ≈
P(the|<s> <s>) P(man|<s> the) P(from|the man) P(jupiter|man from)
P(came|from jupiter) P(</s>|jupiter came) P(</s>|came </s>)

Natural Language Processing 16

 N-gram models
• In general, a n-gram model is an insufficient model of a language because languages
have long-distance dependencies.
– “The computer(s) which I had just put into the machine room is (are) crashing.”
– But we can still effectively use N-Gram models to represent languages.
• Which N-Gram should be used as a language model?
– Bigger N, the model will be more accurate.
• But we may not get good estimates for N-Gram probabilities.
• The N-Gram tables will be more sparse.
– Smaller N, the model will be less accurate.
• But we may get better estimates for N-Gram probabilities.
• The N-Gram table will be less sparse.
– In reality, we do not use higher than Trigram (not more than Bigram).
– Generally in practical applications, Bi-Gram, Trigram and four-gram are used.
– How big are N-Gram tables with 10,000 words?
• Unigram -- 10,000
• Bigram – 10,000*10,000 = 100,000,000
• Trigram – 10,000*10,000*10,000 = 1,000,000,000,000

Natural Language Processing 17

 N-Grams and Markov Models
• The assumption that the probability of a word depends only on the previous word(s) is
called Markov assumption.
• Markov models are the class of probabilistic models that assume that we can predict
the probability of some future unit without looking too far into the past.
• A bigram is called a first-order Markov model (because it looks one token into the
past);
• A trigram is called a second-order Markov model;
• In general a N-Gram is called a N-1 order Markov model.

Natural Language Processing 18

Bi- Gram example – one word history
Eg: “about five minutes from” Assumption: Next word may be college or class.
P(college| about five minutes from) = Count (about five minutes from college) /
count (about five minutes from)
Note: start of the sentence <s> to be added
Count(about five minutes from college) = P(about | <s>) * P(five | about) * P(minutes | five)
*P(from | minutes) * P( college | from)
Count(about five minutes from) = P(about | <s>) * P(five | about) * P(minutes | five)
*P(from | minutes)
P(college| about five minutes from) = Count (about five minutes from college) /
count (about five minutes from)

=P(about | <s>) * P(five | about) * P(minutes | five)

*P(from | minutes) * P( college | from)
----------------------------------------------------------
P(about | <s>) * P(five | about) * P(minutes | five)
*P(from | minutes)
= P( college | from)
Similary for P(class| about five minutes from) = Count (about five minutes from class) /
count (about five minutes from)
= P( class| from)
Tri- gram example – two word history
Eg: “about five minutes from” Assumption: Next word may be college or class.
P(college| about five minutes from) = Count (about five minutes from college) /
count (about five minutes from)
Note: start of the sentence <s> to be added
Count(about five minutes from college) = P(five | <s> about) * P(minutes | about five)
*P(from | five minutes) * P( college | minutes from)
Count(about five minutes from) = P(five | <s> about) * P(minutes | about five)
*P(from | five minutes)
P(college| about five minutes from) = Count (about five minutes from college) /
count (about five minutes from)

=P(five | <s> about) * P(minutes | about five)

*P(from | five minutes) * P( college | minutes from)
----------------------------------------------------------
P(five | <s> about) * P(minutes | about five)
*P(from | five minutes)
= P( college | minutes from)
Similary for P(class| about five minutes from) = Count (about five minutes from class) /
count (about five minutes from)
= P( class| minute from)
Four gram example – three word history
Eg: “about five minutes from” Assumption: Next word may be college or class.
P(college| about five minutes from) = Count (about five minutes from college) /
count (about five minutes from)
Note: start of the sentence <s> to be added
Count(about five minutes from college) = P(minutes | <s> about five) * P(from | about five
minutes) *P(college | five minutes from)
Count(about five minutes from) = P(minutes | <s> about five) * P(from | about five
minutes)
P(college| about five minutes from) = Count (about five minutes from college) /
count (about five minutes from)
=P(minutes | <s> about five) * P(from | about five
minutes) *P(college | five minutes from)
----------------------------------------------------------
P(minutes | <s> about five) * P(from | about five
minutes)
= P( college | five minutes from)
Similary for P(class| about five minutes from) = Count (about five minutes from class) /
count (about five minutes from)
= P( class| five minute from)
 Estimating N-Gram Probabilities
• Estimating n-gram probabilities is called maximum likelihood estimation (or
MLE).
• We get the MLE estimate for the parameters of an n-gram model by getting counts
from a corpus, and normalizing the counts so that they lie between 0 and 1.

• Estimating bigram probabilities:

C(wn−1wn ) C(wn−1wn )
∑ w C(wn−1w)
P(wn|wn-1) = = where C is the count of
C(wn−1 ) that pattern in the corpus

• Estimating N-Gram probabilities

n−1 n−1 w)
P(w|n w n−N +1 ) = C(wn−N + 1n
n−1 )
C(w n−N +1

Natural Language Processing 22

 Estimating N-Gram Probabilities
Estimating Bi-gram probabilities – using frequency table we can
identify the probability
A mini-corpus: We augment each sentence with a special symbol <s> at the beginning of the
sentence, to give us the bigram context of the first word, and special end-symbol </s>.
Word Frequency
<s> I am Henry</s>
<s> I like college</s> <S> 7
<s> Do henry like college </s> </S> 7
<s>Henry I am </s> I 6
<s> Do I like henry </s>
Am 2
<s> Do I like college </s>
<s> I do like henry </s> Henry 5

Like 5
1. What is the most probable next word predicted by the model for the College 3
following word sequence?
do 4

1. <s> Do ?
P(</s> | do) = 0/4, P( I | do) =2/4, P( am | do) =0/4, P( henry | do) = 1/4,
P( like | do) = 1/4, P( college | do) = 0/4, P( do | do) = 0/4
Here I has more probability so the next word is Do I
Natural Language Processing 23
 Estimating N-Gram Probabilities Word Frequency

<S> 7
Estimating Bi-gram probabilities – cont…. </S> 7
2. <s> I like Henry ? I 6
P(</s> | henry ) = 3/5, P( I | henry) =1/5, P( am | henry) =0/5, Am 2
P( henry | henry) = 0/5,P( like | henry) = 1/5, P( college | henry) = 0/5, Henry 5

P( do | henry) = 0/5 Like 5

Here </s> has more probability College 3
so the next word is End of the sentence. do 4
-----------------------------------------------------------------------------------------------------
Estimating Tri-gram probabilities
1. What is the most probable next word predicted by the model for the
following word sequence? By using tri-gram.
Do I like ?
P(I like) = 3
P(</s> | I like) = 0/3, P( I | I like) = 0/3, P( am | I like) = 0/3, P( henry | I like) = 1/3,
P( like| I like) = 0/3, P( college | I like) = 2/3, P( do | I like) = 0/3

Here college is more probable.

So the next word is college. Do I like college

Natural Language Processing 24

 Estimating N-Gram Probabilities
Estimating Four-gram probabilities
1. What is the most probable next word predicted by the model for the
following word sequence? By using four-gram
P(I like college) = 2
P(</s> | I like college) = 2/2, P( I | I like college) = 0/2, P( am | I like
college) = 0/2,
P( henry I like college) = 0/2, P( like| I like college) = 0/2, P( college | I like
college) = 0/2,
P( do | I like college) = 0/2
Here </s> end of the sentence is more probable.
--------------------------------------------------------------------------------------------
Word Frequency
Which of the following sentence is better?
Gets higher probability with this model. Use bigram. <S> 7
</S> 7
1. <s> I like college </s>, 2. <s> Do I like henry </s>
I 6
<s> I like college </s> = P(i/<s>)*P(like/I)*P(college/like)*P(</s>/college) Am 2
= (3/7)*(3/6)*(3/5)*(3/3) = 9/70 =0.13 Henry 5
<s> Do I like henry </s> = P(do/<s>)*P(I/do)*P(like/i)*P(henry/like)*
Like 5
P(</s>/henry) Colleg 3
=(3/7)*(2/4)*(3/6)*(2/5)*(3/5)=9/350 = 0.025 e
So the first sentence have high probability. Natural Language Processing
do 4
25
 Simple (Unsmoothed) N-gram in NLP
A simple unsmoothed n-gram is a sequence of "n" words taken directly from a text
without any adjustments, where each sequence represents a unit of analysis; for
example, if considering a sentence "The quick brown fox jumps", a unigram (n=1)
would be "The", "quick", "brown", "fox", "jumps", while a bigram (n=2) would be
"The quick", "quick brown", "brown fox", "fox jumps".

Key points about unsmoothed n-grams:

No smoothing:

Unlike smoothed n-grams, unsmoothed models directly calculate the probability of

an n-gram based on its raw frequency in the text, which can lead to issues with
unseen n-grams (words not present in the training data) having a probability of
zero.
Example with a sentence:
Unigrams (n=1): "The", "quick", "brown", "fox", "jumps"
Bigrams (n=2): "The quick", "quick brown", "brown fox", "fox jumps"
Trigrams (n=3): "The quick brown", "quick brown fox", "brown fox jumps"
Laplace (Add-One) Smoothing: Word Frequency
Which sentence has more probable? <S> 7
1. <s> like college </s> </S> 7
=P(like / <s>) * P(college/ like) * P(</s>/college) I 6
Am 2
= (0/7)* (3/5)*(3/3) = 0
Henry 5
2. <s> Do I like henry </s>
= P(do/<s>)*P(I/do)*P(like/i)*P(henry/like)*P(</s>/henry) Like 5
College 3
=(3/7)*(2/4)*(3/6)*(2/5)*(3/5)=9/350 = 0.025
As per the value 2nd statement is more probable do 4
But in real like college has more probable, bec of zero probability its showing wrong
answer.
To avoid zero probability we need to use laplace smoothing.:
In numerator we have to add 1.
In denominator we have to add number based on unique words. In this corpus we have 7
unique words.
1. <s> like college </s>
=P(like / <s>) * P(college/ like) * P(</s>/college)== (0+1/7+7)* (3+1/5+7)*(3+1/3+7)
=(1/14)*(4/12)*(4/10) = 0.0095
2. . <s> Do I like henry </s>
= P(do/<s>)*P(I/do)*P(like/i)*P(henry/like)*P(</s>/henry)
=(3+1/7+7)*(2+1/4+7)*(3+1/6+7)*(2+1/5+7)*(3+1/5+7)=9/350 = 0.0020
 Evaluating Language Models

• Does our language model prefer good sentences to bad ones?

– Assign higher probability to “real” or “frequently observed” sentences than
“ungrammatical” or “rarely observed” sentences?

• We train parameters of our model on a training set.

• We test the model’s performance on data we haven’t seen.

– A test set is an unseen dataset that is different from our training set, totally
unused.

• An evaluation metric tells us how well our model does on the test set.

Natural Language Processing 28

 Evaluating Language Models
Extrinsic Evaluation
• Extrinsic Evaluation of a N-gram language model is to use it in an application and
measure how much the application improves.

• To compare two language models A and B:

– Use each of language model in a task such as spelling corrector, MT system.
– Get an accuracy for A and for B
• How many misspelled words corrected properly
• How many words translated correctly
– Compare accuracy for A and B
• The model produces the better accuracy is the better model.

• Extrinsic evaluation can be time-consuming.

Natural Language Processing 29

 Evaluating Language Models
Intrinsic Evaluation
• An intrinsic evaluation metric is one that measures the quality of a model
independent of any application.

• When a corpus of text is given and to compare two different n-gram models,
– Divide the data into training and test sets,
– Train the parameters of both models on the training set, and
– Compare how well the two trained models fit the test set.
• Whichever model assigns a higher probability to the test set

• In practice, probability-based metric called perplexity is used instead of

raw probability as our metric for evaluating language models.

Natural Language Processing 30

 Evaluating Language Models
Perplexity
• The best language model is one that best predicts an unseen test set
– Gives the highest P(testset)
• The perplexity of a language model on a test set is the inverse probability of the
test set, normalized by the number of words.
• Minimizing perplexity is the same as maximizing probability
• The perpelexity PP for a test set W=w1w2…wN is

PP(W) by chain rule

• The perpelexity PP for bigrams:

PP(W)

Natural Language Processing 31

 Evaluating Language Models
Perplexity as branching factor
• Perplexity can be seen as the weighted average branching factor of a language.
– The branching factor of a language is the number of possible next words that can follow
any
word.
• Let’s suppose a sentence consisting of random digits
• What is the perplexity of this sentence according to a model that assign P=1/10 to each
digit?

Natural Language Processing 32

 Evaluating Language Models
Perplexity
• Lower perplexity = better model
• Training 38 million words, test 1.5 million words, WSJ

• An intrinsic improvement in perplexity does not guarantee an (extrinsic) improvement in

the performance of a language processing task like speech recognition or machine
translation.
– Nonetheless, because perplexity often correlates with such improvements, it is commonly used
as a quick check on an algorithm.
– But a model’s improvement in perplexity should always be confirmed by an end-to-end
evaluation of a real task before concluding the evaluation of the model.
Eg: Perplexity for Bigram : <s> I Like College </s>
P(W) =P(I/<s>)*P(like/I)*P(college/Like)*P(</s>/college) =(3/7)*(3/6)*(3/5)*(3/3)=9/70
=0.13
PP(W)=(1/0.13)1/4 =1.67 (4 represent no. of terms)
Eg: Perplexity for Trigram : <s> I Like College </s>
P(W)=P(like/<s> I)*P(college/I Like)*P(</s>/Like college) =(1/3)*(2/3)*(3/3)=2/9 =0.22
PP(W)=(1/0.22)1/3 =1.66 (3 represent no. Natural Language Processing
of terms) (less perplexity) 33