Shattering Hypothesis Class

machine-learning learning-theory set-theory

Definition

Shattering

A hypothesis class $\mathcal{H}$ is said to shatter a finite set of instances $X=\{x_1,\dots ,x_n\}\subseteq \mathcal{X}$ if $\mathcal{H}$ can realise every possible binary labelling of $X$. Formally, $\mathcal{H}$ shatters $X$ if:

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

This indicates that the class $\mathcal{H}$ is sufficiently flexible to classify the points in $X$ in any possible configuration.

Relation to Model Capacity

The concept of shattering is the operational component of the VC dimension. The VC dimension of a class $\mathcal{H}$ is defined as the size of the largest set $X$ that can be shattered by $\mathcal{H}$. If a class can shatter a set of size $n$, it implies the class has at least $2^n$ distinct functional behaviours on those points.