Computational Learning Theory Reading Mitchell chapter 7 Suggested exercises 7 1 7 2 7 5 7 7 Machine Learning 10 701 Tom M Mitchell Machine Learning Department Carnegie Mellon University November 1 2010 D training examples instances drawn at random from Probability distribution P x Can we bound in terms of D training examples instances drawn at random from Probability distribution P x Can we bound training examples Probability distribution P x in terms of if D was a set of examples drawn from and independent of h then we could use standard statistical confidence intervals to determine that with 95 probability lies in the interval but D is the training data for h Target concept is the usually unknown boolean fn to be learned c X 0 1 true error less Any learner that outputs a hypothesis consistent with all training examples i e an h contained in VSH D What it means Haussler 1988 probability that the version space is not exhausted after m training examples is at most Suppose we want this probability to be at most 1 How many training examples suffice 2 If then with probability at least 1 Example H is Conjunction of Boolean Literals Consider classification problem f X Y instances X X1 X2 X3 X4 where each Xi is boolean learned hypotheses are rules of the form IF X1 X2 X3 X4 0 1 THEN Y 1 ELSE Y 0 i e rules constrain any subset of the Xi How many training examples m suffice to assure that with probability at least 0 9 any consistent learner will output a hypothesis with true error at most 0 05 Example H is Decision Tree with depth 2 Consider classification problem f X Y instances X X1 XN where each Xi is boolean learned hypotheses are decision trees of depth 2 using only two variables How many training examples m suffice to assure that with probability at least 0 9 any consistent learner will output a hypothesis with true error at most 0 05 Sufficient condition Holds if learner L requires only a polynomial number of training examples and processing per example is polynomial note here is the difference between the training error and true error true error training error degree of overfitting Additive Hoeffding Bounds Agnostic Learning Given m independent coin flips of coin with true Pr heads bound the error in the maximum likelihood estimate Relevance to agnostic learning for any single hypothesis h But we must consider all hypotheses in H So with probability at least 1 every h satisfies General Hoeffding Bounds When estimating parameter inside a b from m examples When estimating a probability is inside 0 1 so And if we re interested in only one sided error then 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 labels each member of S positive or negative 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 What is VC dimension of lines in a plane H2 w0 w1x1 w2x2 0 y 1 VC dimension examples What is VC dimension of H2 w0 w1x1 w2x2 0 y 1 VC H2 3 For Hn linear separating hyperplanes in n dimensions VC Hn n 1 For any finite hypothesis space H can you give an upper bound on VC H in terms of H hint yes More VC Dimension Examples to Think About Logistic regression over n continuous features Over n boolean features Linear SVM over n continuous features Decision trees defined over n boolean features F X1 Xn Y Decision trees of depth 2 defined over n 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 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 1 any learner L any 0 1 8 and any 0 0 01 Then there exists a distribution and a 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
View Full Document
Unlocking...