PAC Learning Model

Intro

This model intends to fix the major problem with the consistency model. It should say something about generalizing from a smaller set of data to a larger set of examples.

Generalization Error

Our goal is to obtain an accurate hypothesis. We need to define an error to measure the accuracy. $Pr_{x\sim D}[h(x) \neq c(x)] = err_D(h)$ where x is an example that comes from an unknown target distribution D. h is the hypothesis. testing examples also come from D.

Now we no longer seek a hypothesis that is consistent with training set. Rather, we want to formulate a hypothesis that minimize the $err_D(h)$.

Note: Since the training data is randomly selected from an unknown distribution, there is always the chance the training set is very unrepresentative of the source distribution.

The Probably Approximately Correct Model

A target concept class $C$ is PAC-learnable by a hypothesis space $H$ if $\exists$ an algorithm A such that $\forall c \in C$, any target distribution D, any positive $\epsilon$ and $\delta$, A uses a training set $S = \{(x_1, c(x_1)), (x_2, c(x_2), ..., (x_m, c(x_m))\}$ where $m = ploy(\frac{1}{\epsilon}, \frac{1}{\delta}, ...)$ examples taken from iid from D and produces $h \in H$ such that $err_D(h) \leq \epsilon$ and $Pr[err_D(h)] \leq 1 - \delta$

Explanation:

• m is a polynomial dependent on $\epsilon$ and $\delta$. for a more accurate hypothesis, you need to a larger training set.

• $\epsilon$ is the accuracy parameter, $\delta$ is the confidence parameter. They are both user specified.

• We want a hypothesis that is highly probably ($1 - \delta$) approximately correct ($\epsilon$-good). The probably approximately correct model, get it?