Shattering Coefficient

Definition

$\mathcal{N}(\mathcal{F},n)=\max \{|{\mathcal{F}}_{X_1,\dots ,X_n}|:X_1,\dots ,X_n\in \mathcal{X}\}$, the maximal number of distinct labelings of $n$ points. As a function of $n$ it is the growth function $S_{\mathcal{F}}(n)$ (also ${\Pi }_{\mathcal{F}}(n)$). $\mathcal{F}$ shatters a set if it realizes all $2^n$ labelings on it.

Formula

Rules for any growth function:

$$\mathcal{N}(\mathcal{F},0)=1,1\le \mathcal{N}(\mathcal{F},n)\le 2^n,\mathcal{N}(\mathcal{F},n)\le \mathcal{N}(\mathcal{F},n+1)\le 2\mathcal{N}(\mathcal{F},n),\mathcal{N}(\mathcal{F},n)\le \sum _{i=0}^d\left(\genfrac{}{}{0ex}{}{n}{i}\right)$$

Examples on $\mathbb{R}$: half-lines $n+1$, two-sided half-lines $2n$, intervals $1+n+\left(\genfrac{}{}{0ex}{}{n}{2}\right)$. It replaces the number of functions $m$ in the finite-class bound (Theorem 10); consistency needs $\log \mathcal{N}(\mathcal{F},2n)/n\to 0$.

Appears in

• Lecture 3, definition and examples
• Lecture 3, growth function and its properties
• Lecture 3, exam-style table task
• Lecture 3, which growth functions give consistency

Related concepts

• VC Dimension
• Generalization Bound