推论 3.18

推论 3.18

设 $\mathcal{H}$ 是一个假设集合，且 $\mathrm{VCdim}\left(\mathcal{H}\right)=d$。 那么对于所有 $m\ge d$， {\Pi }_{\mathcal{H}}\left( m\right) \leq {\left( \frac{em}{d}\right) }^{d} = O\left( {m}^{d}\right) . \tag{3.28}

\begin{proof} 证明首先使用 Sauer 引理。 由于 $m\ge d$， 第一步不等式将每个加项乘以一个大于或等于 1 的因子， 第二步不等式则是在求和中添加非负加项。

$$\begin{array}{rl}{\Pi }_{\mathcal{H}}(m)& \le \sum _{i=0}^d\left(\genfrac{}{}{0ex}{}{m}{i}\right)\\ & \le \sum _{i=0}^d\left(\genfrac{}{}{0ex}{}{m}{i}\right){\left(\frac{m}{d}\right)}^{d-i}\\ & \le \sum _{i=0}^m\left(\genfrac{}{}{0ex}{}{m}{i}\right){\left(\frac{m}{d}\right)}^{d-i}\\ & ={\left(\frac{m}{d}\right)}^d\sum _{i=0}^m\left(\genfrac{}{}{0ex}{}{m}{i}\right){\left(\frac{d}{m}\right)}^i\\ & ={\left(\frac{m}{d}\right)}^d{\left(1+\frac{d}{m}\right)}^m\\ & \le {\left(\frac{m}{d}\right)}^d{e}^d.\end{array}$$

在使用二项式定理简化表达式后，最终不等式可以通过使用以下一般不等式得到 $\left(1-x\right)\le e^{-x}$ \end{proof}