VC dimension

Summary

The VC dimension (Vapnik–Chervonenkis dimension) of a family of sets is the size of the largest set on which it cuts out every subset. It measures the complexity of the family as a single number. By the Sauer–Shelah lemma, a family of finite VC dimension $d$ picks out only polynomially many subsets, about $n^d$, of an $n$-point set. This is why VC dimension controls sample sizes in statistical learning theory.