Vapnik–Chervonenkis dimension (VC dimension)

Imagine handing a hypothesis class a small set of points and asking it to label them in every possible way — all black-or-white assignments at once. The VC dimension is the size of the largest point set the class can label in every one of those ways. It is a worst-case measure of expressive reach: a class that can carve any labeling onto d points but fails on some set of d+1 points has VC dimension d. For thresholds on the line it is 1; for half-planes in the plane it is 3.

Formally, a class of binary-valued functions shatters a set if its restriction to that set realizes all 2^n labelings, and the VC dimension is the supremum of shatterable-set sizes. Its power comes from the Sauer–Shelah lemma: a class of finite VC dimension d can produce only a polynomial number of distinct labelings on m points, on the order of m^d, not 2^m. Feeding this growth bound into a uniform-convergence argument yields generalization gaps shrinking like the square root of (d log m)/m, independent of the input dimension or the number of parameters.

VC dimension explains why classes that look enormous can still generalize and why some can never generalize from finite data. But it is distribution-free and worst-case, so it is often loose: a large margin or a benign data distribution can make the effective capacity far smaller than d suggests, which is exactly why data-dependent measures like Rademacher complexity later refined it.