Past exam of the mathematics course of the University of Cambridge / 2020 / ii / Paper 2 / 30J (Mathematics of Machine Learning)

A sample $x_{1:n}=(x_1,\dots ,x_n)$ is shattered by $\mathcal{F}$ when every binary labeling is realized:The shattering coefficient and VC dimension are

For the lower orthants in ${\mathbb{R}}^d$, the $d$ points $e_1,\dots ,e_d$ are shattered: to realize a subset $I$, choose $a_j=1$ for $j\in I$ and $a_j=1/2$ otherwise. Conversely, among any $d+1$ points choose, for each coordinate, one point attaining the maximum in that coordinate. At most $d$ points have been chosen, so there is an unchosen point $x$. Any lower orthant containing every chosen coordinate maximizer must contain every sample point, including $x$. It cannot realize the labeling that includes all chosen points and excludes $x$. This proves

The Sauer-Shelah lemma states that if $\mathrm{VC}(\mathcal{F})=v<\infty$, thenIn particular, the Sauer-Shelah growth bound gives $s(\mathcal{F},n)\le (n+1{)}^v$.

If $x_{1:n}$ is shattered by ${\bigcup }_{k=1}^r{\mathcal{F}}_k$, then all $2^n$ label vectors belong to the union of the label-vector sets generated by the individual classes. The shattering coefficient of a union and the Sauer-Shelah lemma therefore giveTaking base-two logarithms yieldsFor $r>1$, apply the stated elementary bound with $\alpha ={\log }_{2}r$ and $\beta =v\ge 3$:If $r=1$, the assertion follows directly from $n\le v$. Taking the largest shattered sample size proves

For each $d$-element coordinate set $J\subseteq \{1,\dots ,p\}$, let ${\mathcal{G}}_J$ contain the lower orthants whose finite thresholds occur precisely in the coordinates in $J$. Ignoring the remaining coordinates identifies ${\mathcal{G}}_J$ with the lower-orthant class in ${\mathbb{R}}^d$, so part (a) gives $\mathrm{VC}({\mathcal{G}}_J)=d$. Moreover,is a union of $r=\left(\genfrac{}{}{0ex}{}{p}{d}\right)$ such classes. Part (c) and $\left(\genfrac{}{}{0ex}{}{p}{d}\right)\le p^d$ give