Content
Summary
The VC-dimension is a combinatorial measure of a hypothesis class's capacity, defined as the size of the largest set it can shatter. It demonstrates that infinite hypothesis classes can be PAC learnable if their VC-dimension is finite, linking learnability to uniform convergence.
Intuition
Think of the VC-dimension as a measure of how 'flexible' or complex a hypothesis class is. A class shatters a set of points if it can fit any possible binary labeling of those points. If a class can shatter a large set, it is very complex and might overfit; if it cannot shatter even small sets, it is simple. The VC-dimension is the maximum number of points that can be shattered. Crucially, this concept allows us to learn from infinite classes, like threshold functions, provided they have a finite VC-dimension, which bounds their complexity and ensures learnability.
Key equations
The restriction of hypothesis class H to a finite set C, representing all possible labelings H can produce on C.
The condition for shattering: the number of distinct labelings produced by H on C equals the total number of possible binary labelings.
The definition of a threshold function, outputting 1 if x is less than threshold a, and 0 otherwise.
Derivation
- Define the restriction of a hypothesis class H to a finite set C as the set of all labelings H can produce on C.
- A set C is shattered by H if the restriction H_C contains all possible binary labelings, i.e., |H_C| = 2^{|C|}.
- The VC-dimension is the size of the largest set that H can shatter.
- Apply this to threshold functions: they shatter a single point (size 1) but cannot shatter two points (size 2) because they cannot produce the (0, 1) labeling.
- Conclude that the VC-dimension of threshold functions is 1, proving an infinite class can have finite VC-dimension and thus be PAC learnable.
Worked example
Determine if the class of threshold functions H = {h_a: a in R} where h_a(x) = 1[x < a] shatters a set C = {c1, c2} with c1 < c2.
- Identify the required labelings for shattering: (0,0), (0,1), (1,0), (1,1).
- Check if (0,0) is possible: Choose a <= c1. Then h_a(c1)=0 and h_a(c2)=0. Possible.
- Check if (1,1) is possible: Choose a > c2. Then h_a(c1)=1 and h_a(c2)=1. Possible.
- Check if (1,0) is possible: Choose a such that c1 < a <= c2. Then h_a(c1)=1 and h_a(c2)=0. Possible.
- Check if (0,1) is possible: We need h_a(c1)=0 and h_a(c2)=1. This requires a <= c1 and a > c2. Since c1 < c2, no such a exists.
Answer The class does not shatter C because it cannot produce the labeling (0,1). Thus, the VC-dimension is not 2.
Common mistakes
- Assuming a hypothesis class must be finite to be learnable; infinite classes like thresholds are learnable if they have finite VC-dimension.
- Confusing the restriction H_C with the original class H; H_C only considers labelings on the specific finite set C.
- Thinking any infinite class can shatter any set; shattering depends on the specific structure of H, as thresholds cannot shatter sets of size 2.