【机器学习基础】系列博客为参考周志华老师的《机器学习》一书，自己所做的读书笔记。
本文为原创文章，未经本人允许，禁止转载。转载请注明出处。
1.稳定性
无论是基于VC维还是Rademacher复杂度来推导泛化误差界，所得到的结果均与具体学习算法无关，对所有学习算法都适用。这使得人们能够脱离具体学习算法的设计来考虑学习问题本身的性质，但在另一方面，若希望获得与算法有关的分析结果，则需另辟蹊径。稳定性（stability）分析是这方面一个值得关注的方向。
顾名思义，算法的“稳定性”考察的是算法在输入发生变化时，输出是否会随之发生较大的变化。学习算法的输入是训练集，因此下面我们先定义训练集的两种变化。
给定$D = \{ \mathbf{z}_1 = (\mathbf{x}_1,y_1), \mathbf{z}_2 = (\mathbf{x}_2,y_2) , \cdots , \mathbf{z}_m = (\mathbf{x}_m,y_m) \},\mathbf{x}_i \in \mathcal{X}$是来自分布$\mathcal{D}$的独立同分布示例，$y_i = \{ -1,+1 \}$。对假设空间$\mathcal{H}:\mathcal{X}\to \{ -1,+1 \}$和学习算法$\mathfrak{L}$，令$\mathfrak{L}_D \in \mathcal{H}$表示基于训练集$D$从假设空间$\mathcal{H}$中学得的假设。考虑$D$的以下变化：
-
$D^{\backslash i}$表示移除$D$中第$i$个样例得到的集合：
\[D^{\backslash i} = \{ \mathbf{z}_1,\mathbf{z}_2,...,\mathbf{z}_{i-1},\mathbf{z}_{i+1},...,\mathbf{z}_m \}\] -
$D^i$表示替换$D$中第$i$个样例得到的集合：
\[D^i = \{ \mathbf{z}_1,\mathbf{z}_2,...,\mathbf{z}_{i-1},\mathbf{z}_i', \mathbf{z}_{i+1},...,\mathbf{z}_m \}\]其中$\mathbf{z}’_i = (\mathbf{x}’_i,y’_i)$，$\mathbf{x}’_i$服从分布$\mathcal{D}$并独立于$D$。
损失函数$\ell(\mathfrak{L}_D(\mathbf{x}),y):\mathcal{Y} \times \mathcal{Y} \to \mathbb{R}^+$刻画了假设$\mathfrak{L}_D$的预测标记$\mathfrak{L}_D(\mathbf{x})$与真实标记$y$之间的差别，简记为$\ell (\mathfrak{L}_D,\mathbf{z})$。下面定义关于假设$\mathfrak{L}_D$的几种损失。
-
泛化损失：
\[\ell (\mathfrak{L},\mathcal{D}) = \mathbb{E}_{\mathbf{x}\in \mathcal{X},\mathbf{z}=(\mathbf{x},y)} [ \ell (\mathfrak{L}_D,\mathbf{z}) ] \tag{1}\] -
经验损失：
\[\hat{\ell} (\mathfrak{L},D) = \frac{1}{m} \sum_{i=1}^m \ell (\mathfrak{L}_D,\mathbf{z}_i) \tag{2}\] -
留一（leave-one-out）损失：
\[\ell_{loo}(\mathfrak{L},D)=\frac{1}{m}\sum_{i=1}^m \ell (\mathfrak{L}_{D^{\backslash i}},\mathbf{z}_i) \tag{3}\]
下面定义算法的均匀稳定性（uniform stability）：
定义12.10 对任何$\mathbf{x}\in \mathcal{X},\mathbf{z}=(\mathbf{x},y)$，若学习算法$\mathfrak{L}$满足：
\[\lvert \ell (\mathfrak{L}_D,\mathbf{z}) - \ell (\mathfrak{L}_{D^{\backslash i}},\mathbf{z}) \rvert \leqslant \beta , i=1,2,...,m \tag{4}\]则称$\mathfrak{L}$关于损失函数$\ell$满足$\beta$-均匀稳定性。
显然，若算法$\mathfrak{L}$关于损失函数$\ell$满足$\beta$-均匀稳定性，则有：
\[\begin{align} \lvert \ell (\mathfrak{L}_D,\mathbf{z}) - \ell (\mathfrak{L}_{D^i},\mathbf{z}) \rvert &= \lvert \ell (\mathfrak{L}_D,\mathbf{z}) - \ell (\mathfrak{L}_{D^{\backslash i}},\mathbf{z}) + \ell (\mathfrak{L}_{D^{\backslash i}},\mathbf{z}) - \ell (\mathfrak{L}_{D^i},\mathbf{z}) \rvert \\& \leqslant \lvert \ell (\mathfrak{L}_D,\mathbf{z}) - \ell (\mathfrak{L}_{D^{\backslash i}},\mathbf{z}) \rvert + \lvert \ell (\mathfrak{L}_{D^{\backslash i}},\mathbf{z}) - \ell (\mathfrak{L}_{D^i},\mathbf{z}) \rvert \\&= \lvert \ell (\mathfrak{L}_D,\mathbf{z}) - \ell (\mathfrak{L}_{D^{\backslash i}},\mathbf{z}) \rvert + \lvert \ell (\mathfrak{L}_{D^i},\mathbf{z}) - \ell (\mathfrak{L}_{D^{\backslash i}},\mathbf{z}) \rvert \\& \leqslant 2 \beta \end{align}\]也就是说，移除示例的稳定性包含替换示例的稳定性。
若损失函数$\ell$有界，即对所有$D$和$\mathbf{z}=(\mathbf{x},y)$有$0 \leqslant \ell (\mathfrak{L}_D,\mathbf{z}) \leqslant M$，则有：
定理12.8 给定从分布$\mathcal{D}$上独立同分布采样得到的大小为$m$的示例集$D$，若学习算法$\mathfrak{L}$满足关于损失函数$\ell$的$\beta$-均匀稳定性，且损失函数$\ell$的上界为$M$，$0 < \delta <1$，则对任意$m \geqslant 1$，以至少$1-\delta$的概率有：
\[\ell (\mathfrak{L},\mathcal{D}) \leqslant \hat{\ell}(\mathfrak{L},D) + 2\beta + (4m\beta+M)\sqrt{\frac{\ln (1 / \delta)}{2m}} \tag{5}\] \[\ell (\mathfrak{L},\mathcal{D}) \leqslant \ell _{loo} (\mathfrak{L},D) + \beta + (4m\beta + M) \sqrt{\frac{\ln (1 / \delta)}{2m}} \tag{6}\]定理12.8给出了基于稳定性分析推导出的学习算法$\mathfrak{L}$学得假设的泛化误差界。从式(5)可看出，经验损失与泛化损失之间差别的收敛率为$\beta \sqrt{m}$；若$\beta = O(\frac{1}{m})$，则可保证收敛率为$O(\frac{1}{\sqrt{m}})$。与定理12.3和定理12.6比较可知，这与基于VC维和Rademacher复杂度得到的收敛率一致。
需注意，学习算法的稳定性分析所关注的是$\lvert \hat{\ell} (\mathfrak{L},D) - \ell (\mathfrak{L},\mathcal{D}) \rvert$，而假设空间复杂度分析所关注的是$\sup_{h \in \mathcal{H}} \lvert \hat{E}(h) - E(h) \rvert$；也就是说，稳定性分析不必考虑假设空间中所有可能的假设，只需根据算法自身的特性（稳定性）来讨论输出假设$\mathfrak{L}_D$的泛化误差界。那么，稳定性与可学习性之间有什么关系呢？
首先，必须假设$\beta \sqrt{m} \to 0$，这样才能保证稳定的学习算法$\mathfrak{L}$具有一定的泛化能力，即经验损失收敛于泛化损失，否则可学习性无从谈起。为便于计算，我们假定$\beta = \frac{1}{m}$，代入式(5)可得：
\[\ell (\mathfrak{L},\mathcal{D}) \leqslant \hat{\ell} (\mathfrak{L},D) + \frac{2}{m} + (4 + M) \sqrt{\frac{\ln (1 / \delta)}{2m}} \tag{7}\]对损失函数$\ell$，若学习算法$\mathfrak{L}$所输出的假设满足经验损失最小化，则称算法$\mathfrak{L}$满足经验风险最小化（Empirical Risk Minimization）原则，简称算法是ERM的。关于学习算法的稳定性和可学习性，有如下定理：
最小化经验误差和最小化经验损失有时并不相同，这是由于存在某些病态的损失函数$\ell$使得最小化经验损失并不是最小化经验误差。为简化讨论，这里假定最小化经验损失的同时会最小化经验误差。
定理12.9 若学习算法$\mathfrak{L}$是ERM且稳定的，则假设空间$\mathcal{H}$可学习。
为什么学习算法的稳定性能导出假设空间的可学习性？学习算法和假设空间是两码事。事实上，要注意到稳定性与假设空间并非无关，由稳定性的定义可知两者通过损失函数$\ell$联系起来。
2.定理12.9的证明
对这部分证明不太感兴趣，就没细看，这里贴出原书中的证明，感兴趣的小伙伴们可以看一看。
令$g$表示$\mathcal{H}$中具有最小泛化损失的假设，即
\[\ell (g,\mathcal{D}) = \min_{h \in \mathcal{H}} \ell (h,\mathcal{D})\]再令
\[\epsilon' = \frac{\epsilon}{2}\] \[\frac{\delta}{2} = 2 \exp \left( -2m(\epsilon')^2 \right)\]由Hoeffding不等式可知，当$m\geqslant \frac{2}{\epsilon^2} \ln \frac{4}{\delta}$时，
\[\lvert \ell (g,\mathcal{D}) - \hat{\ell} (g,D) \rvert \leqslant \frac{\epsilon}{2}\]以至少$1-\delta / 2$的概率成立。令式(7)中
\[\frac{2}{m}+(4+M)\sqrt{\frac{\ln (2/\delta)}{2m}} = \frac{\epsilon}{2}\]解得$m = O(\frac{1}{\epsilon^2}\ln \frac{1}{\delta})$使
\[\ell (\mathfrak{L},\mathcal{D}) \leqslant \hat{\ell} (\mathfrak{L},D) + \frac{\epsilon}{2}\]以至少$1-\delta / 2$的概率成立。从而可得
\[\begin{align} \ell (\mathfrak{L},\mathcal{D}) - \ell (g,\mathcal{D}) & \leqslant \hat{\ell} (\mathfrak{L},D) + \frac{\epsilon}{2} - \left( \hat{\ell} (g,D) - \frac{\epsilon}{2} \right) \\& \leqslant \hat{\ell} (\mathfrak{L},D) - \hat{\ell} (g,D) + \epsilon \\& \leqslant \epsilon \end{align}\]以至少$1-\delta$的概率成立。定理12.9得证。
