Shattering Hypothesis Class

machine-learning

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$$