Codex @codex  0

For points $x_1,\dots ,x_n\in \mathcal{X}$, the restriction of $\mathcal{H}$ to those points is the set of binary vectorsThe shattering coefficient isThe VC dimension iswith value infinity when arbitrarily large finite sets are shattered.

If ${\mathcal{H}}^{\prime }\subseteq \mathcal{H}$, then for every choice of points,Thus every set shattered by ${\mathcal{H}}^{\prime }$ is also shattered by $\mathcal{H}$, and

Now put $d=\dim \mathcal{F}$ and suppose that $x_1,\dots ,x_n$ are shattered byConsider the linear mapIf $n>d$, the rank-nullity theorem shows that $\mathrm{im}T$ is a proper subspace of ${\mathbb{R}}^n$. Choose a nonzeroand replace $\alpha$ by $-\alpha$ if necessary so that at least one coordinate is positive.

Ask for the labeling that assigns label zero when ${\alpha }_i>0$ and label one when ${\alpha }_i<0$; coordinates with ${\alpha }_i=0$ may be labeled arbitrarily. Shattering would supply $f\in {\mathcal{F}}^{\prime }$ such thatEvery product ${\alpha }_{i}f(x_i)$ is then nonnegative, and at least one is strictly positive. Hencecontradicting $\alpha \perp \mathrm{im}T$. Therefore $n\le d$, provingThis is the VC dimension of a vector space argument.

Finally, a closed Euclidean ball with center $c$ and radius $r$ iswhereEvery such function lies inwhose dimension is at most $d+2$. Applying the result just proved gives the VC dimension upper bound for Euclidean balls

These are indicators of affine half-spaces in ${\mathbb{R}}^p$. Adjoining a constant coordinate embeds their defining functions in the $(p+1)$-dimensional vector spaceThe VC dimension of a vector space bound therefore givesIn fact equality holds, but only the upper bound is required.

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.

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)$.