PAC Learnablity

Probably approximately learnable

Definition

A learning task over instance space X is PAC Learnable iff an algorithm can be found that:

For every c ∈ C, for every distribution D, for every $0 < ϵ < 1 / 2$ and for every $0 < δ < 1 / 2$ , is such that:
$P r [e r r o r_{D, c} (A (E X (c, D), ε, δ)) < ε] > 1 - δ$
where the probability is taken over the calls to $E X (c, D)$

Explanation of $P r [e r r o r_{D, c} (A (E X (c, D), ε, δ)) < ε] > 1 - δ$

Let's break this ugly thing down:

1. $A (E X (c, D), ε, δ)$

This is just the definition of the Learning Algorithms! (check the link)
It outputs a classifier. So we can simplify to:
$P r [e r r o r_{D, c} (c l a s s i f i e r) < ε] > 1 - δ$

2. $e r r o r_{D, c} (c l a s s i f i e r) < ε$

It's asking if the classifier, given datapoints from distribution D and labeled by c, has an error rate less than $ϵ$
It's basically checking if the classifier is good enough!
So we can simplify to:
- $P r [g o o d E n o u g h (c l a s s i f i e r)] > 1 - δ$

3. $P r [g o o d E n o u g h (c l a s s i f i e r)] > 1 - δ$

Checking if the probability of the classifier being good enough is more than $1 - δ$

Sum up

A Concept Class C is PAC learnable iff an algorithm can be found that:

For every instance from C
For every distribution D
For every needed error rate
For every needed confidence rate
With probability $1 - δ$ outputs a good enough classifier
- A classifier that when given datapoints from D labeled by C, has less than $ϵ$ error
With probability $δ$ outputs a bullshit classifier
- A classifier that when given datapoints from D labeled by C, has more than $ϵ$ error

Note

PAC learnability is the equivalent of Uncomputability. If it CAN be learned or not.
It says NOTHING about how much time and memory it takes to learn!

Example

The concept class of axis-parallel rectangles is PAC learnable because there exists an algorithm ( $A_{B F P}$ ) that:

No matter what the target rectangle is
No matter what how you choose training data
No matter what level of confidence you need
No matter how accurate you want it to be
It can learn a model that with $1 - δ$ chance has good enough accuracy

How do we know $A_{B P F}$ has these properties?
It's a theorem. :)

Definition

Explanation of Pr[errorD,c(A(EX(c,D),ε,δ))<ε]>1−δ

1. A(EX(c,D),ε,δ)

2. errorD,c(classifier)<ε

3. Pr[goodEnough(classifier)]>1−δ