1Machine LearningMachine Learning1010--701/15701/15--781, Spring 2008781, Spring 2008NaNaïïve ve BayesBayesClassifierClassifierEric XingEric XingLecture 3, January 23, 2006Reading: Chap. 4 CB and handoutsClassificationz Representing data:z Choosing hypothesis classz Learning: h:X a Yz X – featuresz Y – target classes2Suppose you know the following …z Classification-specific Dist.: P(X|Y)z Class prior (i.e., "weight"): P(Y)z This is a generative model of the data!),;()|(1111Σ==µrXpYXp),;()|(2222Σ==µrXpYXpBayes classifier:Optimal classificationz Theorem: Bayes classifier is optimal!z That isz Proof:z Recall last lecture:z How to learn a Bayes classifier?3Recall Bayes RuleWhich is shorthand for:Equivalently: Recall Bayes RuleWhich is shorthand for:Common abbreviation:4Learning Bayes Classifierz 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 Suppose Y is composed of k classesz Likelihood, P(X|Y):z Suppose X is composed of n binary featuresz Complex model → High variance with limited data!!!5Naïve Bayes:assuming that Xiand Xjare conditionally independent given Y, for all i≠jConditional Independencez X is conditionally independent of Y given Z, if the probability distribution governing X is independent of the value of Y, giventhe value of ZWhich we often writez e.g.,z Equivalent to:6Summaryz Bayes classifier is the best classifierwhich minimizes the probability of classification error.z Nonparametric and parametric classifierz 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 densitiesz when an infinite number of samples are usedz The resulting error is the Bayes error, the smallest achievable error given the underlying distributions.The Naïve Bayes assumptionz Naïve Bayes assumption:z Features are independent given class:z More generally:z How many parameters now?z Suppose X is composed of n binary features7The Naïve Bayes Classifierz Given:z Prior P(Y)z n conditionally independent features X given the class Yz For each Xi, we have likelihood P(Xi|Y)z Decision rule:z If assumption holds, NB is optimal classifier!Naïve Bayes Algorithmz Train Naïve Bayes (examples)z for each* value ykz estimatez for each* value xijof each attribute Xiz estimatez Classify (Xnew)* probabilities must sum to 1, so need estimate only n-1 parameters...8Learning NB: parameter estimationz Maximum Likelihood Estimate (MLE): choose θ that maximizes probability of observed data Dz Maximum a Posteriori (MAP) estimate:choose θ that is most probable given prior probability and the dataMLE for the parameters of NBDiscrete features:z Maximum likelihood estimates (MLE’s):z Given datasetz Count(A=a,B=b) ← number of examples where A=a and B=b9Subtleties of NB classifier 1 –Violating the NB assumptionz Often the Xiare not really conditionally independentz We use Naïve Bayes in many cases anyway, and it often works pretty wellz 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 dataz 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) = 0z Thus, no matter what the values X2,…,Xntake:z P(Y=T | X1,X2,…,X1000=T, …, Xn) = 0z What now???10MAP for the parameters of NBDiscrete features:z Maximum a Posteriori (MAP) estimate: (MAP’s):z Given prior:z Consider binary featurezθis a Bernoulli ratez Let βa=Count(X=a) ← number of examples where X=a),()()()()()(),;(FTFTFTFTBPFTFTααθθθθααααααθαααα111111−−−−−=−ΓΓ+Γ=Bayesian learning for NB parameters – a.k.a. smoothingz Posterior distribution of θz Bernoulli:z Multinomialz MAP estimate:z Beta prior equivalent to extra thumbtack flipsz As N → ∞, prior is “forgotten”z But, for small sample size, prior is important!11MAP for the parameters of NBz Dataset of N examplesz Let βiab=Count(Xi=a,Y=b) ← number of examples where Xi=a and Y=bz Let γb=Count(Y=b) z Prior Q(Xi|Y) ∝ Multinomial(αi1, …, αiK) or Multinomial(α/K) Q(Y) ∝ Multinomial(τi1, …, τiM) or Multinomial(τ/M) m “virtual” examplesz MAP estimatez Now, even if you never observe a feature/class, posterior probability never zeroText classificationz Classify e-mailsz Y = {Spam,NotSpam}z Classify news articlesz Y = {what is the topic of the article?}z Classify webpagesz Y = {Student, professor, project, …}z What about the features X?z The text!12Features X are entire document – Xifor ithword in articleNB for Text classificationz P(X|Y) is huge!!!z Article at least 1000 words, X={X1,…,X1000}z Xirepresents ithword in document, i.e., the domain of Xiis entire vocabulary, e.g., Webster Dictionary (or more), 10,000 words, etc.z NB assumption helps a lot!!!z P(Xi=xi|Y=y) is just the probability of observing word xiin a document on topic y13Bag of words modelz 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 ignoredz 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.in is lecture lecture next over person remember room sitting the the the to to up wake when youBag of words modelz 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 ignoredz Sounds really silly, but often works very well!14Bag of words modelz 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 ignoredz 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 youBag of Words Approachaardvark 0about 2all 2Africa 1apple 0anxious 0...gas 1...oil 1…Zaire 015NB with Bag of Words for text classificationz Learning phase:z Prior P(Y)z Count how many documents you have from each topic (+ prior)z P(Xi|Y) z
View Full Document
Unlocking...