【概述】

无论是基于 VC 维还是 Rademacher 复杂度来推导泛化误差界，所得到的结果均与具体学习算法无关，对所有学习算法都适用，这使得人们能够脱离具体学习算法的设计来考虑学习问题本身的性质，但在另一方面，若希望获得与算法有关的分析结果，则需另辟蹊径，稳定性分析（Stability Analysis）就是这方面中的一个方向

【基本定义】

两种变化

算法的稳定性，考察的是算法在输入发生变化时，输出是否会发生较大的变化，由于学习算法的输入是训练集，因此先定义训练集的两种变化

对于训练集 $D=\{z_1=(\mathbf{x}_1,y_1),z_2=(\mathbf{x}_2,y_2),\cdots,z_n=(\mathbf{x}_n,y_n)\}$，$\mathbf{x}_i\in\mathcal{X},y_i=\{-1,+1\}$ 是来自于分布 $\mathcal{D}$ 的独立同分布样本，假设空间 $\mathcal{H}:\mathcal{X}\rightarrow\{-1,+1\}$ 和学习算法 $\mathcal{L}$，令 $\mathcal{L}_D\in \mathcal{H}$ 表示基于训练集 $D$ 从假设空间 $\mathcal{H}$ 中习得的假设

考虑 $D$ 的以下变化：

$\begin{gather*} D^{\backslash i} = \{ z_1,z_2,\cdots,z_{i-1},z_{i+1},\cdots,z_n \} \\ D^{i} = \{ z_1,z_2,\cdots,z_{i-1},z_{i}',z_{i+1},\cdots,z_n \}, z_{i}'=(\mathbf{x}_i',y_i') \\ \end{gather*}$

其中，$D^{\backslash i}$ 表示移除 $D$ 中第 $i$ 个样本得到的集合，$D^{i}$ 表示替换 $D$ 中第 $i$ 个样本得到的集合

三种损失

损失函数 $\ell(\mathcal{L}_D(\mathbf{x}),y): \mathcal{Y}\times \mathcal{Y} \rightarrow \mathbb{R}^+$ 刻画了假设 $\mathcal{L}_D$ 的预测标记 $\mathcal{L}_D(\mathbf{x})$ 与真实标记 $y$ 间的差别，简记为 $\ell(\mathcal{L}_D,z)$

由此，定义关于假设 $\mathcal{L}_D$ 的是三种损失：

泛化损失

$\ell(\mathcal{L},\mathcal{D}) = \mathbb{E}_{\mathbf{x}\in\mathcal{X},z=(\mathbf{x},y)} [ \ell(\mathcal{L}_D,z) ]$

经验损失

$\hat{\ell}(\mathcal{L},\mathcal{D}) = \frac{1}{n} \sum_{i=1}^n \ell(\mathcal{L}_D,z_i)$

留一损失

$\ell_{\text{loo}}(\mathcal{L},\mathcal{D}) = \frac{1}{n} \sum_{i=1}^n\ell(\mathcal{L}_{D^{\backslash i}},z_i)$

【均匀稳定性】

对任意 $\mathbb{x}\in\mathcal{X},z=(\mathbf{x},y)$，若学习算法 $\mathcal{L}$ 满足：

$|\ell(\mathcal{L}_D,z)-\ell(\mathcal{L}_{D^{\backslash i}},z)| \leq \beta,i=1,2,\cdots,n$

则称 $\mathcal{L}$ 关于损失函数 $\ell$ 满足 $\beta$ 均匀稳定性

显然，若算法 $\mathcal{L}$ 满足 $\beta$ 均匀稳定性，则有：

$\begin{align*} |\ell(\mathcal{L}_D,z)-\ell(\mathcal{L}_{D^{i}},z)| &\leq |\ell(\mathcal{L}_D,z)-\ell(\mathcal{L}_{D^{\backslash i}},z)| + |\ell(\mathcal{L}_{D^{i}},z)-\ell(\mathcal{L}_{D^{\backslash i}},z)| \\ &\leq 2\beta \end{align*}$

也就是说，移除样本的稳定性包含替换样本的稳定性

【泛化误差界】

对给定从分布 $D$ 上独立同分布采样得到的大小为 $n$ 的样本集 $D$，若学习算法 $\mathcal{L}$ 满足关于损失函数 $\ell$ 的 $\beta$ 均匀稳定性，且损失函数 $\ell$ 的上界为 $M$，则对任意 $m\geq 1$，至少以 $1-\delta$ 的概率有：

$\begin{gather*} \ell (\mathcal{L},\mathcal{D}) \leq \hat{\ell}(\mathcal{L},D) + 2\beta + (4n\beta+M)\sqrt{\frac{\ln\frac{1}{\delta}}{2n}} \\ \ell (\mathcal{L},\mathcal{D}) \leq \ell_{\text{loo}}(\mathcal{L},D) + \beta + (4n\beta+M) \sqrt{\frac{\ln\frac{1}{\delta}}{2n}} \end{gather*}$

上式给出了基于稳定性分析导出的学习算法 $\mathcal{L}$ 习得假设的泛化误差界

可以看出，经验损失和泛化损失之间差别的收敛率是 $\beta\sqrt{n}$，若令 $\beta=O(\frac{1}{n})$，则可保证收敛率为 $O(\sqrt{\frac{1}{n}})$，这与基于 VC 维和 Rademacher 复杂度得到的收敛率一致

需要注意的是，学习算法的稳定性分析所关注的是 $|\hat{\ell}(\mathcal{L},D)-\ell(\mathcal{L},\mathcal{D})|$，而假设空间复杂度分析所关注的是 $\sup_{h\in \mathcal{H}}|\hat{\mathbb{E}}(h)-\mathbb{E}(h)|$，也就是说，稳定性分析不必考虑假设空间中所有可能的假设，只需根据算法自身的稳定性来讨论输出假设 $\mathcal{L}_D$ 的泛化误差界

【稳定性与可学习性】

为保证稳定的学习算法 $\mathcal{L}$ 具有一定的泛化能力，假设 $\beta\sqrt{n}\rightarrow 0$，即经验损失收敛于泛化损失

为便于计算，假定 $\beta=\frac{1}{n}$，代入泛化误差界，有：

$\ell (\mathcal{L},\mathcal{D}) \leq \hat{\ell}(\mathcal{L},D) + \frac{2}{n} + (4+M)\sqrt{\frac{\ln\frac{1}{\delta}}{2n}}$

对于损失函数 $\ell$，若学习算法 $\mathcal{L}$ 所输出的假设满足经验损失最小化，则称 $\mathcal{L}$ 满足经验风险最小化（Empirical Risk Minimization）原则，即学习算法是 ERM 的

通过学习算法的稳定性的定义，可以导出假设空间的可学习性，两者通过损失函数 $\ell$ 联系起来，即若学习算法 $\mathcal{L}$ 是 ERM 且稳定的，那么假设空间 $\mathcal{H}$ 可学习