Geometric Classifiers
Shattering is an all-labelings requirement, not a one-labeling test.
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?
Choose four points: Use an appropriate four-point set for which the rectangle class has the required flexibility.
Consider every labeling: Check the all-0 assignment, the all-1 assignment, and every mixed assignment of binary labels.
Select 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?
Find the extremes: From the five-point set, identify the leftmost, rightmost, lowest, and highest points.
Assign the requested labels: Give label 1 to those four extreme points and label 0 to the remaining point.
Apply 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 |
Common Reasoning Errors
Showing only one labeling can be realized.
Shattering requires every possible labeling of the point set, not merely one successful labeling.
Fix:
Check the all-0, all-1, and every mixed assignment.Using one successful four-point arrangement as evidence that every five-point set works.
The five-point proof must work for any five-point set and identifies a labeling that each such set fails.
Fix:
Find the leftmost, rightmost, lowest, and highest points, then label those four positive and the remaining point negative.Stopping after proving that four points can be shattered.
The construction proves only that the VC-dimension is at least 4.
Fix:
Also prove the upper bound by showing that no five-point set can be shattered.Counting hypotheses instead of testing labeling flexibility.
The decisive issue is how the class labels finite point sets.
Fix:
Analyze 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
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
- Shattering means realizing every possible binary labeling of one point set.
- An axis-aligned rectangle labels included points 1 and excluded points 0.
- An appropriate set of four points can be shattered, including all-0, all-1, and mixed labelings.
- For any five points, labeling the leftmost, rightmost, lowest, and highest points 1 and the remaining point 0 cannot be realized.
- The VC-dimension of axis-aligned rectangles is exactly 4.
Key Takeaways
- 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.