Evaluation of Language Models
Smoothing
Evaluating Language Model
Evaluation of Language Models, Basic Smoothing
Pawan Goyal (IIT Kharagpur)
Does it prefer good sentences to bad sentences?
Assign higher probability to real (or frequently observed) sentences than ungrammatical (or rarely observed) ones
Week 2: Lecture 5
2 / 16
Evaluating Language Model
Evaluation of Language Models, Basic Smoothing
Pawan Goyal (IIT Kharagpur)
Does it prefer good sentences to bad sentences?
Assign higher probability to real (or frequently observed) sentences than ungrammatical (or rarely observed) ones
Training and Test Corpora
Parameters of the model are trained on a large corpus of text, called
training set.
Performance is tested on a disjoint (held-out) test data using an
evaluation metric
Two ways of evaluating a Language Model — extrinsic and intrinsic
Week 2: Lecture 5
2 / 16
Extrinsic evaluation of N-grams models
Evaluation of Language Models, Basic Smoothing
3 / 16
Pawan Goyal (IIT Kharagpur)
Comparison of two models, A and B
Use each model for one or more tasks: spelling corrector, speech recognizer, machine translation
Get accuracy values for A and B Compare accuracy for A and B
Week 2: Lecture 5
What’s a metric for MT?
Are there bias fairness issues?
Intrinsic evaluation: Perplexity
Evaluation of Language Models, Basic Smoothing
Pawan Goyal (IIT Kharagpur)
Intuition: The Shannon Game
How well can we predict the next word?
Week 2: Lecture 5
4 / 16
Intrinsic evaluation: Perplexity
Evaluation of Language Models, Basic Smoothing
Pawan Goyal (IIT Kharagpur)
Intuition: The Shannon Game
How well can we predict the next word?
I always order pizza with cheese and .. . The president of India is .. .
I wrote a .. .
How well does a Language Model work in predicting the next word?
Week 2: Lecture 5
4 / 16
Intrinsic evaluation: Perplexity
Evaluation of Language Models, Basic Smoothing
Pawan Goyal (IIT Kharagpur)
Intuition: The Shannon Game
How well can we predict the next word?
I always order pizza with cheese and .. . The president of India is .. .
I wrote a .. .
Unigram model doesn’t work for this game.
since it does not use the context (previous words)
Week 2: Lecture 5
4 / 16
Intrinsic evaluation: Perplexity
Evaluation of Language Models, Basic Smoothing
Pawan Goyal (IIT Kharagpur)
Intuition: The Shannon Game
How well can we predict the next word?
I always order pizza with cheese and .. . The president of India is .. .
I wrote a .. .
Unigram model doesn’t work for this game.
A better model of text
is one which assigns a higher probability to the actual word
Week 2: Lecture 5
4 / 16
Perplexity
Evaluation of Language Models, Basic Smoothing
Pawan Goyal (IIT Kharagpur)
The best language model is one that best predics an unseen test set
Perplexity (PP(W))
Perplexity is the inverse probability of the test data, normalized by the number of words:
Week 2: Lecture 5
5 / 16
Perplexity
Evaluation of Language Models, Basic Smoothing
Pawan Goyal (IIT Kharagpur)
The best language model is one that best predics an unseen test set
Perplexity (PP(W))
Perplexity is the inverse probability of the test data, normalized by the number
of words:
1 2 N
PP(W)= P(w w .. . w )
— 1
N
Week 2: Lecture 5
5 / 16
Perplexity
Evaluation of Language Models, Basic Smoothing
Pawan Goyal (IIT Kharagpur)
The best language model is one that best predics an unseen test set
Perplexity (PP(W))
Perplexity is the inverse probability of the test data, normalized by the number
of words:
1 2 N
PP(W)= P(w w .. . w )
— 1
N
Applying chain Rule
Week 2: Lecture 5
5 / 16
Perplexity
Evaluation of Language Models, Basic Smoothing
Pawan Goyal (IIT Kharagpur)
The best language model is one that best predics an unseen test set
Perplexity (PP(W))
Perplexity is the inverse probability of the test data, normalized by the number
of words:
1 2 N
PP(W)= P(w w .. . w )
— 1
N
Applying chain Rule
For bigrams
This expression will be different for different LMs.
Week 2: Lecture 5
5 / 16
Evaluation of Language Models, Basic Smoothing
Pawan Goyal (IIT Kharagpur)
Example: A Simple Scenario
Consider a sentence consisting of N random digits
Week 2: Lecture 5
6 / 16
Example: A Simple Scenario
Evaluation of Language Models, Basic Smoothing
Pawan Goyal (IIT Kharagpur)
Consider a sentence consisting of N random digits
Find the perplexity of this sentence as per a model that assigns a probability p = 1/10 to each digit.
Week 2: Lecture 5
6 / 16
Example: A Simple Scenario
Evaluation of Language Models, Basic Smoothing
Pawan Goyal (IIT Kharagpur)
Consider a sentence consisting of N random digits
Find the perplexity of this sentence as per a model that assigns a probability p = 1/10 to each digit.
Week 2: Lecture 5
6 / 16
Example: A Simple Scenario
Evaluation of Language Models, Basic Smoothing
Pawan Goyal (IIT Kharagpur)
Consider a sentence consisting of N random digits
Find the perplexity of this sentence as per a model that assigns a probability p = 1/10 to each digit.
Week 2: Lecture 5
6 / 16
Lower perplexity = better model
Evaluation of Language Models, Basic Smoothing
Pawan Goyal (IIT Kharagpur)
WSJ Corpus
Training: 38 million words
Test: 1.5 million words
LM trained over the training set
Perplexity computed over the test set
Week 2: Lecture 5
7 / 16
Lower perplexity = better model
Evaluation of Language Models, Basic Smoothing
Pawan Goyal (IIT Kharagpur)
WSJ Corpus
Training: 38 million words
Test: 1.5 million words
What do these values indicate?
In other words, how to interpret the value of perplexity?
Week 2: Lecture 5
7 / 16
Lower perplexity = better model
Evaluation of Language Models, Basic Smoothing
Pawan Goyal (IIT Kharagpur)
WSJ Corpus
Training: 38 million words
Test: 1.5 million words
Unigram perplexity: 962?
The model is as confused on test data as if it had to choose uniformly and independently among 962 possibilities for each word.
Week 2: Lecture 5
7 / 16
Once we have built a Language Model, what can we do?
One interesting application - generate sentences / word sequences
Evaluation of Language Models, Basic Smoothing
Pawan Goyal (IIT Kharagpur)
The Shannon Visualization Method
Use the language model to generate word sequences
Week 2: Lecture 5
8 / 16
The Shannon Visualization Method
Evaluation of Language Models, Basic Smoothing
Pawan Goyal (IIT Kharagpur)
Use the language model to generate word sequences
Choose a random bigram
(<s>,w) as per its probability
There is a bigram (<s>, w) for every word w in the vocabulary, and a probability for each such bigram.
Week 2: Lecture 5
8 / 16
One word w will be sampled according to these probabilities.
The Shannon Visualization Method
Use the language model to generate word sequences
Choose a random bigram (<s>,w) as per its probability
Choose a random bigram (w,x) as per its probability
Evaluation of Language Models, Basic Smoothing
Pawan Goyal (IIT Kharagpur)
Week 2: Lecture 5
8 / 16
The Shannon Visualization Method
Use the language model to generate word sequences
Choose a random bigram (<s>,w) as per its probability
Choose a random bigram (w,x) as per its probability
And so on until we choose
</s>
Evaluation of Language Models, Basic Smoothing
Pawan Goyal (IIT Kharagpur)
Week 2: Lecture 5
8 / 16
The Shannon Visualization Method
Use the language model to generate word sequences
Choose a random bigram (<s>,w) as per its probability
Choose a random bigram (w,x) as per its probability
And so on until we choose
</s>
Evaluation of Language Models, Basic Smoothing
Pawan Goyal (IIT Kharagpur)
Week 2: Lecture 5
8 / 16
Top-k vs. Top-p Sampling
Two strategies for truncating the next-token probability distribution before sampling
Kept
Excluded
K
Top-k Sampling (k = 3)
Keep only the k tokens with the highest probability, discard the rest.
40%
the
25%
a
15%
an
10%
this
6%
some
4%
one
Result: always keeps exactly 3 tokens — “the,” “a,” “an” (40+25+15 = 80% of the mass), regardless of how peaked or flat the distribution is.
P
Top-p Sampling (p = 0.9)
Keep the smallest set of top tokens whose cumulative probability ≥ p.
40%
the
25%
a
15%
an
10%
this
6%
some
4%
one
Result: keeps 4 tokens this time — adds “this” since 40+25+15+10 = 90% ≥ p. The candidate pool size adapts to the shape of the distribution.
Both methods renormalize the kept probabilities and sample from that shrunken distribution.
Shakespeare as Corpus
Evaluation of Language Models, Basic Smoothing
9 / 16
Pawan Goyal (IIT Kharagpur)
N = 884,647 tokens, V = 29,066
Shakespeare produced 300,000 bigram types out of V2 = 844 million possible bigrams.
Week 2: Lecture 5
Evaluation of Language Models, Basic Smoothing
10 / 16
Pawan Goyal (IIT Kharagpur)
Approximating Shakespeare
Week 2: Lecture 5
Problems with simple MLE estimate: zeros
Evaluation of Language Models, Basic Smoothing
Pawan Goyal (IIT Kharagpur)
In Shakespeare’s works, only 300,000 bigrams out of possible 844 million bigrams have non-zero probability.
So, even for a large corpus, most bigrams have probability zero.
Week 2: Lecture 5
11 / 16
Problems with simple MLE estimate: zeros
Evaluation of Language Models, Basic Smoothing
Pawan Goyal (IIT Kharagpur)
Training set
... denied the allegations
... denied the reports
... denied the claims
... denied the request
Test Data
... denied the offer
... denied the loan
Week 2: Lecture 5
11 / 16
Problems with simple MLE estimate: zeros
Evaluation of Language Models, Basic Smoothing
Pawan Goyal (IIT Kharagpur)
Training set
... denied the allegations
... denied the reports
... denied the claims
... denied the request
Test Data
... denied the offer
... denied the loan
Zero probability n-grams
P(offer | denied the) = 0
The test set will be assigned a probability 0 And the perplexity can’t be computed
Week 2: Lecture 5
11 / 16
Evaluation of Language Models, Basic Smoothing
Pawan Goyal (IIT Kharagpur)
Language Modeling: Smoothing
Week 2: Lecture 5
12 / 16
Language Modeling: Smoothing
Evaluation of Language Models, Basic Smoothing
Pawan Goyal (IIT Kharagpur)
With sparse statistics
Probabilities: 3/7, 2/7, 1/7, 1/7
But it is not a good idea to assign probability zero to all other words in the vocabulary.
Smoothing: transfer some probability mass from these words (for which probability is already non-zero) to other words as well. There are several ways to do smoothing.
Week 2: Lecture 5
12 / 16
Language Modeling: Smoothing
Evaluation of Language Models, Basic Smoothing
Pawan Goyal (IIT Kharagpur)
With sparse statistics
Steal probability mass to generalize better
Distribute the probability mass of 2/7 among the other words
Week 2: Lecture 5
12 / 16
Laplace Smoothing (Add-one estimation)
Evaluation of Language Models, Basic Smoothing
Pawan Goyal (IIT Kharagpur)
Pretend as if we saw each word (N-gram) one more time that we actually did
Week 2: Lecture 5
13 / 16
Laplace Smoothing (Add-one estimation)
Evaluation of Language Models, Basic Smoothing
Pawan Goyal (IIT Kharagpur)
Pretend as if we saw each word (N-gram) one more time that we actually did
Just add one to all the counts!
Week 2: Lecture 5
13 / 16
Laplace Smoothing (Add-one estimation)
Evaluation of Language Models, Basic Smoothing
Pawan Goyal (IIT Kharagpur)
Pretend as if we saw each word (N-gram) one more time that we actually did
Just add one to all the counts!
Week 2: Lecture 5
13 / 16
Laplace Smoothing (Add-one estimation)
Evaluation of Language Models, Basic Smoothing
Pawan Goyal (IIT Kharagpur)
Pretend as if we saw each word (N-gram) one more time that we actually did
Just add one to all the counts!
Week 2: Lecture 5
13 / 16
Reconstituted counts as effect of smoothing
Evaluation of Language Models, Basic Smoothing
Pawan Goyal (IIT Kharagpur)
Effective bigram count (c*(wn—1wn))
Week 2: Lecture 5
14 / 16
More general formulations: Add-k
Evaluation of Language Models, Basic Smoothing
Pawan Goyal (IIT Kharagpur)
Add k to the count of each n-gram
Week 2: Lecture 5
16 / 16
Binomial with Beta prior
More general formulations: Add-k
Evaluation of Language Models, Basic Smoothing
Pawan Goyal (IIT Kharagpur)
Let kV = m
Week 2: Lecture 5
16 / 16
More general formulations: Add-k
Evaluation of Language Models, Basic Smoothing
Pawan Goyal (IIT Kharagpur)
Unigram prior smoothing:
Week 2: Lecture 5
16 / 16
A good value of k or m?
Can be optimized on held-out set
There are several advanced smoothing algorithms:
Good-Turing Kneser-Ney
Basic idea - reallocate the probability mass of n-grams that have been seen (in the training data) to the n-grams that were never seen