Past exam of the mathematics course of the University of Cambridge / 2025 / ii / Paper 2 / 31L (Mathematics of Machine Learning)

A set of points $x_1,\dots ,x_n$ is shattered by $H$ when every one of the $2^n$ binary label vectors is realized by some $h\in H$. The shattering coefficient isand the VC dimension is

The Sauer--Shelah lemma states that if $VC(H)=D<\infty$, thenfor every $n$; in particular $s(H,n)\le (n+1{)}^D$.

Two ordered points $x_1<x_2$ are shattered by intervals: an interval can contain neither, either one alone, or both. Three ordered points cannot be shattered, because an interval containing the first and third must also contain the middle one. Hence

The choice $\delta =1$ labels an interval positively and its complement negatively, while $\delta =-1$ reverses those labels. On three ordered points, every subset is either a consecutive block or the complement of a consecutive block, so all eight labelings occur. Thus three points are shattered.

Four ordered points are not shattered: the alternating labeling $+,-,+,-$ has neither its positive set nor its negative set consecutive, so it cannot arise from an interval or its complement. Therefore

Only the symmetric part of $M$ contributes to $x^{T}Mx$. The functionstherefore form a real vector space of dimensionwith coordinates given by the quadratic monomials $x_i^2$ and $x_i{x}_j$ for $i<j$. The theorem on signs of a finite-dimensional function space says that the sign class of a $D$-dimensional real vector space has VC dimension at most $D$. Consequently

Use the empirical Rademacher conventionBecause $H_3$ is symmetric under $h\mapsto -h$, optimizing a linear functional over the positive ${\ell }^1$ hull defining $\mathcal{F}$ gives

By part (c), $VC(H_3)\le D=d(d+1)/2$. Sauer--Shelah therefore bounds the number $N$ of distinct label vectors on the sample byMassart's finite-class lemma states that for $A\subseteq \{-1,1{\}}^n$,Applying it to the distinct label vectors of $H_3$ gives