Vapnik-Chervonenkis dimension

SSU

Let $\mathcal{H}\subseteq {\left\{-1,+1\right\}}^{\mathcal{X}}$, the vapnik-Chervonenkis dimension of $\mathcal{H}$, denoted as $d_{\text{VC}}(\mathcal{H})$ is the cardinality of the largest set of points from $\mathcal{X}$ that can be shattered by $\mathcal{H}$.

The set of $m$ input points $\{x_1,\cdots ,x_m\}$ is shattered by $\mathcal{H}$, if for every labeling $y\in {\left\{-1,+1\right\}}^m$, there exists a hypothesis $h\in \mathcal{H}$ such that

$$h(x_i)=y_i.$$

In other words, VC-dimension for hypothesis class is the maximum number of points this class can realize - for every possible labeling, there exists a classifier in set $|\mathcal{H}|$.

Important examples

Class of models	$d_{\text{VC}}(\mathcal{H})$
Linear classifiers from ${\mathbb{R}}^d$	= $d+1$	line can always separate 3 points, plane can always separate 4 points, …
Threshold classifier	= $1$	Any two points with different labels break the threshold if they lie on “wrong side” of the threshold
Finite hypothesis space	$\le {\log }_2(\Vert \mathcal{H}\Vert )$	There is $2^m$ possible labeling or $m$ points. We need at least that many hypothesis to shatter $m$ points.
Memorizers	$\infty$	You can memorize any number of points.
Nearest neighbors classifiers	$\infty$	Theoretically same as memorizer, we can have infinitely close points for each