定理 3.17 Sauer 引理

定理 3.17 Sauer 引理

设 $\mathcal{H}$ 是一个假设集合，且 $\mathrm{VCdim}\left(\mathcal{H}\right)=d$。 那么，对于所有 $m\in \mathbb{N}$，以下不等式成立： {\Pi }_{\mathcal{H}}\left( m\right) \leq \mathop{\sum }\limits_{{i = 0}}^{d}\left( \begin{matrix} m \\ i \end{matrix}\right) \tag{3.27}

\begin{proof}

• 通过对 $m+d$ 进行归纳

• 该声明对于以下情况显然成立：

  • $m=1$ 和 $d=0$
  • $d=1$

• 假设对于 $(m-1,d-1)$ 和 $(m-1,d)$ 的情况成立

  • 固定一个集合 $\mathcal{S}=\{x_1,\dots ,x_m\}$
    • 具有 ${\Pi }_{\mathcal{H}}(m)$ 种二分法
  • 令 $\mathcal{G}={\mathcal{H}}_{|\mathcal{S}}$
    • 通过对 $\mathcal{S}$ 限制得到的概念集合

• 考虑的集合：

  • 在 ${\mathcal{S}}^{\prime }=\{x_1,\dots ,x_{m-1}\}$ 上的族
  • 定义 ${\mathcal{G}}_1={\mathcal{G}}_{|{\mathcal{S}}^{\prime }}$
    • 通过对 ${\mathcal{S}}^{\prime }$ 限制得到的概念集合

• 通过将每个概念识别为在 ${\mathcal{S}}^{\prime }$ 或 $\mathcal{S}$ 中的非零点集合

  • 定义 ${\mathcal{G}}_2$： ${\mathcal{G}}_2=\left\{g^{\prime }\subseteq {\mathcal{S}}^{\prime }:\left(g^{\prime }\in \mathcal{G}\right)\wedge \left(g^{\prime }\cup \left\{x_m\right\}\in \mathcal{G}\right)\right\}.$
  • 由于 $g^{\prime }\subseteq {\mathcal{S}}^{\prime }$ 且 $g^{\prime }\in \mathcal{G}$
    • 表示在没有添加 $x_m$ 的情况下，它是 $\mathcal{G}$ 的一个概念

• 约束条件 $g^{\prime }\cup \{x_m\}\in \mathcal{G}$

  • 意味着将 $x_m$ 添加到 $g^{\prime }$ 中也使其成为 $\mathcal{G}$ 的一个概念
  • ${\mathcal{G}}_1$ 和 ${\mathcal{G}}_2$ 的构造在图 3.6 中以图示方式展示

Figure 3.6 在 Sauer 引理的证明中，${\mathcal{G}}_1$ 和 ${\mathcal{G}}_2$ 的构造示意图。

根据我们对 ${\mathcal{G}}_1$ 和 ${\mathcal{G}}_2$ 的定义，可以观察到 $\left|{\mathcal{G}}_1\right|+\left|{\mathcal{G}}_2\right|=\left|\mathcal{G}\right|.$

由于 $\mathrm{VCdim}\left({\mathcal{G}}_1\right)\le \mathrm{VCdim}\left(\mathcal{G}\right)\le d$，

• 根据增长函数的定义并利用归纳假设， $\left|{\mathcal{G}}_1\right|\le {\Pi }_{{\mathcal{G}}_1}\left(m-1\right)\le \sum _{i=0}^d\left(\begin{array}{c}m-1\\ i\end{array}\right).$

• 根据 ${\mathcal{G}}_2$ 的定义：

  • 如果一个集合 $\mathcal{Z}\subseteq {\mathcal{S}}^{\prime }$ 被 ${\mathcal{G}}_2$ 打散
  • 则集合 $\mathcal{Z}\cup \{x_m\}$ 也会被 $\mathcal{G}$ 打散

• 可见

  • $\mathrm{VCdim}\left({\mathcal{G}}_2\right)\le \mathrm{VCdim}\left(\mathcal{G}\right)-1=d-1,$
  • 并且根据增长函数的定义以及使用归纳假设，$\left|{\mathcal{G}}_2\right|\le {\Pi }_{{\mathcal{G}}_2}\left(m-1\right)\le \sum _{i=0}^{d-1}\left(\begin{array}{c}m-1\\ i\end{array}\right).$ 那么

$$\begin{array}{rl}\left|\mathcal{G}\right|& =\left|{\mathcal{G}}_1\right|+\left|{\mathcal{G}}_2\right|\\ & \le \sum _{i=0}^d\left(\genfrac{}{}{0ex}{}{m-1}{i}\right)+\sum _{i=0}^{d-1}\left(\genfrac{}{}{0ex}{}{m-1}{i}\right)\\ & =\sum _{i=0}^d\left[\left(\genfrac{}{}{0ex}{}{m-1}{i}\right)+\left(\genfrac{}{}{0ex}{}{m-1}{i-1}\right)\right]\\ & =\sum _{i=0}^d\left(\genfrac{}{}{0ex}{}{m}{i}\right).\end{array}$$

这就完成了归纳证明。 \end{proof}