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.