PAC Learning

machine-learning statistics learning-theory

Definition

PAC Learning

Probably Approximately Correct (PAC) learning is a mathematical framework for quantifying the learnability of a hypothesis class $\mathcal{H}$. A class $\mathcal{H}$ is PAC-learnable if there exists a learning algorithm $A$ and a sample complexity function $m(ϵ,\delta )$ such that for any distribution $P$ and any parameters $ϵ,\delta \in (0,1)$:

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

provided that the sample size $m\ge m(ϵ,\delta )$. The parameters define the rigor of the guarantee:

• Approximately Correct ($ϵ$): The hypothesis achieves an error rate no greater than $ϵ$.
• Probably ($1-\delta$): This accuracy is achieved with high confidence.

Learnability of Finite Classes

If the hypothesis class $\mathcal{H}$ is finite and the realisability assumption holds, any hypothesis that is consistent with the training set (i.e., has zero empirical risk) is PAC-learnable. The required sample complexity is bounded by:

$$m\ge \frac{1}{ϵ}\left(\ln |\mathcal{H}|+\ln \frac{1}{\delta }\right)$$

Derivation Intuition: Consider a “bad” hypothesis with $R(h)>ϵ$. The probability that this hypothesis is consistent with a single sample is at most $1-ϵ$. For $m$ independent samples, the probability that a bad hypothesis remains consistent is $(1-ϵ{)}^m$. To ensure that the probability of any bad hypothesis in $\mathcal{H}$ being consistent is less than $\delta$, we require $|\mathcal{H}|(1-ϵ{)}^m<\delta$. Using the inequality $1-ϵ\le e^{-ϵ}$, this yields $|\mathcal{H}|e^{-mϵ}<\delta$, which solves to the bound above.

Learnability of Infinite Classes

For classes with infinite cardinality, such as linear separators in ${\mathbb{R}}^d$, PAC-learnability is determined by the VC dimension. A class is PAC-learnable if and only if its VC dimension is finite.