Let $\mathcal{H}$ be a family of functions $h: \mathcal{X} \rightarrow\{0,1\}$ with $|\mathcal{H}| \geqslant 2$. Define the shattering coefficient $s(\mathcal{H}, n)$ and the $V C$ dimension $\mathrm{VC}(\mathcal{H})$ of $\mathcal{H}$.

Briefly explain why if $\mathcal{H}^{\prime} \subseteq \mathcal{H}$ and $\left|\mathcal{H}^{\prime}\right| \geqslant 2$, then $\mathrm{VC}\left(\mathcal{H}^{\prime}\right) \leqslant \mathrm{VC}(\mathcal{H})$.

Prove that if $\mathcal{F}$ is a vector space of functions $f: \mathcal{X} \rightarrow \mathbb{R}$ with $\mathcal{F}^{\prime} \subseteq \mathcal{F}$ and we define

$$\mathcal{H}=\left\{\mathbf{1}_{\{u: f(u) \leqslant 0\}}: f \in \mathcal{F}^{\prime}\right\}$$

then $\operatorname{VC}(\mathcal{H}) \leqslant \operatorname{dim}(\mathcal{F})$.

Let $\mathcal{A}=\left\{\left\{x:\|x-c\|_{2}^{2} \leqslant r^{2}\right\}: c \in \mathbb{R}^{d}, r \in[0, \infty)\right\}$ be the set of all spheres in $\mathbb{R}^{d}$. Suppose $\mathcal{H}=\left\{\mathbf{1}_{A}: A \in \mathcal{A}\right\}$. Show that

$$\mathrm{VC}(\mathcal{H}) \leqslant d+2$$

$\left[\right.$ Hint: Consider the class of functions $\mathcal{F}^{\prime}=\left\{f_{c, r}: c \in \mathbb{R}^{d}, r \in[0, \infty)\right\}$, where

$$f_{c, r}(x)=\|x\|_{2}^{2}-2 c^{T} x+\|c\|_{2}^{2}-r^{2}$$