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 $P$ satisfying the realisability assumption, the following holds:

${\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 produced hypothesis $h_S$ is approximately correct (error $\le ϵ$) with a probability of at least $1-\delta$ (probably).

Link to original