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

Fix an $m$-point set $S$. The restriction of an intersection $c_1\cap c_2$ to $S$ is determined by the ordered pair of restrictions $c_1{|}_S,c_2{|}_S$. Some pairs can yield the same intersection, so the growth function of a hypothesis class satisfiesAssume first that $d\ge 1$. If $12d$ points were shattered by $H_2$, the Sauer-Shelah lemma would implyBut $e<3$, so $(12e{)}^2<36^2=1296<4096=2^{12}$. Raising this strict inequality to the positive integer power $d$ gives a contradiction. No $12d$-point set can therefore be shattered; neither can any larger set, since shattering passes to subsets. ConsequentlyThe printed strict inequality needs $d\ge 1$. For example, on a nonempty domain let $H$ contain only the identically zero classifier. Then $\mathrm{VC}(H)=\mathrm{VC}(H_2)=0$, whereas the stated conclusion would require $0<0$. More generally, a nonempty hypothesis class of VC dimension zero has only one distinct labelling function, since two different functions would shatter a point on which they differ. Its self-intersection class also has VC dimension zero.