Shattering

A hypothesis class $\mathcal{H}$ is said to shatter a finite set $C\subset \mathcal{X}$ if the restriction of $\mathcal{H}$ to C is the set of all functions from $C$ to $\{0,1\}$ (for binary classification). In other words, $|{\mathcal{H}}_C|=2^{|C|}$ and every possible binary function on $C$ is part of some hypothesis in $\mathcal{H}$ and is, in that sense, not restrictive on the possible solutions.

Whenever some set $C\subset \mathcal{X}$ is shattered by $\mathcal{H}$, an adversary is not restricted by $\mathcal{H}$ as they can construct a distribution over $C$ based on any target function from $C$ to $\{0,1\}$, while still maintaining realizability (on $C$), yielding the No-Free-Lunch theorem.

Intuitively, if a set $C$ is shattered by $\mathcal{H}$, and we receive a sample containing half the instances of $C$, the labels of these instances give us no information about the labels of the rest of the instances in $C$ – every possible labeling of the rest of the instances can be explained by some hypothesis in $\mathcal{H}$.

Vapnik-Chervonenkis-dimension

The VC-dimension of a hypothesis class $\mathcal{H}$ is the maximal size of a set $C\subset \mathcal{X}$ that can be shattered by $\mathcal{H}.$
If $\mathcal{H}$ can shatter sets of arbitrarily large size, then $\mathcal{H}$ is said to have infinite VC-dimension, and is consequently not PAC learnable. On the other hand, the following holds and is termed The Fundamental Theorem of Statistical Learning:

Let $\mathcal{H}$ be a hypothesis class of functions from $\mathcal{X}$ to $\{0,1\}$ under the binary loss function. Then the uniform convergence property, PAC learnability and finite VC-dimension are all equivalent. Quantitatively, if $\mathrm{VCdim}(\mathcal{H})=d<\mathrm{\infty }$, then there are absolute constants $C_1,C_2$ such that:

1. $\mathcal{H}$ has the uniform convergence property with sample complexity:

2. $\mathcal{H}$ is (agnostic) PAC learnable with sample complexity:

3. $\mathcal{H}$ is PAC learnable (i.e, under strict realizability) with sample complexity:

This theorem holds for some other learning problems such as regression with the absolute or squared error loss, but not for all learning tasks.

Example

Let $\mathcal{H}=\{h_a:a\in \mathbb{R}\}$ be the class of threshold functions over $\mathbb{R}$, where $h_a:\mathbb{R}\to \{0,1\}$ is defined by $h_a(x)={\mathbb{1}}_{[x<a]}$ (i.e., $1$ if $x<a$ and $0$ otherwise). Although $\mathcal{H}$ is of infinite size, it is PAC learnable, as its VC dimension is finite:

• $\mathcal{H}$ shatters sets of size 1. Take $C=\{c_1\}$. Choosing $a=c_1+1$ gives $h_a(c_1)=1$, while $a=c_1-1$ gives $h_a(c_1)=0$. Hence ${\mathcal{H}}_C$ is the set of all functions from $C$ to $\{0,1\}$, and $\mathcal{H}$ shatters $C$.
• $\mathcal{H}$ shatters no set of size 2. Take $C=\{c_1,c_2\}$ with $c_1\le c_2$. No $h\in \mathcal{H}$ can realize the labeling $(0,1)$: any threshold assigning label $0$ to $c_1$ must assign label $0$ to $c_2$ as well. Thus not all functions from $C$ to $\{0,1\}$ are in ${\mathcal{H}}_C$, so $C$ is not shattered.
  It follows that $\mathrm{VCdim}(\mathcal{H})=1$.