1©Carlos Guestrin 2005-2007Bayes optimal classifierNaïve BayesMachine Learning – 10701/15781Carlos Guestrin(presented by Eric Xing)Carnegie Mellon UniversitySeptember 17th, 2007©Carlos Guestrin 2005-2007Machine learning for apartment hunting Now you've moved to Pittsburgh!! And you want to find the most overall satisfying apartment for you to move in:square-ft., # of bedroom, distance to campus, rent, …??nonoyesyesYes/No12001.5270…5001150500110911002433100025066001230Rent ($)# bedroomLiving area (ft2)2©Carlos Guestrin 2005-2007Classification Learn: h:X a Y X – features Y – target classes Suppose you know P(Y|X) exactly, how should you classify? Bayes classifier: Why?©Carlos Guestrin 2005-2007Optimal classification Theorem: Bayes classifier hBayesis optimal! That is Proof:3©Carlos Guestrin 2005-2007Bayes RuleWhich is shorthand for:©Carlos Guestrin 2005-2007How hard is it to learn the optimal classifier? Data = How do we represent these? How many parameters? Prior, P(Y): Suppose Y is composed of k classes Likelihood, P(X|Y): Suppose X is composed of n binary features Complex model → High variance with limited data!!!4©Carlos Guestrin 2005-2007Conditional Independence 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 e.g., Equivalent to:©Carlos Guestrin 2005-2007What if features are independent? Predict 10701Grade From two conditionally Independent features HomeworkGrade ClassAttendance5©Carlos Guestrin 2005-2007The Naïve Bayes assumption Naïve Bayes assumption: Features are independent given class: More generally: How many parameters now? Suppose X is composed of n binary features©Carlos Guestrin 2005-2007The Naïve Bayes Classifier Given: Prior P(Y) n conditionally independent features X given the class Y For each Xi, we have likelihood P(Xi|Y) Decision rule: If assumption holds, NB is optimal classifier!6©Carlos Guestrin 2005-2007MLE for the parameters of NB Given dataset Count(A=a,B=b) ← number of examples where A=a and B=b MLE for NB, simply: Prior: P(Y=y) = Likelihood: P(Xi=xi|Yi=yi) =©Carlos Guestrin 2005-2007Subtleties of NB classifier 1 –Violating the NB assumption Usually, features are not conditionally independent: Actual probabilities P(Y|X) often biased towards 0 or 1 Nonetheless, NB is the single most used classifier out there NB often performs well, even when assumption is violated [Domingos & Pazzani ’96] discuss some conditions for good performance7©Carlos Guestrin 2005-2007Subtleties of NB classifier 2 –Insufficient training data What if you never see a training instance where X1=a when Y=b? e.g., Y={SpamEmail}, X1={‘Enlargement’} P(X1=a | Y=b) = 0 Thus, no matter what the values X2,…,Xntake: P(Y=b | X1=a,X2,…,Xn) = 0 What now???©Carlos Guestrin 2005-2007MAP for Beta distribution MAP: use most likely parameter: Beta prior equivalent to extra thumbtack flips As N → ∞, prior is “forgotten” But, for small sample size, prior is important!8©Carlos Guestrin 2005-2007Bayesian learning for NB parameters – a.k.a. smoothing Dataset of N examples Prior “distribution” Q(Xi,Y), Q(Y) m “virtual” examples MAP estimate P(Xi|Y) Now, even if you never observe a feature/class, posterior probability never zero©Carlos Guestrin 2005-2007Text classification Classify e-mails Y = {Spam,NotSpam} Classify news articles Y = {what is the topic of the article?} Classify webpages Y = {Student, professor, project, …} What about the features X? The text!9©Carlos Guestrin 2005-2007Features X are entire document –Xifor ithword in article©Carlos Guestrin 2005-2007NB for Text classification P(X|Y) is huge!!! Article at least 1000 words, X={X1,…,X1000} Xirepresents ithword in document, i.e., the domain of Xiis entire vocabulary, e.g., Webster Dictionary (or more), 10,000 words, etc. NB assumption helps a lot!!! P(Xi=xi|Y=y) is just the probability of observing word xiin a document on topic y10©Carlos Guestrin 2005-2007Bag of words model Typical additional assumption – Position in document doesn’t matter: P(Xi=xi|Y=y) = P(Xk=xi|Y=y) “Bag of words” model – order of words on the page ignored Sounds really silly, but often works very well!When the lecture is over, remember to wake up the person sitting next to you in the lecture room.©Carlos Guestrin 2005-2007Bag of words model Typical additional assumption – Position in document doesn’t matter: P(Xi=xi|Y=y) = P(Xk=xi|Y=y) “Bag of words” model – order of words on the page ignored Sounds really silly, but often works very well!in is lecture lecture next over person remember room sitting the the the to to up wake when you11©Carlos Guestrin 2005-2007Bag of Words Approachaardvark 0about 2all 2Africa 1apple 0anxious 0...gas 1...oil 1…Zaire 0©Carlos Guestrin 2005-2007NB with Bag of Words for text classification Learning phase: Prior P(Y) Count how many documents you have from each topic (+ prior) P(Xi|Y) For each topic, count how many times you saw word in documents of this topic (+ prior) Test phase: For each document Use naïve Bayes decision rule12©Carlos Guestrin 2005-2007Twenty News Groups results©Carlos Guestrin 2005-2007Learning curve for Twenty News Groups13©Carlos Guestrin 2005-2007What if we have continuous Xi?Eg., character recognition: Xiis ithpixelGaussian Naïve Bayes (GNB):Sometimes assume variance is independent of Y (i.e., σi), or independent of Xi(i.e., σk) or both (i.e., σ)©Carlos Guestrin 2005-2007Estimating Parameters: Y discrete, XicontinuousMaximum likelihood estimates:jth training exampleδ(x)=1 if x true, else 014©Carlos Guestrin 2005-2007Example: GNB for classifying mental states~1 mm resolution~2 images per sec.15,000 voxels/imagenon-invasive, safemeasures Blood Oxygen Level Dependent (BOLD) responseTypical impulse response10 sec[Mitchell et al.]©Carlos Guestrin 2005-2007Brain scans can track activation with precision and sensitivity[Mitchell et al.]15©Carlos Guestrin 2005-2007Gaussian Naïve Bayes: Learned µvoxel,wordP(BrainActivity | WordCategory = {People,Animal})[Mitchell et al.]©Carlos Guestrin 2005-2007Learned Bayes Models – Means
View Full Document
Unlocking...