VC Dimension
How do you measure the capacity of a model — its raw ability to fit arbitrary data — independent of any particular dataset? Counting parameters fails: a single sine-wave classifier has one parameter yet can fit any binary labelling of points on a line. The Vapnik–Chervonenkis (VC) dimension answers the question properly, and it is the quantity that turns "complex models overfit" into a provable bound.
Shattering
Fix a hypothesis class — the set of all classifiers a model can express (e.g. all straight-line decision boundaries in the plane). A set of points is shattered by if, for every way of labelling those points , some hypothesis in realises that labelling exactly.
With points there are possible labellings. Shattering means all are achievable.
Can a straight line shatter these points?
Tip: click any point to flip its label.
A linear classifier shatters a point set if it can realise every +/− labelling. Three points in general position give 8 labellings — all separable. Four points in convex position fail on the diagonal (XOR) labelling, so no line works. The largest set that can always be shattered is the VC dimension: 3 for a 2D linear classifier.
Definition
The VC dimension is the size of the largest point set that can shatter.
Two things must be checked to prove :
- Lower bound (): exhibit one set of points that shatters. You only need a single good configuration — points in "general position."
- Upper bound (): show that no set of points can be shattered. You must rule out every configuration.
The asymmetry matters: shattering is "there exists a set," failing to shatter is "for all sets."
Worked example: 2D linear classifier
The class of linear separators in has .
Three points can be shattered. Place three points in a triangle (not collinear). All labellings are linearly separable — for any split into and , a straight line cleaves them. (Try every labelling in the visualization above with "3 points" selected: 8 / 8.)
Four points cannot. Take any four points. Either three are collinear / one lies inside the triangle of the others, or they sit in convex position. In the convex case, label the two diagonal points and the other two — the XOR labelling. The two points and the two points interleave around the hull, so no single line can separate them. Since some labelling always fails, no 4-point set is shattered. Hence .
The general pattern
A linear classifier in (with bias) has . In 1D that's 2; in 2D, 3; in 3D, 4. The "+1" is the bias term — it adds one degree of freedom, equivalent to lifting the points into one higher dimension.
Capacity is not parameter count
VC dimension and parameter count often agree but need not:
- Linear models: matches the parameter count — the tidy case.
- 1-nearest-neighbor: . It can shatter any finite set (each point is its own nearest neighbor), yet generalizes fine in practice — a hint that VC bounds are worst-case and loose.
- : one real parameter , yet . A single well-chosen frequency realises any labelling of points on the line.
So capacity is about the richness of achievable behaviours, not the number of knobs.
The growth function and Sauer's lemma
Define the growth function as the maximum number of distinct labellings can produce on any points:
It starts at the ceiling (full shattering) but must drop below it once . Sauer's lemma makes the drop precise: for ,
The growth function switches from exponential () to merely polynomial () at the VC dimension. That phase change is exactly what makes generalization possible — there are far fewer "effectively different" hypotheses than the infinite class suggests.
The generalization bound
Bounding the gap between true risk and empirical risk with the polynomial growth function yields the classic VC bound. With probability at least over a sample of size , simultaneously for all :
Read it as the slogan gap :
- More capacity () loosens the bound — complex models need more data.
- More data () tightens it — the gap shrinks like .
- A sample roughly is the order-of-magnitude needed to learn at all.
The bound is loose
VC bounds are distribution-free and worst-case, so they are usually far too pessimistic to use for actual sample-size planning. Deep networks have enormous (often effectively infinite) VC dimension yet generalize — see double descent. The value of VC theory is the qualitative law it proves, not a tight numeric guarantee.
Common mistakes
- "Shattered = can fit this dataset." Shattering requires fitting all labellings of the points, not just the one you happen to have.
- Confusing the quantifiers. needs one shatterable set; needs every -set to fail. People prove the wrong direction by checking a single 4-point set and concluding too much.
- Equating VC dimension with parameter count. 1-NN and the sine classifier break this; capacity is about expressible behaviours.
- Trusting the bound numerically. It is an existence-style worst-case bound; treat it as a scaling law, not a calculator.
Key takeaways
- VC dimension = size of the largest point set a hypothesis class can shatter (realise all labellings).
- A 2D linear classifier has : a triangle is shatterable, but the XOR labelling of any 4 points is not. In general a linear classifier in has .
- Sauer's lemma turns the growth function from exponential to polynomial past the VC dimension — the reason learning is possible.
- The VC bound gives gap : complex models need more data. It is qualitatively right but numerically loose.
Related concepts
- Learning Theory & Generalization: where VC dimension sits among ERM, the generalization gap, and double descent
- Bias-Variance Decomposition: the other lens on capacity vs. error
- The Bias–Variance Tradeoff: capacity dials (, tree depth) seen interactively
- Regularization: Ridge & Lasso: constraining effective capacity to shrink the gap