偏差与方差
这一部分是整个机器学习理论中最优美的章节之一。之前的目光聚焦到“如何训练模型（降低 Loss）”，而现在我们来看看“模型为什么会犯错”。
首先我们要建立一个所谓上帝视角。在现实中，我们只有一份训练数据$D$，但在理论分析中，我们要想象存在无数个平行宇宙。
假设在这个世界上，$x$和$y$拥有一个真实的，完美的函数关系，只不过就是被噪音干扰了：
$$y = TrueFunction(x) + \epsilon$$
那么这个“真实函数”我们通过数学化定义为$E[y|x]$，也就是给定x之后y的期望值。我们用它来表明排除噪音$\epsilon$之后，世界的本来面目。
我们的处境是怎样呢？
我们在某个平行宇宙中收集到了一份特定的数据集：$D = {(x_1, y_1), ..., (x_m, y_m)}$，随后我们用这个$D$训练出了一个模型，我们记作$f(x;D)$。其中：
- $x$是输入，$D$是随机变量。这意味着如果再另一个平行宇宙，数据的噪音哪怕改变了一点点，那么我们训练出的模型$f(x;D')$就长得不一样。
而我们的目标衡量对于一个固定的测试点，我们的模型$f(x;D)$预测的$y$和真实的$y$查了多少？我们可以用均方误差MSE来进行衡量：
$$ \text{Error} = E_{D, \epsilon} \left[ (y - f(x; D))^2 \right] $$
其中，这里的期望 $E$ 是对所有可能的训练集 $D$ 和所有可能的噪音 $\epsilon$ 求平均。也就是说，我们想知道这个算法“平均而言”表现如何。
那么我们要对这个Error公式进行一个开膛破肚。首先把$(y - f(x;D))^2$拆开。为了能够做到这一点，我们需要引入一个概念，叫平均模型 (Expected Model)，记作$\bar{f}(x) = E_D[f(x; D)]$。真实的函数值应当是$E[y|x]$。
假设你训练了1000次模型，每次的数据都不一样。但是你把这1000条曲线叠加起来求得平均值，你就得到了一个非常稳定的平均模型$\bar{f}(x)$。
接下来我们要做一件数学上很漂亮的事：把"误差"这个笼统的概念，精确地分解成三个独立的部分。这个分解过程有点长，但值得坚持。让我告诉你接下来会发生什么：
- 首先，我们把噪音剥离出来（不可约误差）
- 然后，我们把"模型学歪了"和"模型太敏感"分开（偏差 vs 方差）
- 最后，我们得到一个干净利落的公式：$Total Error = Bias^2 + Variance + Noise$
首先剥离噪音：
我们要计算$E[(y - f(x; D))^2]$。我们在括号里减去一个$E[y|x]$，再加上一个$E[y|x]$，我们就得到了：
$$ y - f(x; D) = (y - E[y|x]) + (E[y|x] - f(x; D)) $$
等式两边取平方，并取期望$E$。我们就得到了：
$$E[(y - f(x; D))^2] = E[(A+B)^2] = E[A^2] + E[B^2] + 2E[AB] $$
其中，记：
- $A = y - E[y|x]$: 这是纯噪音 $\epsilon$。
- $B = E[y|x] - f(x; D)$: 这是模型和真理的差距。
- 交叉项 $2E[AB]$: 因为噪音 $\epsilon$ 是随机的，且均值为 0，它和模型 $f$ 无关。所以这一项的期望是 0。
于是，误差的第一部分出现了：
$$ E[A^2] = E[(y - E[y|x])^2] = \text{Variance of Noise} $$
这是不可约误差 (Irreducible Error)。无论你模型多牛，这部分误差（比如传感器本身的精度）你永远消除不掉。
接下来，剥离偏差与方差：
现在我们只剩下第二项：$E[B^2] = E_D [ (E[y|x] - f(x; D))^2 ]$。
我们在里面插入那个“中间人” $\bar{f}(x)$，并做一个和刚才一样的加减变换：
$$E[B^2] = (E[y|x] - \bar{f}(x)) + (\bar{f}(x) - f(x; D)) $$
再次平方展开：
第一部分：$(E[y|x] - \bar{f}(x))^2$。
- 这是真理与平均模型的差距。我们管它叫Bias (偏差)的平方。它衡量了你的模型是否由于太简单而学歪了。
第二部分：$E_D [ (\bar{f}(x) - f(x; D))^2 ]$。
- 这是平均模型与具体某次训练出的模型的差距。这叫方差。它衡量了你的模型是否对数据太敏感，换一波数据就剧烈波动。
交叉项再次为 0（数学推导略，原理同上，常数与随机变量偏差的积的期望）。
最终我们得到：
$$ \text{Total Error} = \text{Bias}^2 + \text{Variance} + \text{Noise} $$
公式推完了，那么这到底意味着什么？
High Bias (高偏差) = 欠拟合 (Underfitting)
想象你正在尝试用一条直线（1st order）去拟合一个正弦波。无论你换多少次数据集，这条直线的“平均位置”离真实的正弦波都很远。它太僵硬了，根本学不到数据的规律。因此，训练误差大，测试误差也大。
High Variance (高方差) = 过拟合 (Overfitting)
现在你尝试用一个 50 次多项式去拟合几个点。正如我们之前所说，它会疯狂扭曲去穿过每一个点。
如果你做无数次实验取平均，这团乱麻的中心其实挺接近真理的（平均线是对的）。但是具体的某一次，你的线可能飞到天上去。因为数据里的一点点噪音就会导致模型发生剧烈变化。因此这些模型的训练误差极小，测试误差极大。
我们想要 Bias 和 Variance 都小，但这很难。我们可以增加模型复杂度（比如增加多项式次数，或者加深神经网络）这样一来：
- Bias $\downarrow$， 模型更灵活，能拟合复杂规律。但是：
- Variance $\uparrow$更敏感，更容易被噪音带偏
我们寻找的“甜点” (Sweet Spot): 就是代表模型泛化能力最强的时刻。在这个点上，模型刚好足够复杂，能够捕获到数据背后的真实规律（Bias够低），同时又足够简单，没有去强行记忆数据里的随即噪音（Variance够低）。
看这个图，如果太靠左，那么你可能还在尝试使用线性回归来做图像识别。模型太简单了不好拟合，所以你啥也学不到。
如果太靠右，那么你可能尝试使用一个1000层的神经网络去尝试拟合10个数据点。这太复杂了，bro把噪点全部背下来了。
你想要找到的甜点就是那个中间的那条蓝色的4th order的线。这就是我们训练模型时想要达到的终极形态。
讲清楚什么是偏差和方差，现在我们就跳出平均情况的假设，讨论一下“我到底要需要多少数据，才能保证我训练的模型是靠谱的”？
PAC理论
在刚才的偏差方差分析中，我们还在用$y - f(x)$这种连续纸的误差。它告诉我们“模型太复杂会High Variance，太简单会High Bias”，是一个解释现象的思维工具。
接下来我们使用PAC理论进行定量分析。我们试图为偏差方差分析中的方差部分划定一个数学上限。现在为了理论推导方便，我们需要回到最简单的二分类问题，也就是 $y \in {0, 1}$。
首先，如果bro是上帝，那么你应该就能知道什么是真实误差 (True Error / Generalization Error)。这个数据表示在整个数据分布$D$上，你的模型$h$犯错的概率：
$$err(h) = P_{x~D}[h(x) \neq c^{*}(x)]$$
这就是那个我们想要知道，但是永远无法直接算出来的数据。
现在回到凡人视角。我们能算出来的误差叫做经验误差(Empirical Error / Training Error)。这个数据表示在我们手头$m$个样本集$S$上，我们的模型$h$犯错的比例：
$$err_S(h) = \frac{1}{m} \sum_{i=1}^m \mathbb{I}[h(x_i) \neq y_i]$$
那么你就在想了：如果能够证明数据量 $m$ 足够大，经验误差 $err_S(h)$ 就会非常接近真实误差 $err(h)$，这样如果我们算出训练误差很低，就可以自信地说：真实误差肯定也很低了。
可靠环境样本复杂度
那我们就假设完美的上帝函数$c^*$包含在我们的备选模型库，假设空间$H$里面。这意味着如果我们搜遍$H$，则我们一定能找到一个模型使得它的训练误差为0。假设空间类似你想要找的函数的范围，例如约定指数函数，多项式还是其它类型的函数。
那么我们假设$H$是有限的，我们需要找多少样本$m$才能保证我们找到的那个“训练误差为0”的模型，它的“真实误差”小于$\epsilon$的概率至少是$1-\delta$？其中：
- $\epsilon$ (Epsilon): 误差容忍度（比如 0.05，即 95% 准确）。
- $\delta$ (Delta): 失败概率（比如 0.01，即我们有 99% 的信心）。
我们定义泛化差距 (Generalization Gap) 为：
$$|err(h) - err_S(h)| \le \epsilon$$
这个差距越大，说明模型越不稳定，Variance越大。我们想要知道如果我们想将Variance压倒$\epsilon$这么小，我们需要多少数据？
则我们通过样本复杂度公式 (Sample Complexity) 可以算出这个值：
$$ m \ge \frac{1}{\epsilon} \left( \ln|H| + \ln\frac{1}{\delta} \right) $$
公式推导过程大概是：
如果一个模型很烂（真实误差 $> \epsilon$），我们暂且称其为“坏模型”。
那么这个坏模型在1 个数据点上蒙混过关的概率是 $< (1-\epsilon)$。它在 $m$ 个 数据点上全部蒙混过关（训练误差保持为 0）的概率是 $< (1-\epsilon)^m \approx e^{-m\epsilon}$。
由于我们一共有 $|H|$ 个模型。所有坏模型里只要有一个蒙混过关，就算失败。因此我们要把所有坏模型漏网的概概率使用Union Bound (联合界)加起来:
$$P(\text{Any bad h survives}) \le |H| \cdot P(\text{One bad h survives})$$
- 我们要让这个坏事发生的概率 $\le \delta$。解这个不等式，就得到了上面的 $m$ 公式。
这样，我们就可以通过PAC理论，来判断：“只要数据量满足公式，我的模型保证在未知数据上也有效”了。
观察公式，你会发现在这里，$m$ 与 $1/\epsilon$ 成 线性 (Linear) 关系。这说明学习很高效，为了提升精度，你需要的数据量与其成线性关系。
不可靠环境样本复杂度
但现实是残酷的。完美的函数 $c^*$ 可能极其复杂，根本不在我们的线性模型库 $H$ 里。或者数据本身就有噪音（同样的 $x$ 有时是 0 有时是 1）。
这时，即使是最好的模型，训练误差也不可能是 0。我们只能追求 “无限逼近真实误差”。
这个定理描述了，我们要找多少样本 $m$，才能保证对于所有的模型 $h$，经验误差和真实误差的差距 $|err_S(h) - err(h)|$ 不超过 $\epsilon$？
则样本复杂度公式：
$$ m \ge \frac{1}{2\epsilon^2} \left( \ln(2|H|) + \ln\frac{1}{\delta} \right) $$
你会发现分母变成了 $2\epsilon^2$。在刚才讲到的可靠情况是 $1/\epsilon$。在 现在的不可靠情况下是 $1/\epsilon^2$。这意味着如果你想要提升精度降低误差，那么你需要的数据量就增长更快。这就是为什么现实中的高精度模型往往需要海量数据。
样本复杂度公式的实际用途主要在于知道“量级”和“趋势”的变化关系。例如，如果我们想让精度翻倍，也就是$\epsilon$减半，我们需要手机多少数据？
这样我们就可以通过公式算出来，在可靠环境下你需要收集两倍多的数据，不可靠环境下为四倍。
VC维
回顾上一张的可靠环境样本复杂度公式：
$$ m \ge \frac{1}{\epsilon} \left( \ln|H| + \ln\frac{1}{\delta} \right) $$
这证明我们需要的数据量$m$与模型数量$|H|$的对数成正比。
哪怕是最简单的 “一维线性分类器”（在数轴上找个点切一刀），因为切点$\theta$可以是任意实数，所以可能的模型数量是无穷大的。$|H| = \infty$
如果直接带入公式，$\ln \infty = \infty$，这意味着我们需要无限多的数据才能训练一个最简单的分类器。这显然是荒谬的，因为我们知道线性分类器很好训练。
所以我们得出结论，直接使用数量$|H|$来衡量模型的复杂度还是太粗糙了。我们需要一把更精细的尺子，用来衡量无限集合的“丰富程度”或“表达能力”。这把尺子就是VC维 (Vapnik-Chervonenkis Dimension)。
在定义VC维之前，我们需要先理解什么是打散 (Shattering)
打散指的是一个假设类能够对某个有限样本集合的所有可能标记方式都能找到对应的分类器来实现。人话来说，模型能够完全区分该集合的所有标签组合。
假定一个假设类$H$和一个样本集合$S = {x_1, x_2, ..., x_n}$。如果对于集合$S$上的所有可能的标签组合，都存在一个假设$h \in H$，使得$h(x_i)$与该标签完全一致，那么我们就说假设类打散了集合$S$。模型能把样本集合的所有可能分类方式都覆盖到。
例如集合里面有三个点，那么对于二分类问题来讲，可能的标记方式就一共有$2^3$种。模型对于这$m$个点拥有上帝般的控制力。无论你怎么标正负，它都能画出一条边界线把他们分开。
现在我们就可以定义这把“尺子”了。
我们定义一个假设空间$H$的VC维，是它所能打散的最大样本数量，记作$d = VCdim(H)$。这包含两层意思：
- 世界上至少存在某一组$d$个点，可以被$H$打散。同时：
- 世界上不存在任何一组$d + 1$个点，可以被$H$打散。
这意味着一旦数据量达到$d + 1$，模型的神力就失效了，它再也没办法拟合所有可能的标签组合了。因为一定会出现某些标签的排列组合，是这个模型死活分不开的。
这一刻就是模型复杂度的极限。
Talk is cheap, show me the examples：
阈值分类器
假设我们的模型是一个阈值分类器。我们会在数轴上选一点$a$，左边是0，右边是1。
一个点可以打散吗？可以。点在$x$，如果要标0，那就把切点$a$放在右边；如果要标1，那就反过来把$a$放在左边。
两个点$(x_1, x_2)$可以打散吗？不难看出我们要实现四种组合：(0, 0), (1, 1), (0, 1), (1, 0)
前三种都好办，但是(1, 0)怎么办？这要求$x_1$是1，放在右边，$x_2$是0，放在左边。但是物理位置上$x_1$在$x_2$的左边。假设方向固定，分类器没法做到这样的分类。
于是我们得出结论：能打散一个，打不散两个。VC维就为1。
那么想象一个区间分类器：我们要做的事在数轴上选个区间$[a, b]$。区间内是1，区间外是0。
同理，两个点怎么标都可以分开，但是三个点$x_1, x_2, x_3$就出问题了。由于我们想要实现(1, 0, 1)，也就是说$x_1$到$x_3$分别是正负正。由于$x_2$夹在中间，如果你想用一个联通的区间包住$x_1$和$x_3$，就会不可避免地把中间的$x_2$也包含进去。所以我们在3失败了。
于是我们得出结论，这样的一个分类器VC维是2。
我们能得出什么规律呢？对于$d$维空间的线性分类器，它的VC维是$d + 1$。 这就是为什么线性回归或逻辑回归中的特征维度$d$如此重要，因为它直接决定了模型的VC维，也就是复杂度。
反过来想，假设对于 2D 线性分类器（VC=3）。如果我有 3 个点，它们不幸共线，你没法把中间的点标为 + 而两头的点标为 - 。这是否意味着 VC 维就变成 2 了？
根据下界的条件和VC维的定义，存在一组$d$个点就可以被打散。只要你能找到一组数据能够被切开，那么VC维就是3。至于这组共线点那就是它们自己的问题，不影响模型的能力上限。
样本复杂度界限
还记得我们之前的问题吗？之前的公式内存在$\ln |H|$。对于线性分类器来说，$|H|$是无穷大，公式失效。因此我们需要用刚学到的VC维$d$来替换掉尴尬的$|H|$。
绍尔引理 (Sauer's Lemma)
如果模型H的VC维是$d$，那这意味着什么？这意味着当数据量$m \le d$时，模型简直无人能挡，能够打散所有$2^m$种组合。
绍尔引理在此之上告诉我们一个事实：一旦数据量超过了模型能力的极限，也就是$m > d$，那么模型能产生的不同标签组合数量就会急剧下降。
因此，我们就可以使用“在$m$个数据上的有效模型数量”来替代$|H|$：
$$ln(Effective |H|) \approx ln(m^d) = d\ln(m)$$
我们就解决了无穷大的$|H|$的问题，取而代之的是有限的$d$和$\ln(m)$
既然我们解决了这一点，我们就回去来得到通用的样本复杂度公式吧：
- 可靠环境样本复杂度：
$$ m \ge C \cdot \frac{1}{\epsilon} \left( d \ln \frac{1}{\epsilon} + \ln \frac{1}{\delta} \right) $$
可以得到$m$的大致量级：$m \approx \frac{d}{\epsilon}$。
这意味着你需要的样本量，大概是你的模型复杂度 ($d$) 的倍数。这就解释了为什么深度学习需要海量数据。
- 不可靠环境样本复杂度：
$$ m \ge C \cdot \frac{1}{\epsilon^2} \left( d + \ln \frac{1}{\delta} \right) $$
$m$的大致量级：$m \approx \frac{d}{\epsilon^2}$。
泛化误差最终公式
那么我们知道数据量为$m$，我们有没有办法找到真实误差$L(f)$最坏是多少？
可以：
$$ L(f) \le \hat{L}(f) + \sqrt{\frac{d \ln m + \ln(\frac{1}{\delta})}{m}} $$
这个公式比较高光了。它包含了两部分：
- Training Loss $\hat{L}(f)$: 你的模型在训练集上表现多好？（Bias 部分）
- Complexity Penalty $\sqrt{\frac{d \ln m + \ln(\frac{1}{\delta})}{m}}$: 你的模型有多复杂？（Variance 部分）
- 分子是 $d$ (VC 维)：模型越复杂，惩罚越大。
- 分母是 $m$ (数据量)：数据越多，惩罚越小（根号速度衰减）。
到最后，我们发现我们实际上目标是要寻找一个模型，既能让 Training Loss 小，又让 VC 维 $d$ 小。这不就是我们上一章学的 正则化 (Regularization) 吗？你看：
- Training Loss $\to$ 数据拟合项。
- Complexity Penalty $\to$ 正则项 ($\lambda |\theta|^2$)。
最后兜兜转转，理论证明了正则化的正确性。正则化就是在强行降低模型的有效 VC 维，从而减小泛化误差的上界。
我们来用一个问题结束本章吧。
根据 VC 维理论，参数越多，$d$越大，泛化误差的上界应该越高。
但在现代深度学习的实践中，我们经常发现：即使参数量远远超过数据量（$d \gg m$, 即过参数化），模型在测试集上的表现依然非常好，并没有发生严重的过拟合。
这是不是意味着VC维理论失效了？还是说我们应该重新理解公式中的$\hat{L}(f)$和Penalty的关系？
还记得公式中$Penalty = \sqrt{\frac{d...}{m}}$吗？
如果$m$固定，而$d$跟随深度学习模型的层数飞速增长，则这个Penalty项在数学上颇有爆炸风险。根据经典VC维理论，当$d \gg m$时，泛化误差的上界确实会变得非常大。这时候这个上界就变得没有什么意义了。
那为什么在现实中我们的模型照常运行？
Training Loss $\hat{L}(f)$的作用是，当模型极大的时候，它有能力将训练误差$\hat{L}(f)$彻底压到0。虽然名义上的$d$很大，但是SGD等算法更倾向于寻找更平滑的那一组解。
所以并不是VC维理论失效了：不等式仍然成立，只是VC太悲观了。目前他还没办法解释为什么在$d \gg m$的过参数化区间内，模型依旧能够表现良好。这促使学界提出了新的理论来替代简单的VC维。