3.3 VC-dimension

在这里，我们引入 VC 维度（Vapnik-Chervonenkis 维度）的概念。

• VC 维度也是一个纯粹的组合性质的概念，
  • 但通常比生长函数（或 Rademacher 复杂度）更容易计算。
• 正如我们将看到的，
  • VC 维度是学习中的一个关键量，
  • 并且与生长函数直接相关。

VC 维度的定义

• 为了进一步说明这一概念，我们将检查一系列假设集的例子，并确定每种情况的 VC 维度。

• 为了计算 VC 维度，我们通常会

  • 先展示一个下界，
  • 然后给出一个匹配的上界。

• 为了给出 VC 维度 $\mathrm{VCdim}\left(\mathcal{H}\right)$ 的下界 $d$，

  • 只需展示一个大小为 $d$ 的集合 $S$ 可以被 $\mathcal{H}$ 打碎。

• 为了给出上界，我们需要证明

  • 没有一个大小为 $d+1$ 的集合 $S$ 可以被 $\mathcal{H}$ 打碎，
    • 这通常更加困难。

• 示例 3.11 实数上的区间

• 示例 3.12 超平面

• 示例 3.12 超平面 一般的d

• 示例 3.14 轴对齐矩形

• 示例 3.15 凸 d-边形类

• 示例 3.16 正弦函数

• 许多其他假设集合的 VC 维度可以通过类似的方式确定或上界（参见本章的练习）。

  • 特别地，任何维度为 $r<\infty$ 的向量空间的 VC 维度最多为 $r$（练习 3.19）。

• 接下来的结果称为 Sauer 引理，它阐明了增长函数与 VC 维度之间的联系。

• 定理 3.17 Sauer 引理

• Sauer 引理的重要性可以通过推论 3.18 看出，它惊人地表明增长函数只表现出两种行为：

  • 要么 $\mathrm{VCdim}\left(\mathcal{H}\right)=d<+\infty$，此时 ${\Pi }_{\mathcal{H}}\left(m\right)=O\left(m^d\right)$，
  • 要么 $\mathrm{VCdim}\left(\mathcal{H}\right)=+\infty$，此时 ${\Pi }_{\mathcal{H}}\left(m\right)=2^m$。

• 推论 3.18

刚刚建立的 VC 维度与增长函数之间的明确关系，再结合 推论 3.9，立即导出了基于 VC 维度的以下泛化界。

推论 3.19 VC 维度泛化界