= Solution
For fixed sample points $x_{1:n}=(x_1,\ldots,x_n)$, write
$$
\mathcal H(x_{1:n})
=\{(h(x_1),\ldots,h(x_n)):h\in\mathcal H\}.
$$
The <shattering coefficient> is
$$
\boxed{s(\mathcal H,n)=\sup_{x_{1:n}\in\mathcal X^n}|\mathcal H(x_{1:n})|.}
$$
Thus 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 therefore
$$
\boxed{\operatorname{VC}(\mathcal H)
=\sup\{n:s(\mathcal H,n)=2^n\},}
$$
with value infinity if arbitrarily large finite sets are shattered.
Back to article page
