神经网络学习理论-1

网络学习理论

在这一章中，我们用严谨的数学语言建模各种问题的可学性，以及在可学的情况下，模型对未见数据的泛化误差（即模型的泛化能力）。同时，我们对模型的学习能力进行定量描述，研究目标为：

学习问题本身，包括采样的数据量的复杂度，这在 PAC 学习和 ERM 边界中描述
模型固有的表达能力，这在 VC 维中描述

归纳（Inductive）与直推（Transductive）

两种学习范式对比

在机器学习中，归纳学习（Inductive Learning）和直推学习（Transductive Learning）代表着两种不同的推理方式：

Inductive Learning：最常见的学习范式。其核心思想是：模型从训练数据中学习到一个通用的规则或模式，然后用这个规则对未见数据进行预测。归纳学习的目标是找到一个能够泛化到所有可能数据的模型

1 2	`model.fit(X_train, y_train) # 训练完成后丢弃训练数据 y_pred = model.predict(X_test) # 泛化到任意新样本`

Transductive Learning：直推学习的目标是直接针对特定的测试数据进行优化。在迁移学习中，模型在训练时就知道测试数据（但不知道测试数据的标签），并尝试直接对这些数据进行预测。

迁移学习的一个典型例子是伪标签（Pseudo-Labeling）方法。在这种方法中，模型首先对未标记数据进行预测，然后将高置信度的预测结果作为伪标签加入训练集，从而提高模型对特定数据的预测能力

1 2	`# 训练时已看到测试样本特征（无需标签） transductive_model.fit(X_train + X_test, y_train)`

在默认情况下，我们的学习理论算法是对 inductive 学习的方式进行的

归纳偏置（Inductive Bias）

任何学习算法都必须具备某种形式的归纳偏置，否则无法进行有效学习（"无免费午餐"定理）。常见偏置类型：

偏置类型	实例	作用机制
奥卡姆剃刀	决策树剪枝	偏好简单假设
局部平滑性	CNN的卷积核	空间局部特征提取
时序依赖性	RNN/LSTM的循环结构	捕捉时间序列模式
权重衰减	L2正则化	抑制模型复杂度

Learnability and Empirical Risk Minimization (ERM)

研究学习理论的直接 intuition 是：什么样的学习问题是可学习的？ 这给出**可学习性（Learnability）**的概念的定义。一个学习问题是可学习的，当且仅当存在一个算法，能够在有限的训练数据下，以较高的概率达到较低的误差。

为了用数学形式化表达这一问题，引入 PAC学习（Probably Approximately Correct Learning）的概念。用于形式化机器学习算法在有限样本下能够泛化到未见数据的条件。PAC学习为理解学习算法的行为和性能提供了严格的理论基础，帮助我们确定学习算法在有限样本下能够泛化的条件。PAC学习的目标是找到一个模型，使其在大多数情况下（高概率）能够近似正确地分类数据：

PAC辨识(PAC Identify)：

PAC辨识：给定 $0 < \epsilon,\delta < 1$ ，对所有概念 $c \in \mathcal{C}$ 和分布 $p$ ，若存在学习算法 $L$ ，其输出假设 $h \in \mathcal{H}$ 满足

P\left( {E\left( h\right) \leq \epsilon }\right) \geq 1 - \delta \\ E\left( h\right) \overset{def}= \mathbb{E}_{(x,y) \sim p}\left[\mathcal{L}(h(x) ,y)\right]

则称学习算法 $L$ 能从假设空间 $\mathcal{H}$ 中PAC辨识概念类 $C$ 。

PAC可学(PAC learnable)：

在计算机中，复杂度的大小是非常重要的，即使一个问题 PAC 可辨识的，如果需要样本的数量过大的话（非多项式复杂度），我们仍然认为这个问题是不可学习的，因此引入 PAC 可学的概念：

令 $D$ 表示从分布 $p$ 中独立同分布地采样得到的数据集，其大小为 $N$ ，给定 $0<\epsilon,\delta < 1$ ，对所有分布 $p$ ：

若存在学习算法 $L$ 和多项式函数 $\operatorname{poly}(\cdot,\cdot,\cdot,\cdot)$
使得对于任何 $N \geq \operatorname{poly}\left( {\frac{1}{\epsilon },\frac{1}{\delta},\operatorname{size}(x) ,\operatorname{size}(c) }\right) ,L$ 能从假设空间 $\mathcal{H}$ 中PAC辨识概念类 $C$ 。其中 $\operatorname{size}(x)$ 表示数据本身的复杂度， $\operatorname{size}(c)$ 表示概念的复杂度，则称概念类C对假设空间 $\mathcal{H}$ 而言是 PAC 可学的，简称概念类 $C$ 是 PAC 可学的
满足 PAC 学习算法 $L$ 所需的最小数据集大小 $N$ ，称为学习算法 $L$ 的样本复杂度

称这个问题是 PAC 可学的

假设空间 ERM 边界&泛化误差

泛化误差是衡量模型在未观测数据上的预测误差的重要指标。它表示模型在独立同分布的新样本上的平均损失。具体来说，假设我们有一个损失函数 $\mathcal{L}(y, f(x))$ ，其中 $y$ 是真实值， $f(x)$ 是模型的预测值，则泛化误差可以定义为：

R(f) = \mathbb{E}[\mathcal{L}(Y, f(X))] = \int_{X \times Y} \mathcal{L}(y, f(x)) p(x, y) dx dy

在训练数据集上对泛化能力的经验估计是：

\hat{R}(f) = \frac{1}{N}\sum_{i=1}^N\mathcal{L}(y_i, f(X_i))

可以证明，对任意函数 $f \in \mathcal{F}$ ，有不小于 $1-\delta$ 的概率满足：

R(f) \le R(\hat{f} ) + \epsilon(d, N, \delta)

其中 $\epsilon(d, N, \delta) = \sqrt{\frac{1}{2N}\left( \log d + \log \frac{1}{\delta}\right)}$ ， $N$ 为训练实例个数， $d$ 为假设集的函数个数（证明见后 appedix）

实例分析

对于大多数情况的假设类，包括任何用实数参数化的假设类都是包含无数个函数的，但是由计算机量化实数的情况下就会变成是有限个：

假设我们有一个假设空间（hypothesis space） $\mathcal{H}$ ，由 $m$ 个实数参数化，再假设实数的表示为 float 类型，即一个实数用 32 位数字表示，则 $\epsilon(d, N, \delta)$ 可以计算为：

\begin{align} \epsilon(d, N, \delta) &= \sqrt{\frac{1}{2N}\left( \log d - \log\delta \right)}\\ &=\sqrt{\frac{1}{2N}\left( \log 2^{32m} - \log\delta \right)} \\ &=\sqrt{\frac{1}{2N}\left( 32m - \log\delta \right)}\\ \end{align} \Rightarrow N = \frac{1}{2\epsilon^2}(32m + \log\frac{1}{\delta})

由于 $\epsilon, \delta$ 只是额定设置的参数（数学意义上的），因此样本量的阶数可以表示为：

N = \frac{1}{2\epsilon^2}(32m + \log\frac{1}{\delta}) = O_{\delta, \epsilon}(m)

这代表着样本复杂度应该和模型参数量成正比的关系，才能保证大模型的效果不会比小模型差

附录：泛化误差约束定理

对于一个固定的假设 $h$ ，Hoeffding不等式告诉我们：

P\left(\left| R(h) - \hat{R}(h)\right| \geq \epsilon \right) \leq 2\exp \left(-2N\epsilon^2\right)

由于 $\mathcal{H}$ 为有限集，设 $d$ 为集合的元素个数，设 $\hat{R}(h)$ 是假设 $h$ 在训练数据上的经验误差， $R(h)$ 是假设 $h$ 的真实误差， $N$ 是训练样本的数量， $\epsilon$ 是误差界，则有

\begin{align} P\left(\exists h \in \mathcal{H} : \left| R(h) - \hat{R}(h)\right| \geq \epsilon \right) &= P\left(\bigcup_{h \in \mathcal{H}} \left| R(h) - \hat{R}(h)\right| \geq \epsilon \right) \\ & \leq \sum_{h \in \mathcal{H}} P\left(\left| R(h) - \hat{R}(h)\right| \geq \epsilon \right) \\ &= d\exp \left(-2N\epsilon^2\right) \\ \end{align}

另 $\delta$ 参数化为 $\delta= d\exp \left(-2N\epsilon^2\right)$ ，我们希望 PAC 可学的条件为

P\left(\exists h \in \mathcal{H} : \left| R(h) - \hat{R}(h)\right| \geq \epsilon \right) \le d\exp \left(-2N\epsilon^2\right)\\ \Leftrightarrow P\left(\forall h \in \mathcal{H} : \left| R(h) - \hat{R}(h) \right| \lt \epsilon \right) \ge 1 - d\exp \left(-2N\epsilon^2\right)

则泛化误差 $\epsilon$ 以 $1-\delta$ 的概率被约束住：

P(R(f) \lt \hat{R}(f) + \epsilon) \ge 1 - \delta

误差界的表达式为：

\epsilon = \sqrt{\frac{1}{2N} \log \frac{d}{\delta}}

VC 维

我们还需要对模型的表达能力去进行刻画

5. 对深度学习的启示

结构偏置设计：CNN/Transformer等架构编码了先验知识
隐式正则化：SGD的噪声引入有助于泛化
双下降现象：挑战传统偏差-方差权衡理论
现代泛化理论：基于范数边界、稳定性分析的新视角

“All models are wrong, but some are useful.” — George Box

以上的学习理论都是在统计学习的范畴内对模型的学习理论的刻画，现代的深度学习模型已经跳出了这个范畴

1. **有限容量假设**  
   VC维理论要求假设空间大小与样本量匹配，而现代神经网络参数量常远超样本数（如GPT-3参数量达1750亿）

2. **偏差-方差权衡**  
   传统曲线显示测试误差先降后升，但深度学习出现"双下降"现象：
   ![双下降曲线](https://ai.stanford.edu/blog/assets/img/2020-12-14-deep-double-descent/learning-curves.png)

3. **显式正则化需求**  
   传统理论强调L1/L2正则化的重要性，但SGD本身具有**隐式正则化**效应：
   ```python
   # 实际训练代码常不加显式正则化
   optimizer = SGD(net.parameters(), lr=0.1, momentum=0.9)

深度学习带来的理论挑战

现象级突破

传统预测	深度学习实践	矛盾点
过参数化导致过拟合	参数量↑ → 泛化能力↑	"更多参数更好用"之谜
训练误差=0时泛化崩溃	完美拟合噪声仍能泛化	标签噪声鲁棒性
凸优化理论适用	非凸损失函数成功优化	损失曲面几何特性

理论新边疆

函数空间复杂度
从参数空间转向函数空间度量，使用**神经切线核（NTK）**分析无限宽网络：

math

复制
1
\lim_{width→∞} \mathbb{E}[f(x)f(y)] = \Theta^{(L)}(x,y)
隐式正则化路径
SGD动态引导参数走向平坦极小值：
压缩感知理论
数据低维流形结构与网络架构的适配性：

math

复制
1
\mathcal{M}_{data} \subset \mathbb{R}^d,\quad dim(\mathcal{M}_{data}) \ll d

新旧理论的融合演进

保留的有效原则

归纳偏置的核心地位
Transformer的注意力机制编码了动态权重分配先验
PAC学习框架扩展
引入计算复杂度约束的新PAC分析：

复制
1
PAC + poly-time → CPAC (Computational PAC)
稳定性分析
均匀稳定性理论解释SGD的泛化优势：
1
\mathbb{E}[|ℓ(h_S,z)−ℓ(h_{S^i},z)|] ≤ β

新兴理论工具

工具	解释维度	典型结论
信息瓶颈理论	信息压缩	网络分阶段拟合噪声/信号
平均场理论	参数分布演化	描述无限宽网络训练动态
随机矩阵理论	梯度协方差分析	解释梯度爆炸/消失现

learning_theory2 上一篇

神经网络学习理论-1 下一篇