PAC learning VC Dimension cont Machine Learning 10701 15781 Carlos Guestrin Carnegie Mellon University November 2nd 2009 Carlos Guestrin 2005 2009 1 Review Generalization error in finite hypothesis spaces Haussler 88 Theorem Hypothesis space H finite dataset D with m i i d samples 0 1 for any learned hypothesis h that is consistent on the training data Even if h makes zero errors in training data may make errors in test Carlos Guestrin 2005 2009 2 1 Using a PAC bound Typically 2 use cases 1 Pick and give you m 2 Pick m and give you Carlos Guestrin 2005 2009 3 Limitations of Haussler 88 bound Consistent classifier Size of hypothesis space Carlos Guestrin 2005 2009 4 2 PAC bound and Bias Variance tradeoff or after moving some terms around with probability at least 1 Important PAC bound holds for all h but doesn t guarantee that algorithm finds best h Carlos Guestrin 2005 2009 5 PAC bound for decision trees of depth k Bad Number of points is exponential in depth But for m data points decision tree can t get too big Number of leaves never more than number data points 2005 2007 Carlos Guestrin 6 3 PAC bound for decision trees with k leaves Bias Variance revisited 2005 2007 Carlos Guestrin 7 What did we learn from decision trees Bias Variance tradeoff formalized Moral of the story Complexity of learning not measured in terms of size hypothesis space but in maximum number of points that allows consistent classification Complexity m no bias lots of variance Lower than m some bias less variance 2005 2007 Carlos Guestrin 8 4 What about continuous hypothesis spaces Continuous hypothesis space H Infinite variance As with decision trees only care about the maximum number of points that can be classified exactly 2005 2007 Carlos Guestrin 9 How many points can a linear boundary classify exactly 1 D 2005 2007 Carlos Guestrin 10 5 How many points can a linear boundary classify exactly 2 D 2005 2007 Carlos Guestrin 11 How many points can a linear boundary classify exactly d D 2005 2007 Carlos Guestrin 12 6 PAC bound using VC dimension Number of training points that can be classified exactly is VC dimension Measures relevant size of hypothesis space as with decision trees with k leaves 2005 2007 Carlos Guestrin 13 Shattering a set of points 2005 2007 Carlos Guestrin 14 7 VC dimension 2005 2007 Carlos Guestrin 15 PAC bound using VC dimension Number of training points that can be classified exactly is VC dimension Measures relevant size of hypothesis space as with decision trees with k leaves Bound for infinite dimension hypothesis spaces 2005 2007 Carlos Guestrin 16 8 Examples of VC dimension Linear classifiers VC H d 1 for d features plus constant term b Neural networks VC H parameters Local minima means NNs will probably not find best parameters 1 Nearest neighbor 2005 2007 Carlos Guestrin 17 Another VC dim example What can we shatter What s the VC dim of decision stumps in 2d 2005 2007 Carlos Guestrin 18 9 Another VC dim example What can t we shatter What s the VC dim of decision stumps in 2d 2005 2007 Carlos Guestrin 19 What you need to know Finite hypothesis space Derive results Counting number of hypothesis Mistakes on Training data Complexity of the classifier depends on number of points that can be classified exactly Finite case decision trees Infinite case VC dimension Bias Variance tradeoff in learning theory Remember will your algorithm find best classifier 2005 2007 Carlos Guestrin 20 10 Bayesian Networks Representation Machine Learning 10701 15781 Carlos Guestrin Carnegie Mellon University November 2nd 2009 2005 2007 Carlos Guestrin 21 Handwriting recognition Character recognition e g kernel SVMs rr r r r c ac r z bc 2005 2007 Carlos Guestrin 22 11 Webpage classification Company home page vs Personal home page vs University home page vs 2005 2007 Carlos Guestrin 23 Handwriting recognition 2 2005 2007 Carlos Guestrin 24 12 Webpage classification 2 2005 2007 Carlos Guestrin 25 Today Bayesian networks One of the most exciting advancements in statistical AI in the last 10 15 years Generalizes na ve Bayes and logistic regression classifiers Compact representation for exponentially large probability distributions Exploit conditional independencies 2005 2007 Carlos Guestrin 26 13 Causal structure Suppose we know the following The flu causes sinus inflammation Allergies cause sinus inflammation Sinus inflammation causes a runny nose Sinus inflammation causes headaches How are these connected 2005 2007 Carlos Guestrin 27 Possible queries Flu Inference Most probable explanation Active data collection Allergy Sinus Headache Nose 2005 2007 Carlos Guestrin 28 14 Car starts BN 18 binary attributes Inference P BatteryAge Starts f 216 terms why so fast Not impressed HailFinder BN more than 354 58149737003040059690390169 terms 2005 2007 Carlos Guestrin 29 Factored joint distribution Preview Flu Allergy Sinus Headache Nose 2005 2007 Carlos Guestrin 30 15 Number of parameters Flu Allergy Sinus Nose Headache 2005 2007 Carlos Guestrin 31 Key Independence assumptions Flu Allergy Sinus Headache Nose Knowing sinus separates the variables from each other 2005 2007 Carlos Guestrin 32 16 Marginal Independence Flu and Allergy are marginally independent Flu t Flu f More Generally Allergy t Allergy f Flu t Flu f Allergy t Allergy f 2005 2007 Carlos Guestrin 33 Marginally independent random variables Sets of variables X Y X is independent of Y if P X x Y y x Val X y Val Y Shorthand Marginal independence P X Y Proposition P statisfies X Y if and only if P X Y P X P Y 2005 2007 Carlos Guestrin 34 17 Conditional independence Flu and Headache are not marginally independent Flu and Headache are independent given Sinus infection More Generally 2005 2007 Carlos Guestrin 35 Conditionally independent random variables Sets of variables X Y Z X is independent of Y given Z if P X x Y y Z z x Val X y Val Y z Val Z Shorthand Conditional independence P X Y Z For P X Y write P X Y Proposition P statisfies X Y Z if and only if P X Y Z P X Z P Y Z 2005 2007 Carlos Guestrin 36 18 Properties of independence Symmetry X Decomposition X Y W Z X Y Z W Contraction X Y W Z X Y Z Weak union X Y Z Y X Z W Y Z X Y Z X Y W Z Intersection Y W Z X W Y Z X Y W Z Only for positive distributions P 0 0 X 2005 2007 Carlos Guestrin 37 The independence assumption Flu Allergy Sinus Headache Nose Local Markov Assumption A variable X is independent of its non descendants given its parents 2005 2007 Carlos Guestrin 38 19 Local Markov Assumption A variable X
View Full Document
Unlocking...