Fix a rectangle (unknown to you):From An Introduction to Computational Learning Theory by Keanrs and Vazirani Draw points from some fixed unknown distribution: You are told the points and whether they are in or out: You propose a hypothesis: Your hypothesis is tested on points drawn from the same distribution: We want an algorithm that:◦ With high probability will choose a hypothesis that is approximately correct. Choose the minimum area rectangle containing all the positive points:h Derive a PAC bound: For fixed:◦ R : Rectangle◦ D : Data Distribution◦ ε : Test Error◦ δ : Probability of failing◦ m : Number of SampleshR We want to show that with high probability the area below measured with respect to Dis bounded by ε :hR< ε We want to show that with high probability the area below measured with respect to Dis bounded by ε :hR< ε/4 Define T to be the region that contains exactly ε/4 of the mass in D sweeping down from the top of R. p(T’) > ε/4 = p(T) IFFT’ contains T T’ contains T IFFnone of our msamplesare from T What is the probabilitythat all samples miss ThR< ε/4T’T What is the probability that all msamples miss T: What is the probability thatwe miss any of the rectangles?◦ Union Bound hR< ε/4T’TA B What is the probability that all msamples miss T: What is the probability thatwe miss any of therectangles:◦ Union Bound hRT= ε/4 Probability that any region has weight greater than ε/4 after m samples is at most: If we fix msuch that: Than with probability 1- δwe achieve an error rate of at most εhRT= ε/4 Common Inequality: We can show: Obtain a lower bound on the samples: Provides a measure of the complexity of a “hypothesis space” or the “power” of “learning machine” Higher VC dimension implies the ability to represent more complex functions The VC dimension is the maximum number of points that can be arranged so that f shatters them. What does it mean to shatter? A classifier f can shatter a set of points if and only if for all truth assignments to those points f gets zero training error Example: f(x,b) = sign(x.x-b) What is the VC Dimension of the classifier:◦ f(x,b) = sign(x.x-b) Conjecture: Easy Proof (lower Bound): Harder Proof (Upper Bound): VC Dimension Conjecture: VC Dimension Conjecture: 4 Upper bound (more Difficult): What is the VC Dimension of:◦ f(x,{w,b})=sign( w . x + b )◦ X in R^d Proof (lower bound):◦ Pick {x_1, …, x_n} (point) locations:◦ Adversary gives assignments {y_1, …, y_n} and you choose {w_1, …, w_n} and b: Proof (upper bound): VC-Dim = d+1◦ Observe that the last d+1 points can always be expressed as: Proof (upper bound): VC-Dim = d+1◦ Observe that the last d+1 points can always be expressed
View Full Document
Unlocking...