VC Dimension

Core Idea

The Vapnik-Chervonenkis (VC) dimension measures the expressive capacity of a hypothesis class by finding the largest set of points the class can shatter — that is, classify in all 2ⁿ possible ways. A hypothesis class with VC dimension d can shatter some set of d points but no set of d+1 points. The VC dimension is the key quantity in the fundamental theorem of statistical learning: a class is PAC-learnable if and only if its VC dimension is finite, and the sample complexity for learning scales linearly with the VC dimension.

Explainer

Building on the PAC framework, we now need a way to measure how "complex" a hypothesis class is, because this complexity determines how many training examples are needed to learn. The Vapnik-Chervonenkis dimension provides exactly this measure. Rather than counting parameters or describing the functional form, VC dimension asks a combinatorial question: what is the largest number of data points that the hypothesis class can classify in every possible way?

The formal definition centers on the concept of shattering. A hypothesis class H shatters a set of points S = {x_1, ..., x_n} if for every possible labeling of these points (every assignment of +1 or -1 to each point), there exists some hypothesis h in H that perfectly classifies them according to that labeling. Since n points have 2ⁿ possible labelings, shattering requires that H is expressive enough to realize all 2ⁿ dichotomies. The VC dimension of H is the largest n for which there exists some set of n points that H can shatter. If H can shatter arbitrarily large sets, its VC dimension is infinite.

The canonical example is linear classifiers in R^d, which have VC dimension d+1. In R², lines can shatter 3 points in general position: for each of the 8 labelings, you can draw a line separating the positives from the negatives. But no set of 4 points can be shattered — by Radon's theorem, any 4 points in the plane contain a partition whose convex hulls overlap, creating a labeling that no line can achieve. This result generalizes: hyperplanes in R^d shatter d+1 points but not d+2, giving VC dimension d+1. The connection to the number of "free parameters" (d+1 coefficients for a hyperplane in R^d) is suggestive but coincidental in general — the sine function counterexample, with one parameter but infinite VC dimension, shows parameters alone do not determine capacity.

The profound consequence is the fundamental theorem of statistical learning: a hypothesis class is PAC-learnable if and only if its VC dimension is finite. When VC dimension is d, the sample complexity for achieving error epsilon with confidence 1-delta is O((d/epsilon) * log(1/epsilon) + (1/epsilon) * log(1/delta)). This is a tight characterization — no measure other than VC dimension (and its equivalents) captures learnability so precisely. For practitioners, VC dimension explains why models with too much capacity overfit (they can shatter the training data, memorizing noise) and why controlling capacity — through regularization, architecture constraints, or explicit complexity penalties — is essential for generalization.