Machine Learning 10-601
Tom M. Mitchell
Machine Learning Department Carnegie Mellon University
January 26, 2015
Today:
• BayesClassifiers
• ConditionalIndependence • NaïveBayes
Readings: Mitchell:
“Naïve Bayes and Logistic Regression”
(available on class website)
Two Principles for Estimating Parameters
• MaximumLikelihoodEstimate(MLE):chooseθthat maximizes probability of observed data
• MaximumaPosteriori(MAP)estimate:chooseθthat is most probable given prior probability and the data
Maximum Likelihood Estimate
X=1 X=0 P(X=1) = θ
P(X=0) = 1-θ (Bernoulli)
Maximum A Posteriori (MAP) Estimate
X=1 X=0
Let’s learn classifiers by learning P(Y|X)
Consider Y=Wealth, X=
Gender HrsWorked P(rich | G,HW) P(poor | G,HW)
F <40.5 .09 .91
F >40.5 .21 .79
M <40.5 .23 .77
M >40.5 .38 .62
How many parameters must we estimate?
Suppose X =
where Xi and Y are boolean RV’s
To estimate P(Y| X1, X2, … Xn)
If we have 30 boolean Xi’s: P(Y | X1, X2, … X30)
How many parameters must we estimate?
Suppose X =
where Xi and Y are boolean RV’s
To estimate P(Y| X1, X2, … Xn)
If we have 30 Xi’s instead of 2?
Bayes Rule
Which is shorthand for:
Equivalently:
Can we reduce params using Bayes Rule?
Suppose X =
where Xi and Y are boolean RV’s
How many parameters to define P(X1,… Xn | Y)?
How many parameters to define P(Y)?
Can we reduce params using Bayes Rule?
Suppose X =
where Xi and Y are boolean RV’s
Naïve Bayes
Naïve Bayes assumes
i.e., that Xi and Xj are conditionally independent given Y, for all i≠j
Conditional Independence
Definition: X is conditionally independent of Y given Z, if the probability distribution governing X is independent of the value of Y, given the value of Z
Which we often write E.g.,
Naïve Bayes uses assumption that the Xi are conditionally independent, given Y. E.g.,
Given this assumption, then:
Naïve Bayes uses assumption that the Xi are conditionally independent, given Y. E.g.,
Given this assumption, then:
in general:
Naïve Bayes uses assumption that the Xi are conditionally independent, given Y. E.g.,
Given this assumption, then:
in general:
How many parameters to describe P(X1…Xn|Y)? P(Y)? • Withoutconditionalindepassumption?
• Withconditionalindepassumption?
Naïve Bayes uses assumption that the Xi are conditionally independent, given Y
Given this assumption, then:
in general:
How many parameters to describe P(X1…Xn|Y)? P(Y)? • Withoutconditionalindepassumption?
• Withconditionalindepassumption?
Naïve Bayes in a Nutshell
Bayes rule:
Assuming conditional independence among Xi’s: So, to pick most probable Y for Xnew = < X1, ..., Xn >
Naïve Bayes Algorithm – discrete Xi
• Train Naïve Bayes (examples) for each* value yk
estimate
for each* value xij of each attribute Xi
estimate • Classify (Xnew)
* probabilities must sum to 1, so need estimate only n-1 of these…
Estimating Parameters: Y, Xi discrete-valued Maximum likelihood estimates (MLE’s):
Number of items in dataset D for which Y=yk
Example: Live in Sq Hill? P(S|G,D,M)
• S=1 iff live in Squirrel Hill • D=1 iff Drive to CMU
• G=1 iff shop at SH Giant Eagle • M=1 iff Rachel Maddow fan
What probability parameters must we estimate?
Example: Live in Sq Hill? P(S|G,D,M)
• S=1 iff live in Squirrel Hill
• G=1 iff shop at SH Giant Eagle
P(S=1) : P(D=1 | S=1) : P(D=1 | S=0) : P(G=1 | S=1) : P(G=1 | S=0) : P(M=1 | S=1) : P(M=1 | S=0) :
• D=1 iff Drive to CMU
• M=1 iff Rachel Maddow fan
P(S=0) : P(D=0 | S=1) : P(D=0 | S=0) : P(G=0 | S=1) : P(G=0 | S=0) : P(M=0 | S=1) : P(M=0 | S=0) :
Example: Live in Sq Hill? P(S|G,D,B)
• S=1 iff live in Squirrel Hill • D=1 iff Drive or carpool to CMU
• G=1 iff shop at SH Giant Eagle • B=1 iff Birthday is before July 1
What probability parameters must we estimate?
Example: Live in Sq Hill? P(S|G,D,E)
• S=1 iff live in Squirrel Hill
• G=1 iff shop at SH Giant Eagle
P(S=1) : P(D=1 | S=1) : P(D=1 | S=0) : P(G=1 | S=1) : P(G=1 | S=0) : P(B=1 | S=1) : P(B=1 | S=0) :
• D=1 iff Drive or Carpool to CMU • B=1 iff Birthday is before July 1
P(S=0) : P(D=0 | S=1) : P(D=0 | S=0) : P(G=0 | S=1) : P(G=0 | S=0) : P(B=0 | S=1) : P(B=0 | S=0) :
Naïve Bayes: Subtlety #1
Often the Xi are not really conditionally independent
• We use Naïve Bayes in many cases anyway, and it often works pretty well
– often the right classification, even when not the right probability (see [Domingos&Pazzani, 1996])
• What is effect on estimated P(Y|X)? – Extremecase:whatifweaddtwocopies:Xi =Xk
Extremecase:whatifweaddtwocopies:Xi =Xk
Extremecase:whatifweaddtwocopies:Xi =Xk
Naïve Bayes: Subtlety #2
If unlucky, our MLE estimate for P(Xi | Y) might be zero. (for example, Xi = birthdate. Xi = Jan_25_1992)
• Why worry about just one parameter out of many?
• What can be done to address this?
Naïve Bayes: Subtlety #2
If unlucky, our MLE estimate for P(Xi | Y) might be zero. (e.g., Xi = Birthday_Is_January_30_1992)
• Why worry about just one parameter out of many?
• What can be done to address this?
Estimating Parameters
• MaximumLikelihoodEstimate(MLE):chooseθthat maximizes probability of observed data
• MaximumaPosteriori(MAP)estimate:chooseθthat is most probable given prior probability and the data
Estimating Parameters: Y, Xi discrete-valued Maximum likelihood estimates:
MAP estimates (Beta, Dirichlet priors):
Only difference: “imaginary” examples
Learning to classify text documents
• Classifywhichemailsarespam?
• Classifywhichemailspromiseanattachment?
• Classifywhichwebpagesarestudenthomepages?
How shall we represent text documents for Naïve Bayes?
Baseline: Bag of Words Approach
aardvark 0 about 2 all 2 Africa 1 apple 0 anxious 0 …
gas 1 …
oil 1 …
Zaire 0
Learning to classify document: P(Y|X) the “Bag of Words” model
• Y discrete valued. e.g., Spam or not
• X=
• Xi is a random variable describing the word at position i in the document
• possible values for Xi : any word wk in English
• Document=bagofwords:thevectorofcountsforall wk’s
– like #heads, #tails, but we have many more than 2 values
– assume word probabilities are position independent (i.i.d. rolls of a 50,000-sided die)
Naïve Bayes Algorithm – discrete Xi
• TrainNaïveBayes(examples) for each value yk
estimate
for each value xj of each attribute Xi
estimate • Classify(Xnew)
prob that word xj appears in position i, given Y=yk
* Additional assumption: word probabilities are position independent
MAP estimates for bag of words
Map estimate for multinomial
What β’s should we choose?
For code and data, see
www.cs.cmu.edu/~tom/mlbook.html
click on “Software and Data”
What you should know:
• Training and using classifiers based on Bayes rule
• Conditional independence – What it is
– Why it’s important
• Naïve Bayes – What it is
– Why we use it so much
– Training using MLE, MAP estimates
– Discrete variables and continuous (Gaussian)
Questions:
• HowcanweextendNaïveBayesifjust2oftheXi‘s are dependent?
• WhatdoesthedecisionsurfaceofaNaïveBayes classifier look like?
• WhaterrorwilltheclassifierachieveifNaïveBayes assumption is satisfied and we have infinite training data?
• CanyouuseNaïveBayesforacombinationof discrete and real-valued Xi?
What if we have continuous Xi ? Eg., image classification: Xi is ith pixel
What if we have continuous Xi ? image classification: Xi is ith pixel, Y = mental state
Still have:
Just need to decide how to represent P(Xi | Y)
What if we have continuous Xi ? Eg., image classification: Xi is ith pixel
Gaussian Naïve Bayes (GNB): assume
Sometimes assume σik
• is independent of Y (i.e., σi), • or independent of Xi (i.e., σk) • or both (i.e., σ)
Gaussian Naïve Bayes Algorithm – continuous Xi (but still discrete Y)
• Train Naïve Bayes (examples) for each value yk
estimate*
for each attribute Xi estimate
class conditional mean , variance
• Classify (Xnew)
* probabilities must sum to 1, so need estimate only n-1 parameters…
jth training example
ith feature
kth class
δ(z)=1 if z true, else 0
Estimating Parameters: Y discrete, Xi continuous Maximum likelihood estimates:
GNB Example: Classify a person’s cognitive activity, based on brain image
• are they reading a sentence or viewing a picture? • reading the word “Hammer” or “Apartment”
• viewing a vertical or horizontal line?
• answering the question, or getting confused?
Stimuli for our study:
ant
or 60 distinct exemplars, presented 6 times each
fMRI voxel means for “bottle”: means defining P(Xi | Y=“bottle) fMRI
Mean fMRI activation over all stimuli:
“bottle” minus mean activation:
below average
activation high
average
Rank Accuracy Distinguishing among 60 words
Tools vs Buildings: where does brain encode their word meanings?
Accuracies of cubical 27-voxel Naïve Bayes classifiers centered at each voxel [0.7-0.8]
Expected values
Given discrete random variable X, the expected value of X, written E[X] is
We also can talk about the expected value of functions of X
Covariance
Given two random vars X and Y, we define the covariance of X and Y as
e.g., X=gender, Y=playsFootball or X=gender, Y=leftHanded
Remember: