Transcript N-grams and Machine Learning

N-Grams and Corpus Based
Techniques for NLP
Sameer Maskey
1
Machine Learning for NLP
Supervised
Classification
Unsupervised
Regression
Clustering
Feature Selection
2
Example: Text Summarization





Let’s say we are doing text summarization
using sentence extraction
Someone gave us a document where each
sentence is scored between 1 to 20 and
Extracting top 10% scoring sentence can
potentially be a summary
We have 100 such documents
Problem: Use a machine learning technique
to build a model that predicts the score of
sentences in a new document
3
Example: Text Summarization
CORPUS
100 documents
Each sentence
scored (1 to 20)
Machine
Learning
CorpusBased
Model
4
Regression for our Text
Summarization Problem


For simplicity let’s assume all of documents are of
equal length ‘N’
Our training dataset (100 documents)



We have 100xN sentences in total
100xN scores, let’s call these scores y’s
For each sentence we know it’s position in the
document. Let’s call these sentence positions x’s
so we get 100xN sentence positions
X  {( x1 , y1 ), ( x2 , y2 )...( x( n 1) x100 , y( n 1) x100 ), ( xnx100 , ynx100 )}
5
Regression as Function
Approximation


Using our training data ‘X’ we must predict a
score for each sentence in a new document
We can do such prediction by finding a
function y=f(x) that fits the training data well


Need to find out what f(x) to use
Need to compute how good the training data fits
with the chosen f(x)
6
Empirical Risk Minimization



Need to compute how good the data fits the chosen
function f(x)
We can define a loss function L(y, f(x))
Find average loss:
Remp
1

N
N
 L( y , f ( x ))
i
i
i 1
Simple Loss Function:
L( yi , f ( xi ))  ( yi  f ( xi ))
2
7
Linear Regression


We can choose f(x) to be linear, polynomial,
exponential or any other class of functions
If we use linear function we get linear regression,
widely used modeling technique
f ( x; )  1 x  0
y  mx  c
Where m is slope and c is intercept on y axis
8
Text Summarization with
Linear Regression


We had Nx100 (xi, yi) pairs where x was sentence
position and y was score for the sentence
Let’s look at a sample plot
12
The line we have found by
minimizing average squared
(xi, f(xi))
error is our model
(summarizer)
Score Error (yi - f(xi))
10
8
6
Given any new ‘x’ (i.e.
sentence position of a new
document) we can predict ‘y’
– score that represents it’s
significance to summary
Series1
(xi, yi)
4
2
0
0
1
2
3
Sentence position
4
5
6
7
8
9
10
9
Naïve Bayes Classifier



Let’s assume instead of score between 1 to 20 for
each sentence, all the sentence have been classified
into two classes – IN SUMMARY (1) , NOT IN
SUMMARY (0)
Now, given a document we want to predict the class
(1) or (0) for each sentence in the document. All the
sentence in class (1) should be included in the
summary
This is a binary classification problem
10
Intuitive Example of Naïve
Bayes Classifier
All figures in the given example are from electronic textbook StatSoft
•
•
•
•
Let us assume the objects can be classified into RED or GREEN
We have a corpus with objected manually labeled as RED or GREEN
We need to figure out if the test object is RED or GREEN
Number of green objects is twice that of red. So, it is reasonable to
assume that a new object (not observed yet) is twice likely to be
green than red (prior probability)
11
Example (RED or GREEN
classification)
Prior probability of GREEN  # of GREEN objects
Total # of objects
Prior probability of RED 

# of RED objects
Total # of objects
There are total of 60 objects with 40 GREEN and 20
RED
Prior probability of GREEN  40
60
Prior probability of RED 
20
60
12
Example (RED or GREEN
classification)
Need to figure out if the
test object is GREEN or
RED

Looking at the picture it is reasonable to assume that likelihood
of object being RED or GREEN can be computed by number of
RED or GREEN objects in the vicinity
Likelihood of X being GREEN 
# of GREEN objects in vicinity of X
Total # of GREEN
Likelihood of X being RED 
# of RED objects in vicinity of X
Total # of RED
13
Example (RED or GREEN
classification)
Need to figure out if the
test object is GREEN or
RED

Looking at the picture it is reasonable to assume that likelihood
of object being RED or GREEN can be computed by number of
RED or GREEN objects in the vicinity
Likelihood of X being GREEN 
# of GREEN objects in vicinity of X  1/40
Total # of GREEN
Likelihood of X being RED 
# of RED objects in vicinity of X  3/20
Total # of RED
14
Example (RED or GREEN
classification)
Posterior probability of X being GREEN = Prior probability of GREEN x
Likelihood of X given GREEN
= 40/60 x 1/40
= 1/60
Posterior probability of X being RED = Prior probability of RED x
Likelihood of X given RED
= 20/60 x 3/40
= 1/40
Hence, we classify our new object X as RED using our
Bayesian classifier model.
15
Document Vectors

Document Vectors




Documents can be represented in different types of vectors:
binary vector, multinomial vector, feature vector
Binary Vector: For each dimension, 1 if the word type
is in the document and 0 otherwise
Multinomial Vector: For each dimension, count # of
times word type appears in the document
Feature Vector: Extract various features from the
document and represent them in a vector. Dimension
equals the number of features
16
Example of a multinomial
document vector
Screening of the critically acclaimed film NumaFung Reserved
tickets can be picked up on the day of the show at the box office at
Arledge Cinema. Tickets will not be reserved if not paid for in
advance.
4 THE
2 TICKETS
2 RESERVED
2 OF
2 NOT
2 BE
2 AT
1 WILL
1 UP
1 SHOW
1 SCREENING
1 PICKED
1 PAID
1 ON
1 OFFICE
1 NUMAFUNG
1 IN
1 IF
1 FOR
1 FILM
1 DAY
1 CRITICALLY
1 CINEMA
1 CAN
1 BOX
1 ARLEDGE
1 ADVANCE
1 ACCLAIMED
4
2
2
2
2
2
2
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
17
Example of a multinomial
document vector
4 THE
2 SEATS
2 RESERVED
2 OF
2 NOT
2 BE
2 AT
1 WILL
1 UP
1 SHOW
1 SHOWING
1 PICKED
1 PAID
1 ON
1 OFFICE
1 VOLCANO
1 IN
1 IF
1 FOR
1 FILM
1 DAY
1 CRITICALLY
1 CINEMA
1 CAN
4
2
2
2
2
2
2
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
But if you want to compare previous
vector to this new vector we cannot do
any computation like cosine measure with
this vector. Why?
->Different dimensions
Hence, if you have multiple
documents you need to first find
set of all words (dimensions) in
the set of documents. Values for
all the words that does not appear
in the given document is 0
18
Feature Vectors




Instead of just using words to represent documents,
we can also extract features and use them to
represent the document
For example, let’s classify History and Physics
documents
We are given ‘N’ documents which are labeled as
‘HISTORY’ or ‘PHYSICS’
We can extract features like document length (LN),
number of nouns (NN), number of verbs (VB),
number of person names (PN), number of place
(CN) names, number of organization names (ON),
number of sentences (NS), number of pronouns
(PNN)
19
Feature Vectors

Extracting such features you get a feature vector of length ‘K’
where ‘K’ is the number of dimensions (features) for each
document
Length
Noun Count
Verb Count
# Person
Name
# Place Name
# Orgzn
Name
.
.
.
780
45
3
4
7
67
23
420
12
56
0
7
3
4
.
.
.
.
.
.
HIST
PHYSICS
…
940
36
3
8
6
55
21
.
.
.
HIST
20
Feature Vectors
Length
Noun Count
Verb Count
# Person
Name
# Place Name
# Orgzn
Name
.
.
.
780
45
3
4
7
67
23
420
12
56
0
7
3
4
.
.
.
.
.
.
HIST

PHYSICS
…
940
36
3
8
6
55
21
940
36
3
8
6
55
21
.
.
.
.
.
.
HIST
HIST
After such feature vector representation we can use various
learning algorithms including Naïve Bayes, Decision Trees, to
classify the new document using the training document set
21
N-Grams
some of the following slides
are from Julia’s lecture
22
N-grams



N-grams  ‘N-words’ ?
It’s ‘N’ consecutive words that one can find in
a given corpus or set of documents ?
‘N-gram’ model is a probabilistic model that
computes probability of Nth word occurring
after seeing ‘N-1’ words – also known as
language model in speech recognition
23
Some Interesting Facts




The most frequent 250 words takes account of
approximately 50% of all tokens in any random text
‘the’ is usually the most frequent word
‘the’ occurs 69,971 times in 1 million word Brown
corpus (7%)
The top 20 words in 1 year of Wall Street Journal is

The, of, to, in, and, for, that, is, on, it, by, with, as, at, said,
mister, from, its, are, he, million
24
Next Word Prediction

From a NY Times story...





Stocks ...
Stocks plunged this ….
Stocks plunged this morning, despite a cut in
interest rates
Stocks plunged this morning, despite a cut in
interest rates by the Federal Reserve, as Wall ...
Stocks plunged this morning, despite a cut in
interest rates by the Federal Reserve, as Wall
Street began
25


Stocks plunged this morning, despite a cut in
interest rates by the Federal Reserve, as Wall
Street began trading for the first time since last …
Stocks plunged this morning, despite a cut in
interest rates by the Federal Reserve, as Wall
Street began trading for the first time since last
Tuesday's terrorist attacks.
26
Human Word Prediction


Clearly, at least some of us have the ability to
predict future words in an utterance.
How?



Domain knowledge
Syntactic knowledge
Lexical knowledge
27
Claim


A useful part of the knowledge needed to allow Word
Prediction can be captured using simple statistical
techniques
In particular, we'll rely on the notion of the probability
of a sequence (a phrase, a sentence)
28
Applications

Why do we want to predict a word, given some
preceding words?
Rank the likelihood of sequences containing various
alternative hypotheses, e.g. for ASR
Theatre owners say popcorn/unicorn sales have doubled...
 Assess the likelihood/goodness of a sentence, e.g. for text
generation or machine translation
The doctor recommended a cat scan.

29
N-Gram Models of Language


Use the previous N-1 words in a sequence to
predict the next word
Language Model (LM)


unigrams, bigrams, trigrams,…
How do we train these models?

Very large corpora
30
Counting Words in Corpora

What is a word?





e.g., are cat and cats the same word?
September and Sept?
zero and oh?
Is _ a word? * ? ‘(‘ ?
How many words are there in don’t ?
Gonna ?
31
Terminology




Sentence: unit of written language
Utterance: unit of spoken language
Types: number of distinct words in a corpus
(vocabulary size)
Tokens: total number of words
32
Corpora

Corpora are collections of text and speech





Brown Corpus
Wall Street Journal
AP news
DARPA/NIST text/speech corpora (Call Home,
ATIS, switchboard, Broadcast News, TDT,
Communicator)
TRAINS, Radio News
33
Simple N-Grams

Assume a language has V word types in its
lexicon, how likely is word x to follow word y?


Simplest model of word probability: 1/V
Alternative 1: estimate likelihood of x occurring in
new text based on its general frequency of
occurrence estimated from a corpus (unigram
probability)
popcorn is more likely to occur than unicorn

Alternative 2: condition the likelihood of x
occurring in the context of previous words
(bigrams, trigrams,…)
mythical unicorn is more likely than mythical popcorn
34
Computing the Probability of a
Word Sequence

Conditional Probability


The Chain Rule generalizes to multiple events


P(A1, …,An) = P(A1) P(A2|A1) P(A3|A1,A2)…P(An|A1…An-1)
Compute the product of component conditional
probabilities?


P(A1,A2) = P(A1) P(A2|A1)
P(the mythical unicorn) = P(the) P(mythical|the)
P(unicorn|the mythical)
The longer the sequence, the less likely we are to
find it in a training corpus
P(Most biologists and folklore specialists believe that in fact the
mythical unicorn horns derived from the narwhal)

Solution: approximate using n-grams
35
Bigram Model

n1
Approximate P(wn |w1 )



by P(wn |wn 1)
P(unicorn|the mythical) by P(unicorn|mythical)
Markov assumption: the probability of a word
depends only on the probability of a limited
history
Generalization: the probability of a word
depends only on the probability of the n
previous words



trigrams, 4-grams, …
the higher n is, the more data needed to train
backoff models
36
Using N-Grams

For N-gram models
P(wn |w1n1)  P(wn |wnn1N 1)



P(wn-1,wn) = P(wn | wn-1) P(wn-1)
By the Chain Rule we can decompose a joint
probability, e.g. P(w1,w2,w3)
P(w1,w2, ...,wn) = P(w1|w2,w3,...,wn) P(w2|w3, ...,wn) …
P(wn-1|wn) P(wn)
For bigrams then, the probability of a sequence is just the
product of the conditional probabilities of its bigrams
P(the,mythical,unicorn) = P(unicorn|mythical)
P(mythical|the) P(the|<start>)
n
P(w1n )   P(wk | wk 1)
k 1
37
Training and Testing

N-Gram probabilities come from a training
corpus



overly narrow corpus: probabilities don't
generalize
overly general corpus: probabilities don't reflect
task or domain
A separate test corpus is used to evaluate the
model, typically using standard metrics



held out test set; development test set
cross validation
results tested for statistical significance
38
A Simple Example

P(I want to eat Chinese food) = P(I |
<start>) P(want | I) P(to | want) P(eat |
to) P(Chinese | eat) P(food | Chinese)
39
A Bigram Grammar Fragment
from BERP
Eat on
.16
Eat Thai
.03
Eat some
.06
Eat breakfast
.03
Eat lunch
.06
Eat in
.02
Eat dinner
.05
Eat Chinese
.02
Eat at
.04
Eat Mexican
.02
Eat a
.04
Eat tomorrow
.01
Eat Indian
.04
Eat dessert
.007
Eat today
.03
Eat British
.001
40
<start> I
.25
Want some
.04
<start> I’d
.06
Want Thai
.01
<start> Tell
.04
To eat
.26
<start> I’m
.02
To have
.14
I want
.32
To spend
.09
I would
.29
To be
.02
I don’t
.08
British food
.60
I have
.04
British restaurant
.15
Want to
.65
British cuisine
.01
Want a
.05
British lunch
.01
41



P(I want to eat British food) = P(I|<start>) P(want|I)
P(to|want) P(eat|to) P(British|eat) P(food|British) =
.25*.32*.65*.26*.001*.60 = .000080
vs. I want to eat Chinese food = .00015
Probabilities seem to capture ``syntactic'' facts, ``world
knowledge''



eat is often followed by an NP
British food is not too popular
N-gram models can be trained by counting and normalization
42
BERP Bigram Counts
I
Want
To
Eat
Chinese
Food
lunch
I
8
1087
0
13
0
0
0
Want
3
0
786
0
6
8
6
To
3
0
10
860
3
0
12
Eat
0
0
2
0
19
2
52
Chinese
2
0
0
0
0
120
1
Food
19
0
17
0
0
0
0
Lunch
4
0
0
0
0
1
0
43
BERP Bigram Probabilities


Normalization: divide each row's counts by appropriate unigram
counts for wn-1
I
Want
To
Eat
Chinese
Food
Lunch
3437
1215
3256
938
213
1506
459
Computing the bigram probability of I I



C(I,I)/C(all I)
p (I|I) = 8 / 3437 = .0023
Maximum Likelihood Estimation (MLE): relative frequency of e.g.
freq(w1, w2)
freq(w1)
44
What do we learn about the
language?

What's being captured with ...






P(want | I) = .32
P(to | want) = .65
P(eat | to) = .26
P(food | Chinese) = .56
P(lunch | eat) = .055
What about...



P(I | I) = .0023
P(I | want) = .0025
P(I | food) = .013
45



P(I | I) = .0023 I I I I want
P(I | want) = .0025 I want I want
P(I | food) = .013 the kind of food I want is ...
46
Approximating Shakespeare


As we increase the value of N, the accuracy of the ngram model increases, since choice of next word
becomes increasingly constrained
Generating sentences with random unigrams...



Every enter now severally so, let
Hill he late speaks; or! a more to leg less first you enter
With bigrams...


What means, sir. I confess she? then all sorts, he is trim,
captain.
Why dost stand forth thy canopy, forsooth; he is this
palpable hit the King Henry.
47

Trigrams



Sweet prince, Falstaff shall die.
This shall forbid it should be branded, if renown made it
empty.
Quadrigrams


What! I will go seek the traitor Gloucester.
Will you not tell me who I am?
48



There are 884,647 tokens, with 29,066 word form
types, in about a one million word Shakespeare
corpus
Shakespeare produced 300,000 bigram types out of
844 million possible bigrams: so, 99.96% of the
possible bigrams were never seen (have zero entries
in the table)
Quadrigrams worse: What's coming out looks like
Shakespeare because it is Shakespeare
49
N-Gram Training Sensitivity


If we repeated the Shakespeare experiment
but trained our n-grams on a Wall Street
Journal corpus, what would we get?
This has major implications for corpus
selection or design
50
Some Useful Empirical
Observations





A small number of events occur with high frequency
A large number of events occur with low frequency
You can quickly collect statistics on the high
frequency events
You might have to wait an arbitrarily long time to get
valid statistics on low frequency events
Some of the zeroes in the table are really zeros But
others are simply low frequency events you haven't
seen yet. How to address?
51
Smoothing Techniques



Every n-gram training matrix is sparse, even
for very large corpora
Solution: estimate the likelihood of unseen ngrams
Problems: how do you adjust the rest of the
corpus to accommodate these ‘phantom’ ngrams?
52
Add-one Smoothing

For unigrams:



Add 1 to every word (type) count
Normalize by N (tokens) /(N (tokens) +V (types))
Smoothed count (adjusted for additions to N) is




c 1 N
N V
i
Normalize by N to get the new unigram probability:
p*  c 1
i N V
i
Add delta smoothing
C ( xyz)  1
P( z | xy) 
C ( xy)  V
C ( xyz)  
P( z | xy) 
C ( xy)  V
53
Witten-Bell Discounting

Basic Idea: Use Count of things you have seen once to estimate
the things you haven’t seen


I.e. Estimate the probability of seeing something for the first time
View training corpus as series of events, one for each token (N)
and one for each new type (T). Probability of seeing something
new is
T
N T

This probability mass will assigned to unseen cases
54
Witten-Bell (cont…)

A zero ngram is just an ngram you haven’t seen yet…but every
ngram in the corpus was unseen once…so...




How many times did we see an ngram for the first time? Once for
each ngram type (T)
T
Est. total probability of unseen bigrams as
N T
Each of Z unseen cases will be assigned an equal portion
probability mass - T/N+T
Seen cases will have probabilities discounted as
55
Witten-Bell (cont…)

But for bigrams we can condition on the first word:



Instead of trying to find what is the probability of finding a
new bigram we can ask what is the probability of finding a
new bigram that starts with the given work wk
Then unseen portion will be assigned probability
mass
And for seen cases we discount as follows:
56
Distributing Among the Zeros

If a bigram “wx wi” has a zero count
Number of bigram types
starting with wx
1
T ( wx)
P( wi | wx) 
Z ( wx) N ( wx)  T ( wx)
Number of bigrams
starting with wx
that were not seen
Actual frequency of
bigrams beginning
with wx
57
Good-Turing Discounting

Re-estimate amount of probability mass for zero (or
low count) ngrams by looking at ngrams with higher
counts





For any n-gram that occurs ‘c’ times assume it occurs c*
times, where Nc is the n number n-grams occurring c times
N c 1
Estimate a smoothed count
c*  c  1
Nc
E.g. N0’s adjusted count is a function of the count of ngrams
that occur once, N1
Probability mass assigned to unseen cases works out to be
n1/N
Counts for bigrams that never occurred (c0) will be just
count of bigrams that occurred once by count of bigrams
that never occurred. How do we know count of bigrams that
never occurred?
58
Backoff methods (e.g. Katz
‘87)



If you don’t have a count for ‘n-gram’ backoff to
weighted ‘n-1’ gram
Alphas needed to make a proper probability
distribution (If we backoff when probability is zero,
we are adding extra probability mass)
For e.g. a trigram model


Compute unigram, bigram and trigram probabilities
In use:

Where trigram unavailable back off to bigram if available, o.w.
unigram probability
59
Summary


N-gram models are approximation to the correct model given by
chain rule
N-gram probabilities can be used to estimate the likelihood




Of a word occurring in a context (N-1)
N-gram models suffer from sparse data
Smoothing techniques deal with problems of unseen words in
corpus
J&M book’s explanation of some smoothing techniques is not
very clear. You can read more about smoothing techniques at
http://research.microsoft.com/~joshuago/tr-10-98.pdf
60