Bayes optimal classifier Na ve Bayes What s learning revisited Machine Learning 10701 15781 Carlos Guestrin Carnegie Mellon University September 21st 2009 Carlos Guestrin 2005 2009 1 Classification Learn h X a Y features Y target classes X Suppose you know P Y X exactly how should you classify Bayes classifier Why 1 Optimal classification Theorem Bayes classifier hBayes is optimal That is Proof Bayes Rule Which is shorthand for 2 How hard is it to learn the optimal classifier Data How do we represent these How many parameters Prior P Y Likelihood P X Y Suppose Y is composed of k classes Suppose X is composed of n binary features Complex model High variance with limited data Conditional 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 3 What if features are independent Predict Thunder From two conditionally Independent features Lightening Rain The Na ve Bayes assumption Na ve Bayes assumption Features are More independent given class generally How many parameters now Suppose X is composed of n binary features 4 The 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 MLE 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 5 Subtleties 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 performance Subtleties 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 Xn take P Y b X1 a X2 Xn 0 What now 6 MAP for Beta distribution MAP use most likely parameter Beta prior equivalent to extra thumbtack flips As N 1 prior is forgotten But for small sample size prior is important Bayesian learning for NB parameters a k a smoothing Dataset of N examples Prior MAP estimate distribution Q Xi Y Q Y m virtual examples P Xi Y Now even if you never observe a feature class posterior probability never zero 7 Text classification Classify e mails Y Classify news articles Y what is the topic of the article Classify webpages Y Spam NotSpam Student professor project What about the features X The text Features X are entire document Xi for ith word in article 8 NB for Text classification P X Y is huge Article at least 1000 words X X1 X1000 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 P Xi xi Y y is just the probability of observing word xi in a document on topic y Bag 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 9 Bag 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 you Bag of Words Approach aardvark 0 about 2 all 2 Africa 1 apple 0 anxious 0 gas 1 oil 1 Zaire 0 10 NB 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 rule Twenty News Groups results 11 Learning curve for Twenty News Groups 12
View Full Document
Unlocking...