The capacity of a model, counted not in parameters but in freedom: the largest set of points the model can label every possible way at all. For half-planes in the plane the number is 3 — a triangle can be split into +/− all 8 ways, but no four points can. Down the center, data flows: a point set and a labeling go in, the shattering engine decides realizable-or-not, the capacity comes out. The blue team builds and defends it; the red team tries to break it.
source V. N. Vapnik & A. Ya. Chervonenkis, On the Uniform Convergence of Relative Frequencies of Events to Their Probabilities (1971), Theory Probab. Appl. 16(2):264 — epubs.siam.org/doi/10.1137/1116025. Rendered, not quoted.
A hypothesis class H shatters a set S of points if for every one of the 2|S| labelings, some h ∈ H realizes it. The VC dimension is the size of the largest set H shatters.
For half-planes in R2 (a hypothesis is w·x + b ≥ 0 → +), a labeling is realizable iff the + points and − points are linearly separable — iff their convex hulls are disjoint. The engine decides that by the separating-axis test over integer coordinates: exact, no floats-that-drift.
VC ≥ 3: a triangle is shattered (all 8 labelings realizable). VC ≤ 3: any 4 points admit a partition whose hulls meet — Radon's theorem (1921) not enumerated in-engine; the engine checks the two canonical quadruples exactly. So VC = 3.
Empirical risk minimization picks the hypothesis that fits the sample best — but nothing there says whether fitting the sample means anything for the unseen. The missing ingredient is capacity.
VC dimension is that number, and it is the hinge of PAC learning: a class with finite VC is learnable, its generalization gap bounded by √(d/n)-style terms; infinite VC and the sample can be memorized without ever generalizing. Each sphere is the next one's premise.
The blue team's live check: recompute the realizable-labeling count for all four configurations and confirm them against the known truth (8 / 14 / 14 / 3). If red tampers, this badge is where it shows.
Two things go in: a finite point set and a labeling (a +/− assignment to each point). The class asked to realize it is the half-planes. Four configurations:
| set | points | 2n |
|---|---|---|
| triangle | 3, general position | 8 |
| square | 4, convex position | 16 |
| triangle+inside | 4, one interior | 16 |
| line | 2, threshold class | 4 |
Shattered means every labeling in the 2n column is realizable. That is the whole game — and it is what you feed the panel below.
Every labeling — click a row to draw its separator (or see that none exists):
| labeling | realizable? |
|---|
Realizability is computed live from convex-hull disjointness (or, for the line, a one-sided threshold), never looked up.
What the machine proves: half-planes in R2 have VC dimension = 3. The triangle is shattered (8/8 = 23); no quadruple is (14/16 for both the square and the triangle-plus-inside — exactly two labelings unrealizable); a one-sided threshold on the line has VC = 1 (shatters 1 point, only 3/4 labelings of 2 points).
The blue team's witness (left) confirms these counts live; the red team (right) tries to make them wrong.
And capacity is a property of the class, not any one hypothesis: it tells you how much the class could fit, not what your fit will do on this data.
“VC dimension = the number of parameters.” Cut. The one-parameter family sin(αx) has infinite VC; parameters and capacity are not the same quantity.
“Four corners, four points — half-planes in the plane have VC 4.” Cut. The corners of a square already fail: the diagonal (XOR) split is not linearly separable. VC = 3, and Radon proves no quadruple survives.
“High VC is bad.” Kept, corrected. Capacity only bounds the generalization gap; you need enough of it to fit the signal. The craft is matching capacity to sample size — structural risk minimization.
The red team's move: claim VC = 4 for planar half-planes — force the engine to report every 4-point labeling as realizable, pretending the square is shattered (16/16). The blue team's witness (window 7) is watching.
Claim VC = 4 and the engine calls the XOR corner-split realizable — but no half-plane realizes it (the diagonals cross). The witness recomputes, the counts disagree with the known truth, and it turns red. Nothing is faked; the attack is real and it is caught.