Sauer-Shelah lemma (source code)

= Sauer-Shelah lemma
{c}
{wiki=Sauer–Shelah_lemma}

If a binary <hypothesis class> $\mathcal H$ has finite <VC dimension> $D$, then its <shattering coefficient> satisfies
$$
s(\mathcal H,n)\le\sum_{j=0}^{\min(D,n)}\binom nj.
$$
The <binomial coefficients> bound how many different label patterns the class can realize. For fixed $D$, their sum grows polynomially in $n$, although the number of unrestricted binary patterns is $2^n$.

Here is an inductive counting proof on a fixed sample. Partition the realized patterns according to their last label, and let $F_0,F_1$ be the corresponding sets of patterns on the first $n-1$ points. Put $P=F_0\cup F_1$ and $Q=F_0\cap F_1$. The original number of patterns is $|P|+|Q|$.

The class $P$ has <VC dimension> at most $D$. The class $Q$ has <VC dimension> at most $D-1$: if $Q$ <shattered> $D$ earlier points, both last labels would extend every pattern there, so the original class would have a <shattered> set of $D+1$ points. Applying <mathematical induction> and <Pascal's identity> gives the displayed <sum>. The base cases are $n=0$, with at most one empty pattern, and $D=0$, with at most one realized pattern.