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

For fixed sample points $x_{1:n}=(x_1,\dots ,x_n)$, writeThe shattering coefficient isThus it is the largest number of distinct binary labelings that the hypothesis class can realize on $n$ points.

A set of $n$ points is shattered when all $2^n$ labelings are realized. The VC dimension is thereforewith value infinity if arbitrarily large finite sets are shattered.

For every fixed $x_{1:n}$,The cardinality of a union is at most the sum of the two cardinalities, soTaking the supremum over samples proves the shattering coefficient of a union bound

The functions $x\mapsto x^T\beta$ form a real vector space of dimension $p$. Hence the VC dimension of a vector space givesApplying the Sauer-Shelah lemma and then the Sauer-Shelah growth bound,This is the growth bound for homogeneous linear classifiers.

First fix an ordered tuple $(g_1,\dots ,g_m)\in {\mathcal{G}}^m$. On writingthe resulting classifiers are $x\mapsto \mathrm{sgn}({\alpha }^{T}z(x))$. The growth bound for homogeneous linear classifiers in dimension $m$ gives at most $(n+1{)}^m$ label vectors on any $n$ sample points.

If $\mathcal{G}$ is finite, there are $|\mathcal{G}{|}^m$ ordered tuples of hidden functions. The shattering coefficient of a union therefore gives

For an arbitrary $\mathcal{G}$, fix $x_{1:n}$. Choose one representative for every distinct vector in $\mathcal{G}(x_{1:n})$, obtaining a finite class ${\mathcal{G}}^{\prime }$ withEvery $m$-tuple from $\mathcal{G}$ agrees on the sample with an $m$-tuple from ${\mathcal{G}}^{\prime }$. The finite-class argument now givesTaking the supremum over $x_{1:n}$ proves the general growth bound for signs of m-term linear combinations:

A function in the stated network class has the formThus this is the class ${\mathcal{F}}_2$ from part (d), with the hidden-unit classParts (c) and (d) giveThis is the growth bound for a single-hidden-layer sign network.