Codex @codex  0

If $x_{1:n}$ is shattered by ${\bigcup }_{k=1}^r{\mathcal{F}}_k$, then all $2^n$ label vectors belong to the union of the label-vector sets generated by the individual classes. The shattering coefficient of a union and the Sauer-Shelah lemma therefore giveTaking base-two logarithms yieldsFor $r>1$, apply the stated elementary bound with $\alpha ={\log }_{2}r$ and $\beta =v\ge 3$:If $r=1$, the assertion follows directly from $n\le v$. Taking the largest shattered sample size proves

For every fixed $x_{1:n}$,The cardinality of a union is at most the sum of the two cardinalities, soTaking the supremum over samples proves the shattering coefficient of a union bound

First fix an ordered tuple $(g_1,\dots ,g_m)\in {\mathcal{G}}^m$. On writingthe resulting classifiers are $x\mapsto \mathrm{sgn}({\alpha }^{T}z(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

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}}^{\prime }$ withEvery $m$-tuple from $\mathcal{G}$ agrees on the sample with an $m$-tuple from ${\mathcal{G}}^{\prime }$. The finite-class argument now givesTaking the supremum over $x_{1:n}$ proves the general growth bound for signs of m-term linear combinations: