统计学习理论

概述

统计学习理论为机器学习提供了严格的数学基础，回答了"为什么学习能成功"和"需要多少数据"等根本性问题。本文涵盖 PAC 学习框架、VC 维、泛化界、偏差-方差分解等核心概念。

1. PAC 学习框架

1.1 定义

PAC（Probably Approximately Correct）学习由 Valiant（1984）提出：

目标：学习器能否以高概率找到一个近似正确的假设？

形式定义：假设类 \(\mathcal{H}\) 是 PAC 可学习的，如果存在算法 \(A\)，对于任意：

误差参数 \(\epsilon > 0\)
置信参数 \(\delta > 0\)
数据分布 \(\mathcal{D}\)

只要样本量满足 \(m \geq m_0(\epsilon, \delta)\)，算法 \(A\) 输出假设 \(h\) 满足：

\[ P\left[R(h) - R(h^*) \leq \epsilon\right] \geq 1 - \delta \]

其中 \(R(h) = \mathbb{E}_{(x,y)\sim\mathcal{D}}[\ell(h(x), y)]\) 是真实风险。

1.2 有限假设类的 PAC 界

对于有限假设类 \(|\mathcal{H}| < \infty\)，需要的样本量：

\[ m \geq \frac{1}{\epsilon}\left(\ln|\mathcal{H}| + \ln\frac{1}{\delta}\right) \]

含义：

假设空间越大，需要的样本越多
要求的精度越高（\(\epsilon\) 越小），需要的样本越多
要求的置信度越高（\(\delta\) 越小），需要的样本越多

2. VC 维

2.1 打散（Shattering）

给定数据点集合 \(S = \{x_1, \ldots, x_m\}\)，如果假设类 \(\mathcal{H}\) 能实现 \(S\) 上所有 \(2^m\) 种二分类标签组合，则称 \(\mathcal{H}\) 打散 \(S\)。

2.2 增长函数

增长函数衡量假设类在 \(m\) 个点上的最大分类能力：

\[ \Pi_{\mathcal{H}}(m) = \max_{S:|S|=m} \left|\{(h(x_1), \ldots, h(x_m)) : h \in \mathcal{H}\}\right| \]

显然 \(\Pi_{\mathcal{H}}(m) \leq 2^m\)。

2.3 VC 维定义

假设类 \(\mathcal{H}\) 的 VC 维（Vapnik-Chervonenkis dimension）\(d_{VC}\) 是能被 \(\mathcal{H}\) 打散的最大点集大小：

\[ d_{VC}(\mathcal{H}) = \max\{m : \Pi_{\mathcal{H}}(m) = 2^m\} \]

2.4 经典示例

假设类	VC 维	说明
\(\mathbb{R}\) 上的阈值函数	1	能打散 1 个点，不能打散 2 个
\(\mathbb{R}^2\) 上的线性分类器	3	能打散 3 个非共线点
\(\mathbb{R}^d\) 上的线性分类器	\(d + 1\)
\(k\) 个区间的并集	\(2k\)
有 \(W\) 个权重的神经网络	\(O(W \log W)\)	近似结果

2.5 Sauer 引理

\[ \Pi_{\mathcal{H}}(m) \leq \sum_{i=0}^{d_{VC}} \binom{m}{i} \leq \left(\frac{em}{d_{VC}}\right)^{d_{VC}} \]

当 \(m > d_{VC}\) 时，增长函数从指数增长变为多项式增长。

3. 泛化界

3.1 VC 泛化界

对于 VC 维为 \(d\) 的假设类，以概率至少 \(1-\delta\)：

\[ R(h) \leq \hat{R}(h) + \sqrt{\frac{d(\ln(2m/d) + 1) + \ln(4/\delta)}{m}} \]

其中 \(\hat{R}(h) = \frac{1}{m}\sum_{i=1}^{m}\ell(h(x_i), y_i)\) 是经验风险。

解读：

\[ \text{泛化误差} \leq \text{训练误差} + \text{复杂度惩罚} \]

复杂度惩罚 \(\propto \sqrt{d/m}\)
当 \(m \gg d\) 时，训练误差近似泛化误差

3.2 所需样本量

要使泛化界有意义，大约需要：

\[ m = O\left(\frac{d}{\epsilon^2}\right) \]

个样本，其中 \(d = d_{VC}\)，\(\epsilon\) 是可接受的泛化间隙。

4. 偏差-方差分解

对于回归问题，预测误差可以分解为三部分：

\[ \mathbb{E}\left[(y - \hat{f}(x))^2\right] = \underbrace{\left(\mathbb{E}[\hat{f}(x)] - f(x)\right)^2}_{\text{Bias}^2} + \underbrace{\mathbb{E}\left[(\hat{f}(x) - \mathbb{E}[\hat{f}(x)])^2\right]}_{\text{Variance}} + \underbrace{\sigma^2}_{\text{Noise}} \]

成分	来源	含义
偏差 \(\text{Bias}^2\)	模型假设	模型不够灵活，系统性地偏离真实值
方差 \(\text{Variance}\)	数据随机性	模型对训练数据的变化过于敏感
噪声 \(\sigma^2\)	数据本身	不可约的随机误差

偏差-方差权衡

误差
  │  \                    /
  │   \  偏差²          / 方差
  │    \              /
  │     \_____●_____/    ← 最优复杂度
  │      总误差最小点
  │
  └───────────────────→ 模型复杂度
     欠拟合    适中    过拟合

模型复杂度	偏差	方差	表现
低（如线性回归）	高	低	欠拟合
适中	中	中	最优
高（如深度网络）	低	高	过拟合

5. 结构风险最小化（SRM）

Vapnik 提出的学习原则，在经验风险和模型复杂度之间取平衡：

\[ \hat{h} = \arg\min_{h \in \mathcal{H}} \left[\hat{R}(h) + \Omega(\mathcal{H})\right] \]

其中 \(\Omega(\mathcal{H})\) 是复杂度惩罚项。

实例：

方法	复杂度控制 \(\Omega\)
L2 正则化（Ridge）	\(\lambda\\|w\\|^2\)
L1 正则化（LASSO）	\(\lambda\\|w\\|_1\)
SVM	最大化间隔 ↔ \(\\|w\\|^2\)
决策树剪枝	叶节点数
神经网络	Dropout, Weight Decay, 早停

6. Rademacher 复杂度

比 VC 维更精细的复杂度度量，考虑了数据分布。

定义：

\[ \hat{\mathfrak{R}}_m(\mathcal{H}) = \mathbb{E}_{\sigma}\left[\sup_{h \in \mathcal{H}} \frac{1}{m}\sum_{i=1}^{m}\sigma_i h(x_i)\right] \]

其中 \(\sigma_i \in \{+1, -1\}\) 是均匀随机变量（Rademacher 变量）。

直觉：Rademacher 复杂度衡量假设类拟合随机噪声的能力。能拟合纯噪声的假设类复杂度高。

泛化界：

\[ R(h) \leq \hat{R}(h) + 2\mathfrak{R}_m(\mathcal{H}) + \sqrt{\frac{\ln(1/\delta)}{2m}} \]

7. 没有免费午餐定理（NFL）

7.1 定理内容

Wolpert & Macready（1997）：

在所有可能的问题上取平均，没有任何学习算法优于其他算法。对于每个在某些问题上表现好的算法，必然存在另一些问题使其表现差。

7.2 形式化

对于所有学习算法 \(A_1, A_2\) 和均匀分布的目标函数：

\[ \sum_{f} R_{f}(A_1) = \sum_{f} R_{f}(A_2) \]

7.3 实际意义

不存在万能算法：需要根据问题特点选择算法
先验知识很重要：归纳偏置（Inductive Bias）决定了算法在哪些问题上好
不否定比较：在特定问题/分布上，算法有优劣之分

归纳偏置	假设	对应方法
平滑性	相似输入→相似输出	KNN, 核方法
稀疏性	只有少数特征重要	LASSO, 稀疏编码
层级结构	数据有层级特征	深度学习
时间平稳性	统计特性随时间不变	时间序列模型

8. 总结

统计学习理论核心问题：

Q: 为什么学习能成功？
A: 如果假设类不太复杂（VC 维有限），
   且样本量足够大，
   则经验风险趋近真实风险。

Q: 需要多少数据？
A: m = O(d_VC / ε²)

Q: 如何选择模型复杂度？
A: 偏差-方差权衡 / 结构风险最小化

Q: 最好的算法是什么？
A: 没有免费午餐——取决于问题。

参考资料

"Foundations of Machine Learning" - Mohri, Rostamizadeh, Talwalkar
"Understanding Machine Learning" - Shalev-Shwartz & Ben-David
"The Nature of Statistical Learning Theory" - Vapnik
"An Introduction to Computational Learning Theory" - Kearns & Vazirani