= Solution
First fix an ordered tuple $(g_1,\ldots,g_m)\in\mathcal G^m$. On writing
$$
z(x)=(g_1(x),\ldots,g_m(x))\in\mathbb R^m,
$$
the resulting classifiers are $x\mapsto\operatorname{sgn}(\alpha^Tz(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
$$
\boxed{s(\mathcal H_{\mathcal F_2},n)
\leq(n+1)^m|\mathcal G|^m.}
$$
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'$ with
$$
|\mathcal G'|=|\mathcal G(x_{1:n})|
\leq s(\mathcal G,n).
$$
Every $m$-tuple from $\mathcal G$ agrees on the sample with an $m$-tuple from $\mathcal G'$. The finite-class argument now gives
$$
|\mathcal H_{\mathcal F_2}(x_{1:n})|
\leq(n+1)^m s(\mathcal G,n)^m.
$$
Taking the supremum over $x_{1:n}$ proves the general <growth bound for signs of m-term linear combinations>:
$$
\boxed{s(\mathcal H_{\mathcal F_2},n)
\leq(n+1)^m s(\mathcal G,n)^m.}
$$
Back to article page
