Classes of Functions
Intervals over the real numbers form a class of binary-valued functions.
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…
From Intervals to Labels
An interval over the real numbers can be viewed as a binary-valued function. Choose an interval with endpoints a and b, where a is less than b. Every real-number input receives a label according to membership: a point inside the chosen interval receives 1, and a point outside it receives 0. The collection of all such interval functions is the class we will study.
Meaning of Shattering
A finite set is shattered by a class of functions when the class achieves every possible labeling of that set. For a set of n points, each point can receive either 0 or 1, so there are 2^n possible binary labelings. To prove shattering, we must show that every one of those labelings is produced by at least one function in the class.
The important word in the definition is every. Producing several labelings is not enough. A set is shattered only when no possible binary labeling is missing.
Two Points Fully Controlled
Consider the set C = {1, 2}. There are four possible binary labelings of these two points: (0, 0), (1, 0), (0, 1), and (1, 1). The interval class can realize all four. Choose an interval that contains neither point for (0, 0), an interval that contains only the first point for (1, 0), an interval that contains only the second point for (0, 1), and an interval that contains both points for (1, 1). Therefore, the class of intervals shatters {1, 2}.
Checking a Two-Point Set
Determine whether the interval class shatters C = {1, 2}.
- 1List the labelings
The two points have four possible binary labelings: (0, 0), (1, 0), (0, 1), and (1, 1).
- 2Match intervals to labelings
Use an interval containing neither point, only the first point, only the second point, or both points, respectively.
- 3Apply the definition
Because every possible labeling has an interval witness, the set is shattered.
The interval class shatters C = {1, 2}.
Three Points Reveal the Limit
Now take any three real points and arrange them in order as c1 less than or equal to c2 less than or equal to c3. Consider the labeling (1, 0, 1). It asks for an interval that contains the first and third points but excludes the middle point. That is impossible: an interval that reaches both outer points must also contain the point lying between them. Thus, the interval class fails to realize at least one labeling on every three-point set.
Reading the VC-Dimension
The VC-dimension of a function class is the size of the largest set that the class shatters. For intervals, the two-point result gives a lower bound: the VC-dimension is at least 2. The three-point obstruction gives the matching upper bound: no set of size 3 is shattered, so the VC-dimension cannot be 3 or larger. Together, these facts establish VCdim(H) = 2 for the class H of intervals over the real numbers.
When determining a VC-dimension, separate the proof into two tasks: demonstrate one set of a given size that is shattered, then show that no set of the next larger size can be shattered. These matching bounds identify the exact value.
Common Reasoning Errors
Common mistake Confusing some labelings with every labeling.
What it looks likeAn interval may produce several different labelings on a set.
Why it failsShattering requires every possible labeling, not merely multiple labelings.
Do this insteadList all binary labelings and verify that each one has an interval witness.
Common mistake Ignoring the order of three real points.
What it looks likeTreating (1, 0, 1) as an arbitrary symbolic pattern.
Why it failsThe impossibility depends on the middle point lying between the two outer points.
Do this insteadWrite the points in order as c1, c2, c3 before analyzing the labeling.
Common mistake Thinking that failure on one particular three-point set is sufficient by itself.
What it looks likeShowing only that one chosen triple is not shattered.
Why it failsTo rule out VC-dimension 3, the argument must apply to every three-point set.
Do this insteadUse the ordering argument for an arbitrary three-point set.
Common mistake Stopping after proving that two points can be shattered.
What it looks likeConcluding that the VC-dimension is 2 from the two-point construction alone.
Why it failsThe two-point construction gives only a lower bound.
Do this insteadAlso prove that no three-point set can be shattered.
Quick Check
Suppose three real points are ordered as p1 less than p2 less than p3. Explain in one or two sentences why no interval can assign the labels (1, 0, 1) to these points. Then state what this tells you about the VC-dimension of the interval class.
Hints
- Focus on what must happen to the point p2 if an interval contains both p1 and p3.
- Combine the two-point shattering result with the three-point impossibility result.
- 1Intervals label real-number points by membership: inside receives 1 and outside receives 0. Shattering means realizing every possible binary labeling of a finite set. Intervals shatter two points because all four two-point labelings can be realized. They cannot shatter three points because the ordered labeling (1, 0, 1) would require an interval to contain two outer points while excluding the point between them. Therefore, the VC-dimension of the class of intervals over the real numbers is 2.
Key Takeaways
- Intervals over the real numbers form a class of binary-valued functions based on membership.
- A set is shattered when every possible binary labeling of that set is realized by some function in the class.
- The interval class shatters the two-point set {1, 2}.
- No three-point set can be shattered because the labeling (1, 0, 1) is impossible for an interval.
- The VC-dimension of the interval class is 2.