Bayesian Learning Chapter 6: Bayesian Learning (Part 2)
CS 536: Machine Learning Littman (Wu, TA)
[Read Ch. 6, except 6.3] [Suggested exercises: 6.1, 6.2, 6.6] Bayes Theorem
MAP, ML hypotheses MAP learners Minimum description length principle Bayes optimal classier Nave Bayes learner (today) Example: Learning over text data (today) Bayesian belief networks (skim) Expectation Maximization algorithm (later)
Nave Bayes Classifier
Along with decision trees, neural networks, kNN, one of the most practical and most used learning methods. When to use: Moderate or large training set available Attributes that describe instances are conditionally independent given classification Successful applications: Diagnosis Classifying text documents
Nave Bayes Classifier
Assume target function f : X ! V, where each instance x described by attributes . Most probable value of f (x) is: vMAP = argmaxvj in V P(vj|a1, a2 … an) = argmaxvj in V P(a1, a2 … an, |vj) P(vj ) / P(a1, a2 … an) = argmaxvj in V P(a1, a2 … an, |vj) P(vj )
Nave Bayes Assumption
P(a1, a2 … an, |vj ) = #i P(ai |vj ), which gives Nave Bayes classifier: vNB = argmaxvj in V P(vj ) #i P(ai |vj ) Note: No search in training!
Nave Bayes Algorithm
Nave_Bayes_Learn(examples) For each target value vj ^ P(vj) " estimate P(vj) For each attribute value ai of each attribute a ^ P(ai|vj) " estimate P(ai|vj) Classify_New_Instance(x) ^ ^ vNB = argmaxvj in V P(vj) #i P(ai |vj)
Nave Bayes: Example
Consider PlayTennis again, and new instance Want to compute: vNB = argmaxvj in V P(vj) #i P(ai |vj)
Nave Bayes: Subtleties
1. Conditional independence assumption is often violated P(a1, a2 … an, |vj) = #i P(ai |vj) ...but it works surprisingly well anyway. Note don't need estimated posteriors P(vj|x) to be correct; need only that argmaxvj in V P(vj|a1, a2 … an) = argmaxvj in V P(vj) #i P(ai |vj) Domingos & Pazzani [1996] for analysis Nave Bayes posteriors often unrealistically close to 1 or 0

下一页