Examples of VC-Dimension
VC-dimension is a measure of the capacity of a class of functions.
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.
Choose one point: Start with the set C = {c1}, which contains one real number.
Vary 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.
Evaluate 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 |
Common Misreadings
Treating one successful labeling as proof that a set is shattered.
Shattering concerns the class's ability to realize the required labelings, not merely one labeling produced by one function.
Fix:
For the one-point set, check that changing the threshold can produce both possible labels.Ignoring the order c1 ≤ c2 when analyzing two points.
Threshold functions act along the ordered real line, so the threshold creates an ordered change in labels.
Fix:
Keep the order visible and check whether the labeling 10 can be produced. It cannot in this threshold example.Concluding that the VC-dimension is 2 because H can label two points in some ways.
A two-point set must support every required labeling, not merely several of them.
Fix:
Notice 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
Answer: 1
H shatters a one-point set but does not shatter a two-point ordered set.
Key Takeaways
- VC-dimension measures the capacity of a class of functions.
- The class of threshold functions over the real numbers is denoted by H.
- H shatters the one-point set {c1}.
- H does not shatter the ordered two-point set {c1, c2} with c1 ≤ c2.
- The VC-dimension of threshold functions over R is 1.
Key Takeaways
- 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.