机器学习数学基础 120 章

VC 维、增长函数与打散

层级：C｜建议先修：01-03、08-11、08-12

VC 维衡量一个二分类假设类在最不利位置的一组样本上能实现多丰富的标记方式。它把无限假设类的“有效容量”压缩成一个整数。

1. 二分类假设类

设

H⊆{h:X→{0,1}}.\mathcal H\subseteq\{h:\mathcal X\to\{0,1\}\}.

给定一组无标签点

S={x1,ldots,xm},S=\{x_1,ldots,x_m\},

每个 hh 会产生一个标记向量

(h(x1),…,h(xm))∈{0,1}m.(h(x_1),\ldots,h(x_m))\in\{0,1\}^m.

2. 打散

若 H\mathcal H 能在 SS 上实现全部 2m2^m 种二元标记，则称 SS 被 H\mathcal H 打散（shatter）。

打散要求同一组点上的每一种标记都能由类中某个假设实现，并不要求同一个假设同时实现所有标记。

3. VC 维

H\mathcal H 的 VC 维定义为它能打散的最大点数：

VCdim⁡(H)=sup⁡{m:∃S,∣S∣=m,H 打散 S}.\operatorname{VCdim}(\mathcal H) =\sup\{m:\exists S,|S|=m,\mathcal H\text{ 打散 }S\}.

若任意大的有限点集都能被打散，则 VC 维为无穷。

“存在一组能打散”很重要：VC 维看最有利于展现模型容量的位置，不要求任意点集都能打散。

4. 阈值分类器

实线上的阈值类

ha(x)=1[x≥a]h_a(x)=\mathbf1[x\ge a]

VC 维为 1：

  • 任意一个点可通过调整阈值标成 0 或 1；
  • 对两个有序点 x1<x2x_1<x_2，标记 (1,0)(1,0) 无法实现。

若允许区间分类器 ha,b(x)=1[a≤x≤b]h_{a,b}(x)=\mathbf1[a\le x\le b]，VC 维为 2。

5. 线性分类器

Rd\mathbb R^d 中带截距的仿射超平面分类器

hw,b(x)=1[wTx+b≥0]h_{\mathbf w,b}(\mathbf x) =\mathbf1[\mathbf w^T\mathbf x+b\ge0]

VC 维为 d+1d+1。例如二维直线分类器 VC 维为 3：适当位置的三个点可实现全部标记，但任意四点都无法保证被打散。

齐次超平面 wTx=0\mathbf w^T\mathbf x=0 不含截距，VC 维通常为 dd。

6. 证明 VC 维的套路

要证明 VCdim⁡(H)=d\operatorname{VCdim}(\mathcal H)=d，通常分两步：

  1. 下界：构造一组 dd 个点，并证明全部 2d2^d 种标记都可实现；
  2. 上界：证明任何 d+1d+1 个点都不能被打散。

只举出某一组点无法打散不能证明上界；上界必须排除所有可能点集。

7. 增长函数

增长函数定义为在任意 mm 个点上最多能实现的标记数量：

ΠH(m)=max⁡x1,ldots,xm∣{(h(x1),…,h(xm)):h∈H}∣.\Pi_{\mathcal H}(m) =\max_{x_1,ldots,x_m} \left|\{(h(x_1),\ldots,h(x_m)):h\in\mathcal H\}\right|.

总有 ΠH(m)≤2m\Pi_{\mathcal H}(m)\le2^m。若 m≤dVCm\le d_{VC}，则可达到 2m2^m；超过 VC 维后，增长速度会从指数受到限制。

8. Sauer–Shelah 引理

若 d=VCdim⁡(H)<∞d=\operatorname{VCdim}(\mathcal H)<\infty，且 m≥dm\ge d，则

ΠH(m)≤∑i=0d(mi)≤(emd)d.\Pi_{\mathcal H}(m) \le\sum_{i=0}^d\binom mi \le\left(\frac{em}{d}\right)^d.

这说明有限 VC 维的假设类在样本上的有效标记数只按 mdm^d 多项式增长，而非 2m2^m 指数增长。

9. VC 泛化界

对 0-1 损失，一类典型的统一泛化界具有形式

sup⁡h∈H∣R(h)−R^(h)∣=O(dlog⁡(n/d)+log⁡(1/δ)n).\sup_{h\in\mathcal H}|R(h)-\hat R(h)| =O\left(\sqrt{\frac{d\log(n/d)+\log(1/\delta)}{n}}\right).

不同定理的常数和对数项略有差异，但核心依赖是：VC 维越大，需要更多样本；样本量增大，泛化差距按约 1/n1/\sqrt n 缩小。

可实现情形下 PAC 样本复杂度通常约为

O(dlog⁡(1/ε)+log⁡(1/δ)ε),O\left(\frac{d\log(1/\varepsilon)+\log(1/\delta)}{\varepsilon}\right),

而 agnostic 情形常为 O((d+log⁡(1/δ))/ε2)O((d+\log(1/\delta))/\varepsilon^2) 的量级，具体形式依定理而异。

10. VC 维与参数数量

VC 维经常与参数数量相关，但不等于参数数量。模型的运算形式、参数约束、实数精度和组合结构都会影响容量。某些含少量参数的高度振荡函数也可能有很大甚至无限 VC 维。

对现代神经网络，仅靠参数数目给出的 VC 界往往太松；范数、间隔、压缩和算法隐式偏置可能更能解释实际泛化。

11. 多分类与实值函数扩展

VC 维针对二值分类。多分类有 Natarajan 维等推广；实值函数和回归常用 pseudo-dimension、fat-shattering dimension 或 Rademacher 复杂度。

12. 易错点

  1. 打散是“存在一组点且实现所有标记”，不是训练准确率达到 100%。
  2. VC 维高表示容量大，不表示一定过拟合；样本量和算法偏置同样重要。
  3. VC 维不依赖具体标签分布，是分布无关的最坏情况复杂度。
  4. 有限 VC 维界可以很松，不能直接当作工程所需样本量。

常见问答

Q1：为什么阈值类不能打散两个点？
阈值产生的正类只能是数轴一侧，无法让左点为正而右点为负（按定义方向固定）。

Q2：一组四点不能被二维直线打散，是否就证明 VC 维不超过 3？
不能；必须证明任何四点都不能被打散。完整证明可借助凸包交叉等几何结论。

Q3：VC 维是否越小越好？
不是。太小会导致逼近能力不足；需要在表达能力与有限样本估计能力之间平衡。

Q4：正则化会改变 VC 维吗？
若只限制训练算法而不改变函数集合，经典 VC 维可能不变；若范数约束真正缩小假设类，或改用间隔复杂度，则可得到更细的容量控制。

练习

  1. 证明实线阈值分类器的 VC 维为 1。
  2. 说明实线区间分类器可以打散任意两个不同点。
  3. 写出增长函数与 VC 维的关系。
  4. 为什么证明 VC 维上界比证明下界通常更难？

答案与提示

  1. 单点的两种标记都可实现；任意两个有序点的 (1,0)(1,0) 标记不可实现。
  2. 空区间实现全负，只覆盖左/右点实现单正，覆盖二者实现全正。
  3. VC 维是使 ΠH(m)=2m\Pi_{\mathcal H}(m)=2^m 的最大 mm；超过它后由 Sauer 引理控制增长。
  4. 下界只需构造一个可打散点集，上界要排除所有更大点集。