Shattering and the Growth Function

A linear classifier in 2D and a lookup table that memorizes every training point are both "hypothesis classes," but they clearly don't have the same flexibility — one is constrained to straight-line decision boundaries, the other can fit literally anything. Learning theory needs a precise, countable way to measure that difference, one that doesn't depend on any particular dataset. The tool is shattering: asking, for a specific set of points, whether a hypothesis class can produce every possible labeling of them, and then tracking how that ability scales as the point set grows — the growth function.

The analogy: a lock that can open every combination

Imagine a lock with 3 tumblers, each with 10 positions, so there are $10^3 = 1{,}000$ possible combinations. A "master key" that can be reconfigured to open any one of those 1,000 combinations, on demand, hasn't just memorized one — it can realize every possibility the lock permits. A hypothesis class "shatters" a set of $n$ points the same way: it isn't just capable of getting one particular labeling right, it can produce all $2^n$ possible right/wrong labelings of those points, by choosing a different member of the class for each one. That total flexibility — not accuracy on any one labeling — is what shattering measures.

The formal definition

A hypothesis class $\mathcal{H}$ shatters a set of points $\{x_1, \dots, x_n\}$ if, for every one of the $2^n$ possible ways to assign $\pm 1$ labels to those points, some $h \in \mathcal{H}$ realizes exactly that labeling. The growth function $\Pi_{\mathcal{H}}(n)$ counts the maximum number of distinct labelings $\mathcal{H}$ can produce on any set of $n$ points:

$$\Pi_{\mathcal{H}}(n) = \max_{x_1, \dots, x_n} \left|\{(h(x_1), \dots, h(x_n)) : h \in \mathcal{H}\}\right|$$

In words: pick the $n$ points that give $\mathcal{H}$ its best possible shot, then count how many genuinely different labeling patterns $\mathcal{H}$ can realize on them. If $\Pi_{\mathcal{H}}(n) = 2^n$, the class shatters some set of $n$ points — full flexibility at that size. The growth function can never exceed $2^n$ (there are only $2^n$ labelings to realize in the first place), and the largest $n$ for which $\Pi_{\mathcal{H}}(n) = 2^n$ is the class's VC dimension (The VC Generalization Bound).

Worked example 1: linear classifiers shattering 3 points in 2D

Take 3 points in the plane forming a triangle, not collinear. There are $2^3 = 8$ possible labelings. A linear classifier (a line with everything on one side labeled $+1$) can realize all 8: all-plus, all-minus, and each single point isolated as $+1$ or $-1$ against the other two — every case is achievable by placing a line correctly, since any one point of a non-collinear triangle can be separated from the other two by some line. Three points, no labeling failures: linear classifiers in 2D shatter this set.

Worked example 2: the same class failing on 4 points

Take 4 points in the plane in "convex position" (a quadrilateral, no point inside the triangle of the others). Try labeling the two diagonal corners $+1$ and the other two $-1$ — an X pattern. No single line can separate this XOR-like arrangement: any line putting both $+1$ corners on one side necessarily puts at least one $-1$ corner there too, since the $+1$ points are diagonally opposite. That's one labeling (out of 16) linear classifiers can't realize, so they do not shatter this set of 4 — and no set of 4 points can be shattered by lines in 2D, capping the growth function well below $2^4=16$ from $n=4$ onward.

Try to draw a boundary above that separates diagonal corners of a 4-point square from each other — a single straight decision boundary can't do it, which is exactly the failed labeling in worked example 2.

What this means in practice

Shattering is the mechanism, not just a definition — it's the reason a model class's flexibility can be pinned to a single number (the VC dimension) that appears directly inside generalization bounds. A model class that shatters large point sets easily (deep enough decision trees, high-degree polynomials) can fit almost any training labeling, including the noise, which is exactly the flexibility that risks overfitting once you move past its VC dimension.