VC Dimension

Definition

$\mathrm{VC}(\mathcal{F})=\max \{n:\exists X_1,\dots ,X_n\text{ shattered by }\mathcal{F}\}$, and $\infty$ if there is no maximum. To show $\mathrm{VC}=d$: one set of $d$ points is shattered, and no set of $d+1$ points is.

Formula

$$\mathcal{N}(\mathcal{F},n)\le \sum _{i=0}^d\left(\genfrac{}{}{0ex}{}{n}{i}\right)\le (\frac{en}{d}{)}^d(n\ge d),R(f)\le R_n(f)+2\sqrt{\frac{d\log (2en/d)-\log \delta }{n}}$$

• Dichotomy: the growth function is $2^n$ (VC $=\infty$) or polynomial of degree $d$.
• ERM is consistent w.r.t. $\mathcal{F}$ iff $\mathrm{VC}(\mathcal{F})<\infty$ (Theorem 14). Sample size $\sim d/{\epsilon }^2$.
• Values: half-lines 1, intervals 2, unions of two intervals 4, axis-parallel rectangles 4, convex $d$-gons $2d+1$, linear classifiers in ${\mathbb{R}}^d$ $d+1$, margin classifiers $\min \{R^2/{\rho }^2,d+1\}$, neural networks $O(W\log W)$, $\mathrm{sgn}\sin (tx)$ $\infty$.

Appears in

• Lecture 3, definition and examples
• Lecture 3, Sauer-Shelah lemma
• Lecture 3, Theorems 13 and 14
• Lecture 3, linear classifiers (Radon)
• Lecture 3, margin classifiers
• Lecture 3, neural networks
• Lecture 3, exam-style task

Related concepts

• Shattering Coefficient
• Generalization Bound
• Margin