What does PAC learning theory mean?

Question

I am new in machine learning. I am studying a course in machine learning (Stanford University ) and I did not understand what is meant by this theory and what is its utility. I am wondering if someone could detail this theory for me.

This theory is based on this equation.

Answer 1

Probably approximately correct (PAC) learning theory helps analyze whether and under what conditions a learner $L$ will probably output an approximately correct classifier. (You'll see some sources use $A$ in place of $L$.)

First, let's define "approximate." A hypothesis $h \in H$ is approximately correct if its error over the distribution of inputs is bounded by some $\epsilon, 0 \le \epsilon \le \frac{1}{2}.$ I.e., $error_D(h)\lt \epsilon$, where $D$ is the distribution over inputs.

Next, "probably." If $L$ will output such a classifier with probability $1 - \delta$, with $0 \le \delta \le \frac{1}{2}$, we call that classifier probably approximately correct.

Knowing that a target concept is PAC-learnable allows you to bound the sample size necessary to probably learn an approximately correct classifier, which is what's shown in the formula you've reproduced:

$$m \ge\frac{1}{\epsilon}(ln|H| + ln\frac{1}{\delta})$$

To gain some intuition about this, note the effects on $m$ when you alter variables in the right-hand side. As allowable error decreases, the necessary sample size grows. Likewise, it grows with the probability of an approximately correct learner, and with the size of the hypothesis space $H$. (Loosely, a hypothesis space is the set of classifiers your algorithm considers.) More plainly, as you consider more possible classifiers, or desire a lower error or higher probability of correctness, you need more data to distinguish between them.

For more, this and other related videos may be helpful, as might this lengthy introduction or one of many machine learning texts, say Mitchell, for example.

Answer 2

The definition of probably approximately correct is due to Valiant. It is meant to give a mathematically rigorous definition of what is machine learning.
Let me ramble a bit. While PAC uses the term 'hypothesis', mostly people use the word model instead of hypothesis. With a nod to the statistics community I prefer model, but I'll attempt to use both. Machine learning starts with some data, $(x_i, y_i)$ and one wants to find a hypothesis or model that will, given the inputs $x_i$ return $y_i$ or something very close. More importantly given new data $\tilde{x}$ the model will compute or predict the corresponding $\tilde{y}$ .
Really one isn't interested in how accurate the hypothesis is on the given (training) data except that it is hard to believe that a model that was created using some data will not accurately reflect that data set, but will be accurate on any future data sets. The two important caveats are that one cannot predict new data with 100% accuracy and there is also the possibility that the data examples one has seen miss something important. A toy example would be that if I gave you the 'data' 1,2,3,4 one would 'predict' that 5 would be the next number. If you tested this by asking people what was the next number in the sequence, most people would say 5. Someone could say 1,000,000 though. If you were given the sequence 1,2,3,...999,999 one would be surer that the next number is 1,000,000. However the next number could be 999,999.5, or even 5. The point is that the more data one sees, the more sure one can be that one has produced an accurate model, but one can never be absolutely certain.

The definition of probably approximately correct gives a mathematically precise version of this idea. Given data $x_i, 1 \leq i \leq m$ with output $y_i$ and a class of models $f_{\theta} $ which constitute the hypotheses one can ask 2 questions. Can we use the data to find a specific hypothesis $f_{\Theta}$ that is likely to be really accurate in predicting new values ? Further how likely is it that the model is as accurate as we expect it to be ? That is can we train a model that is highly likely to be very accurate. As in Sean Easter's answer, we say a class of hypotheses (class of models) is PAC if we can do an 'epsilon, delta' argument. That is we can say with probability $ p >1-\delta $ that our model $f_{\Theta}$ is accurate to within $\epsilon$ . How much data one must see to satisfy a specific pair $(\delta,\epsilon) $ depends on the actual $(\delta,\epsilon) $ and how complex the given class of hypothesis are.

More precisely, a class of hypotheses $\mathcal{H}$ or models $f_{\theta}$ is PAC if for any pair $(\epsilon, \delta)$ with $ 0 < \epsilon,\delta , <.5 $ there is a specific model $f_{\Theta}$ such that any new data $\tilde{x}, \tilde{y} $, this model will satisfy $Err(f_{\Theta}(\tilde{x}) ,\tilde{y} ) < \epsilon$ with probability $ p > 1-\delta $ if the model was selected (trained) with at least $ m = m(\delta,\epsilon,\mathcal{H}) $ training examples. Here Err is the chosen loss function which is usually $(f_{\Theta}(\tilde{x}) -\tilde{y})^2$.

The diagram you have gives a formula for how much data one needs to train on for a given class of hypotheses to satisfy a given pair $(\delta,\epsilon) $. I could be wrong, but I believe that this definition was given by Valiant in a paper called "A Theory of the Learnable" and was in part responsible for Valiant winning the Turing prize.