MLE’s, Bayesian Classifiers and Naïve BayesNaïve Bayes in a NutshellNaïve Bayes Algorithm – discrete XiEstimating Parameters: Y, Xi discrete-valuedExample: Live in Sq Hill? P(S|G,D,M)Slide 6Naïve Bayes: Subtlety #1Slide 8Naïve Bayes: Subtlety #2Learning to classify text documentsSlide 11Slide 12Baseline: Bag of Words ApproachSlide 14Slide 15Slide 16Slide 17What if we have continuous Xi ?Slide 19Gaussian Naïve Bayes Algorithm – continuous Xi (but still discrete Y)Estimating Parameters: Y discrete, Xi continuousGNB Example: Classify a person’s cognitive activity, based on brain imageStimuli for our study:Slide 24Scaling up: 60 exemplarsRank Accuracy Distinguishing among 60 wordsWhere in the brain is activity that distinguishes tools vs. buildings?voxel clusters: searchlightsWhat you should know:Questions:What is form of decision surface for Naïve Bayes classifier?MLE’s, Bayesian Classifiers and Naïve BayesMachine Learning 10-601Tom M. MitchellMachine Learning DepartmentCarnegie Mellon UniversityJanuary 30, 2008Required reading: • Mitchell draft chapter, sections 1 and 2. (available on class website)Naïve Bayes in a NutshellBayes rule:Assuming conditional independence among Xi’s:So, classification rule for Xnew = < X1, …, Xn > is:Naïve Bayes Algorithm – discrete Xi •Train Naïve Bayes (examples) for each* value ykestimatefor each* value xij of each attribute Xiestimate•Classify (Xnew) * probabilities must sum to 1, so need estimate only n-1 parameters...Estimating Parameters: Y, Xi discrete-valued Maximum likelihood estimates (MLE’s): Number of items in set D for which Y=ykExample: Live in Sq Hill? P(S|G,D,M)•S=1 iff live in Squirrel Hill•G=1 iff shop at Giant Eagle•D=1 iff Drive to CMU•M=1 iff Dave Matthews fanExample: Live in Sq Hill? P(S|G,D,M)•S=1 iff live in Squirrel Hill•G=1 iff shop at Giant Eagle•D=1 iff Drive to CMU•M=1 iff Dave Matthews fanNaïve Bayes: Subtlety #1If unlucky, our MLE estimate for P(Xi | Y) may be zero. (e.g., X373= Birthday_Is_January30)•Why worry about just one parameter out of many?•What can be done to avoid this?Estimating Parameters: Y, Xi discrete-valued Maximum likelihood estimates: MAP estimates (Dirichlet priors):Only difference: “imaginary” examplesNaïve Bayes: Subtlety #2Often 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)?–Special case: what if we add two copies: Xi = XkLearning to classify text documents•Classify which emails are spam•Classify which emails are meeting invites•Classify which web pages are student home pagesHow shall we represent text documents for Naïve Bayes?Baseline: Bag of Words Approachaardvark 0about 2all 2Africa 1apple 0anxious 0...gas 1...oil 1…Zaire 0For code and data, see www.cs.cmu.edu/~tom/mlbook.html click on “Software and Data”What if we have continuous Xi ?Eg., image classification: Xi is ith pixelWhat if we have continuous Xi ?Eg., image classification: Xi is ith pixelGaussian Naïve Bayes (GNB): assumeSometimes assume variance•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 ykestimate*for each attribute Xi estimate class conditional mean , variance •Classify (Xnew) * probabilities must sum to 1, so need estimate only n-1 parameters...Estimating Parameters: Y discrete, Xi continuous Maximum likelihood estimates: jth training examplez)=1 if z true, else 0ith featurekth classGNB Example: Classify a person’s cognitive activity, based on brain image• are they reading a sentence of viewing a picture?• reading the word “Hammer” or “Apartment”• viewing a vertical or horizontal line?• answering the question, or getting confused?timeStimuli for our study:antor60 distinct exemplars, presented 6 times eachfMRI voxel means for “bottle”: means defining P(Xi | Y=“bottle)Mean fMRI activation over all stimuli:“bottle” minus mean activation:fMRI activation highbelow averageaverageScaling up: 60 exemplarsBODY PARTS leg arm eye foot handFURNITURE chair table bed desk dresserVEHICLES car airplane train truck bicycleANIMALS horse dog bear cow catKITCHEN UTENSILS glass knife bottle cup spoonTOOLS chisel hammer screwdriver pliers sawBUILDINGS apartment barn house church iglooPART OF A BUILDING window door chimney closet archCLOTHING coat dress shirt skirt pantsINSECTS fly ant bee butterfly beetleVEGETABLES lettuce tomato carrot corn celeryMAN MADE OBJECTS refrigerator key telephone watch bellCategories ExemplarsRank Accuracy Distinguishing among 60 wordsWhere in the brain is activity that distinguishes tools vs. buildings?Accuracy at each voxel witha radius 1 searchlightAccuracy of a radius one classifier centered at each voxel:voxel clusters: searchlightsAccuracies of cubical27-voxel classifierscentered ateach significantvoxel[0.7-0.8]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 (Bernoulli) and continuous (Gaussian)Questions:•Can you use Naïve Bayes for a combination of discrete and real-valued Xi? •How can we easily model just 2 of n attributes as dependent?•What does the decision surface of a Naïve Bayes classifier look like?What is form of decision surface for Naïve Bayes
View Full Document
Unlocking...