PAC learning VC Dimension and Marginbased Bounds cont Machine Learning 10701 15781 Carlos Guestrin Carnegie Mellon University March 5th 2007 2005 2007 Carlos Guestrin 1 A simple setting Classification m data points Finite number of possible hypothesis e g dec trees of depth d A learner finds a hypothesis h that is consistent with training data Gets zero error in training errortrain h 0 What is the probability that h has more than true error errortrue h 2005 2007 Carlos Guestrin 2 But there are many possible hypothesis that are consistent with training data 2005 2007 Carlos Guestrin 3 Union bound P A or B or C or D or 2005 2007 Carlos Guestrin 4 How likely is learner to pick a bad hypothesis Prob h with errortrue h gets m data points right There are k hypothesis consistent with data How likely is learner to pick a bad one 2005 2007 Carlos Guestrin 5 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 2005 2007 Carlos Guestrin 6 Using a PAC bound Typically 2 use cases 1 Pick and give you m 2 Pick m and give you 2005 2007 Carlos Guestrin 7 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 2005 2007 Carlos Guestrin 8 Limitations of Haussler 88 bound Consistent classifier Size of hypothesis space 2005 2007 Carlos Guestrin 9 What if our classifier does not have zero error on the training data A learner with zero training errors may make mistakes in test set What about a learner with errortrain h in training set 2005 2007 Carlos Guestrin 10 Simpler question What s the expected error of a hypothesis The error of a hypothesis is like estimating the parameter of a coin Chernoff bound for m i i d coin flips x1 xm where xi2 0 1 For 0 1 2005 2007 Carlos Guestrin 11 Using Chernoff bound to estimate error of a single hypothesis 2005 2007 Carlos Guestrin 12 But we are comparing many hypothesis Union bound For each hypothesis hi What if I am comparing two hypothesis h1 and h2 2005 2007 Carlos Guestrin 13 Generalization bound for H hypothesis Theorem Hypothesis space H finite dataset D with m i i d samples 0 1 for any learned hypothesis h 2005 2007 Carlos Guestrin 14 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 2005 2007 Carlos Guestrin 15 What about the size of the hypothesis space How large is the hypothesis space 2005 2007 Carlos Guestrin 16 Boolean formulas with n binary features 2005 2007 Carlos Guestrin 17 Number of decision trees of depth k Recursive solution Given n attributes Hk Number of decision trees of depth k H0 2 Hk 1 choices of root attribute possible left subtrees possible right subtrees n Hk Hk Write Lk log2 Hk L0 1 Lk 1 log2 n 2Lk So Lk 2k 1 1 log2 n 1 2005 2007 Carlos Guestrin 18 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 19 2005 2007 Carlos Guestrin Number of decision trees with k leaves Hk Number of decision trees with k leaves H0 2 Loose bound Reminder 2005 2007 Carlos Guestrin 20 PAC bound for decision trees with k leaves Bias Variance revisited 2005 2007 Carlos Guestrin 21 Announcements Midterm on Wednesday Open book and notes no other material Bring a calculator No laptops PDAs or cellphones 2005 2007 Carlos Guestrin 22 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 23 What about continuous hypothesis spaces Continuous hypothesis space H 1 Infinite variance As with decision trees only care about the maximum number of points that can be classified exactly 2005 2007 Carlos Guestrin 24 How many points can a linear boundary classify exactly 1 D 2005 2007 Carlos Guestrin 25 How many points can a linear boundary classify exactly 2 D 2005 2007 Carlos Guestrin 26 How many points can a linear boundary classify exactly d D 2005 2007 Carlos Guestrin 27 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 28 Shattering a set of points 2005 2007 Carlos Guestrin 29 VC dimension 2005 2007 Carlos Guestrin 30 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 31 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 32 Another VC dim example What can we shatter What s the VC dim of decision stumps in 2d 2005 2007 Carlos Guestrin 33 Another VC dim example What can t we shatter What s the VC dim of decision stumps in 2d 2005 2007 Carlos Guestrin 34 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 35 Big Picture Machine Learning 10701 15781 Carlos Guestrin Carnegie Mellon University March 5th 2007 2005 2007 Carlos Guestrin 36 What you have learned thus far Learning is function approximation Point estimation Regression Na ve Bayes Logistic regression Bias Variance tradeoff Neural nets Decision trees Cross validation Boosting Instance based learning SVMs Kernel trick PAC learning VC dimension Margin bounds Mistake bounds 2005 2007 Carlos Guestrin 37 Review material in terms of Types of learning problems Hypothesis
View Full Document
Unlocking...