Luminosity

外观

第四讲：学习理论、复杂度与泛化界

约 2909 字大约 10 分钟

Machine LearningLearning TheoryGeneralization

本文由 GPT-5.6-sol 完成。

训练误差低，并不自动意味着模型真的学会了。学习理论试图回答一个更困难的问题：仅凭有限样本，我们凭什么相信模型在未来数据上仍然有效？

答案不会是一句“防止过拟合”，而是一组可以量化的关系：样本越多，经验平均越接近总体期望；假设空间越复杂，这种接近越难保证；模型既要能逼近真实规律，又不能拥有无限制的自由度。

一、经验风险与期望风险

设数据 (X,Y)(X,Y) 来自未知分布 PP。模型 ff 的期望风险为

R(f)=E(X,Y)∼P[ℓ(Y,f(X))],R(f)=\mathbb E_{(X,Y)\sim P} \left[\ell(Y,f(X))\right],

而训练集 S={(xi,yi)}i=1nS=\{(x_i,y_i)\}_{i=1}^n 上的经验风险是

R^S(f)=1n∑i=1nℓ(yi,f(xi)).\hat R_S(f)=\frac1n\sum_{i=1}^n \ell(y_i,f(x_i)).

训练真正能计算的是 R^S(f)\hat R_S(f)，我们真正关心的却是 R(f)R(f)。两者之差

R(f)−R^S(f)R(f)-\hat R_S(f)

称为泛化差距。学习理论的核心任务之一，就是以高概率控制这个差距。

1. Bayes 最优与偏差—方差

平方损失下，Bayes 最优预测是条件均值

f∗(x)=E[Y∣X=x].f^*(x)=\mathbb E[Y\mid X=x].

若观测可写成 Y=f∗(X)+εY=f^*(X)+\varepsilon，且 E[ε∣X]=0\mathbb E[\varepsilon\mid X]=0，则测试误差可分解为

E[(Y−f^(X))2]=σ2+Bias⁡2[f^(X)]+Var⁡[f^(X)].\mathbb E[(Y-\hat f(X))^2] =\sigma^2 +\operatorname{Bias}^2[\hat f(X)] +\operatorname{Var}[\hat f(X)].

噪声是不可约误差；偏差来自模型或学习规则过于僵硬；方差则表示训练集稍有变化，模型就发生多大变化。模型复杂度提高时，偏差常下降、方差常上升，但这是一种典型趋势，而不是对所有算法都逐点成立的定律。

2. 近似误差与估计误差

令假设空间为 H\mathcal H，其中风险最小者为

fH∗=arg⁡min⁡f∈HR(f),f_{\mathcal H}^*=\arg\min_{f\in\mathcal H}R(f),

经验风险最小化得到

f^=arg⁡min⁡f∈HR^S(f).\hat f=\arg\min_{f\in\mathcal H}\hat R_S(f).

相对所有可测函数中的最优解 f∗f^*，超额风险可拆成

R(f^)−R(f∗)=R(fH∗)−R(f∗)⏟近似误差+R(f^)−R(fH∗)⏟估计误差.R(\hat f)-R(f^*) =\underbrace{R(f_{\mathcal H}^*)-R(f^*)}_{\text{近似误差}} +\underbrace{R(\hat f)-R(f_{\mathcal H}^*)}_{\text{估计误差}}.

扩大 H\mathcal H 往往降低近似误差，却可能提高估计误差。这比一句“模型越复杂越容易过拟合”更准确：真正需要平衡的是表达能力与有限样本下的可估计性。

二、PAC 学习：把“学得会”写成概率陈述

PAC 是 Probably Approximately Correct，即“以高概率近似正确”。它引入两个容忍参数：

  • ε\varepsilon 控制允许的误差；
  • δ\delta 控制结论失败的概率。

粗略地说，若存在学习算法，使得当样本量达到某个关于 1/ε1/\varepsilon、1/δ1/\delta 和问题复杂度的多项式规模后，有

Pr⁡(R(f^)≤ε)≥1−δ,\Pr\left(R(\hat f)\le\varepsilon\right) \ge1-\delta,

则称该问题在相应设定下 PAC 可学习。上述形式对应可实现情形；在不可实现或 agnostic 设定中，通常改为控制超额风险

R(f^)−inf⁡f∈HR(f)≤ε.R(\hat f)-\inf_{f\in\mathcal H}R(f)\le\varepsilon.

PAC 的重点不是承诺“永不出错”，而是明确说明：在怎样的样本量下，以多大的置信度，能把风险控制到什么精度。

三、从期望到高概率：常用概率工具

1. Jensen 不等式

若 φ\varphi 是凸函数，则

φ(E[X])≤E[φ(X)].\varphi(\mathbb E[X]) \le \mathbb E[\varphi(X)].

它是许多期望上界的起点。例如指数函数是凸的，矩母函数方法便可将尾概率问题转化为指数矩的控制。

2. Markov 与 Chebyshev 不等式

对非负随机变量 XX，Markov 不等式给出

Pr⁡(X≥a)≤E[X]a,a>0.\Pr(X\ge a)\le\frac{\mathbb E[X]}a, \qquad a>0.

对均值 μ\mu、方差 σ2\sigma^2 的随机变量应用于 (X−μ)2(X-\mu)^2，得到 Chebyshev 不等式

Pr⁡(∣X−μ∣≥t)≤σ2t2.\Pr(|X-\mu|\ge t) \le\frac{\sigma^2}{t^2}.

它们只使用很少的分布信息，因此适用面广，但界通常较松。

3. Hoeffding 不等式

若独立随机变量 Xi∈[ai,bi]X_i\in[a_i,b_i]，则

Pr⁡(∣1n∑i=1nXi−E1n∑i=1nXi∣≥ε)≤2exp⁡(−2n2ε2∑i(bi−ai)2).\Pr\left( \left|\frac1n\sum_{i=1}^nX_i- \mathbb E\frac1n\sum_{i=1}^nX_i\right| \ge\varepsilon\right) \le 2\exp\left( -\frac{2n^2\varepsilon^2} {\sum_i(b_i-a_i)^2} \right).

特别地，当 Xi∈[0,1]X_i\in[0,1] 时，右侧为 2e−2nε22e^{-2n\varepsilon^2}。与 Chebyshev 的多项式尾界相比，指数衰减正是有限样本泛化界常用 Hoeffding 的原因。

4. McDiarmid 不等式

若函数 g(X1,…,Xn)g(X_1,\ldots,X_n) 在替换第 ii 个输入时最多变化 cic_i，则

Pr⁡(g−Eg≥t)≤exp⁡(−2t2∑ici2).\Pr(g-\mathbb E g\ge t) \le \exp\left(-\frac{2t^2}{\sum_i c_i^2}\right).

它把“独立变量的平均值集中”推广到“对每个样本都不太敏感的函数集中”。之后控制经验 Rademacher 复杂度与其期望之差时会再次出现这种思想。

四、有限假设空间的泛化保证

假设使用 00-11 损失。对固定 h∈Hh\in\mathcal H，Hoeffding 给出

Pr⁡(∣R(h)−R^S(h)∣>ε)≤2e−2nε2.\Pr\left(|R(h)-\hat R_S(h)|>\varepsilon\right) \le2e^{-2n\varepsilon^2}.

但训练后的 h^\hat h 是看过数据才选出来的，不能把它当作事先固定的假设。对有限 H\mathcal H 使用 union bound：

Pr⁡(∃h∈H:∣R(h)−R^S(h)∣>ε)≤2∣H∣e−2nε2.\Pr\left( \exists h\in\mathcal H: |R(h)-\hat R_S(h)|>\varepsilon \right) \le2|\mathcal H|e^{-2n\varepsilon^2}.

令右侧不超过 δ\delta，便有：以至少 1−δ1-\delta 的概率，对所有 h∈Hh\in\mathcal H 同时成立

R(h)≤R^S(h)+log⁡(2∣H∣/δ)2n.R(h) \le\hat R_S(h) +\sqrt{\frac{ \log(2|\mathcal H|/\delta)}{2n}}.

值得注意的是，复杂度只以 log⁡∣H∣\log|\mathcal H| 出现，而误差随 1/n1/\sqrt n 缩小。这个结论还解释了为什么必须得到一致收敛：只有界对所有候选假设同时成立，才能安全地用于训练后选出的模型。

五、无限假设空间：Rademacher 复杂度

1. 定义与直觉

对样本 S=(x1,…,xn)S=(x_1,\ldots,x_n)，函数类 F\mathcal F 的经验 Rademacher 复杂度定义为

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_i f(x_i) \right],

其中 σi\sigma_i 独立地以相同概率取 +1+1 或 −1-1。

它测量函数类拟合随机符号的能力：如果一组函数连纯噪声标签也能轻易追随，它在有限样本上就具有较高复杂度；如果做不到，复杂度较低。关键是，它不仅看候选函数有多少，还看这些函数在当前样本上的实际行为。

2. 泛化界

若 f(x)∈[0,1]f(x)\in[0,1]，则存在常数约定略有不同的标准界：以至少 1−δ1-\delta 的概率，对所有 f∈Ff\in\mathcal F，

E[f(X)]≤1n∑i=1nf(xi)+2R^S(F)+3log⁡(2/δ)2n.\mathbb E[f(X)] \le\frac1n\sum_{i=1}^n f(x_i) +2\hat{\mathfrak R}_S(\mathcal F) +3\sqrt{\frac{\log(2/\delta)}{2n}}.

经验误差、函数类复杂度和置信项分别承担不同角色。前者由训练决定，中间项惩罚表达能力，最后一项随样本量增大而减小。

3. 线性函数类的例子

设

F={x↦w⊤x:∥w∥2≤B},∥xi∥2≤R.\mathcal F =\{\boldsymbol x\mapsto\boldsymbol w^\top\boldsymbol x: \|\boldsymbol w\|_2\le B\}, \qquad \|\boldsymbol x_i\|_2\le R.

利用对偶范数与 Jensen 不等式可得

R^S(F)≤BRn.\hat{\mathfrak R}_S(\mathcal F) \le\frac{BR}{\sqrt n}.

这说明控制权重范数确实能控制泛化复杂度。正则化不再只是优化中的经验技巧，它与函数类的有效容量直接相关。

4. 收缩性质

若损失 ℓ(y,⋅)\ell(y,\cdot) 关于预测值是 LL-Lipschitz 的，则大致有

Rn(ℓ∘F)≤LRn(F).\mathfrak R_n(\ell\circ\mathcal F) \le L\mathfrak R_n(\mathcal F).

因此可以先控制预测函数类的复杂度，再把结论传递给损失函数类。这是从模型约束推导风险界的重要桥梁。

六、增长函数：只计算样本上的分类方式

对二分类假设类 H\mathcal H，增长函数定义为

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

即使 H\mathcal H 本身是无限集合，它在 nn 个样本上能产生的二分方式仍可能有限。于是有限类证明中的 ∣H∣|\mathcal H| 可以被“样本上真正可区分的预测数量”替代。

对取值有界的有限函数集合，Massart 引理给出类似

R^S(F)≤r2log⁡∣F∣n\hat{\mathfrak R}_S(\mathcal F) \le \frac{r\sqrt{2\log|\mathcal F|}}{n}

的上界，其中 rr 控制对应预测向量的二范数。把它与增长函数结合，就能连接组合复杂度与 Rademacher 复杂度。

七、VC 维：能打散多少个点

1. 打散与 VC 维

若对一组 mm 个点的任意二元标记，都存在 h∈Hh\in\mathcal H 完全实现，则称 H\mathcal H 打散这组点。VC 维定义为可被打散的最大点数：

VCdim⁡(H)=max⁡{m:H 能打散某个 m 点集合}.\operatorname{VCdim}(\mathcal H) =\max\{m:\mathcal H\text{ 能打散某个 }m\text{ 点集合}\}.

它问的不是某组数据能否分类，而是是否存在一组位置最有利的点，让假设类实现全部 2m2^m 种标记。

2. Sauer 引理

若 dVC=VCdim⁡(H)<nd_{\mathrm{VC}}=\operatorname{VCdim}(\mathcal H)<n，则

ΠH(n)≤∑i=0dVC(ni)≤(endVC)dVC.\Pi_{\mathcal H}(n) \le\sum_{i=0}^{d_{\mathrm{VC}}}{n\choose i} \le\left(\frac{en}{d_{\mathrm{VC}}}\right)^{d_{\mathrm{VC}}}.

这一步非常关键：当 VC 维有限时，增长函数不再按 2n2^n 指数增长，而只按关于 nn 的多项式增长。

3. VC 泛化界

结合增长函数与集中不等式，可以得到代表性的统一收敛界

sup⁡h∈H∣R(h)−R^S(h)∣=O(dVClog⁡(n/dVC)+log⁡(1/δ)n).\sup_{h\in\mathcal H} |R(h)-\hat R_S(h)| =O\left( \sqrt{\frac{ d_{\mathrm{VC}}\log(n/d_{\mathrm{VC}}) +\log(1/\delta)}{n}} \right).

不同推导中的常数和对数项写法会略有差别，真正稳定的结构是：VC 维越大，需要的样本越多；固定复杂度时，泛化差距随 nn 增大而缩小。

4. 线性分类器的 VC 维

在 Rd\mathbb R^d 中，带偏置的线性分类器

hw,b(x)=sgn⁡(w⊤x+b)h_{\boldsymbol w,b}(\boldsymbol x) =\operatorname{sgn}(\boldsymbol w^\top\boldsymbol x+b)

的 VC 维为 d+1d+1。因此线性分类器虽然包含无限多个参数取值，其统计容量仍能由有限的维数刻画。这也提醒我们：集合“无限”并不等于“不可学习”，真正重要的是它能在有限样本上实现多少种独立选择。

八、怎样阅读一个泛化界

典型界可以概括为

真实风险≤经验风险+模型复杂度+置信项.\text{真实风险} \le \text{经验风险} +\text{模型复杂度} +\text{置信项}.

阅读时应检查四件事：

  1. 界是对固定模型成立，还是对整个假设空间同时成立？
  2. 损失是否有界，样本是否独立同分布？
  3. 复杂度依赖的是参数个数、范数、间隔，还是数据相关量？
  4. 它给的是最坏情形保证，还是足以预测实际测试误差的紧界？

泛化界经常偏松，但这不意味着它没有价值。它更像一张结构图：告诉我们哪些因素必须付出代价，哪些正则化确实缩小了函数类，以及为什么仅报告训练误差在逻辑上不够。

九、小结

本讲的推理主线是

有限样本⟶集中不等式⟶一致收敛⟶复杂度度量⟶泛化保证.\text{有限样本} \longrightarrow \text{集中不等式} \longrightarrow \text{一致收敛} \longrightarrow \text{复杂度度量} \longrightarrow \text{泛化保证}.

有限假设类用 log⁡∣H∣\log|\mathcal H| 计价；无限函数类可以用 Rademacher 复杂度、增长函数或 VC 维计价。它们形式不同，却共同表达一个朴素事实：学习不只是在训练集上找到低误差函数，还要限制“从多少种解释中挑中了它”。

更新日志

2026/9/27 10:05
查看所有更新日志
  • eea03-update 0927 japaneseVocabulary.js于

版权归属：Luminosity

许可证：署名-非商业性-相同方式共享 4.0 国际 (CC-BY-NC-SA-4.0)

Powered by VuePress and Plume Theme
Copyright © 2026.08.03 Luminosity