Past exam of the mathematics course of the University of Cambridge / 2026 / ii / Paper 1 / 31K (Mathematics of Machine Learning)

For points $x_1,\dots ,x_n$, count the distinct vectors $(h(x_1),\dots ,h(x_n))$; maximize over samples to get $s(H,n)$. The shattering coefficient equals $2^n$ exactly when some sample is shattered, and the largest such $n$ is $\mathrm{VC}(H)$.

Order the $n$ sample points. Each of the $m-1$ cut points can occupy one of at most $n+1$ gaps. Once those gaps are chosen the fixed ${\beta }_k$ determine every sign, so

For each coordinate, the $m$ interval indicators sum to one, so the span of all displayed indicators has dimension at mostTherefore VC dimension of a vector space gives
$\mathrm{VC}(H_{F_2})\le 1+p(m-1)$.

On an $n$-sample, each coordinate partition has at most $(n+1{)}^{m-1}$ placements, hence all $p$ partitions have at most $(n+1{)}^{p(m-1)}$ configurations. For each fixed configuration, the sign class from a vector space of dimension $1+p(m-1)$ has at most $(n+1{)}^{1+p(m-1)}$ patterns. Multiplication gives