CONCEPT
The VC Dimension
The Vapnik-Chervonenkis dimension—a single number measuring how much variety of behavior a class of learning machines can produce on a finite sample, and the key to the fundamental theorem of statistical learning: generalization is guaranteed when effective capacity is controlled relative to the amount of training data.
The VC dimension is the cornerstone of statistical learning theory and one of the most consequential mathematical ideas in the history of artificial intelligence. Introduced by
Vladimir Vapnik and Alexey Chervonenkis in their 1971 paper on the uniform convergence of relative frequencies to probabilities, it answers a question that the machine learning community had treated as intuitive but had never made rigorous: how powerful, in the sense relevant to
learning, is a given class of models? The answer is a number—the size of the largest set of points that the model class can label in every possible way. A model class with VC dimension
d can shatter some set of
d points (assign them every possible binary labeling) but cannot shatter any set of
d+1 points. From this number flow the bounding theorems: the gap between a model’s training error and its true error on the underlying