Computational Learning Theory

[anthonyche]

In Bias-Variance analysis looked at components of the generalization error for arbitrary concept classes

Now we will ask about the "learnability" of specific concept classes.

How easy is it to find the target concept in terms of:

computational effort?
Training sample size?

Two sources of failure

Training sets of size m may not be enough to pick out f
The training set is large enough but is  bad

We introduce two parameters

𝜹： The probability of failure due to a bad sample 𝜺:

The PAC model