> For the complete documentation index, see [llms.txt](https://zedive.gitbook.io/project-l/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://zedive.gitbook.io/project-l/part-3/advanced_topics/machine_learning/learning-theory/pac_learning_model.md).

# 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.![](https://3556266963-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-LtpqP4Bii7DT_BTd4fN%2F-LtpqQ7GPCPppH_fyCKt%2F-LtpqZgXCIeuwlE5Yv6d%2FScreen%20Shot%202016-11-27%20at%202.25.49%20PM.png?generation=1573935272173457\&alt=media)

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?