|
|
| Line 7: |
Line 7: |
| | | | |
| | * Mitchell Chapter 7 | | * Mitchell 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 === | | === What you should remember === |
