VC Dimension and Shattering

To establish a VC dimension exactly, two directions are required: a lower bound showing that a particular number of points can be shattered, and an upper bound showing that no larger set can be shattered.

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…

Why Capacity Matters

A classification class is more expressive when it can realize more different labelings of data points. VC dimension measures this capacity through shattering: it is the largest number of points for which the class can produce every possible binary labeling.

Definition

The VC dimension of a classification class is the largest number of points that the class can shatter. A set of points is shattered when every possible assignment of binary labels to those points can be produced by some classifier in the class.

How can a hypothesis class realize every possible binary labeling of a set of points, and how does the largest such set determine VC dimension?

Key point

Homogeneous Halfspaces

For homogeneous halfspaces, the separating boundary is required to pass through the origin. The classification decision is controlled by the weight vector through dot products with the input vectors. The VC dimension of homogeneous halfspaces in R^{^d} is d.

Why can homogeneous halfspaces shatter d points but fail to shatter d+1 points because every separating hyperplane must pass through the origin?

Worked example

Shattering the Standard Basis Vectors

Show that the d standard basis vectors in R^{^d} can be shattered by homogeneous halfspaces.

1
Choose the points
Use the d standard basis vectors e1 through ed. Each basis vector has a 1 in one coordinate and 0 in all the others.
2
Choose a labeling
Take any desired binary labeling y1 through yd for these points.
3
Construct the weight vector
Use the desired labels as the coordinates of the weight vector w.
4
Evaluate each point
The dot product of w with ei selects the i-th coordinate of w, so the dot product equals yi.
5
Conclude the lower bound
Because every desired labeling can be obtained, the d standard basis vectors are shattered.

Result

Homogeneous halfspaces in R^{^d} can shatter at least d points.

The basis-vector construction works because each basis vector isolates one coordinate of the weight vector. Selecting the coordinates of w to match the desired labels lets the classifier independently realize the labeling on those d points.

The upper bound uses a different idea. Any d+1 vectors in R^{^d} are linearly dependent, so there are real coefficients, not all zero, whose weighted combination of the vectors equals the zero vector. If a weight vector produced positive dot products on the vectors with positive coefficients and negative dot products on those with negative coefficients, applying that weight vector to the dependence relation would create incompatible sign conditions. Therefore, some labeling cannot be realized.

Adding a Bias

Non-homogeneous halfspaces include a bias term, so the separating boundary is not required to pass through the origin. This additional parameter increases the VC dimension in R^{^d} from d to d+1.

How does allowing a bias term move the separating hyperplane and enable shattering d+1 points?

Worked example

The Non-Homogeneous Lower Bound

Identify a set of d+1 points that can be shattered by non-homogeneous halfspaces in R^{^d}.

1
Choose the points
Use the zero vector together with the d standard basis vectors.
2
Use the bias-enabled class
The source construction uses non-homogeneous halfspaces, which are not restricted to boundaries passing through the origin.
3
Conclude the lower bound
This set of d+1 vectors is shattered, so the VC dimension is at least d+1.

Result

Non-homogeneous halfspaces in R^{^d} can shatter at least d+1 points.

The upper bound follows by reducing the non-homogeneous problem in R^{^d} to a homogeneous problem in R^{^d+1}. If d+2 vectors in R^{^d} could be shattered by non-homogeneous halfspaces, the reduction would produce d+2 vectors in R^{^d+1} shattered by homogeneous halfspaces. That contradicts the homogeneous result, because homogeneous halfspaces in R^{^d+1} have VC dimension d+1 and cannot shatter d+2 vectors.

What does the weight vector control about a decision boundary, what does the bias control, and how do their degrees of freedom change the shattering argument?

Common Reasoning Errors

Common mistake
Treating a successful construction on d points as a complete proof that the homogeneous VC dimension is d.
What it looks like
The standard basis construction shows that d points can be shattered.
Why it fails
It establishes only the lower bound. A larger set might still be shatterable unless an upper bound is proved.
Do this instead
Add the linear-dependence argument showing that no d+1 vectors in R^d can be shattered.
Common mistake
Applying the homogeneous result directly to non-homogeneous halfspaces in the same dimension.
What it looks like
Claiming that non-homogeneous halfspaces in R^d also have VC dimension d because the weight vector has d coordinates.
Why it fails
The bias term changes the shattering argument by allowing a boundary that is not required to pass through the origin.
Do this instead
Use the zero vector together with the d basis vectors for the lower bound and the reduction to homogeneous halfspaces in R^(d+1) for the upper bound.
Common mistake
Ignoring the sign structure in the linear-dependence proof.
What it looks like
Using linear dependence without separating positive and negative coefficients.
Why it fails
The contradiction depends on requiring opposite dot-product signs for the groups determined by the coefficients.
Do this instead
Separate indices with positive coefficients from those with negative coefficients and apply the proposed weight vector to the dependence relation.

Capacity Check

MEDIUM

Explain the two-part proof that homogeneous halfspaces in R^{^d} have VC dimension d. Your response should identify the shattered set used for the lower bound and the property of d+1 vectors used for the upper bound.

Hints

For the lower bound, consider the standard basis vectors.
For the upper bound, use linear dependence among d+1 vectors in R^{^d}.
Explain how the signs of the coefficients create the contradiction.

Your attempt (not saved)

MEDIUM

Compare the homogeneous and non-homogeneous cases in R^{^d}. State the VC dimension in each case and explain what role the bias term plays.

Hints

The homogeneous boundary is required to pass through the origin.
The non-homogeneous lower-bound construction uses the zero vector and the d standard basis vectors.
For the non-homogeneous upper bound, use the reduction to homogeneous halfspaces in R^{^d+1}.

Your attempt (not saved)

Final Takeaways

1
VC dimension is the largest number of points that a classification class can shatter.
2
Shattering means realizing every possible binary labeling of a selected set of points.
3
Homogeneous halfspaces in R^{^d} have VC dimension d: the standard basis gives the lower bound, and linear dependence gives the upper bound.
4
Non-homogeneous halfspaces in R^{^d} have VC dimension d+1: the zero vector plus the basis vectors gives the lower bound, and reduction to homogeneous halfspaces in R^{^d+1} gives the upper bound.
5
The weight vector controls the dot-product signs used in the shattering construction, while the bias term removes the requirement that the boundary pass through the origin.

At a glance

VC dimension measures classification capacity through the largest shattered set.
Homogeneous halfspaces in R^{^d} have VC dimension d.
The homogeneous lower bound uses the d standard basis vectors.
The homogeneous upper bound uses linear dependence among d+1 vectors.
Allowing a bias term increases the non-homogeneous VC dimension to d+1.

Related concepts

More concepts starting with V