AI, machine learning and deep learning · Advanced

The VC-Dimension

Written by SignalsLab

Early edition: these lessons are being reviewed.

Content

Summary

The VC-dimension is a combinatorial measure of a hypothesis class's capacity, defined as the size of the largest set it can shatter. It demonstrates that infinite hypothesis classes can be PAC learnable if their VC-dimension is finite, linking learnability to uniform convergence.

Intuition

Think of the VC-dimension as a measure of how 'flexible' or complex a hypothesis class is. A class shatters a set of points if it can fit any possible binary labeling of those points. If a class can shatter a large set, it is very complex and might overfit; if it cannot shatter even small sets, it is simple. The VC-dimension is the maximum number of points that can be shattered. Crucially, this concept allows us to learn from infinite classes, like threshold functions, provided they have a finite VC-dimension, which bounds their complexity and ensures learnability.

Key equations

HC={(h(c1),…,h(cm)):h∈H}
(1)

The restriction of hypothesis class H to a finite set C, representing all possible labelings H can produce on C.

|HC|=2|C|
(2)

The condition for shattering: the number of distinct labelings produced by H on C equals the total number of possible binary labelings.

ha(x)=𝟙[x<a]
(3)

The definition of a threshold function, outputting 1 if x is less than threshold a, and 0 otherwise.

Derivation

  1. Define the restriction of a hypothesis class H to a finite set C as the set of all labelings H can produce on C.
  2. A set C is shattered by H if the restriction H_C contains all possible binary labelings, i.e., |H_C| = 2^{|C|}.
  3. The VC-dimension is the size of the largest set that H can shatter.
  4. Apply this to threshold functions: they shatter a single point (size 1) but cannot shatter two points (size 2) because they cannot produce the (0, 1) labeling.
  5. Conclude that the VC-dimension of threshold functions is 1, proving an infinite class can have finite VC-dimension and thus be PAC learnable.

Worked example

Problem

Determine if the class of threshold functions H = {h_a: a in R} where h_a(x) = 1[x < a] shatters a set C = {c1, c2} with c1 < c2.

  1. Identify the required labelings for shattering: (0,0), (0,1), (1,0), (1,1).
  2. Check if (0,0) is possible: Choose a <= c1. Then h_a(c1)=0 and h_a(c2)=0. Possible.
  3. Check if (1,1) is possible: Choose a > c2. Then h_a(c1)=1 and h_a(c2)=1. Possible.
  4. Check if (1,0) is possible: Choose a such that c1 < a <= c2. Then h_a(c1)=1 and h_a(c2)=0. Possible.
  5. Check if (0,1) is possible: We need h_a(c1)=0 and h_a(c2)=1. This requires a <= c1 and a > c2. Since c1 < c2, no such a exists.

Answer The class does not shatter C because it cannot produce the labeling (0,1). Thus, the VC-dimension is not 2.

Common mistakes

  • Assuming a hypothesis class must be finite to be learnable; infinite classes like thresholds are learnable if they have finite VC-dimension.
  • Confusing the restriction H_C with the original class H; H_C only considers labelings on the specific finite set C.
  • Thinking any infinite class can shatter any set; shattering depends on the specific structure of H, as thresholds cannot shatter sets of size 2.

Animation

Animation coming soon

The animated version of this lesson is being prepared for the web. In the Signals AI app, lessons are drawn step by step.

Code

This is a text lesson: it has no animation code yet.

ccBYNC© 2026 SignalsLab. Lesson text shared as is under CC BY-NC 4.0.