Machine Learning 1010 701 15701 15 781 Spring 2008 Na ve Bayes Classifier Eric Xing Lecture 3 January 23 2006 Reading Chap 4 CB and handouts Classification z Representing data z Choosing hypothesis class z Learning h X a Y z X features z Y target classes 1 Suppose you know the following z Classification specific Dist P X Y p X Y 1 r p1 X 1 1 p X Y 2 r p2 X 2 2 z Class prior i e weight P Y z This is a generative model of the data Bayes classifier Optimal classification z Theorem Bayes classifier is optimal z z Proof z z That is Recall last lecture How to learn a Bayes classifier 2 Recall Bayes Rule Which is shorthand for Equivalently Recall Bayes Rule Which is shorthand for Common abbreviation 3 Learning Bayes Classifier z Training data z Learning estimating P X Y and P Y z Classification using Bayes rule to calculate P Y Xnew How hard is it to learn the optimal classifier z How do we represent these How many parameters z Prior P Y z z Likelihood P X Y z z Suppose Y is composed of k classes Suppose X is composed of n binary features Complex model High variance with limited data 4 Na ve Bayes assuming that Xi and Xj are conditionally independent given Y for all i j Conditional Independence z 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 z e g z Equivalent to 5 Summary z Bayes classifier is the best classifierwhich minimizes the probability of classification error z Nonparametric and parametric classifier z A nonparametric classifier does not rely on any assumption concerning the structure of the underlying density function z A classifier becomes the Bayes classifier if the density estimates converge to the true densities z when an infinite number of samples are used z The resulting error is the Bayes error the smallest achievable error given the underlying distributions The Na ve Bayes assumption z z Na ve Bayes assumption z Features are independent given class z More generally How many parameters now z Suppose X is composed of n binary features 6 The Na ve Bayes Classifier z Given z Prior P Y z n conditionally independent features X given the class Y z For each Xi we have likelihood P Xi Y z Decision rule z If assumption holds NB is optimal classifier Na ve Bayes Algorithm z z Train Na ve Bayes examples z for each value yk z estimate z for each value xij of each attribute Xi z estimate Classify Xnew probabilities must sum to 1 so need estimate only n 1 parameters 7 Learning NB parameter estimation z Maximum Likelihood Estimate MLE choose that maximizes probability of observed data D z Maximum a Posteriori MAP estimate choose that is most probable given prior probability and the data MLE for the parameters of NB Discrete features z Maximum likelihood estimates MLE s z Given dataset z Count A a B b number of examples where A a and B b 8 Subtleties of NB classifier 1 Violating the NB assumption z Often the Xi are not really conditionally independent z We use Na ve Bayes in many cases anyway and it often works pretty well z often the right classification even when not the right probability see Domingos Pazzani 1996 z But the resulting probabilities P Y Xnew are biased toward 1 or 0 why Subtleties of NB classifier 2 Insufficient training data z z What if you never see a training instance where X1000 a when Y b z e g Y SpamEmail or not X1000 Rolex z P X1000 T Y T 0 Thus no matter what the values X2 Xn take z z P Y T X1 X2 X1000 T Xn 0 What now 9 MAP for the parameters of NB Discrete features z Maximum a Posteriori MAP estimate MAP s z Given prior z Consider binary feature z is a Bernoulli rate P T F z T 1 1 F 1 T F T 1 1 F 1 B T F T F Let a Count X a number of examples where X a Bayesian learning for NB parameters a k a smoothing z z Posterior distribution of z Bernoulli z Multinomial MAP estimate z Beta prior equivalent to extra thumbtack flips z As N prior is forgotten z But for small sample size prior is important 10 MAP for the parameters of NB z z Dataset of N examples z Let iab Count Xi a Y b number of examples where Xi a and Y b z Let b Count Y b Prior Q Xi Y Multinomial i1 iK or Multinomial K Q Y Multinomial i1 iM or Multinomial M m virtual examples z MAP estimate z Now even if you never observe a feature class posterior probability never zero Text classification z Classify e mails z z Classify news articles z z Y what is the topic of the article Classify webpages z z Y Spam NotSpam Y Student professor project What about the features X z The text 11 Features X are entire document Xi for ith word in article NB for Text classification z z P X Y is huge z Article at least 1000 words X X1 X1000 z Xi represents ith word in document i e the domain of Xi is entire vocabulary e g Webster Dictionary or more 10 000 words etc NB assumption helps a lot z P Xi xi Y y is just the probability of observing word xi in a document on topic y 12 Bag of words model z Typical additional assumption Position in document doesn t matter P Xi xi Y y P Xk xi Y y z Bag of words model order of words on the page ignored z 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 Bag of words model z Typical additional assumption Position in document doesn t matter P Xi xi Y y P Xk xi Y y z Bag of words model order of words on the page ignored z 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 you 13 Bag of words model z Typical additional assumption Position in document doesn t matter P Xi xi Y y P Xk xi Y y z Bag of words model order of words on the page ignored z 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 you Bag of Words Approach aardvark 0 about 2 all 2 Africa 1 apple 0 anxious 0 gas 1 oil 1 Zaire 0 14 NB with Bag of Words for text classification z Learning phase z Prior P Y z …
View Full Document
Unlocking...