Understanding VC-Dimension in Machine Learning
VC-dimension is a measure of the capacity of a class of functions.
Capacity Before Counting
A class of functions can represent some label patterns but not others. VC-dimension gives us a way to measure that representational capacity. In this article, we examine threshold functions over the real numbers, written as the class H, and test how many points H can label in every possible way.
The central question is not whether H can label one particular collection of points. It is whether H can realize every possible binary labeling of that collection.
Thresholds on the Real Line
A threshold function places a dividing point on the ordered real line. Points on the two sides of that threshold receive different binary labels. Moving the threshold changes which points fall on each side. Because the real numbers are ordered, the labels produced on a list of points from left to right must follow the order imposed by the threshold: one side receives one label and the other side receives the other label.
H is the class of threshold functions over the real numbers. The VC-dimension of H is determined by the largest size of a set that H can shatter.
The One-Point Test
Begin with a set containing one real number, written as C = {c1}. A one-point set has only two possible binary labelings: the point can receive label 0, or it can receive label 1. H shatters this set because an appropriate threshold can be placed on either side of c1, producing each of those two labelings.
Testing C = {c1}
Determine whether H can realize every binary labeling of the one-point set C = {c1}.
List the labelings: There are two possible labels for the single point: 0 and 1.
Move the threshold: Place the threshold on one side of c1 to obtain one label, then place it on the other side to obtain the other label.
Check the definition: Both possible labelings are realizable by members of H.
H shatters the one-point set C = {c1}.
The Two-Point Test
Now consider two ordered points, C = {c1, c2}, with c1 ≤ c2. To shatter this set, H would need to realize every binary labeling of these two points. In particular, it would need to realize the reversed labeling in which c1 receives 1 and c2 receives 0.
A single threshold cannot assign label 1 to the left point and label 0 to the right point. Since c1 comes before c2, placing the threshold so that c1 is on the label-1 side also places c2 on that same side or requires the labels to change in the opposite order. The labeling 1, 0 is therefore unavailable. Because at least one required labeling is missing, H does not shatter the two-point set.
What do you think happens?
For ordered points c1 ≤ c2, can a threshold produce the labeling c1 = 1 and c2 = 0?
Reveal answer
Answer: No, the reversed labeling is not possible.
A threshold divides the ordered line into two regions, so the labels cannot reverse from 1 at the earlier point to 0 at the later point.
From Tests to Dimension
| Set tested | What H must realize | Result |
|---|---|---|
| One point, C = {c1} | Both possible labels for one point | H shatters the set |
| Two ordered points, C = {c1, c2}, c1 ≤ c2 | Every binary labeling, including 1, 0 | H does not shatter the set |
The one-point test succeeds, while the two-point test fails. Therefore, the largest set size established by these tests is one. The VC-dimension of the threshold-function class H over the real numbers is 1.
VC-dimension measures the capacity of a function class by asking for the largest size of a set that the class can shatter.
Mistakes in Shattering Tests
Checking only one convenient labeling
Shattering requires every binary labeling of the set, not merely one or several successful labelings.
Fix:
For two points, check all required labelings and pay special attention to the reversed labeling 1, 0.Ignoring the order c1 ≤ c2
Threshold functions act on the ordered real line, and the order determines which label transitions are possible.
Fix:
Write the points in order before examining the labelings.Confusing the number of points tested with the VC-dimension
A tested set size is not automatically a successful shattering size.
Fix:
The dimension is the largest size for which the set is shattered. Here, one point succeeds and two points do not.
A Reliable Checking Routine
- Name the function class being tested. For this topic, it is H, the class of threshold functions over the real numbers.
- Choose a set of ordered points.
- List the binary labelings that must be realized.
- Ask whether one member of H can realize each labeling.
- Find the largest set size for which every labeling is realizable.
Check Your Understanding
Suppose C contains one real point. Explain why the two possible binary labelings of that point can be produced by changing the side of the point on which the threshold is placed. Then explain why the same reasoning cannot realize the reversed labeling for two ordered points.
Hints
- Start by listing the two possible labels for one point.
- For two points, write c1 ≤ c2 and inspect the labeling 1, 0.
- Remember that shattering requires every labeling.
Key Takeaways
- VC-dimension measures the capacity of a class of functions.
- H denotes the class of threshold functions over the real numbers.
- H shatters a one-point set because both possible labels for that point can be produced.
- H does not shatter two ordered points because the reversed labeling 1, 0 cannot be produced by one threshold.
- The VC-dimension of threshold functions over the real numbers is 1.
Key Takeaways
- VC-dimension measures the capacity of a function class through shattering.
- Threshold functions over the real numbers form the class H.
- H can realize both labelings of a one-point set.
- H cannot realize every labeling of two ordered points, because 1, 0 is impossible.
- Therefore, the VC-dimension of H is 1.