VC Dimension

Some model classes are inherently more flexible than others — a straight line can't fit every possible arrangement of points, but a wiggly enough curve can fit almost anything. The VC dimension (Vapnik–Chervonenkis dimension) formalizes this by asking: what is the largest number of points, in the worst-case arrangement, that this model class can perfectly classify no matter how those points are labeled? A model class with a higher VC dimension is more expressive, and models that are more expressive are more prone to overfitting a finite training set.

A straight line in two dimensions has VC dimension 3: it can perfectly separate any labeling of 3 points (as long as they aren't collinear), but there exists an arrangement of 4 points no line can separate for every possible labeling. This number matters beyond trivia because learning theory uses it to bound how much training data a model needs before its training performance reliably predicts its performance on new data — a higher VC dimension means more data is needed before you can trust the training score.

Worked example. A linear classifier (VC dimension 3) trained on 50 data points is far more likely to generalize reliably than a highly flexible model with VC dimension in the thousands trained on the same 50 points — the flexible model can memorize the training labels almost regardless of what they are, which is exactly what a high VC dimension predicts.