Generalization in Machine Learning
Shattering means realizing every possible 0/1 labeling on a chosen set.
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.
List the possible labelings: Because each of the two points can receive label 0 or 1, inspect the labelings 00, 01, 10, and 11.
Search within H: For each labeling, ask whether some hypothesis in H gives x1 and x2 exactly that pair of labels.
Apply 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.
Treating one shattered set as proof of the exact VC-dimension.
A shattered set of size three proves only that the VC-dimension is at least three. A larger shattered set may still exist.
Fix:
To establish the exact VC-dimension, also rule out shattered sets of every larger relevant size.Checking only one labeling of a chosen set.
Shattering requires every possible 0/1 labeling on the chosen set, not merely one particular labeling.
Fix:
Enumerate the possible labelings and check each one.Confusing a set with its size.
A set can be shattered, while VC-dimension is a numerical maximum over shattered sets.
Fix:
Use 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.
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)?
Use the definition of shattering: H can realize every possible 0/1 labeling on the four points in C.
Translate to a capacity statement: Because a set of size four is shattered, the largest shattered-set size cannot be smaller than four.
Avoid 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
- A hypothesis class shatters a chosen set when it realizes every possible 0/1 labeling of that set.
- A single missing labeling means the chosen set is not shattered.
- VCdim(H) is the maximal size of a set shattered by H.
- Finding a shattered set of size three or four establishes only a lower bound until larger sets are ruled out.
- In PAC learning, the capacity of H matters because the class's realizable labelings describe how much freedom it has under relevant distributions.
Key Takeaways
- 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.