Shattering
The two matching bounds give VCdim(H) = 2 for the class H of intervals over the real numbers.
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…
A Labeling Challenge
Imagine placing a finite collection of points on the real number line. An interval chooses some of those points and leaves the others unchosen. We can record this choice with binary labels: a point inside the interval receives 1, and a point outside the interval receives 0. The central question is how many different labelings an interval class can produce on the same fixed set of points.
What do you think happens?
Can one class of intervals produce every possible binary labeling of two ordered points?
Reveal answer
Yes
Intervals can select neither point, either one of the two points, or both points. Therefore they realize all four labelings of a two-point set.
Intervals as Binary Functions
The class of intervals over the real numbers is a class of binary-valued functions. An interval is determined by endpoints a and b with a less than b. For a chosen interval, each real number receives the value 1 if it lies inside the interval and the value 0 if it lies outside it.
The interval therefore acts as a rule for labeling points. It does not assign arbitrary labels independently to each point. Instead, the labels are controlled by membership in one connected region of the real line: points selected by the interval receive 1, while points not selected receive 0.
Meaning of Shattering
A function class shatters a finite set when it achieves every possible labeling of that set. For a set of n points, every assignment of binary values to those points must be produced by some function in the class.
For two points, the possible labelings are 0, 0; 0, 1; 1, 0; and 1, 1. To prove that intervals shatter the two-point set, we must show that each of these four patterns can be produced by choosing a suitable interval. It is not enough to produce several patterns; shattering requires every possible pattern.
Two Points Can Be Shattered
The set containing 1 and 2
Show that intervals realize every labeling of the set C = {1, 2}.
- 1Labeling 0, 0
Choose an interval that contains neither 1 nor 2.
- 2Labeling 1, 0
Choose an interval around 1 that does not contain 2.
- 3Labeling 0, 1
Choose an interval around 2 that does not contain 1.
- 4Labeling 1, 1
Choose an interval wide enough to contain both 1 and 2.
All four labelings are realized, so the interval class shatters C = {1, 2}.
| Label of 1 | Label of 2 | What the interval must do |
|---|---|---|
| 0 | 0 | Exclude both points |
| 1 | 0 | Include 1 and exclude 2 |
| 0 | 1 | Exclude 1 and include 2 |
| 1 | 1 | Include both points |
The four possible binary labelings of the two-point set {1, 2}.
The Three-Point Obstacle
Now consider any three points and arrange them from left to right as c1, c2, and c3, with c1 less than or equal to c2 and c2 less than or equal to c3. One possible labeling is 1, 0, 1: the two outer points should be inside the interval, while the middle point should be outside.
This labeling cannot be produced by an interval. If an interval reaches c1 and c3, then it must also include the point c2 lying between them. The interval cannot include both outer points while leaving the middle point outside.
From Shattering to VC-Dimension
The VC-dimension of a function class is the size of the largest set shattered by that class. It measures how many different labelings the class can produce on a finite set at its largest completely flexible size.
For intervals, the lower bound comes from the two-point set {1, 2}, which is shattered. Therefore the VC-dimension is at least 2. The upper bound comes from the three-point argument: no set of three points can be shattered because the labeling 1, 0, 1 is impossible. Therefore the VC-dimension cannot be 3 or larger.
The two matching bounds give VCdim(H) = 2 for the class H of intervals over the real numbers.
Common Reasoning Mistakes
Common mistake Showing only some labelings of two points
What it looks likeProducing 0, 0 and 1, 1, then concluding that the set is shattered
Why it failsShattering requires every possible labeling, including 1, 0 and 0, 1.
Do this insteadList all four labelings of two points and account for each one.
Common mistake Treating the labels of three points as independent choices
What it looks likeAssuming an interval can always produce 1, 0, 1 because each point is assigned a binary value
Why it failsThe labels must come from one interval, and an interval that contains both outer points must contain the point between them.
Do this insteadUse the order of the points on the real line when checking whether a labeling is possible.
Common mistake Proving only that one particular three-point set is not shattered
What it looks likeUsing three selected numbers and stopping after showing that their 1, 0, 1 labeling fails
Why it failsTo establish the upper bound, the argument must apply to any three-point set.
Do this insteadWrite the points generally as c1, c2, and c3 in sorted order, then apply the middle-point argument.
Common mistake Confusing a lower bound with the final VC-dimension
What it looks likeFinding a shattered set of two points and immediately declaring the VC-dimension to be 2
Why it failsA shattered two-point set proves only that the VC-dimension is at least 2.
Do this insteadAlso show that no three-point set is shattered, giving the matching upper bound.
Check Your Understanding
Let C be a set of three ordered real points c1, c2, and c3. Explain why the labeling 1, 0, 1 cannot be produced by any interval. Then state what this implies about shattering three-point sets.
Hints
- Identify which points the interval must contain.
- Use the fact that c2 lies between c1 and c3.
- Connect the failed labeling to the definition of shattering.
For the set C = {1, 2}, describe what an interval must do to produce each of the four labelings: 0, 0; 0, 1; 1, 0; and 1, 1. Use your list to justify that intervals shatter C.
Hints
- Interpret 1 as inside the interval.
- Interpret 0 as outside the interval.
- There are four possible binary labelings of two points.
Final Takeaways
- 1Intervals over the real numbers form a class of binary-valued functions: points inside an interval receive 1, and points outside receive 0.
- 2A class shatters a finite set when it realizes every possible binary labeling of that set.
- 3Intervals shatter the two-point set {1, 2} because they can realize all four labelings.
- 4No interval can realize the labeling 1, 0, 1 on three ordered points because the middle point lies between the two outer points.
- 5The largest shattered set has size 2, so the VC-dimension of intervals over the real numbers is 2.
At a glance
- Shattering means realizing every possible labeling of a fixed finite set.
- An interval labels points according to membership: inside means 1 and outside means 0.
- Intervals shatter two points but cannot shatter three points.
- The impossible three-point labeling is 1, 0, 1.
- The VC-dimension of the class of intervals over the real numbers is 2.