机器学习数学基础 120 章

Rademacher 复杂度与稳定性直觉

层级：C｜建议先修：05-21、08-11、08-13

VC 维衡量二分类假设类最坏情况下能实现多少标记。Rademacher 复杂度进一步考虑函数在给定样本上的取值幅度；算法稳定性则从“替换一个训练样本会让模型改变多少”解释泛化。

1. 为什么需要数据依赖复杂度

同一个假设类在不同数据分布上可能表现出不同有效容量。最坏情况 VC 维不使用实际样本位置，也不直接适合许多实值损失。

Rademacher 复杂度通过测试函数类拟合随机正负噪声的能力，衡量它在当前样本上的丰富程度。

2. Rademacher 随机变量

Rademacher 变量 σi\sigma_i 以相等概率取 +1+1 和 −1-1：

P(σi=1)=P(σi=−1)=12.P(\sigma_i=1)=P(\sigma_i=-1)=\frac12.

它们相互独立且与训练样本独立，满足 E[σi]=0\mathbb E[\sigma_i]=0、Var⁡(σi)=1\operatorname{Var}(\sigma_i)=1。

3. 经验 Rademacher 复杂度

给定样本 S=(x1,ldots,xn)S=(x_1,ldots,x_n) 和实值函数类 F\mathcal F，一种常用定义为

R^S(F)=Eσ[sup⁡f∈F1n∑i=1nσif(xi)].\hat{\mathfrak R}_S(\mathcal F) =\mathbb E_{\boldsymbol\sigma} \left[ \sup_{f\in\mathcal F} \frac1n\sum_{i=1}^n\sigma_if(x_i) \right].

有些教材在定义前加 2，比较公式时要检查约定。

若类中能找到函数与任意随机符号高度对齐，复杂度就大；若所有函数输出受强约束、无法追随噪声，复杂度就小。

4. 总体 Rademacher 复杂度

再对样本抽样取期望：

Rn(F)=ES∼Dn[R^S(F)].\mathfrak R_n(\mathcal F) =\mathbb E_{S\sim\mathcal D^n} [\hat{\mathfrak R}_S(\mathcal F)].

经验版本可由当前数据估计，总体版本用于理论表达。

5. 典型泛化界

若函数值或损失有界，则以至少 1−δ1-\delta 的概率，对所有 f∈Ff\in\mathcal F，有类似

E[f(X)]≤1n∑i=1nf(xi)+2Rn(F)+Clog⁡(1/δ)n\mathbb E[f(X)] \le\frac1n\sum_{i=1}^nf(x_i) +2\mathfrak R_n(\mathcal F) +C\sqrt{\frac{\log(1/\delta)}{n}}

的界。常数随采用经验或总体复杂度、函数值范围和定理版本变化。

结构依然清晰：真实风险不超过经验风险、类复杂度罚项和置信罚项之和。

6. 对称化直觉

证明中常引入独立“幽灵样本” S′S'，把未知期望与经验平均之差转化为两个经验平均之差；再用随机符号交换对应样本，得到 Rademacher 和。

因此随机符号不是凭空出现，而是用来表达样本抽样差异的对称性。

7. 收缩性质

若损失函数 ϕ\phi 是 LL-Lipschitz，则复合类通常满足收缩不等式：

Rn(ϕ∘F)≤LRn(F)\mathfrak R_n(\phi\circ\mathcal F) \le L\mathfrak R_n(\mathcal F)

（可能依定义带常数）。这使我们能先控制预测函数类复杂度，再传递到损失类。

8. 线性函数类示例

设

F={x↦wTx:∥w∥2≤B},∥xi∥2≤R.\mathcal F=\{x\mapsto\mathbf w^T\mathbf x:\|\mathbf w\|_2\le B\}, \quad\|x_i\|_2\le R.

由 Cauchy–Schwarz 不等式，

R^S(F)=BnEσ∥∑iσixi∥2≤BRn.\hat{\mathfrak R}_S(\mathcal F) =\frac{B}{n}\mathbb E_\sigma \left\|\sum_i\sigma_i x_i\right\|_2 \le\frac{BR}{\sqrt n}.

这说明控制权重范数和输入尺度可直接限制复杂度，而且界未显式依赖维数。

9. margin 与分类

线性分类不仅受超平面维数影响，还受间隔和权重范数影响。若数据在单位球内、分类间隔大，则可得到与 (R/γ)2(R/\gamma)^2 有关的复杂度，而非仅依赖原始维度。这更贴近 SVM 的泛化直觉。

10. 算法稳定性

稳定性不直接衡量整个假设类，而是衡量学习算法对单个样本扰动的敏感性。若训练集 S,S(i)S,S^{(i)} 只差一个样本，算法输出分别为 A(S),A(S(i))A(S),A(S^{(i)})。

若对任意测试点 zz，

∣ℓ(A(S),z)−ℓ(A(S(i)),z)∣≤β,|\ell(A(S),z)-\ell(A(S^{(i)}),z)|\le\beta,

则称具有某种 β\beta-一致稳定性。β\beta 越小，替换一个样本对预测损失影响越小，泛化通常越好。

11. 稳定性为何带来泛化

训练误差使用模型训练过的样本，真实误差使用新样本。把训练样本中的一个点替换为独立新点时，如果算法输出几乎不变，就能把这两种情形联系起来。

强凸正则化 ERM 常具有良好稳定性。例如适当条件下，稳定参数可随 1/(λn)1/(\lambda n) 缩小：样本越多或正则越强，单点影响越小。

12. 稳定性与优化

稳定性还依赖算法本身：即使函数类相同，不同优化路径、早停和随机化也可能产生不同泛化。随机梯度方法的步长、迭代次数和损失光滑性会影响稳定性。

这提供了理解“过参数模型为何仍可能泛化”的另一条路线：不能只看假设类最坏容量，还要看算法实际选择了哪些解。

13. 易错点

  1. Rademacher 复杂度不是训练标签上的拟合能力，而是拟合独立随机符号的能力。
  2. 定义常数因教材不同而异，比较结论要统一约定。
  3. 复杂度界需要有界性或 Lipschitz 等条件，不能忽略定理假设。
  4. 稳定性小是有利证据，不代表自动解决分布偏移和数据泄漏。

常见问答

Q1：Rademacher 复杂度越小越好吗？
只从估计误差看越小越有利，但类过小会增大逼近误差；仍需平衡表达能力。

Q2：为什么用随机标签测试容量？
随机标签没有可泛化结构。能高度拟合它们说明函数类自由度足以追随抽样噪声。

Q3：经验 Rademacher 复杂度能精确计算吗？
一般不易，需要多次随机符号和求解类内优化；理论上常使用解析上界。

Q4：稳定性与交叉验证有关系吗？
二者都考察训练数据扰动对结果的影响，但交叉验证是评估方法，稳定性是算法性质和泛化分析工具。

练习

  1. 说明常数函数类的 Rademacher 复杂度为何很小。
  2. 解释线性类复杂度上界 BR/nBR/\sqrt n 中每个量的作用。
  3. 什么是损失的 Lipschitz 性？它为何能传递复杂度界？
  4. 用自然语言说明“一致稳定性如何连接训练误差和真实误差”。

答案与提示

  1. 所有样本输出相同，无法独立追随每个随机符号；正负符号大致抵消。
  2. 权重半径 BB 和输入半径 RR 越大，类越灵活；样本量以平方根速度降低复杂度。
  3. 输入变化 Δ\Delta 导致函数值变化至多 L∣Δ∣L|\Delta|，因此复合损失不会把预测类差异无限放大。
  4. 替换一个训练样本为独立新样本时模型损失变化很小，于是“在训练点上测量”和“在新点上测量”的期望差可被控制。