第5章：稳定性

编辑：赵志民，李一飞，王茂霖，詹好

---

本章前言

本章将探讨学习理论中的稳定性。在前一章中，我们介绍了不同的复杂度度量方法，并给出了与特定算法无关的泛化界限。 然而，这些泛化界限是否能通过分析特定算法的性质得到更好的学习保障？这些分析是否能够扩展到具有相似性质的其他学习算法上？ 本章旨在回答这些问题，通过算法稳定性的应用推导出依赖于算法的学习保证。

5.1 【概念解释】留一交叉验证的风险

90页中提到的留一风险（leave-one-out risk）是指依次从数据集中移除某一数据后，利用剩余数据训练的模型与被移除数据之间的风险。本质上，这保证了用于风险测试的数据不会包含在训练集中，类似于模型选择时的留一验证。

5.2 【证明补充】均匀稳定性与泛化误差上界

92页中，定理5.1讨论了均匀稳定性与泛化性的关系。以下是该证明过程中均匀稳定性与泛化性之间联系的分析。

证明简述

对于读者来说，前几章的阅读应使大家对涉及 $ln$ 和根号的不等式已经有所了解，并能意识到这与指数函数的不等式有关，并反解风险 $ϵ$。这里我们希望通过样本的稳定性推导出关于风险的泛化性。因此，在证明时必须将风险之间的差距转化为损失函数之间的风险。

由于定理中提到的替换样本 $\beta$-均匀稳定性和移除样本 $\gamma$-均匀稳定性是非常强的条件，适用于任意的数据集 D 和任意的样本 z，因此我们可以得到关于经验风险与泛化风险差距（即 $\mathrm{\Phi }(D)$） 的估计式。

通过对损失函数的差值求和平均可以得到风险 (Risk) 的差距。由于替换样本的 $\beta$-均匀稳定性适用于任意 z，因此我们可以推导出 (5.22) 和 (5.23) 式，并使用 McDiarmid 不等式推导出经验风险与泛化风险的差距（即 $\mathrm{\Phi }(D)$） 超过其平均值至少 $ϵ$ 的概率。即：

$$P(\varphi (D)\ge \mathbb{E}[\mathrm{\Phi }(D)]+ϵ)\le exp(\frac{-2m{ϵ}^2}{(2m\beta +M{)}^2})$$

之后进行简单的放缩估计即可得到最终的结果：

$$P(R({\mathcal{L}}_{\mathcal{D}})-\hat{R}({\mathcal{L}}_{\mathcal{D}})\ge \beta +ϵ)\le exp(\frac{-2m{ϵ}^2}{(2m\beta +M{)}^2})$$

值得注意的是，（5.22）中的最后一步不等式推导其实省略了一步：

$$\begin{array}{rl}& \frac{|\ell ({\mathfrak{L}}_D,z_i)-\ell ({\mathfrak{L}}_{D^{i,z_i^{\prime }}},z_i^{\prime })|}{m}+\sum _{j\ne i}\frac{|\ell ({\mathfrak{L}}_D,z_j)-\ell ({\mathfrak{L}}_{D^{i,z_i^{\prime }}},z_j)|}{m}\\ & \le \frac{M}{m}+\frac{m-1}{m}\beta \\ & \le \frac{M}{m}+\beta \end{array}$$

之所以这么做，是因为当样本量 $m$ 较大时，$\frac{\beta }{m}$ 的大小可以忽略不计，因此在结论中并未出现这一项。

另外，（5.23）式也省略了一步：

$$|E_{z\sim \mathcal{D}}[\ell ({\mathfrak{L}}_D,z)-\ell ({\mathfrak{L}}_{D^{i,z_i^{\prime }}},z)]|\le E_{z\sim \mathcal{D}}[|\ell ({\mathfrak{L}}_D,z)-\ell ({\mathfrak{L}}_{D^{i,z_i^{\prime }}},z)|]\le E_{z\sim \mathcal{D}}[\beta ]=\beta$$

关于移除样本 $\gamma$-均匀稳定性（5.18）的证明用到了（5.14）的结论，因此在不等式中构造出了类似于 $2m\beta$ 的 $4m\gamma$ 形式，其他推理步骤与（5.17）基本一致。

均匀稳定性与泛化性的关系

在证明过程中，多处涉及了损失函数作差的放缩，即替换样本的 $\beta$-均匀稳定性，但实际上大多数情况下使用该稳定性只是为了简化式子，只有在 (5.24) 与 (5.25) 中体现了稳定性与泛化性的关系。

在 (5.24) 中，通过替换样本的稳定性，我们可以得到经验风险与泛化风险的差距（即 $\mathrm{\Phi }(D)$) 在替换样本前后的风险可以被上界 $2\beta +M/m$ 控制住。根据 McDiarmid 不等式的描述，如果实值函数关于变量的替换具有较好的稳定性，那么该实值函数与期望的差距也将受到上界控制。简言之，如果实值函数替换一个变量后变化不大，那么无论如何替换，变化都不会过大，因此该实值函数的取值总会在一定范围内，与其均值（即期望）相差不大。

因此在 (5.25) 中，我们可以得到经验风险与泛化风险的差距（即 $\mathrm{\Phi }(D)$) 也有了上界。通过简单的放缩可以得到一个常数上界，从而得出泛化风险的上界。

5.3 【证明补充】假设稳定性与泛化误差上界

94页中，定理5.2讨论了假设稳定性与泛化性的关系。以下是该证明过程中假设稳定性与泛化性之间联系的分析。

证明简述

证明涉及 $R({\mathcal{L}}_{\mathcal{D}})-\hat{R}({\mathcal{L}}_{\mathcal{D}})$ 的平方平均，因为假设稳定性是较弱的条件，只能保证风险的期望被上界控制，因此只能得到关于期望的不等式。由于不涉及概率与置信度，因此不需要复杂的不等式，简单的放缩即可得到答案。

证明中的一处难点在于（5.30）至（5.33）中关于变量 $z$ 之间的替换。根据独立同分布假设，即 $\mathrm{\forall }i,j\in {\mathbb{N}}^{+},z,z^{\prime },z_i,z_j\sim \mathcal{D}$，可以任意交换 $z,z^{\prime },z_i,z_j$ 的顺序而期望值不变。

例如，在（5.30）中的第一步推导中，不失一般性地用 $z_1,z_2$ 替代 $z_i,z_j$，因此原期望值之和得以简化为只与 $z_1,z_2$ 相关的期望值。

理解这一点后，任何关于变量 $z$ 之间的替换都不会令人感到困惑，其中也包括了定理5.3证明中（5.35）的第二步推导。

另外，在（5.32）的第一步推导中，使用了绝对值不等式 $\mathbb{E}(X+Y)\le \mathbb{E}(|X|)+\mathbb{E}(|Y|)$。这种在期望放缩中运用绝对值不等式的处理方式在全书中非常实用，值得读者留意。

假设稳定性与泛化性的关系

该定理实际上给出了经验风险与泛化风险的差距的平方平均的界，这是因为假设稳定性并不是非常强的条件，而是为了放松均匀稳定性这一较强的条件而引入的。

5.4 【概念解释】过拟合与欠拟合的关系

过拟合和欠拟合是泛化性研究中的重要概念。当经验风险与泛化风险的差距较大时，会发生过拟合；相反，当泛化风险与经验风险的差距较大时，则发生欠拟合。因此，我们在算法设计时，希望尽可能缩小泛化风险与经验风险的差距。

96页中，定理5.3从算法稳定性的角度提出了防止过拟合的方案：当替换训练集的单个样本时，算法的输出函数变化不大，我们认为学习算法 $\mathfrak{L}$ 是稳定的，否则就需要重新进行训练。该方法同样适用于欠拟合的情况，但在实际应用中，算法欠拟合的情况较少，因此我们更多地关注过拟合的预防。

5.5 【概念解释】稳定性与可学习性

97页中，定理5.4讨论了稳定性与可学性之间的关系。以下是定理5.4的梳理分析，探讨稳定性与可学性在证明中的关联。

证明简述

首先，我们回顾不可知 PAC 可学的概念：对于所有分布 $\mathcal{D}$，若存在学习算法 $\mathfrak{L}$ 与多项式函数 $poly(\cdot ,\cdot ,\cdot ,\cdot )$，使得对于任意 $m\ge poly(1/ϵ,1/\delta ,size(\mathbf{x}),size(c))$，$\mathfrak{L}$ 输出的假设能够满足：

$$P(\mathbb{E}(h)-\underset{h^{\prime }\in \mathcal{H}}{min}\mathbb{E}(h^{\prime })\le ϵ)\ge 1-\delta$$

该证明利用了经验风险与泛化风险之间的联系，构造出（5.39），然后分而治之地讨论不同情况下的稳定性关系。

其中，泛化风险与经验风险之差（5.40）可以根据定理5.1改写为：对于任意的 $\delta \in (0,1)$，以至少 $1-\delta$ 的概率有：

$$R({\mathfrak{L}}_D)-\hat{R}({\mathfrak{L}}_D)\le \frac{1}{m}+(2m\beta +M)\sqrt{\frac{ln(1/\delta )}{2m}}$$

参考95页中对 $li{m}_{m\to +\mathrm{\infty }}m\beta$ 的讨论，发现只要满足 $li{m}_{m\to +\mathrm{\infty }}m\beta <\mathrm{\infty }$ 的条件，算法的泛化性能便可得到保障，因此应确保 $\beta$ 的取值不要太大。在此定理中，我们选取 $\beta =1/m$，此时（5.40）简化为：

$$R({\mathfrak{L}}_D)-\hat{R}({\mathfrak{L}}_D)\le \frac{1}{m}+(2+M)\sqrt{\frac{ln(1/\delta )}{2m}}$$

在处理 ERM 算法情况下泛化风险与经验风险之差（5.42）时，原书中有一处小错误，但对最终结论影响不大。以下是正确的推导过程：

根据 $\ell ({\mathfrak{L}}_D,z)\in [0,M]$，可以得到 $\hat{R}\in [0,M]$，又因为 $R(h^{\ast })=E_{\mathcal{D}}(\hat{R}(h^{\ast }))$，此时根据 Hoeffding 不等式（1.30），可知至少以 $1-\delta$ 的概率有：

$$\hat{R}(h^{\ast })-R(h^{\ast })\le M\sqrt{\frac{ln(1/\delta )}{2m}}$$

结合（5.39）至（5.42）可知，至少以 $1-\delta$ 的概率有：

$$R({\mathfrak{L}}_D)-R(h^{\ast })\le \frac{1}{m}+(2+M)\sqrt{\frac{ln(1/\delta )}{2m}}+M\sqrt{\frac{ln(1/\delta )}{2m}}$$

此时（5.44）变为：

$$ϵ=\frac{1}{m}+(1+M)\sqrt{\frac{2ln(1/\delta )}{m}}$$

令 $m^{\prime }=\sqrt{m}$，则可以将上式转化为关于 $m^{\prime }$ 的一元二次方程：

$$ϵm^{\prime 2}-A{m}^{\prime }-1=0$$

其中 $A=(1+M)\sqrt{2ln(1/\delta )}$，根据求根公式可得：

$$m^{\prime }=\frac{A\pm \sqrt{A^2+4ϵ}}{2ϵ}=O(\frac{1}{ϵ}\sqrt{ln(\frac{1}{\delta })})$$

至此，我们得到了 $m$ 的渐近复杂度：

$$m=m^{\prime 2}=O(\frac{1}{{ϵ}^2}ln(\frac{1}{\delta }))$$

接下来的推导便水到渠成。

稳定性与可学性

这里只能达到不可知 PAC 可学的原因是泛化界只能以概率达到，无法保证在任何函数空间内都能达到上界以下。因此，这里只能讨论稳定性与不可知 PAC 可学性的关系。

事实上，稳定性与可学性的关系类似于第四章中讲到的泛化界与可学性的关系。通过 ERM 算法得到最小经验风险函数后，结合均匀稳定性带来的泛化上界，我们可以获得可学性。

5.6 【证明补充】二次分布下的 k-近邻算法稳定性

105页中，引理5.2讨论了二次分布 $X\sim B(k,1/2)$ 的 k-近邻的稳定性。这里我们给出详细的证明过程。

给定整数 $k>0$，若随机变量 $X$ 满足：

$$P(X=i)=\frac{1}{2^k}(\genfrac{}{}{0ex}{}{k}{i}),i\in [k]$$

则对任意正整数 $a$ 有：

$$P(|X-\frac{k}{2}|\le \frac{a}{2})<\frac{2\sqrt{2}a}{\sqrt{\pi k}}$$

首先，我们根据 $k$ 的取值将情况分为两类讨论。

当 $k$ 为偶数时，二项式展开的最大项为：

$$\frac{1}{2^k}(\genfrac{}{}{0ex}{}{k}{k/2})\le \frac{2}{\sqrt{2\pi k}}\exp (\frac{1}{12k}-\frac{2}{6k+1})<\frac{2}{\sqrt{2\pi k}}$$

第二步推导利用了 Stirling 公式，最后一步推导则利用了函数 $l(x)=\exp (\frac{1}{12x}-\frac{2}{6x+1})$ 在 $[1,\mathrm{\infty })$ 区间单调递增且取值在 $(0,1)$ 之间的特性。

因此，我们有：

$$P(|X-\frac{k}{2}|\le \frac{a}{2})=(a+1)\frac{2}{\sqrt{2\pi k}}<\frac{4a}{\sqrt{2\pi k}}$$

当 $k$ 为奇数且 $k>1$ 时，二项式展开的最大项为：

$$\frac{1}{2^k}(\genfrac{}{}{0ex}{}{k}{(k-1)/2})<\frac{1}{2^{k-1}}(\genfrac{}{}{0ex}{}{k-1}{(k-1)/2})<\frac{1}{\sqrt{2\pi (k-1)}}<\frac{2}{\sqrt{\pi k}}$$

当 $k=1$ 时，二项式展开的最大项为 $\frac{1}{2}<\frac{2}{\sqrt{\pi }}$ 因此，我们有：

$$P(|X-\frac{k}{2}|\le \frac{a}{2})=a\frac{2}{\sqrt{\pi k}}<\frac{4a}{\sqrt{2\pi k}}$$

综上，引理5.2得证。

5.7 【概念解释】稳定性理论的适用范围

细心的读者可能已经注意到，这里的稳定性仅在某些条件下才能适用，以下是对这些条件的总结。

首先，本章的分析假设输出函数 ${\mathfrak{L}}_D$ 与训练集 $D$ 的顺序无关，但这在实际应用中并不一定成立。例如，在随机梯度下降算法中，训练集的顺序会影响最终的输出函数，因此这里的稳定性并不适用于随机梯度下降算法。

另外，在样本扰动分析中，我们几乎没有单独讨论新增样本的情况。这是因为在数据或概念发生漂移的情况下，稳定性的要求不一定成立，因为此时训练集的分布与真实分布已不再一致。而在研究训练集 $D$ 的扰动对算法 ${\mathfrak{L}}_D$ 输出函数的影响时，我们希望经验风险的变化尽可能小，这恰好与在线学习（Online Learning）的目标相抵触。

具体而言，在线学习指的是在数据不断到来的过程中，动态地更新模型，因此该训练方式更关注模型的可塑性，即在旧场景中训练的模型是否能通过优化在新场景中表现优异。因此，在实际应用中，我们需要平衡学习算法的可塑性与稳定性。

为了更好地评估在线学习的性能，本书引入了遗憾界的概念，即在线学习与离线学习算法之间最小损失的差值，具体分析请参见第八章。