Computational Learning Theory Part 2 VC dimension Sample Complexity Mistake bounds Required reading Mitchell chapter 7 Optional advanced reading Kearns Vazirani Introduction to Computational Learning Theory Machine Learning 10 701 Tom M Mitchell Machine Learning Department Carnegie Mellon University October 17 2006 Last time PAC Learning 1 Finite H assume target function c H Suppose we want this to be at most Then m examples suffice 2 Finite H agnostic learning perhaps c not in H with probability at least 1 every h in H satisfies What if H is not finite Can t use our result for finite H Need some other measure of complexity for H Vapnik Chervonenkis VC dimension VC H 3 Sample Complexity based on VC dimension How many randomly drawn examples suffice to exhaust VSH D with probability at least 1 ie to guarantee that any hypothesis that perfectly fits the training data is probably 1 approximately correct Compare to our earlier results based on H VC dimension examples Consider X want to learn c X 0 1 What is VC dimension of Open intervals Closed intervals x VC dimension examples Consider X want to learn c X 0 1 What is VC dimension of Open intervals x VC H1 1 VC H2 2 Closed intervals VC H3 2 VC H4 3 VC dimension examples Consider X 2 want to learn c X 0 1 What is VC dimension of lines in a plane H wx b 0 y 1 VC dimension examples Consider X 2 want to learn c X 0 1 What is VC dimension of H w x b 0 y 1 VC H1 3 For linear separating hyperplanes in n dimensions VC H n 1 For any finite hypothesis space H give an upper bound on VC H in terms of H More VC Dimension Examples Decision trees defined over n boolean features F X1 Xn Y Decision trees defined over n continuous features Where each internal tree node involves a threshold test Xi c Decision trees of depth 2 defined over n features Logistic regression over n continuous features Over n boolean features How about 1 nearest neighbor Tightness of Bounds on Sample Complexity How many examples m suffice to assure that any hypothesis that fits the training data perfectly is probably 1 approximately correct How tight is this bound Lower bound on sample complexity Ehrenfeucht et al 1989 Consider any class C of concepts such that VC C 2 any learner L any 0 1 8 and any 0 0 01 Then there exists a distribution and target concept in C such that if L observes fewer examples than Then with probability at least L outputs a hypothesis with Agnostic Learning VC Bounds Sch lkopf and Smola 2002 With probability at least 1 every h H satisfies Structural Risk Minimization Vapnik Which hypothesis space should we choose Bias variance tradeoff H4 H3 H2 H1 SRM choose H to minimize bound on true error unfortunately a somewhat loose bound What You Should Know Sample complexity varies with the learning setting Learner actively queries trainer Examples provided at random Within the PAC learning setting we can bound the probability that learner will output hypothesis with given error For ANY consistent learner case where c 2 H For ANY best fit hypothesis agnostic learning where perhaps c not in H VC dimension as measure of complexity of H Quantitative bounds characterizing bias variance in choice of H but the bounds are quite loose Mistake bounds in learning Conference on Learning Theory http www learningtheory org
View Full Document
Unlocking...