2006 Carlos Guestrin1PAC-learning, VC Dimension and Margin-based BoundsMachine Learning – 10701/15781Carlos GuestrinCarnegie Mellon UniversityMarch 6th, 2006More details:General: http://www.learning-with-kernels.org/Example of more complex bounds:http://www.research.ibm.com/people/t/tzhang/papers/jmlr02_cover.ps.gz2006 Carlos Guestrin2Announcements 1 Midterm on Wednesday open book, texts, notes,… no laptops bring a calculator2006 Carlos Guestrin3Announcements 2 Final project details are out!!! http://www.cs.cmu.edu/~guestrin/Class/10701/projects.html Great opportunity to apply ideas from class and learn more Example project: Take a dataset Define learning task Apply learning algorithms Design your own extension Evaluate your ideas many of suggestions on the webpage, but you can also do your own Boring stuff: Individually or groups of two students It’s worth 20% of your final grade You need to submit a one page proposal on Wed. 3/22 (just after the break) A 5-page initial write-up (milestone) is due on 4/12 (20% of project grade) An 8-page final write-up due 5/8 (60% of the grade) A poster session for all students will be held on Friday 5/5 2-5pm in NSH atrium (20% of the grade) You can use late days on write-ups, each student in team will be charged a late day per day. MOST IMPORTANT:2006 Carlos Guestrin4What now… We have explored many ways of learning from data But… How good is our classifier, really? How much data do I need to make it “good enough”?2006 Carlos Guestrin5How 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?2006 Carlos Guestrin6Union bound P(A or B or C or D or …)2006 Carlos Guestrin7How 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?2006 Carlos Guestrin8Review: Generalization error in finite hypothesis spaces [Haussler ’88] Theorem: Hypothesis space H finite, dataset Dwith m i.i.d. samples, 0 < ε < 1 : for any learned hypothesis h that is consistent on the training data:2006 Carlos Guestrin9Using a PAC bound Typically, 2 use cases: 1: Pick ε and δ, give you m 2: Pick m and δ, give you ε2006 Carlos Guestrin10Review: Generalization error in finite hypothesis spaces [Haussler ’88] Theorem: Hypothesis space H finite, dataset Dwith 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 test2006 Carlos Guestrin11Limitations of Haussler ‘88 bound Consistent classifier Size of hypothesis space2006 Carlos Guestrin12Simpler 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.d.d. coin flips, x1,…,xm, where xi∈ {0,1}. For 0<ε<1:2006 Carlos Guestrin13But we are comparing many hypothesis: Union boundFor each hypothesis hi:What if I am comparing two hypothesis, h1 and h2?2006 Carlos Guestrin14Generalization bound for |H| hypothesis Theorem: Hypothesis space H finite, dataset Dwith m i.i.d. samples, 0 < ε < 1 : for any learned hypothesis h:2006 Carlos Guestrin15PAC bound and Bias-Variance tradeoff Important: PAC bound holds for all h, but doesn’t guarantee that algorithm finds best h!!!or, after moving some terms around,with probability at least 1-δδδδ::::2006 Carlos Guestrin16What about the size of the hypothesis space? How large is the hypothesis space?2006 Carlos Guestrin17Boolean formulas with n binary features2006 Carlos Guestrin18Number of decision trees of depth kRecursive solution Given n attributesHk= Number of decision trees of depth kH0=2Hk+1= (#choices of root attribute) *(# possible left subtrees) *(# possible right subtrees)= n * Hk* HkWrite Lk= log2HkL0= 1Lk+1= log2n + 2LkSo Lk= (2k-1)(1+log2n) +12006 Carlos Guestrin19PAC 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 points2006 Carlos Guestrin20Number of decision trees with k leavesHk= Number of decision trees with k leavesH0=2Reminder:Loose bound:2006 Carlos Guestrin21PAC bound for decision trees with k leaves – Bias-Variance revisited2006 Carlos Guestrin22What 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 variance2006 Carlos Guestrin23What 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!2006 Carlos Guestrin24How many points can a linear boundary classify exactly? (1-D)2006 Carlos Guestrin25How many points can a linear boundary classify exactly? (2-D)2006 Carlos Guestrin26How many points can a linear boundary classify exactly? (d-D)2006 Carlos Guestrin27Shattering a set of points2006 Carlos Guestrin28VC dimension2006 Carlos Guestrin29PAC 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:2006 Carlos Guestrin30Examples 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?2006 Carlos Guestrin31Another VC dim. example What’s the VC dim. of decision stumps in 2d?2006 Carlos Guestrin32PAC bound for SVMs SVMs use a linear classifier For d features, VC(H) = d+1:2006 Carlos Guestrin33VC dimension and SVMs: Problems!!! What about kernels? Polynomials: num. features grows really fast = Bad bound Gaussian kernels can classify any set
View Full Document
Unlocking...