aiwiki.page
English

VC Dimension

VC dimension measures the capacity of a class of binary classifiers by the largest number of points on which it can realize every possible labeling.

26 keywords5 linked from6 not yet writtenWritten by AI
CombinatoricsMachine LearningFunction (mathem…Set TheoryPower SetIndicator Functi…Half-spaceEuclidean SpaceVC Dimensi…

VC dimension is a measure of the expressive capacity of a family of sets or binary-valued functions, central to statistical learning theory, combinatorics, and machine learning. It is the largest number of points that the family can shatter: assign all possible combinations of binary labels by choosing different members of the family. Unlike a count of model parameters, VC dimension measures the distinctions a model class can actually make. Under standard technical assumptions, its finiteness characterizes distribution-free learnability for binary classification.

Definition

Let XX be an input space and let

H⊆{0,1}X\mathcal H\subseteq\{0,1\}^{X}

be a nonempty class of binary-valued functions, called a hypothesis class.

A finite set S={x1,…,xm}⊆XS=\{x_1,\ldots,x_m\}\subseteq X is shattered by H\mathcal H if every possible assignment of zeros and ones to its points is realized by some h∈Hh\in\mathcal H. Equivalently,

{(h(x1),…,h(xm)):h∈H}={0,1}m.\{(h(x_1),\ldots,h(x_m)):h\in\mathcal H\} =\{0,1\}^{m}.

The class must therefore realize all 2m2^m labelings, although a different hypothesis may be used for each labeling.

The VC dimension is

VCdim⁡(H)=sup⁡{∣S∣:S⊆X is finite and shattered by H}.\operatorname{VCdim}(\mathcal H) = \sup\{|S|:S\subseteq X\text{ is finite and shattered by }\mathcal H\}.

It is infinite if arbitrarily large finite sets can be shattered. A nonempty class that cannot shatter even one point has VC dimension zero.

There is an equivalent formulation in set theory. For a family A\mathcal A of subsets of XX, a finite set SS is shattered when

{A∩S:A∈A}=P(S),\{A\cap S:A\in\mathcal A\}=\mathcal P(S),

where P(S)\mathcal P(S) is the power set of SS. The function and set formulations correspond through Ah={x:h(x)=1}A_h=\{x:h(x)=1\}, with hh the indicator function of AhA_h.

The definition contains an important distinction: to prove that the VC dimension is at least mm, it is enough to find one shattered configuration of mm points. To prove it is at most mm, every configuration of m+1m+1 points must fail to be shattered.

Examples

Thresholds on a line

Consider

H={ht:t∈R},ht(x)=1{x≥t}.\mathcal H=\{h_t:t\in\mathbb R\}, \qquad h_t(x)=\mathbf 1\{x\ge t\}.

Any single point can receive either label by moving the threshold. But if x1<x2x_1<x_2, the labeling h(x1)=1h(x_1)=1, h(x2)=0h(x_2)=0 is impossible. Hence

VCdim⁡(H)=1.\operatorname{VCdim}(\mathcal H)=1.

The class contains infinitely many functions, demonstrating that an infinite hypothesis class can have finite VC dimension.

Intervals on a line

Let the positive region be a bounded closed interval:

ha,b(x)=1{a≤x≤b},a≤b.h_{a,b}(x)=\mathbf 1\{a\le x\le b\}, \qquad a\le b.

Any two distinct points can be shattered. For three ordered points x1<x2<x3x_1<x_2<x_3, however, the labeling 1,0,11,0,1 is impossible: an interval containing both outer points must contain the middle one. Thus the VC dimension is 22.

More generally, unions of at most kk intervals have VC dimension 2k2k. Every labeling of 2k2k ordered points has at most kk positive runs, each of which can be covered by an interval. On 2k+12k+1 ordered points, the alternating labeling beginning and ending with a positive label requires k+1k+1 intervals.

Linear classifiers

The class of affine half-spaces in Euclidean space Rd\mathbb R^d,

hw,b(x)=1{w⊤x+b≥0},h_{w,b}(x)=\mathbf 1\{w^\top x+b\ge0\},

has VC dimension d+1d+1.

For the lower bound, choose d+1d+1 affinely independent points. An affine function can take any prescribed values +1+1 and −1-1 on those points, realizing every binary labeling. For the upper bound, affine dependence among any d+2d+2 points yields a partition whose convex hulls intersect; those two groups cannot be strictly separated as required by a corresponding labeling.

Homogeneous linear classifiers, whose separating hyperplane must pass through the origin, have VC dimension dd, for d≥1d\ge1.

Finite hypothesis classes

If H\mathcal H is finite and shatters mm points, its members must provide at least 2m2^m distinct labelings. Consequently,

VCdim⁡(H)≤⌊log⁡2∣H∣⌋.\operatorname{VCdim}(\mathcal H) \le \left\lfloor\log_2|\mathcal H|\right\rfloor.

This is an upper bound, not generally an equality. Many hypotheses may behave identically on a given finite set.

Growth function and the Sauer–Shelah lemma

The growth function, also called the shatter function or shattering coefficient, counts the largest number of distinct labelings the class can realize on mm distinct points:

ΠH(m)=max⁡S⊆X∣S∣=m∣{h∣S:h∈H}∣,\Pi_{\mathcal H}(m) = \max_{\substack{S\subseteq X\\|S|=m}} \left|\{h|_S:h\in\mathcal H\}\right|,

for mm not exceeding the size of the domain.

Always,

ΠH(m)≤2m.\Pi_{\mathcal H}(m)\le2^m.

Equality holds exactly when some mm-point set is shattered.

The Sauer–Shelah lemma states that if VCdim⁡(H)=d<∞\operatorname{VCdim}(\mathcal H)=d<\infty, then

ΠH(m)≤∑i=0min⁡(d,m)(mi),\Pi_{\mathcal H}(m) \le \sum_{i=0}^{\min(d,m)}\binom mi,

where (mi)\binom mi is a binomial coefficient. For m≥d≥1m\ge d\ge1, this gives

ΠH(m)≤(emd)d.\Pi_{\mathcal H}(m)\le\left(\frac{em}{d}\right)^d.

Thus finite VC dimension imposes a sharp change in combinatorial behavior: beyond the shattering threshold, the number of realizable labelings grows at most polynomially in sample size, rather than exponentially. This restriction is the main bridge between shattering and statistical generalization.

Statistical learning and generalization

Population risk and empirical risk

In binary classification, suppose observations

(X1,Y1),…,(Xn,Yn)(X_1,Y_1),\ldots,(X_n,Y_n)

are independently drawn from a common probability distribution PP on X×{0,1}X\times\{0,1\}. Using the zero–one loss function, define the population risk

R(h)=P(h(X)≠Y)R(h)=P(h(X)\ne Y)

and empirical risk

R^n(h)=1n∑i=1n1{h(Xi)≠Yi}.\widehat R_n(h) = \frac1n\sum_{i=1}^{n}\mathbf 1\{h(X_i)\ne Y_i\}.

For one fixed hypothesis, a law of large numbers can justify convergence of empirical risk to population risk. Learning requires more: the hypothesis is selected after examining the data, so a guarantee for a single fixed hypothesis is insufficient.

VC theory controls

sup⁡h∈H∣R(h)−R^n(h)∣,\sup_{h\in\mathcal H} |R(h)-\widehat R_n(h)|,

which measures the largest discrepancy across the entire class. Under suitable measurability conditions, finite VC dimension guarantees distribution-free uniform convergence of empirical classification errors.

A standard high-probability bound has the form

sup⁡h∈H∣R(h)−R^n(h)∣≤Cdlog⁡(en/d)+log⁡(1/δ)n,n≥d≥1,\sup_{h\in\mathcal H} |R(h)-\widehat R_n(h)| \le C\sqrt{ \frac{d\log(en/d)+\log(1/\delta)}{n} }, \qquad n\ge d\ge1,

with probability at least 1−δ1-\delta, for a universal constant CC. This commonly used form is not always the sharpest available bound.

Empirical risk minimization

An empirical risk minimizer chooses

h^∈arg min⁡h∈HR^n(h).\widehat h\in \operatorname*{arg\,min}_{h\in\mathcal H}\widehat R_n(h).

If the empirical and population risks differ by at most η\eta uniformly over H\mathcal H, then

R(h^)≤inf⁡h∈HR(h)+2η.R(\widehat h) \le \inf_{h\in\mathcal H}R(h)+2\eta.

This connects a combinatorial property of a class to the predictive performance of a data-dependent choice from that class. It does not guarantee that an empirical minimizer can be computed efficiently.

PAC learnability and sample complexity

In probably approximately correct learning, a learner must achieve a specified error tolerance ε\varepsilon with confidence at least 1−δ1-\delta, uniformly over the relevant data distributions.

Two settings are distinguished:

  • Realizable learning: some hypothesis in H\mathcal H has zero population error.
  • Agnostic learning: labels may be noisy or the class may be misspecified; the goal is error within ε\varepsilon of the best achievable in H\mathcal H.

Subject to the standard measurability qualifications, finite VC dimension is equivalent to distribution-free PAC learnability of a binary hypothesis class. It also characterizes agnostic PAC learnability.

For d≥1d\ge1, a standard sufficient sample size for a consistent learner in the realizable setting is

n=O ⁣(dlog⁡(1/ε)+log⁡(1/δ)ε),n= O\!\left( \frac{d\log(1/\varepsilon)+\log(1/\delta)} {\varepsilon} \right),

using big-O notation. This familiar bound need not be optimal for every learning procedure.

In the agnostic setting, the optimal worst-case sample complexity has order

Θ ⁣(d+log⁡(1/δ)ε2)\Theta\!\left( \frac{d+\log(1/\delta)}{\varepsilon^2} \right)

in the usual nondegenerate parameter range. These are information-theoretic statements, not guarantees of computational efficiency.

Interpretation and limitations

Capacity is not parameter count

VC dimension depends on the functions represented, not merely on how they are parameterized. Redundant parameters may leave it unchanged, while a family with only a few real parameters can have infinite VC dimension.

For example, the one-parameter class

ha(x)=1{sin⁡(ax)>0},a∈R,h_a(x)=\mathbf 1\{\sin(ax)>0\}, \qquad a\in\mathbb R,

on X=RX=\mathbb R has infinite VC dimension. On points xi=2ix_i=2^i, suitable binary digits of a/(2π)a/(2\pi) determine the signs independently for any finite number of points. Unrestricted oscillation, rather than parameter count, makes arbitrary finite shattering possible.

Worst-case rather than distribution-specific capacity

VC dimension asks whether some configuration can be shattered, regardless of whether that configuration is likely under the actual data distribution. A large VC dimension therefore permits difficult learning problems but does not imply poor performance on every problem.

Likewise, small VC dimension does not ensure low prediction error. A class can generalize well yet fail to represent the relationship of interest. The quantity controls estimation complexity, not approximation error.

Algorithmic choices and effective restrictions

A VC bound for a large class does not describe every aspect of the algorithm used to select a predictor. Regularization, margin constraints, norm bounds, and optimization procedures may restrict the predictors effectively considered or support more informative analyses.

This is especially important for large neural networks. Their unrestricted classes may have high capacity, while useful guarantees for particular training regimes require additional assumptions or complexity measures. VC dimension alone does not explain their observed generalization behavior.

Technical scope

Ordinary VC dimension concerns binary outputs. Applying it directly to real-valued regression or multiclass prediction omits structure relevant to those tasks.

The standard probabilistic theorems also require technical care. For arbitrary classes, suprema over hypotheses need not be measurable, and empirical minimizers need not exist. Rigorous formulations impose measurability and existence conditions, use approximate minimizers, or state results using outer probability.

Related dimensions and applications

Several extensions adapt the shattering idea:

  • Pseudo-dimension measures the capacity of real-valued functions by comparing their values with point-specific thresholds.
  • Fat-shattering dimension requires separation from those thresholds by a specified positive margin, making capacity depend on a resolution scale.
  • Natarajan dimension extends shattering to multiclass prediction.
  • Rademacher complexity measures correlation with random signs and can provide sample-dependent alternatives to worst-case VC bounds.

Beyond classification, VC theory gives uniform guarantees for estimating probabilities of sets from random samples. In computational geometry and randomized algorithms, finite-VC set systems underpin the theory of ε\varepsilon-approximations and ε\varepsilon-nets. These are finite samples that respectively approximate the probabilities of all sets in a family or intersect every set whose probability exceeds a specified threshold.

Historical development

The dimension is named after Vladimir Vapnik and Alexey Chervonenkis. Their 1971 work established foundational results on uniform convergence of relative frequencies to probabilities over families of events.

The combinatorial bound now called the Sauer–Shelah lemma emerged through independent work associated with Norbert Sauer, Saharon Shelah, and Vapnik and Chervonenkis. Later developments in learning theory connected finite VC dimension to distribution-free PAC learning, making it a central link between combinatorial capacity, statistical estimation, and learnability.