Past exam of the computer science course of the University of Oxford / 2015 / Computational learning theory / 1 / a

The hypothesis class $H$ shatters a set $S$ when it realizes every binary labelling of $S$: for every function $g:S\to \{0,1\}$ there is an $h\in H$ with $h{|}_S=g$. Identifying each classifier with its positive set, this sayswhere $\mathcal{P}(S)$ is the power set. Different labellings may require different members of the hypothesis class.

The VC dimension isIt is infinite if arbitrarily large finite sets are shattered. A hypothesis class has VC dimension zero when it shatters no one-point set; for a nonempty hypothesis class, the empty set is always shattered.

The shattering coefficient, also called the growth function of a hypothesis class, counts the largest number of labellings obtainable on $m$ inputs:When $X$ has at least $m$ points, the same value is obtained by maximizing $|\{h{|}_S:h\in H\}|$ over $m$-point sets $S$. Always ${\Pi }_H(m)\le 2^m$, with equality exactly when some $m$-point set is shattered.

The Sauer-Shelah lemma says that a hypothesis class of finite VC dimension $d$ satisfiesIn particular, for $m\ge d\ge 1$,Here the binomial coefficients count small subsets. One way to obtain the last inequality is to set $t=d/m\le 1$: since $t^j\ge t^d$ for $j\le d$,Thus finite VC dimension replaces the unrestricted exponential number of labellings by a polynomial bound in the sample size.