VapnikChervonenkisdimension

Vapnik-Chervonenkis dimension, commonly abbreviated as VC dimension, is a fundamental measure of the capacity or complexity of a hypothesis class H of binary classifiers defined on a domain X. The VC dimension d is the largest size of a finite subset S of X that can be shattered by H; if no such finite bound exists, the VC dimension is infinite. A subset S is shattered if, for every possible binary labeling of S, there exists a hypothesis h in H that agrees with that labeling on S.

The concept links model capacity to learnability in statistical learning theory. Finite VC dimension implies uniform convergence of empirical risk to true risk and underpins PAC (probably approximately correct) learning guarantees. The growth function m_H(n) counts how many distinct labelings H can realize on any set of n points, and Sauer’s lemma provides an upper bound m_H(n) ≤ sum_{i=0}^d C(n,i), where d is the VC dimension. These bounds yield sample complexity estimates showing how many labeled examples are needed to learn within a given error and confidence.

Examples help illustrate the idea: the set of all threshold functions on the real line has VC dimension 1, while the set of all intervals on the real line has VC dimension 2. For linear classifiers in R^d, the VC dimension is d+1 when a bias term is allowed (and d if the origin is fixed).

The notion was introduced by Vladimir Vapnik and Alexey Chervonenkis in the 1960s and has become a central concept in statistical learning theory, widely used to analyze and compare learning algorithms.