Probably Approximately Correct Learning

machine-learning

Definition

Probably Approximately Correct Learning

The Probably Approximately Correct (PAC) learning framework is a model in computational learning theory that analyzes whether and how efficiently a learning algorithm can produce a model with good generalisation performance. It provides a formal guarantee that the learned model will be mostly accurate, most of the time.

The name breaks down its core guarantee for a learned hypothesis $h$:

• Approximately Correct: The model’s true error (risk) is low, bounded by a small error parameter $ϵ>0$.
• Probably: This guarantee of being “approximately correct” holds with a high probability, at least $1-\delta$, where $\delta >0$ is a small confidence parameter.

Formalism

A hypothesis space $\mathcal{H}$ is considered PAC-learnable if, for any choice of $ϵ>0$ and $\delta >0$, there is a learning algorithm that, given a sufficient number of i.i.d. training samples, will produce a hypothesis $h_S$ satisfying:

$P_{S\sim P^n}\left(R(h_S)\le {\min }_{h^{\ast }\in \mathcal{H}}R(h^{\ast })+ϵ\right)\ge 1-\delta$

The central aim of the PAC framework is to determine the sample complexity—the minimum number of training samples $n$ required to meet these guarantees for a given hypothesis space. This links the amount of data needed to the desired level of accuracy and confidence.