10-601 PAC
Contents
Slides
- Ziv's lecture: Slides in pdf.
Readings
the PAC learning, VC dimension, etc. in Tom Mitchell 's Chapter 7
An example of PAC learnability of Boolean literals : Learning a Boolean Conjunction
(from http://www.cis.temple.edu/~giorgio/cis587/readings/pac.html)
We can efficiently PAC learn concepts that are represented as the conjunction of boolean literals (i.e. positive or negative boolean variables). Here is a learning algorithm:
1. Start with an hypothesis h which is the conjunction of each variable and its negation x1 & ~x1 & x2 & ~x2 & .. & xn & ~xn.
2. Do nothing with negative instances.
3. On a positive instance a, eliminate in h ~xi if ai is positive, eliminate xi if ai is negative. For example if a positive instance is 01100 then eliminate x1, ~x2, ~x3, x4, and x5.
In this algorithm h, as domain, is non-decreasing and at all times contained in the set denoted by c. [By induction: certainly true initially, ..]. We will have an error when h contains a literal z which is not in c.
We compute first the probability that a literal z is deleted from h because of one specific positive example. Clearly this probability is 0 if z occurs in c, and if ~z is in c the probability is 1. At issue are the z where neither z nor ~z is in c.
We would like to eliminate both of them from h. If one of the two remains, we have an error for an instance a that is positive for c and negative for h. Let's call these literals, free literals.
We have:
error(h) is less than or equal to the Sum of the probabilities of the free literals z in h not to be eliminated by one positive example.
Since there are at most 2*n literals in h, if h is a bad hypothesis, i.e. an hypothesis with error greater than epsilon, we will have
Probability[free literal z is eliminated from h by one positive example] > epsilon/(2*n)
From this we obtain :
Probability[free literal z survives one positive example] = 1 - Probability[free literal z is eliminated from h by one positive example] < (1 - epsilon/(2*n))
Probability[free literal z survives m positive examples] < (1 - epsilon/(2*n))^m
Probability[some free literal z survives m positive examples] < 2n*(1 - epsilon/(2*n))^m < 2n*(e^(-epsilon/(2*n)))^m = 2n*e^(-(m*epsilon)/(2*n))
That is
m > (2*n/epsilon)*(ln(1/delta)+n*ln(2))
What you should remember
- Relationships between sample complexity, error bound, and “capacity” of chosen hypothesis space
- 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 in H)
- For ANY “best fit” hypothesis (agnostic learning, where perhaps c not in H)
- VC dimension as measure of complexity of H
