VC Dimension

Let \((X,\mathcal{H})\) be a set system i.e. a set \(X\) and a class \(\mathcal{H}\) of subsets of \(X\), and define this set system to shatter a set \(A\) if each subset \(a \subseteq A\) can be expressed as \(a=A\cap h\) for some \(h \in \mathcal{H}\).

Here, \(X\) is the instance space, for e.g. the space of all possible emails, and \(\mathcal{H}\) is the class of potential hypothesis where a hypothesis \(h\) is a subset of \(X\) e.g. emails which are classified as spam.

The VC dimension (VC stands for Vapnik–Chervonenkis) of \(\mathcal{H}\) is the size of the largest set shattered by \(\mathcal{H}\). I.e. if \(VCdim(\mathcal{H})=d\) then there are \(d\) points \(x_1,\cdots,x_d \in X\) such that all possible labellings for them can be achieved by using hypotheses from \(\mathcal{H}\).