Natural Language UnderstandingStatistical Language Modeling


原 PPT 独立图片资源
Natural Language
Understanding

Statistical Language Modeling
Mingming Sun
BIMSA

Outline


原 PPT 独立图片资源
Outline
Statistical Language Modeling
Building a N-Gram Language Model
Generalization to Unseen Words
Generation
Evaluation

2.1 Statistical Language Modeling 2.1.1 Statistical Language Modeling



原 PPT 独立图片资源

2.1 Statistical Language Modeling 2.1.1 Statistical Language Modeling

原 PPT 独立图片资源

Problem: Is this Document Natural?


原 PPT 独立图片资源
Problem: Is this Document Natural?

Symbolic Approach:
Decompose the document into sentences and paragraphs;
Check whether each sentence is generated by valid generative gramma;
Check whether the former and latter sentences/paragraphs satisfy coherent relations;
Check whether the knowledge stated in the document be consistent with the real world.
…
Statistical Approach
Check whether 𝑝(𝐷)>𝜃

Language Modeling


原 PPT 独立图片资源
Language Modeling

Probabilistic Sequence Model:



The sentence/document is generated by Next-Word-Generation: generate 𝑤𝑖 given 𝑤1,⋯, 𝑤𝑖−1.
原 PPT 独立图片资源

Predicting Next Words


原 PPT 独立图片资源
Predicting Next Words

The water of Walden Pond is beautifully ...
blue
green
clear
refrigerator
that
tomorrow

Examples


原 PPT 独立图片资源
Examples

𝑃(“𝑇ℎ𝑒 𝑤𝑎𝑡𝑒𝑟 𝑜𝑓 𝑊𝑎𝑙𝑑𝑒𝑛 𝑃𝑜𝑛𝑑”)= 𝑃(𝑇ℎ𝑒)
× 𝑃(𝑤𝑎𝑡𝑒𝑟|𝑇ℎ𝑒)
×  𝑃(𝑜𝑓|𝑇ℎ𝑒 𝑤𝑎𝑡𝑒𝑟) 
×  𝑃(𝑊𝑎𝑙𝑑𝑒𝑛|𝑇ℎ𝑒 𝑤𝑎𝑡𝑒𝑟 𝑜𝑓) 
×  𝑃(𝑃𝑜𝑛𝑑|𝑇ℎ𝑒 𝑤𝑎𝑡𝑒𝑟 𝑜𝑓 𝑊𝑎𝑙𝑑𝑒𝑛)

How to estimate these probabilities


原 PPT 独立图片资源
How to estimate these probabilities

Could we just count and divide?





No! Too many possible sentences!
We’ll never see enough data for estimating these
原 PPT 独立图片资源
原 PPT 独立图片资源
=

Markov Assumption


原 PPT 独立图片资源
Markov Assumption

原 PPT 独立图片资源
原 PPT 独立图片资源
≈
Simplify the problem by applying Markov Assumption:

Bigram Model


原 PPT 独立图片资源
Bigram Model

原 PPT 独立图片资源
原 PPT 独立图片资源

N-gram Model


原 PPT 独立图片资源
N-gram Model

原 PPT 独立图片资源
Generalize the Markov Assumption to Higher Order Markov Assumption:
Given the previous 𝑛−1 words, probability of  𝑛-th word is independent of words prior to 𝑛−𝑁+1 words.

Simplest Case: Unigram Model


原 PPT 独立图片资源
Simplest Case: Unigram Model

To him swallowed confess hear both . Which . Of save on trail for are ay device and rote life have
Hill he late speaks ; or ! a more to leg less first you enter
Months the my and issue of year foreign new exchange’s September
were recession exchange new endorsed a acquire to six executives
原 PPT 独立图片资源

Example of Bigram Model


原 PPT 独立图片资源
Example of Bigram Model

Why dost stand forth thy canopy, forsooth; he is this palpable hit the King Henry. Live king. Follow.
What means, sir. I confess she? then all sorts, he is trim, captain.
Last December through the way to preserve the Hudson corporation N. B. E. C. Taylor would seem to complete the major central planners one gram point five percent of U. S. E. has already old M. X. corporation of living
on information such as more frequently fishing to keep her
原 PPT 独立图片资源

Pros and Cons of N-gram Model


原 PPT 独立图片资源
Pros and Cons of N-gram Model

Pros:
Make Statistical Language Model feasible, greatly promote the research;
Cons:
N-grams do not modeling semantic relationships.
N-grams can't handle long-distance dependencies.
“The soups that I made from that new cookbook I bought yesterday were amazingly delicious."

Application of N-Gram Model


原 PPT 独立图片资源
Application of N-Gram Model

Build a N-Gram Model from a Corpus, and use it to:
Calculate the probability of a sequence:
Select most possible (in ASR) /natural (in MT) result;
Generate a sequence:
Input completion in Input Method/Code Editing/Search Query;

2.1 Statistical Language Modeling 2.1.2 Building an N-gram Language Model



原 PPT 独立图片资源

2.1 Statistical Language Modeling 2.1.2 Building an N-gram Language Model

原 PPT 独立图片资源

Build a N-Gram Model from Corpus


原 PPT 独立图片资源
Build a N-Gram Model from Corpus

Language distributions are different among problem domains:
If task-specific (legal or medical), use a training corpus that has a similar genre to your task.
Variety is important:
Make sure to cover different kinds of language patterns in the task domain.

Estimating Bigram Probabilities


原 PPT 独立图片资源
Estimating Bigram Probabilities

<s> I am Sam </s>
<s> Sam I am </s>
<s> I do not like green eggs and ham </s>
原 PPT 独立图片资源
原 PPT 独立图片资源
sam.tiff

More examples: Berkeley Restaurant Project


原 PPT 独立图片资源
More examples:
Berkeley Restaurant Project

can you tell me about any good cantonese restaurants close by
tell me about chez panisse
i’m looking for a good place to eat breakfast
when is caffe venezia open during the day

Raw Bigram Counts: 9222 Sentences


原 PPT 独立图片资源
Raw Bigram Counts: 9222 Sentences

berp1

Raw Bigram Probabilities


原 PPT 独立图片资源
Raw Bigram Probabilities

berp3
berp2

Bigram estimates of sentence probabilities


原 PPT 独立图片资源
Bigram estimates of sentence probabilities

𝑃(<s> 𝐼 𝑤𝑎𝑛𝑡 𝑒𝑛𝑔𝑙𝑖𝑠ℎ 𝑓𝑜𝑜𝑑 </𝑠>) 
=    𝑃(𝐼|<𝑠>)  
×  𝑃(𝑤𝑎𝑛𝑡|𝐼) 
×  𝑃(𝑒𝑛𝑔𝑙𝑖𝑠ℎ|𝑤𝑎𝑛𝑡)
×  𝑃(𝑓𝑜𝑜𝑑|𝑒𝑛𝑔𝑙𝑖𝑠ℎ)   
×  𝑃(</𝑠>|𝑓𝑜𝑜𝑑)
=  .000031

Dealing with scale in large n-grams


原 PPT 独立图片资源
Dealing with scale in large n-grams

Log Probabilities: avoids underflow from multiplying many small numbers
原 PPT 独立图片资源

Larger ngrams: 4-grams, 5-grams


原 PPT 独立图片资源
Larger ngrams: 4-grams, 5-grams

N-grams from Corpus of Contemporary American English (COCA) 1 billion words (Davies 2020)
Google Web 5-grams (Franz and Brants 2006) 1 trillion words)

Infini-grams (∞-grams)


原 PPT 独立图片资源
Infini-grams (∞-grams)

The biggest n-gram LM ever built to date.
Trained on 5 trillion tokens;
Contains about 5 quadrillion (or 5 thousand trillion, or 5x10^15) unique n-grams.

Larger-N is Better


原 PPT 独立图片资源
Larger-N is Better

原 PPT 独立图片资源
https://infini-gram.io/

But the world always surprise you


原 PPT 独立图片资源
But the world always surprise you

Shakespeare Corpus: 884,647 words , voc size =29,066;
Shakespeare produced 300,000 bigram types out of 844 million possible bigrams;
So 99.96% of the possible bigrams were never seen in the corpus ;
That sparsity is even worse for 4-grams;
But you may see them in applications.

2.1 Statistical Language Modeling 2.1.3 Generalization to Unseen Words



原 PPT 独立图片资源

2.1 Statistical Language Modeling 2.1.3 Generalization to Unseen Words

原 PPT 独立图片资源

Zero Probability Problem


原 PPT 独立图片资源
Zero Probability Problem

Training:
… ate lunch
… ate dinner
… ate a
… ate the
𝑃(𝑏𝑟𝑒𝑎𝑘𝑓𝑎𝑠𝑡 | 𝑎𝑡𝑒) = 0

Application: Probability

𝑃(𝐼 𝑎𝑡𝑒 𝑏𝑟𝑒𝑎𝑘𝑓𝑎𝑠𝑡) = 0
Application: Generation
Cannot generate breakfast

Smoothing


原 PPT 独立图片资源
Smoothing

We have sparse statistics

allegations
reports
claims
attack
request
man
outcome
…

allegations


attack

man
outcome
…
allegations
reports
claims
request



Steal probability mass to generalize better

Add-one Estimation (Laplace smoothing)


原 PPT 独立图片资源
Add-one Estimation (Laplace smoothing)

Pretend we saw each word one more time than we did
Just add one to all the counts!

MLE estimate:

Add-1 estimate:
原 PPT 独立图片资源
原 PPT 独立图片资源
原 PPT 独立图片资源

Backoff and Interpolation


原 PPT 独立图片资源
Backoff and Interpolation

More context length results in more Sparsity;
Less context reduces the Zero probability problem;
Condition on less context for contexts you know less about
Backoff:
use trigram if you have good evidence,
otherwise bigram, otherwise unigram
Interpolation:
mix unigram, bigram, trigram
Interpolation works better

Linear Interpolation


原 PPT 独立图片资源
Linear Interpolation

Simple interpolation


Lambdas conditional on context:
原 PPT 独立图片资源
原 PPT 独立图片资源
interp2

Backoff


原 PPT 独立图片资源
Backoff

Suppose you want:
𝑃(𝑝𝑎𝑛𝑐𝑎𝑘𝑒𝑠| 𝑑𝑒𝑙𝑖𝑐𝑖𝑜𝑢𝑠 𝑠𝑜𝑢𝑓𝑓𝑙é)
If the trigram probability is 0, use the bigram
𝑃(𝑝𝑎𝑛𝑐𝑎𝑘𝑒𝑠| 𝑠𝑜𝑢𝑓𝑓𝑙é)
If the bigram probability is 0, use the unigram
𝑃(𝑝𝑎𝑛𝑐𝑎𝑘𝑒𝑠)
Complication: need to discount the higher-order ngram so probabilities don't sum higher than 1 (e.g., Katz backoff)

Stupid Backoff


原 PPT 独立图片资源
Stupid Backoff

Backoff without discounting (not a true probability)
原 PPT 独立图片资源
原 PPT 独立图片资源

2.1 Statistical Language Modeling 2.1.4 Generation



原 PPT 独立图片资源

2.1 Statistical Language Modeling 2.1.4 Generation

原 PPT 独立图片资源

Generating Language using N-Gram Model


原 PPT 独立图片资源
Generating Language using N-Gram Model

The Shannon (1948) Visualization Method
Unigram



Bigram
REPRESENTING AND SPEEDILY IS AN GOOD APT OR COME CAN DIFFERENT NATURAL HERE HE THE A IN CAME THE TO OF TO EXPERT GRAY COME TO FURNISHES THE LINE MESSAGE HAD BE THESE.
THE HEAD AND IN FRONTAL ATTACK ON AN ENGLISH WRITER THAT THE CHARACTER OF THIS POINT IS THEREFORE ANOTHER METHOD FOR THE LETTERS THAT THE TIME OF WHO EVER TOLD THE PROBLEM FOR AN UNEXPECTED.
原 PPT 独立图片资源

How Shannon sampled those words in 1948


原 PPT 独立图片资源
How Shannon sampled those words in 1948

"Open a book at random and select a letter at random on the page. This letter is recorded. The book is then opened to another page and one reads until this letter is encountered. The succeeding letter is then recorded. Turning to another page this second letter is searched for and the succeeding letter recorded, etc."
Stack of open books

Sampling a word from a distribution


原 PPT 独立图片资源
Sampling a word from a distribution

原 PPT 独立图片资源

Visualizing Bigrams the Shannon Way


原 PPT 独立图片资源
Visualizing Bigrams the Shannon Way

Choose a random bigram (<𝑠>, 𝑤) according to its probability 𝑝(𝑤|<𝑠>);
Now choose a random bigram (𝑤, 𝑥)  according to its probability 𝑝(𝑥|𝑤);
And so on until we choose </𝑠>;
Then string the words together
<s> I
I want
want to
to eat
eat Chinese
Chinese food
food </s>
I want to eat Chinese food

Approximating Shakespeare


原 PPT 独立图片资源
Approximating Shakespeare

原 PPT 独立图片资源

The Wall Street Journal


原 PPT 独立图片资源
The Wall Street Journal

原 PPT 独立图片资源

2.1 Statistical Language Modeling 2.1.5 Evaluation



原 PPT 独立图片资源

2.1 Statistical Language Modeling 2.1.5 Evaluation

原 PPT 独立图片资源

Evaluation of N-Gram Model


原 PPT 独立图片资源
Evaluation of N-Gram Model

Extrinsic Evaluation:
Evaluate the model on external Task
Intrinsic Evaluation:
Directly measures language model performance at predicting words.
Doesn't necessarily correspond with real application performance
But gives us a single general metric for language models

Recall: Evaluating the Machine Learning Algorithms


原 PPT 独立图片资源
Recall: Evaluating the Machine Learning Algorithms

Training Data: Used to train a machine given a hyper-parameter setting;
Development Data: Evaluate the trained machines to select the best hyper-parameter setting;
Testing Data: Evaluate the real performance of the selected machine;
Datasets should be with the same distribution with the final task;
Datasets should be no overlap. Do not test on training data!
Train Data
Dev Data
Test Data

What is a Good Language Model


原 PPT 独立图片资源
What is a Good Language Model

A good LM prefers the next word that actually occurs;
Assign higher probability to “time” given “Once upon a _”;
Assign near zero probability to “and” given “Once upon a _”;
A good LM prefers “real” sentences:
Assign higher probability to “real” or “frequently observed” sentences
Assigns lower probability to “word salad” or “rarely observed” sentences

How to Evaluate N-Gram Model on a Dataset


原 PPT 独立图片资源
How to Evaluate N-Gram Model on a Dataset

The test set represents the real sentences;
The best LM assigns high probability to the entire test set.
A good performance metric for LM:
𝑝(𝑡𝑒𝑠𝑡 𝑠𝑒𝑡)
When comparing two LMs, A and B
We compute 𝑃𝐴(𝑡𝑒𝑠𝑡 𝑠𝑒𝑡) and 𝑃𝐵(𝑡𝑒𝑠𝑡 𝑠𝑒𝑡)
The one with larger probability is better.

The Problem of Probability as a Metric


原 PPT 独立图片资源
The Problem of Probability as a Metric

Probability of test set depends on the number of tokens in it:
Sentence probability gets smaller for longer sentences
Dataset probability gets smaller for larger dataset;
We’d prefer a metric that is per-word, normalized by length, so we could compare across texts of different lengths.

Perplexity


原 PPT 独立图片资源
Perplexity

Perplexity is the inverse probability of the test set, normalized by the number of words;





Minimizing perplexity is the same as maximizing probability
原 PPT 独立图片资源
pp2
pp3
Bigrams:
Chain rule:

Perplexity for Sentence and Corpus


原 PPT 独立图片资源
Perplexity for Sentence and Corpus

Compute the log likelihood for each sentence
Given a sentence 𝑆 = 𝑤1, 𝑤2, …, 𝑤𝑁, the log perplexity per word is:
𝐿𝑜𝑔 𝑃𝑃𝐿(𝑆)= −1𝑁∑𝑖=1𝑁  𝐿𝑜𝑔 𝑃(𝑤𝑖 |𝑤1, …, 𝑤𝑁−1)
Compute the perplexity for each sentence
𝑃𝑃𝐿(𝑆) = 𝑒𝑥𝑝(−1𝑁∑𝑖=1𝑁𝐿𝑜𝑔 𝑃(𝑤𝑖 |𝑤1, …, 𝑤𝑁−1))
Aggregate over all sentences in the corpus
Compute the total log-likelihood across all tokens then normalize by the total number of tokens:
𝑃𝑃𝐿𝐶𝑜𝑟𝑝𝑢𝑠 =𝑒𝑥𝑝( −1𝑁𝑡𝑜𝑡𝑎𝑙∑𝑆∈𝐶𝑜𝑟𝑝𝑢𝑠∑𝑖=1𝑁𝑆𝐿𝑜𝑔 𝑃(𝑤𝑖 |𝑤1, …, 𝑤𝑁𝑆−1)) 
where 𝑁𝑡𝑜𝑡𝑎𝑙 is the total number of tokens in the dataset.

Empirical Studies


原 PPT 独立图片资源
Empirical Studies

WSJ Dataset:
the Wall Street Journal newspaper
Training 38 million words, test 1.5 million words

Unigram
Bigram
Trigram
Perplexity
962
170
109