Accuracy Parameter (PAC-learning)

Definition

Accuracy Parameter (PAC-learning)

The accuracy parameter $\epsilon >0$ specifies the maximum allowed prediction error of a Hypothesis produced by a PAC learner.

A hypothesis $h$ is considered sufficiently accurate if

$$\underset{x\sim D}{\mathrm{Pr}}\left[h(x)\ne c(x)\right]\le \epsilon .$$

Smaller values of $\epsilon$ require the learned hypothesis to approximate the target concept more closely.