VC-Dimension in Machine Learning

The theorem gives two equivalent ways to recognize the relevant learning condition: examine uniform convergence of empirical risk to true risk, or examine whether the hypothesis class has finite VC-dimension.

Programming

Interactive lab

Try it: Shattering and VC Dimension

What it means for a hypothesis class to shatter a set of points: all labelings are checked exactly, each realizable one with a witness hypothesis drawn, until the first labeling no hypothesis can produce — linked to the VC dimensions of thresholds (1), intervals (2), halfspaces in the plane (3) and axis-aligned rectangles (4).

How it works

Pick a hypothesis class and place n points.
Enumerate all labelings of the points with 0 / 1.
For each labeling decide exactly whether some hypothesis produces it (thresholds: every 1 left of every 0; intervals: no 0 between the outer 1s; rectangles: no 0 in the bounding box of the 1s; halfspaces: strict linear separability).
Draw a witness hypothesis for every realizable labeling.
The set is shattered if every labeling is realized; VCdim is the size of the largest shattered set.

Default run (6 steps): 2 points and the class of intervals on a line (VC dimension 2). Check all 2^2 = 4 labelings: is each one produced by some hypothesis? … All 4 labelings are realized: intervals on a line shatter these 2 points, so VCdim >= 2. Theory: VCdim = 2, so no set of 3 points can be shattered.

Simplified: At most 6 points on a 0–10 board. The lab checks one placement at a time: failing to shatter one set of n points does not by itself show VCdim < n — that needs every placement (the lab states the known VC dimension).

Educational simulation

Loading the simulation…

The Learning Boundary

A central question in statistical learning is whether a hypothesis class can support reliable learning. The Fundamental Theorem of Statistical Learning gives a precise answer for hypotheses that map a domain X to binary labels {0, 1} using the 0-1 loss. It connects two views of the same boundary: how risk behaves across an entire hypothesis class and how complex that class is.

Key point

Shattering and Capacity

VC-dimension is a measure that characterizes the complexity and learnability of a hypothesis class. Intuitively, it describes how much freedom the class has to realize different binary labelings on a finite set of points. A set is shattered when the hypothesis class can realize the relevant labelings on that set. The VC-dimension is determined by the largest size of a finite set that the class can shatter. The important distinction for the theorem is whether this measure is finite or infinite.

Which labelings of a finite set can the hypothesis class realize, and how does the largest shattered set determine VC-dimension?

Worked example

Reading a Shattering Test

Suppose a hypothesis class is tested on a finite set S. Consider whether the class can realize each binary labeling of S.

1
Inspect the set
Start with the selected finite set of points. The question is about the labelings that the hypothesis class can produce on this same set.
2
Check the labelings
If the class can realize all the relevant binary labelings on S, then S is shattered by the class.
3
Compare set sizes
Repeat the reasoning for larger finite sets. The largest size that can be shattered determines the VC-dimension when that size is finite.
4
Interpret the result
A finite result describes a bounded capacity in this sense. An infinite VC-dimension means that arbitrarily large finite sets can be shattered.

Result

VC-dimension records the shattering capacity of the hypothesis class, not the performance of one isolated hypothesis.

Uniform Risk Agreement

Uniform convergence describes agreement between two views of risk: empirical risk and true risk. Empirical risk is the risk assessed from the available sample, while true risk is the corresponding risk in the underlying learning setting. Uniform convergence says that empirical risk converges to true risk across the hypothesis class as a whole. The word uniformly is essential: the claim is not only about one selected hypothesis, but about all hypotheses in the class.

How do empirical risks for all hypotheses compare with their corresponding true risks, and what does uniform closeness look like as sample size increases?

The Fundamental Equivalence

Definition

In the setting of binary-valued hypotheses that map X to {0, 1} and use the 0-1 loss, the Fundamental Theorem of Statistical Learning states that uniform convergence is equivalent to finite VC-dimension. The theorem therefore identifies one learning condition in two equivalent forms: empirical risk converges uniformly to true risk, and the hypothesis class has finite VC-dimension.

How are finite VC-dimension, uniform convergence, and learnability connected in the Fundamental Theorem of Statistical Learning?

This equivalence is useful because the two sides emphasize different evidence. Uniform convergence focuses on the behavior of empirical and true risk over the whole class. VC-dimension focuses on the class's complexity through its shattering capacity. In this theorem's setting, the two tests agree.

When Capacity Is Infinite

Infinite VC-dimension means that the hypothesis class can shatter arbitrarily large finite sets. The source result associates infinite VC-dimension with non-learnability. Through the theorem's equivalence, this also marks the failure of the finite-complexity condition linked to uniform convergence.

How does the ability to shatter arbitrarily large finite sets prevent empirical risk from reliably approximating true risk?

Common Interpretation Errors

Common mistake
Treating uniform convergence as a statement about only one selected hypothesis.
What it looks like
A learner checks that one hypothesis has similar empirical and true risk and calls this uniform convergence.
Why it fails
Uniform convergence concerns the hypothesis class as a whole, not only one hypothesis.
Do this instead
Ask whether empirical risk converges to true risk across the entire hypothesis class.
Common mistake
Describing VC-dimension as the performance of a trained model.
What it looks like
A learner uses the observed risk of one model as the model's VC-dimension.
Why it fails
VC-dimension measures the complexity and shattering capacity of a hypothesis class.
Do this instead
Separate the class-level complexity measure from the risk behavior of an individual hypothesis.
Common mistake
Forgetting the theorem's setting.
What it looks like
A learner states the equivalence without mentioning binary-valued hypotheses or 0-1 loss.
Why it fails
The source theorem is stated for hypotheses mapping X to binary labels {0, 1} with 0-1 loss.
Do this instead
Include the binary-classification and 0-1-loss setting when stating the theorem.
Common mistake
Assuming infinite VC-dimension guarantees better learning because the class can represent many labelings.
What it looks like
A learner treats unlimited shattering capacity as automatically beneficial.
Why it fails
The source result associates infinite VC-dimension with non-learnability.
Do this instead
Recognize that, in this theorem's setting, infinite VC-dimension rules out the relevant learnability condition.

Check Your Understanding

EASY

A hypothesis class consists of binary-valued hypotheses and is studied with the 0-1 loss. You are told that its VC-dimension is finite. What corresponding statement does the Fundamental Theorem of Statistical Learning support about empirical risk and true risk across the class?

Hints

Use the theorem's equivalence rather than focusing on one hypothesis.
The relevant risk property is uniform convergence.

Your attempt (not saved)

MEDIUM

A second hypothesis class can shatter arbitrarily large finite sets. What does this imply about its VC-dimension, and what learning consequence is associated with that result?