Generalization in Machine Learning
A learning algorithm does not consider every imaginable rule equally.
Why Capacity Matters
A learning algorithm does not consider every imaginable rule equally. It works with a hypothesis class H: the collection of hypotheses that the learner is allowed to consider. The size of this collection is not measured only by counting hypotheses. A more useful question is how freely H can assign binary labels to a chosen collection of input points. VC-dimension turns that freedom into a measure of hypothesis-class capacity.
Tracing Every Labeling
Start with a finite set C contained in the input space X. Each point in C can receive one of two labels: 0 or 1. The hypothesis class H shatters C when H can realize every possible labeling of the points in C. The requirement is therefore collective: one hypothesis in H must realize each labeling, although different labelings may be realized by different hypotheses.
Checking a two-point set
Suppose the chosen set is C = {x1, x2}. Determine what must be checked before calling C shattered.
- 1List the possible labelings
Because each of the two points can receive label 0 or 1, inspect the labelings 00, 01, 10, and 11.
- 2Search within H
For each labeling, ask whether some hypothesis in H gives x1 and x2 exactly that pair of labels.
- 3Apply the definition
If all four labelings are realized by hypotheses in H, then H shatters C. If even one labeling is impossible, C is not shattered.
The set C is shattered exactly when every possible binary labeling of its points is realizable by H.
From a Set to a Dimension
The VC-dimension of H, written VCdim(H), is the maximal size of a set shattered by H. It records the size of the largest collection of points on which H can realize every possible binary labeling.
Common mistake Treating one shattered set as proof of the exact VC-dimension.
What it looks likeFinding a shattered set of size three and immediately concluding that VCdim(H) equals three.
Why it failsA shattered set of size three proves only that the VC-dimension is at least three. A larger shattered set may still exist.
Do this insteadTo establish the exact VC-dimension, also rule out shattered sets of every larger relevant size.
Common mistake Checking only one labeling of a chosen set.
What it looks likeShowing that H can realize the labeling 01 on two points.
Why it failsShattering requires every possible 0/1 labeling on the chosen set, not merely one particular labeling.
Do this insteadEnumerate the possible labelings and check each one.
Common mistake Confusing a set with its size.
What it looks likeSaying that a set of three points is the VC-dimension.
Why it failsA set can be shattered, while VC-dimension is a numerical maximum over shattered sets.
Do this insteadUse set language for the particular collection of points and VC-dimension language for the largest size.
When Shattering Fails
Consider a generated toy class H containing two hypotheses evaluated on the chosen set C = {x1, x2}. Let one hypothesis produce labeling 00 and the other produce labeling 11. The class can realize those two labelings, but it cannot realize 01 or 10. Therefore C is not shattered by H. The failure of even one required labeling is enough to prevent shattering.
Chosen set C = {x1, x2}
Available labelings from H = {00, 11}The class realizes only two labelings on C.
Required labelings = {00, 01, 10, 11}
Missing labelings = {01, 10}
Conclusion: C is not shatteredThe comparison with all required labelings reveals that C is not shattered.
Capacity and PAC Learning
VC-dimension measures capacity through the largest collection of points on which a hypothesis class can realize every binary labeling. This capacity matters in the PAC framework because the class determines how much freedom the learner has when choosing rules. In PAC learnability, the adversary is restricted to distributions for which some hypothesis in H achieves zero risk. When a distribution is concentrated on a set C, the behavior of H on C becomes central: the labelings that H can realize describe the class's freedom in that situation.
A Practical Check
A hypothesis class H shatters a set C of four points. What does this fact establish, and what does it not establish?
Hints
- Separate the statement about this particular set from the statement about the maximum size of any shattered set.
- Ask whether larger shattered sets have been ruled out.
Interpreting a shattered four-point set
H shatters a particular set C containing four points. What can be concluded about VCdim(H)?
- 1Use the definition of shattering
H can realize every possible 0/1 labeling on the four points in C.
- 2Translate to a capacity statement
Because a set of size four is shattered, the largest shattered-set size cannot be smaller than four.
- 3Avoid overclaiming
No conclusion that four is the exact VC-dimension is justified unless larger shattered sets have been ruled out.
VCdim(H) is at least four. It equals four only if no set of size greater than four can be shattered by H.
Key Takeaways
- 1A hypothesis class shatters a chosen set when it realizes every possible 0/1 labeling of that set.
- 2A single missing labeling means the chosen set is not shattered.
- 3
VCdim(H)is the maximal size of a set shattered by H. - 4Finding a shattered set of size three or four establishes only a lower bound until larger sets are ruled out.
- 5In PAC learning, the capacity of H matters because the class's realizable labelings describe how much freedom it has under relevant distributions.
At a glance
- Shattering concerns every possible binary labeling on one chosen set.
- VC-dimension records the largest size of any set that the hypothesis class can shatter.
- A shattered set of a known size gives a lower bound on VC-dimension, not necessarily the exact value.
- Hypothesis-class capacity is central to PAC analysis because it describes the class's freedom to realize labelings under distributions.