Examples of VC-Dimension
The central result is that the VC-dimension of H, the class of threshold functions over R, is 1.
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…
Capacity Questions
When studying a class of functions, we want to know how much variation that class can represent. VC-dimension provides a measure of this capacity. The example in this article is the class of threshold functions over the real numbers, denoted by H.
The central result is that the VC-dimension of H, the class of threshold functions over R, is 1.
Threshold Class H
H is the class of threshold functions over the real numbers. A threshold function separates real-valued inputs according to the location of a threshold. The VC-dimension question is therefore: how large a set of real-valued points can H handle in every required labeling pattern?
The important idea is that changing the threshold changes the labeling produced on the selected points. The capacity test does not ask whether one fixed threshold gives every labeling. It asks whether the class H contains enough threshold functions to produce all required labelings for a particular set.
One-Point Test
Testing C = {c1}
Determine what the one-point test shows about H.
- 1Choose one point
Start with the set C = {c1}, which contains one real number.
- 2Vary the threshold
A threshold can be placed so that c1 receives one label, and it can be moved so that c1 receives the other label.
- 3Evaluate the capacity test
Because H can produce both possible labels for this one-point set, the source states that H shatters C.
H shatters the one-point set {c1}.
The one-point test establishes that the capacity of H is at least 1: H can shatter a set containing one real number.
Two-Point Limit
Now consider two ordered points, C = {c1, c2}, with c1 ≤ c2. This test is stricter because H would need to represent every required labeling of both points in order to shatter the set.
A threshold applied to ordered points changes labels in threshold order. It can produce the patterns 00, 01, and 11 under the usual two-label ordering, but it cannot produce the reversed pattern 10: the earlier point would receive one label while the later point receives the opposite label. Since at least one labeling is unavailable, H does not shatter the two-point set.
The two-point test is decisive. H shatters a one-point set, but H does not shatter a two-point set with c1 ≤ c2.
Reading the Result
The one-point and two-point tests place the capacity of H between these two cases. H succeeds on a set of size one and fails on a set of two ordered points. Therefore, the VC-dimension of threshold functions over R is 1.
| Test set | Result for H | Meaning |
|---|---|---|
| C = {c1} | Shattered | H can handle a set of size one in the required way |
| C = {c1, c2}, c1 ≤ c2 | Not shattered | H cannot produce every required labeling of two ordered points |
The two capacity tests that determine the VC-dimension result for H.
Common Misreadings
Common mistake Treating one successful labeling as proof that a set is shattered.
What it looks likeA learner finds one threshold that labels the point c1 in one particular way and concludes that {c1} is shattered.
Why it failsShattering concerns the class's ability to realize the required labelings, not merely one labeling produced by one function.
Do this insteadFor the one-point set, check that changing the threshold can produce both possible labels.
Common mistake Ignoring the order c1 ≤ c2 when analyzing two points.
What it looks likeA learner treats the two points as unrelated and assumes that every pair of labels can be selected independently.
Why it failsThreshold functions act along the ordered real line, so the threshold creates an ordered change in labels.
Do this insteadKeep the order visible and check whether the labeling 10 can be produced. It cannot in this threshold example.
Common mistake Concluding that the VC-dimension is 2 because H can label two points in some ways.
What it looks likeThe patterns 00, 01, and 11 are available, so the learner counts the two points as shattered.
Why it failsA two-point set must support every required labeling, not merely several of them.
Do this insteadNotice the missing pattern 10. Because one labeling is unavailable, the two-point set is not shattered.
Check Your Understanding
Explain in your own words why the one-point set {c1} passes the shattering test while the ordered two-point set {c1, c2}, with c1 ≤ c2, fails it.
Hints
- For one point, ask whether changing the threshold can produce both possible labels.
- For two ordered points, identify the labeling that a threshold cannot produce.
- Use the successful one-point test and failed two-point test to state the VC-dimension.
What do you think happens?
What is the VC-dimension of the threshold-function class H over R?
Reveal answer
1
H shatters a one-point set but does not shatter a two-point ordered set.
Key Takeaways
- 1VC-dimension measures the capacity of a class of functions.
- 2The class of threshold functions over the real numbers is denoted by H.
- 3H shatters the one-point set {c1}.
- 4H does not shatter the ordered two-point set {c1, c2} with c1 ≤ c2.
- 5The VC-dimension of threshold functions over R is 1.
At a glance
- VC-dimension is a measure of the capacity of a class of functions.
- Threshold functions over R form the class H.
- H can produce both labels for a one-point set, so it shatters that set.
- For two ordered points, H cannot produce every labeling, so it does not shatter the set.
- The VC-dimension of H is 1.