Understanding VC Dimension
Counting hypotheses works for a finite class and collapses immediately for the usual ones: there are infinitely many intervals on a line, infinitely many hyperplanes in the plane. What matters for generalisation was never the count, though. It is how many genuinely different behaviours the class can exhibit on the data you actually hold, and that number is finite even when the class is not.
A set of points is shattered by a family when every assignment of labels to those points is realised by some member of the family. The VC dimension is the size of the largest shattered set. The quantifiers repay attention: some set of that size must be shattered, and no set one larger may be. So establishing a value takes two arguments, an example and an impossibility, which is why the figure is found by search rather than recalled.
Intervals on a line make the definition concrete. Two points are easy - an interval can include both, either, or neither. Three points defeat them: including the outer two forces the middle one in, so the labelling (1, 0, 1) is unreachable. Seven of eight labellings are achievable and the dimension is therefore 2, held down by one missing pattern. Axis-aligned rectangles shatter the four points of a diamond and fail on any five, because the extremes in the four directions box in whatever is left.
The payoff is Sauer's lemma: a class of VC dimension d realises at most the sum of binomial coefficients C(n, 0) through C(n, d) labellings on n points, a polynomial rather than 2^n. Since a uniform generalisation bound charges the logarithm of the number of distinct behaviours, that polynomial becomes roughly d log n, small enough that the guarantee keeps tightening as data accumulates. Capacity thereby stops being a count of hypotheses and becomes a count of behaviours.
How to Calculate
VC(H) = max{ k : some S with |S| = k is shattered }, |H|_S ≤ Σ_{i≤d} C(n, i)
where
- H
- the hypothesis class - all intervals, all rectangles, all hyperplanes
- shattered
- every one of the 2^k labellings of S is realised by some member of H
- d
- the VC dimension of H
- |H|_S
- the number of distinct labellings H can produce on a sample of size n
Example of VC Dimension
Thresholds on a line have VC dimension 1 and intervals have 2, both found by enumerating every labelling of every candidate set rather than by inspection. On three points the intervals realise 7 of the 8 labellings, missing exactly (1, 0, 1).
Axis-aligned rectangles shatter the diamond (0,1), (1,0), (2,1), (1,2) - all 16 labellings are realised - and fail once the centre (1,1) is added, since a rectangle holding the four extremes must hold the centre too.
At VC dimension 2 the count of achievable labellings runs 4, 7, 16, 56, 211 for n of 2, 3, 5, 10, 20, against 4, 8, 32, 1024 and 1,048,576 unrestricted. At n = 2 the bound still permits everything; the gap opens immediately afterwards.
Frequently Asked Questions
Is a higher VC dimension worse?
It is more capacity, which costs data rather than being bad in itself. A class too small for the problem cannot represent the truth at all. The dimension tells you what you are paying, so it belongs alongside the bias-variance trade rather than in opposition to it.
Does a finite VC dimension guarantee good performance?
It guarantees that training error approaches true error as data accumulates, and nothing about whether either is small. A class can generalise perfectly and still be uniformly wrong, which is the bias half of the trade.
Why do modern networks generalise with enormous capacity?
Classical VC bounds are worst-case over all distributions and all training sets, and are vacuous at these parameter counts. The explanation is an active research question involving implicit regularisation from the optimiser and margin-based measures, not a flaw in the definition.
The Bottom Line
VC dimension answers a question counting cannot: how much a class of infinitely many hypotheses can actually do on the data in front of it. Establishing a value takes two arguments, an example that shatters and an impossibility one point larger, which is why it is searched for rather than recalled.