Hypothesis Class

machine-learning

Definition

Hypothesis Class

A hypothesis class $\mathcal{H}$ is the pre-determined set of all valid hypothesis that the learning algorithm is allowed to choose from.

Supervised Learning:

$$\mathcal{H}\subseteq \{h\mid h:\mathcal{X}\to \mathcal{Y}\}$$

PAC

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

Shattering

Definition

Shattering Hypothesis Class

A hypothesis class $\mathcal{H}$ shatters instances $X\subseteq \mathcal{X}$ of the instance space $\mathcal{X}$ if for all $(y_1,\dots ,y_n)\subseteq \{0,1{\}}^n$ there is an $h\in \mathcal{H}$ with $h(x_i)=y_i$ for $i=1,\dots n$:

$$\forall (y_1,\dots ,y_n)\in \{0,1{\}}^n:\exists h\in \mathcal{H}:\forall i\in \{1,\dots ,n\}:h(x_i)=y_i$$

Link to original