Hypothesis Classes in Machine Learning

When studying a hypothesis class, the important question is not simply how many hypotheses the class contains.

Programming

The Flexibility Question

When studying a hypothesis class, the important question is not simply how many hypotheses the class contains. The more useful question is how flexibly its hypotheses can label a finite collection of points. For axis-aligned rectangles, the decisive boundary is between four points and five points.

Key point

The final result is a sharp boundary: an appropriate set of four points can be shattered, but no set of five points can be shattered.

What Shattering Requires

Definition

A hypothesis class shatters a finite point set when, for every possible assignment of binary labels to those points, some hypothesis in the class realizes that assignment. For four points, this means realizing all 16 possible labelings, including the labeling in which all four points receive 1, the labeling in which all four receive 0, and every mixed assignment between them.

How can the same four-point set receive every possible positive and negative labeling, and how do we verify that none is missing?

Rectangle-Induced Labels

An axis-aligned rectangle acts as a hypothesis for labeling points in two-dimensional space. After a rectangle is chosen, each point receives a binary label according to the rectangle's inclusion rule: the selected rectangle determines which points are labeled 1 and which points are labeled 0. Moving, resizing, or repositioning the rectangle changes the labeling it produces. The question is whether the available rectangle choices can produce every requested labeling of a particular point set.

Which points become positive or negative when the selected rectangle is changed?

The visual shows the central mechanism: the point set stays fixed while the chosen rectangle changes. A class shatters the set only if suitable choices are available for every binary labeling, not merely for the two labelings shown in one illustration.

The Four-Point Lower Bound

Worked example

Showing that four points can be shattered

Show what must be established to prove that the VC-dimension of axis-aligned rectangles is at least 4.

1
Choose an appropriate four-point set
The lower-bound proof begins by exhibiting a set of four points for which rectangle choices can realize every binary assignment.
2
Include the extreme labelings
The rectangle class must realize the labeling in which all four points receive 1 and the labeling in which all four points receive 0.
3
Include every mixed labeling
It must also realize every assignment containing both labels. For four points, the complete collection contains 16 possible labelings.
4
Conclude the lower bound
Because every labeling of this four-point set can be realized by a suitable axis-aligned rectangle, the class shatters four points.

Result

The VC-dimension is at least 4.

How can rectangle placements account for all 16 labelings of four points?

Key point

This is an existence argument. It is enough to exhibit one suitable set of four points whose complete set of labelings can be realized. The proof does not require every possible arrangement of four points to have this property.

The Five-Point Obstruction

What do you think happens?

For an arbitrary set of five points, which labeling can be used to show that the set is not shattered?

Label the four boundary-extreme points 1 and the remaining point 0
Label every point 1
Label every point 0

Reveal answer

Answer:

Label the leftmost, rightmost, lowest, and highest points 1, and label the remaining point 0.

The source argument identifies those four extreme points. An axis-aligned rectangle cannot realize the requested combination, so this labeling is missing from the class's realizable labelings.

The upper-bound proof works for any set of five points. Identify a leftmost point, a rightmost point, a lowest point, and a highest point. Label these four points 1 and label the remaining point 0. An axis-aligned rectangle cannot realize this requested labeling. Therefore, every five-point set has at least one labeling that the rectangle class cannot produce.

Which labeling cannot an axis-aligned rectangle realize, and what geometric feature makes it impossible?

Key point

The proof does not need to identify the same missing labeling for every five-point set. It gives a rule that works for any such set: use the four named extreme points as the positive points and the remaining point as the negative point.

How does proving the four-point lower bound and the five-point obstruction determine the VC-dimension?

Common Reasoning Errors

Common mistake
Testing only one labeling
What it looks like
Finding a rectangle that labels a selected group of points 1 does not establish shattering.
Why it fails
Shattering requires every possible labeling of the point set to be realizable.
Do this instead
Check the complete collection of labelings, including all-0, all-1, and every mixed assignment.
Common mistake
Using only the four-point construction
What it looks like
Showing that four points can be shattered is treated as the complete proof.
Why it fails
That establishes only the lower bound. It does not rule out the possibility that five points or more can also be shattered.
Do this instead
Add the five-point obstruction to establish the upper bound.
Common mistake
Assuming any five-point labeling is impossible
What it looks like
A learner claims that every labeling of five points fails.
Why it fails
The upper-bound argument requires only one unrealizable labeling for each five-point set.
Do this instead
Identify the leftmost, rightmost, lowest, and highest points, label those four 1, and label the remaining point 0.
Common mistake
Counting hypotheses instead of testing label flexibility
What it looks like
The size of the rectangle hypothesis class is used as the main route to the VC-dimension.
Why it fails
The relevant question is how flexibly the class labels finite point sets.
Do this instead
Use shattering and the four-point/five-point boundary.

Check Your Understanding

MEDIUM

Suppose you are given five points and asked whether axis-aligned rectangles shatter them. Describe the labeling you would test first, and explain why failure on that one labeling is enough to reject shattering.

Hints

Identify the leftmost, rightmost, lowest, and highest points.
Give those four points label 1 and the remaining point label 0.
A set is shattered only when every labeling is realizable.

Your attempt (not saved)

Worked example

A complete VC-dimension argument

Use the four-point construction and five-point obstruction to determine the VC-dimension.

1
Lower bound
An appropriate set of four points can be shattered, so the VC-dimension is at least 4.
2
Upper bound
Every set of five points has a labeling that no axis-aligned rectangle can realize, so no five-point set can be shattered.
3
Combine the bounds
The lower bound reaches 4, while the upper bound prevents the value from reaching 5.

Result

The VC-dimension of axis-aligned rectangles is exactly 4.

Exact Boundary

1
Shattering means realizing every possible binary labeling of a point set, not merely one selected labeling.
2
An axis-aligned rectangle is evaluated by the binary labeling it assigns to points in two-dimensional space.
3
An appropriate set of four points can be shattered, giving a lower bound of 4.
4
For any five points, labeling the leftmost, rightmost, lowest, and highest points 1 and the remaining point 0 produces an unrealizable labeling.
5
The VC-dimension of axis-aligned rectangles is exactly 4.

Key Takeaways

Shattering is an all-labelings requirement.
Four points can be shattered by axis-aligned rectangles for an appropriate point arrangement.
Every five-point set has a labeling that axis-aligned rectangles cannot realize.
The four-point lower bound and five-point upper bound meet, establishing VC-dimension 4.

More concepts starting with H