CS 188: Artificial Intelligence

Naïve Bayes

Instructors: Dan Klein and Pieter Abbeel --- University of California, Berkeley
[These slides were created by Dan Klein and Pieter Abbeel for CS188 Intro to AI at UC Berkeley. All CS188 materials are available at http://ai.berkeley.edu.]
 Machine Learning

 Up until now: how use a model to make optimal decisions

 Machine learning: how to acquire a model from data / experience

 Learning parameters (e.g. probabilities)
 Learning structure (e.g. BN graphs)
 Learning hidden concepts (e.g. clustering)

 Today: model-based classification with Naive Bayes

Classification
 Example: Spam Filter
 Input: an email Dear Sir.
 Output: spam/ham
First, I must solicit your confidence in
this transaction, this is by virture of its
 Setup: nature as being utterly confidencial and
 Get a large collection of example emails, each labeled top secret. …
“spam” or “ham” TO BE REMOVED FROM FUTURE
 Note: someone has to hand label all this data! MAILINGS, SIMPLY REPLY TO THIS
 Want to learn to predict labels of new, future emails MESSAGE AND PUT "REMOVE" IN THE
SUBJECT.

 Features: The attributes used to make the ham / 99 MILLION EMAIL ADDRESSES
spam decision FOR ONLY $99
 Words: FREE! Ok, Iknow this is blatantly OT but I'm
 Text Patterns: $dd, CAPS beginning to go insane. Had an old Dell
 Non-text: SenderInContacts Dimension XPS sitting in the corner and
 decided to put it to use, I know it was
… working pre being stuck in the corner,
but when I plugged it in, hit the power
nothing happened.
 Example: Digit Recognition
 Input: images / pixel grids
0
 Output: a digit 0-9
1
 Setup:
 Get a large collection of example images, each labeled with a digit
 Note: someone has to hand label all this data! 2
 Want to learn to predict labels of new, future digit images

1
 Features: The attributes used to make the digit decision
 Pixels: (6,8)=ON
 Shape Patterns: NumComponents, AspectRatio, NumLoops
 … ??
 Other Classification Tasks
 Classification: given inputs x, predict labels (classes) y

 Examples:
 Spam detection (input: document,
classes: spam / ham)
 OCR (input: images, classes: characters)
 Medical diagnosis (input: symptoms,
classes: diseases)
 Automatic essay grading (input: document,
classes: grades)
 Fraud detection (input: account activity,
classes: fraud / no fraud)
 Customer service email routing
 … many more

 Classification is an important commercial technology!

Model-Based Classification
 Model-Based Classification
 Model-based approach
 Build a model (e.g. Bayes’ net) where
both the label and features are
random variables
 Instantiate any observed features
 Query for the distribution of the label
conditioned on the features

 Challenges
 What structure should the BN have?
 How should we learn its parameters?
 Naïve Bayes for Digits
 Naïve Bayes: Assume all features are independent effects of the label

 Simple digit recognition version: Y

 One feature (variable) Fij for each grid position <i,j>
 Feature values are on / off, based on whether intensity
is more or less than 0.5 in underlying image
 Each input maps to a feature vector, e.g. F1 F2 Fn

 Here: lots of features, each is binary valued

 Naïve Bayes model:

 What do we need to learn?

 General Naïve Bayes
 A general Naive Bayes model:
Y

|Y| parameters

F1 F2 Fn

|Y| x |F|n values n x |F| x |Y|

parameters

 We only have to specify how each feature depends on the class

 Total number of parameters is linear in n
 Model is very simplistic, but often works anyway
 Inference for Naïve Bayes
 Goal: compute posterior distribution over label variable Y
 Step 1: get joint probability of label and evidence for each label

+
 Step 2: sum to get probability of evidence

 Step 3: normalize by dividing Step 1 by Step 2

 General Naïve Bayes
 What do we need in order to use Naïve Bayes?
 Inference method (we just saw this part)
 Start with a bunch of probabilities: P(Y) and the P(Fi|Y) tables
 Use standard inference to compute P(Y|F1…Fn)
 Nothing new here

 Estimates of local conditional probability tables

 P(Y), the prior over labels
 P(Fi|Y) for each feature (evidence variable)
 These probabilities are collectively called the parameters of the model
and denoted by 
 Up until now, we assumed these appeared by magic, but…
 …they typically come from training data counts: we’ll look at this soon
Example: Conditional Probabilities

1 0.1 1 0.01 1 0.05

2 0.1 2 0.05 2 0.01
3 0.1 3 0.05 3 0.90
4 0.1 4 0.30 4 0.80
5 0.1 5 0.80 5 0.90
6 0.1 6 0.90 6 0.90
7 0.1 7 0.05 7 0.25
8 0.1 8 0.60 8 0.85
9 0.1 9 0.50 9 0.60
0 0.1 0 0.80 0 0.80
 Naïve Bayes for Text
 Bag-of-words Naïve Bayes:
 Features: Wi is the word at positon i
 As before: predict label conditioned on feature variables (spam vs. ham)
 As before: assume features are conditionally independent given label
 New: each Wi is identically distributed Word at position
i, not ith word in
the dictionary!
 Generative model:

 “Tied” distributions and bag-of-words

 Usually, each variable gets its own conditional probability distribution P(F|Y)
 In a bag-of-words model
 Each position is identically distributed
 All positions share the same conditional probs P(W|Y)
 Why make this assumption?
 Called “bag-of-words” because model is insensitive to word order or reordering
 Example: Spam Filtering
 Model:
 What are the parameters?

ham : 0.66 the : 0.0156 the : 0.0210

spam: 0.33 to : 0.0153 to : 0.0133
and : 0.0115 of : 0.0119
of : 0.0095 2002: 0.0110
you : 0.0093 with: 0.0108
a : 0.0086 from: 0.0107
with: 0.0080 and : 0.0105
from: 0.0075 a : 0.0100
... ...

 Where do these tables come from?

 Spam Example
Word P(w|spam) P(w|ham) Tot Spam Tot Ham
(prior) 0.33333 0.66666 -1.1 -0.4
Gary 0.00002 0.00021 -11.8 -8.9
would 0.00069 0.00084 -19.1 -16.0
you 0.00881 0.00304 -23.8 -21.8
like 0.00086 0.00083 -30.9 -28.9
to 0.01517 0.01339 -35.1 -33.2
lose 0.00008 0.00002 -44.5 -44.0
weight 0.00016 0.00002 -53.3 -55.0
while 0.00027 0.00027 -61.5 -63.2
you 0.00881 0.00304 -66.2 -69.0
sleep 0.00006 0.00001 -76.0 -80.5

P(spam | w) = 98.9
Training and Testing
 Important Concepts
 Data: labeled instances, e.g. emails marked spam/ham
 Training set
 Held out set
 Test set
 Features: attribute-value pairs which characterize each x Training
 Experimentation cycle Data
 Learn parameters (e.g. model probabilities) on training set
 (Tune hyperparameters on held-out set)
 Compute accuracy of test set
 Very important: never “peek” at the test set!
 Evaluation
 Accuracy: fraction of instances predicted correctly Held-Out
Data
 Overfitting and generalization
 Want a classifier which does well on test data
 Overfitting: fitting the training data very closely, but not
generalizing well Test
 We’ll investigate overfitting and generalization formally in a few Data
lectures
Generalization and Overfitting
 Overfitting
30

25

20
Degree 15 polynomial
15

10

-5

-10

-15
0 2 4 6 8 10 12 14 16 18 20
Example: Overfitting

2 wins!!
 Example: Overfitting
 Posteriors determined by relative probabilities (odds ratios):

south-west : inf screens : inf

nation : inf minute : inf
morally : inf guaranteed : inf
nicely : inf $205.00 : inf
extent : inf delivery : inf
seriously : inf signature : inf
... ...

What went wrong here?

 Generalization and Overfitting
 Relative frequency parameters will overfit the training data!
 Just because we never saw a 3 with pixel (15,15) on during training doesn’t mean we won’t see it at test time
 Unlikely that every occurrence of “minute” is 100% spam
 Unlikely that every occurrence of “seriously” is 100% ham
 What about all the words that don’t occur in the training set at all?
 In general, we can’t go around giving unseen events zero probability

 As an extreme case, imagine using the entire email as the only feature
 Would get the training data perfect (if deterministic labeling)
 Wouldn’t generalize at all
 Just making the bag-of-words assumption gives us some generalization, but isn’t enough

 To generalize better: we need to smooth or regularize the estimates

Parameter Estimation
 Parameter Estimation
 Estimating the distribution of a random variable
 Elicitation: ask a human (why is this hard?) b
r b
br
b
br
r b b
r
b

b b

 Empirically: use training data (learning!)

 E.g.: for each outcome x, look at the empirical rate of that value:

r r b

 This is the estimate that maximizes the likelihood of the data

Smoothing
 Maximum Likelihood?
 Relative frequencies are the maximum likelihood estimates

 Another option is to consider the most likely parameter value given the data

????
Unseen Events
 Laplace Smoothing

 Laplace’s estimate:
 Pretend you saw every outcome
r r b
once more than you actually did

 Can derive this estimate with

Dirichlet priors (see cs281a)
 Laplace Smoothing
 Laplace’s estimate (extended):
 Pretend you saw every outcome k extra times
r r b

 What’s Laplace with k = 0?

 k is the strength of the prior

 Laplace for conditionals:

 Smooth each condition independently:
 Estimation: Linear Interpolation*
 In practice, Laplace often performs poorly for P(X|Y):
 When |X| is very large
 When |Y| is very large

 Another option: linear interpolation

 Also get the empirical P(X) from the data
 Make sure the estimate of P(X|Y) isn’t too different from the empirical P(X)

 What if  is 0? 1?

 For even better ways to estimate parameters, as well as details of

the math, see cs281a, cs288
 Real NB: Smoothing
 For real classification problems, smoothing is critical
 New odds ratios:

helvetica : 11.4 verdana : 28.8

seems : 10.8 Credit : 28.4
group : 10.2 ORDER : 27.2
ago : 8.4 <FONT> : 26.9
areas : 8.3 money : 26.5
... ...

Do these make more sense?

Tuning
 Tuning on Held-Out Data

 Now we’ve got two kinds of unknowns

 Parameters: the probabilities P(X|Y), P(Y)
 Hyperparameters: e.g. the amount / type of
smoothing to do, k, 

 What should we learn where?

 Learn parameters from training data
 Tune hyperparameters on different data
 Why?
 For each value of the hyperparameters, train
and test on the held-out data
 Choose the best value and do a final test on
the test data
Features
 Errors, and What to Do
 Examples of errors
Dear GlobalSCAPE Customer,
GlobalSCAPE has partnered with ScanSoft to offer you the
latest version of OmniPage Pro, for just $99.99* - the
regular list price is $499! The most common question we've
received about this offer is - Is this genuine? We would like
to assure you that this offer is authorized by ScanSoft, is
genuine and valid. You can get the . . .

. . . To receive your $30 Amazon.com promotional certificate,

click through to
http://www.amazon.com/apparel
and see the prominent link for the $30 offer. All details are
there. We hope you enjoyed receiving this message. However,
if you'd rather not receive future e-mails announcing new
store launches, please click . . .
 What to Do About Errors?
 Need more features– words aren’t enough!
 Have you emailed the sender before?
 Have 1K other people just gotten the same email?
 Is the sending information consistent?
 Is the email in ALL CAPS?
 Do inline URLs point where they say they point?
 Does the email address you by (your) name?

 Can add these information sources as new

variables in the NB model

 Next class we’ll talk about classifiers which let

you easily add arbitrary features more easily
 Baselines
 First step: get a baseline
 Baselines are very simple “straw man” procedures
 Help determine how hard the task is
 Help know what a “good” accuracy is

 Weak baseline: most frequent label classifier

 Gives all test instances whatever label was most common in the training set
 E.g. for spam filtering, might label everything as ham
 Accuracy might be very high if the problem is skewed
 E.g. calling everything “ham” gets 66%, so a classifier that gets 70% isn’t very good…

 For real research, usually use previous work as a (strong) baseline

 Confidences from a Classifier
 The confidence of a probabilistic classifier:
 Posterior over the top label

 Represents how sure the classifier is of the

classification
 Any probabilistic model will have confidences
 No guarantee confidence is correct

 Calibration
 Weak calibration: higher confidences mean
higher accuracy
 Strong calibration: confidence predicts accuracy
rate
 What’s the value of calibration?
 Summary
 Bayes rule lets us do diagnostic queries with causal probabilities

 The naïve Bayes assumption takes all features to be independent given the class label

 We can build classifiers out of a naïve Bayes model using training data

 Smoothing estimates is important in real systems

 Classifier confidences are useful, when you can get them

Next Time: Perceptron!