Geometric Classifiers
A geometric classifier assigns labels to points by placing a geometric shape in space.
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).
Loading the simulation…
The Boundary Between Four and Five
A geometric classifier assigns labels to points by placing a geometric shape in space. For axis-aligned rectangles, the decisive question is not how many rectangles exist. The important question is how flexibly rectangles can label a finite collection of points. Four points can be shattered, but no set of five points can be shattered. That boundary determines the VC-dimension.
The proof has two parts: construct one set of four points that supports every labeling, then show that every set of five points fails for at least one labeling.
Shattering Means Every Labeling
A point set is shattered by a hypothesis class when every possible assignment of binary labels to the points can be realized by some hypothesis in that class. For axis-aligned rectangles, this means that for each labeling of the selected points, there must be a rectangle that realizes exactly that labeling.
The diagram shows representative stages rather than an exhaustive list. The requirement is stronger than moving between these examples: every possible labeling of the selected points must have its own suitable rectangle.
How Rectangles Assign Labels
An axis-aligned rectangle has its sides aligned with the coordinate directions. Its left, right, top, and bottom boundaries determine the rectangular region. A point receives label 1 when it is included by the chosen rectangle and label 0 when it is outside. To realize a target labeling, the rectangle must include exactly the points marked 1 and exclude every point marked 0.
When checking a proposed rectangle, inspect both sides of the labeling requirement: verify that every positive point is inside and every negative point is outside. Including the positive points alone is not enough.
Why Four Points Can Be Shattered
The lower-bound argument starts by exhibiting an appropriate set of four points. For this set, every possible binary assignment can be realized by selecting a suitable axis-aligned rectangle. The assignments include the case in which all four points receive label 1, the case in which all four receive label 0, and every mixed assignment between those extremes.
Verifying the lower bound
What must be shown to prove that the VC-dimension is at least 4?
- 1Choose four points
Use an appropriate four-point set for which the rectangle class has the required flexibility.
- 2Consider every labeling
Check the all-0 assignment, the all-1 assignment, and every mixed assignment of binary labels.
- 3Select a rectangle
For each labeling, choose an axis-aligned rectangle that includes exactly the points labeled 1.
Because every labeling of this four-point set can be realized, the VC-dimension is at least 4.
Why Five Points Must Fail
The upper-bound argument works for any set of five points. Identify a leftmost point, a rightmost point, a lowest point, and a highest point. Label these four extreme points 1 and label the remaining point 0. An axis-aligned rectangle that contains all four extreme points cannot exclude the remaining point. Therefore, this requested labeling cannot be realized.
Testing a five-point labeling
Can an axis-aligned rectangle label the four extreme points 1 and the remaining point 0?
- 1Find the extremes
From the five-point set, identify the leftmost, rightmost, lowest, and highest points.
- 2Assign the requested labels
Give label 1 to those four extreme points and label 0 to the remaining point.
- 3Apply the rectangle constraint
Any axis-aligned rectangle containing all four extreme points also contains the remaining point, so it cannot produce the requested labels.
At least one labeling fails for every five-point set, so no five-point set is shattered.
From Bounds to VC-Dimension
The four-point construction establishes a lower bound: the VC-dimension is at least 4. The five-point obstruction establishes an upper bound: no set of five points can be shattered, so the VC-dimension cannot be 5 or larger. Since these bounds meet, the VC-dimension of axis-aligned rectangles is exactly 4.
| Question | Four points | Five points |
|---|---|---|
| Can the set be shattered? | Yes, for an appropriate set | No, for every set |
| Proof role | Lower bound | Upper bound |
| Consequence | VC-dimension is at least 4 | VC-dimension is less than 5 |
The lower and upper bounds combine to give the exact value.
Common Reasoning Errors
Common mistake Showing only one labeling can be realized.
What it looks likeFinding a rectangle that includes a selected group of positive points.
Why it failsShattering requires every possible labeling of the point set, not merely one successful labeling.
Do this insteadCheck the all-0, all-1, and every mixed assignment.
Common mistake Using one successful four-point arrangement as evidence that every five-point set works.
What it looks likeAssuming that adding one more point preserves the same flexibility.
Why it failsThe five-point proof must work for any five-point set and identifies a labeling that each such set fails.
Do this insteadFind the leftmost, rightmost, lowest, and highest points, then label those four positive and the remaining point negative.
Common mistake Stopping after proving that four points can be shattered.
What it looks likeConcluding that the VC-dimension is 4 from the lower-bound argument alone.
Why it failsThe construction proves only that the VC-dimension is at least 4.
Do this insteadAlso prove the upper bound by showing that no five-point set can be shattered.
Common mistake Counting hypotheses instead of testing labeling flexibility.
What it looks likeTrying to determine the VC-dimension from the number of rectangles.
Why it failsThe decisive issue is how the class labels finite point sets.
Do this insteadAnalyze which labelings can be realized on a selected collection of points.
Check Your Understanding
Explain in your own words why the four-point argument gives a lower bound while the five-point argument gives an upper bound. In your explanation, state what must be true for a point set to be shattered.
Hints
- Start with the meaning of every possible labeling.
- Ask what one successful four-point construction proves.
- For five points, identify the four extreme points and the remaining point.
What do you think happens?
Suppose an appropriate four-point set can realize every labeling, but every five-point set has one labeling that fails. What is the VC-dimension?
Reveal answer
4
The four-point construction proves the value is at least 4, and the five-point obstruction proves it cannot reach 5.
Key Takeaways
- 1Shattering means realizing every possible binary labeling of one point set.
- 2An axis-aligned rectangle labels included points 1 and excluded points 0.
- 3An appropriate set of four points can be shattered, including all-0, all-1, and mixed labelings.
- 4For any five points, labeling the leftmost, rightmost, lowest, and highest points 1 and the remaining point 0 cannot be realized.
- 5The VC-dimension of axis-aligned rectangles is exactly 4.
At a glance
- Shattering is an all-labelings requirement, not a one-labeling test.
- Four points can be shattered by axis-aligned rectangles for an appropriate point arrangement.
- Every five-point set has a labeling that no axis-aligned rectangle can realize.
- The lower and upper bounds meet at 4, so the VC-dimension is exactly 4.