Shattering
Intervals over the real numbers form a class of binary-valued functions.
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
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}.
Labeling 0, 0: Choose an interval that contains neither 1 nor 2.
Labeling 1, 0: Choose an interval around 1 that does not contain 2.
Labeling 0, 1: Choose an interval around 2 that does not contain 1.
Labeling 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
Showing only some labelings of two points
Shattering requires every possible labeling, including 1, 0 and 0, 1.
Fix:
List all four labelings of two points and account for each one.Treating the labels of three points as independent choices
The labels must come from one interval, and an interval that contains both outer points must contain the point between them.
Fix:
Use the order of the points on the real line when checking whether a labeling is possible.Proving only that one particular three-point set is not shattered
To establish the upper bound, the argument must apply to any three-point set.
Fix:
Write the points generally as c1, c2, and c3 in sorted order, then apply the middle-point argument.Confusing a lower bound with the final VC-dimension
A shattered two-point set proves only that the VC-dimension is at least 2.
Fix:
Also 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
- Intervals over the real numbers form a class of binary-valued functions: points inside an interval receive 1, and points outside receive 0.
- A class shatters a finite set when it realizes every possible binary labeling of that set.
- Intervals shatter the two-point set {1, 2} because they can realize all four labelings.
- No interval can realize the labeling 1, 0, 1 on three ordered points because the middle point lies between the two outer points.
- The largest shattered set has size 2, so the VC-dimension of intervals over the real numbers is 2.
Key Takeaways
- 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.