Past exam of the mathematics course of the University of Cambridge / 2023 / ii / Paper 2 / 31J / a / Solution

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.