Probably Approximately Correct Learning

machine-learning

Definition

Probably Approximately Correct Learning

The Probably Approximately Correct (PAC) framework is a theoretical model that analyses the learnability of a hypothesis class $\mathcal{H}$. It determines if a learning algorithm can reliably select a hypothesis that is “close enough” to the best possible solution, given a reasonable amount of data.

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(ϵ,\delta )$ such that:

For any parameters $ϵ,\delta \in (0,1)$ and any distribution $\mathcal{D}$ over $\mathcal{X}\times \mathcal{Y}$ (assuming realisability), if the algorithm receives $m\ge m(ϵ,\delta )$ i.i.d. samples, it produces a hypothesis $h_S$ such that:

$${\mathrm{Pr}}_{S\sim {\mathcal{D}}^m}\left(R_{\mathcal{D}}(h_S)\le ϵ\right)\ge 1-\delta$$

Key Guarantees:

• Approximately Correct: The true risk is bounded by error parameter $ϵ$ (i.e., $R_{\mathcal{D}}(h_S)\le ϵ$).
• Probably: This low error is achieved with probability at least $1-\delta$.

Link to original