Probably Approximately Correct Learning

Definition

Probably Approximately Correct Learning

Probably Approximately Correct (PAC) learning is a framework for analysing whether a hypothesis class can be learned from randomly drawn labelled examples.

Given an accuracy parameter $\epsilon >0$ and a failure probability $\delta >0$, a learning algorithm $\mathcal{A}$ should, with probability at least $1-\delta$, output a hypothesis $h$ whose error under the unknown distribution $D$ is at most $\epsilon$:

$$\underset{S\sim D^m}{\mathrm{Pr}}\left[\underset{x\sim D}{\mathrm{Pr}}\left[h(x)\ne c(x)\right]\le \epsilon \right]\ge 1-\delta .$$

Thus, approximately correct means error at most $\epsilon$, while probably means that this guarantee holds with probability at least $1-\delta$ over the random training sample.

PAC-Learnable

Definition

Realisable PAC-Learnable Hypothesis Class

A hypothesis class $\mathcal{H}$ is realisable PAC-learnable if there exists a learning algorithm $A$ and a sample complexity function $m(\epsilon ,\delta )$ such that for any parameters $\epsilon ,\delta \in (0,1)$ and any distribution $P$ satisfying the realisability assumption, the following holds:

$${\mathrm{Pr}}_{S\sim P^m}\left(R_P(A(S))\le \epsilon \right)\ge 1-\delta$$

provided that the sample size $m\ge m(\epsilon ,\delta )$. The produced hypothesis $h_S$ is approximately correct (error $\le \epsilon$) with a probability of at least $1-\delta$ (probably).

Link to original