Why count patterns instead of models?
A large collection of classifiers can still behave in only a few different ways on a particular sample. For example, moving a threshold along the real line gives infinitely many functions, but on distinct ordered points it produces only label sequences. Generalization depends on the possible errors on observed points, not simply on the number of parameter values. We make this idea precise by counting restrictions to finite sets.
Definition 17.1.1
(Shattering and growth)
Let be a nonempty set of functions from to . A finite set is shattered if every function is the restriction of some member of . The VC dimension is the largest size of a shattered set, or infinity if there is no finite upper bound. Define as the maximum number of distinct restrictions to any distinct inputs, with . If the domain has fewer than points, take the maximum over sets of at most points. Repeated points cannot increase this count.
A failure to shatter one particular set says little about another set. A dimension claim must rule out every larger set, as well as exhibit a set of the claimed size. Labels in the training sample need not be realizable by the class.
The combinatorial theorem
Theorem 17.1.2
(Sauer–Shelah bound)
If has finite VC dimension , then for every integer ,
where for . When , this improves on the trivial bound ; for fixed , it grows polynomially in .
Proof
(Induction by deleting one point)
It suffices to prove the following statement for a family of subsets of an -element set : if no -element set is shattered, then . A subset represents the points assigned label one. Use induction on , simultaneously for all , with immediate. Choose and let . Split the possible restrictions into
Put and . Counting each original set by whether it contains gives . A set shattered by is shattered by , so has dimension at most . If shattered a -element subset of , then for every labeling of , both its extension with absent and its extension with present occur in . Thus would shatter . For , has dimension at most ; for , the same argument shows that is empty and contributes zero. Applying induction to the two families and Pascal's identity gives
This proves the claim and therefore the theorem.
Proof X-ray
Why the intersection loses one dimension
The proof has one counting identity and one structural observation. The identity is bookkeeping: a pattern on that extends in two ways is counted once in the union and once more in the intersection. The structural observation is the non-obvious step. A pattern in the intersection can be realized with either label at the removed point. If the intersection already supplied all patterns on other points, this extra freedom would shatter points. The union merely remembers possible patterns; the intersection remembers patterns with two extensions.
The hypothesis "no -set is shattered" is used twice, at different levels: directly for , and through the extension argument for , where it drops to . That is why the induction must run over all at once. It closes because Pascal's identity matches the two sums term by term.
From counting to a learning guarantee
Let be a positive integer and be independent identically distributed, , and let and . For the next result assume is finite and its classifiers are measurable. This avoids an extra measurability question about a supremum over an infinite family; the counting lemma itself needs no finiteness of .
Theorem 17.1.3
(A finite-class VC uniform bound)
For with ,
Consequently, if minimizes empirical error in , then on the complementary event . The bound can exceed one, in which case one may replace it by one.
Proof
(Ghost sample, random swaps, and a union over patterns)
Introduce an independent ghost sample of size , with empirical error . If the displayed supremum exceeds , select a witnessing classifier using a fixed ordering of the finite class. Conditional on the first sample, its ghost mean has variance at most , so Chebyshev gives probability at least that it is within of its true error. Therefore the probability of the original event is at most twice the probability that some has .
Swap the two observations in each paired position independently with probability one half. The joint law is unchanged. Conditional on all observations, a classifier determines at most one error pattern for each of at most prediction patterns; duplicate inputs only reduce this number. For a fixed pattern, the swapped difference is , where independent signs are equally likely and are fixed. Hoeffding's inequality yields probability at most that its absolute value exceeds . A union bound over patterns and the factor two from the ghost step prove the result.
On the complementary event, compare an empirical minimizer with a population-risk minimizer in the finite class:
No assumption of zero training error is needed.
Worked examples and a counterexample
Worked example 17.1.4
(Thresholds on a line)
Let for . One point is shattered by choosing thresholds on either side. Two ordered points cannot receive labels , so the VC dimension is one. On distinct sorted points, the positive labels form a suffix; all suffixes occur. Thus , exactly the theorem's . For any finite selection of these thresholds, the learning bound becomes under its stated condition.
Worked example 17.1.5
(Intervals have two degrees of shattering)
For classifiers that label a closed interval positive and everything else negative, any two distinct points can receive all four patterns: choose an interval containing neither, either point alone, or both. Three ordered points cannot receive , since an interval containing the endpoints contains the middle. Thus . This argument uses geometry, not a count of endpoints alone.
Worked example 17.1.6
(When the bound becomes informative, and the case )
For a finite threshold class take and . Then and , so the bound is . With probability at least , every empirical error is within of its risk, and an empirical minimizer is within of the best threshold in the class. Compare in the exercises below, where the same formula exceeds one.
At the other extreme, means that no single point is shattered, so all members agree at every input: consists of one function and . The theorem then gives , whereas Hoeffding for one fixed classifier gives . The ghost-sample route is not designed for sharp constants.
Counterexample mode
A parameter count is not a proof of VC dimension
A class of all subsets of an infinite domain shatters every finite set, so its VC dimension is infinite. On any fixed sample it still has only finitely many restrictions, namely . Finite pattern count on each sample alone therefore does not give the polynomial growth required by the theorem. Likewise, the existence of a low-dimensional parameterization by itself does not establish a VC bound without assumptions on how parameters generate classifiers.
A dimension statement has two halves with different quantifiers, and most errors in computing a VC dimension come from mixing them.
Common mistake
(Using one bad configuration to bound the dimension)
To prove it suffices to exhibit one shattered set of size . To prove one must show that every set of points fails. For intervals, two distinct points always give all four patterns, and every three ordered points miss ; both halves are needed for . Showing that one particular set of points is not shattered proves no upper bound: for half-planes in the plane, three collinear points cannot receive the pattern because a half-plane is convex, yet three points not on a line are shattered, so the VC dimension of half-planes is at least three.
Common mistake
(Counting patterns on points instead of )
The symmetrization step conditions on the original and ghost samples together, so the union bound runs over patterns on points. Writing in place of is not justified by this proof. For thresholds it would replace by ; for larger the factor between the two counts can be close to .
Practice with solutions
Quick check
(For consisting of the constant zero and constant one classifiers, find its VC dimension and growth function on a domain with at least points for .)
Solution · Answer
One point is shattered, but on two points only and occur. Hence and for ; .
Quick check
(A family on four points has VC dimension at most one. What is the greatest number of patterns allowed by Sauer–Shelah? Give a family attaining it.)
Solution · Answer
At most . The empty set and four singleton sets form such a family; no pair is shattered because its two-point positive pattern is missing.
Quick check
(Assume , , and a finite threshold class. Evaluate the bound without rounding.)
Solution · Answer
The condition is , and the bound is , which exceeds one. It is valid but uninformative; a probability bound of one is sharper here.
Quick check
(If the empirical error minimizer has training error zero, does the theorem imply population error zero?)
Solution · Answer
No. On the uniform event it only implies ; outside that event no such assertion is made. For instance, a classifier can miss a positive-probability region absent from the sample.