计算学习理论

概述

概念与记号

计算学习理论（computational learning theory）研究的是关于通过「计算」来进行「学习」的理论，即关于机器学习的理论基础，其目的是分析学习任务的困难本质，为学习算法提供理论保证，并根据分析结果指导算法设计。

关注的问题：

1. 怎样刻画「学习」这个过程？
2. 什么样的问题是「可学习的」？
3. 什么样的问题是「易学习的」？
4. 对于给定的学习算法，能否在理论上预测其性能？
5. 理论结果如何指导现实问题的算法设计？

一些相关的概念与记号：

• 样例集 $D = \left\lbrace (\bm{x}_i, y_i) \right\rbrace_{i=1}^m$，其中 $\bm{x}_i \in \mathcal{X}$，仅考虑二分类任务 $y_i \in \mathcal{Y} = \left\lbrace -1, 1 \right\rbrace$。假设 $\mathcal{X}$ 所有样本服从一个隐含未知的分布 $\mathcal{D}$，$D$ 中所有样本都是 i.i.d. 从 $\mathcal{D}$ 中采样得到的。
• 令 $h$ 为从 $\mathcal{X}$ 到 $\mathcal{Y}$ 的一个映射
  • 泛化误差 $E(h; D) = P_{\bm{x} \sim \mathcal{D}}(h(\bm{x}) \ne y)$
  • 经验误差 $\hat{E}(h; D) = \dfrac{1}{m} \displaystyle \sum_{i=1}^m \mathbb{I}(h(\bm{x}_i) \ne y_i)$
  • 由于 $D$ 是 $\mathcal{D}$ 的 i.i.d. 采样，因此 $h$ 的经验误差的期望等于其泛化误差的期望。上下文明确时，分别简记为 $E(h)$ 和 $\hat{E}(h)$。
• 误差参数 $\epsilon$ 表示预先设定的学得模型所应满足的误差要求，即 $E(h)$ 的上限，$E(h) \le \epsilon$。
• 若 $h$ 在数据集 $D$ 上的经验误差为 $0$，则称 $h$ 和 $D$ 一致，否则称 $h$ 和 $D$ 不一致。
• 对于任意两个映射 $h_1, h_2 \in \mathcal{X} \to \mathcal{Y}$，通过不合（disagreement）度量它们之间的差别：$d(h_1, h_2) = P_{\bm{x} \sim \mathcal{D}}(h_1(\bm{x}) \ne h_2(\bm{x}))$。

什么是「学习」

概念（concept）是从样本空间 $\mathcal{X}$ 到标记空间 $\mathcal{Y}$ 的映射，它决定了示例 $\bm{x}$ 的真实标记 $y$。

• 目标概念：若对任何样例 $(\bm{x}, y)$ 均有 $c(\bm{x}) = y$ 成立，则称 $c$ 为目标概念。
• 概念类：所有我们希望学得的目标概念所构成的集合称为概念类（concept class），记为 $\mathcal{C}$。

给定学习算法 $\mathfrak{L}$，它所考虑的所有可能概念的集合称为假设空间（hypothesis space），记为 $\mathcal{H}$：

• 由于学习算法事先并不知道概念类的真实存在，因此 $\mathcal{H}, \mathcal{C}$ 通常是不同的，学习算法会把自认为可能的目标概念集中起来构成 $\mathcal{H}$。
• 对于 $h \in \mathcal{H}$，由于无法确定它是否真是目标概念，因此成为假设（hypothesis）。
• 学习过程可以视为 $\mathfrak{L}$ 在 $\mathcal{H}$ 中进行的搜索过程。

可分的与不可分的：

• 可分的：若目标概念 $c \in \mathcal{H}$，即 $\mathcal{H}$ 中存在假设能将所有的示例完全正确分开（按与真实标记一致的方式），则称该问题对学习算法 $\mathfrak{L}$ 是可分的（separable），也称为一致的（consistent）。
• 不可分的：若目标概念 $c \notin \mathcal{H}$，即 $\mathcal{H}$ 中不存在假设能将所有的示例完全正确分开，则称该问题对学习算法 $\mathfrak{L}$ 是不可分的（non-separable），也称为不一致的（inconsistent）。

对于给定训练集 $D$，我们希望基于学习算法 $\mathfrak{L}$ 学得的模型所对应的假设 $h$ 「尽可能接近目标概念」$c$。

为何不是希望精确地学到目标概念 $c$？

• 获得的训练集 $D$ 往往仅包含有限数目的样例，因此通常会存在一些 $D$ 在上「等效」的假设，学习算法无法区别这些假设；
• 从分布 $\mathcal{D}$ 采样得到 $D$ 的过程有一定的偶然性，即便对同样大小的不同训练集，学的结果也可能有所不同。

可学习性

概率近似正确（Probably Approximately Correct, PAC）：我们希望以较大的把握学得比较好的模型，即以较大概率学得误差满足预设上限的模型。

令 $\delta$ 表示置信度，则有

PAC 辨识（PAC Identify）

对 $0 < \epsilon, \delta < 1$，所有 $c \in \mathcal{C}$ 与分布 $\mathcal{D}$，若存在学习算法 $\mathfrak{L}$，其输出假设 $h \in \mathcal{H}$ 满足

$$P(E(h) \le \epsilon) \ge 1 - \delta$$

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

这样的学习算法 $\mathfrak{L}$ 能以较大概率（至少 $1 - \delta$）学得目标概念 $c$ 的近似（误差最多为 $\epsilon$）。

令 $m$ 表示从分布 $\mathcal{D}$ 中 i.i.d. 采样得到的样例数目，对所有分布 $\mathcal{D}$，若存在学习算法 $\mathfrak{L}$ 和多项式函数 $\operatorname{poly}$，使得对于任意 $m \ge \operatorname{poly}\left(\frac{1}{\epsilon}, \frac{1}{\delta}, \operatorname{size}(\bm{x}), \operatorname{size}(c)\right)$，$\mathfrak{L}$ 能从假设空间 $\mathcal{H}$ 中 PAC 辨识概念类 $\mathcal{C}$，则称概念类 $\mathcal{C}$ 对假设空间 $\mathcal{H}$ 而言是 PAC 可学习的，简称概念类 $\mathcal{C}$ 是 PAC 可学习的。

若考虑对应学习算法 $\mathfrak{L}$ 的时间复杂度，有

PAC 学习算法（PAC Learning Algorithm）

若学习算法使概念类 $\mathcal{C}$ 为 PAC 可学习的，且 $\mathfrak{L}$ 的运行时间也是多项式函数 $\operatorname{poly}\left(\frac{1}{\epsilon}, \frac{1}{\delta}, \operatorname{size}(\bm{x}), \operatorname{size}(c)\right)$，则称概念类 $\mathcal{C}$ 是「高效 PAC 可学习（efficiently PAC learnable）」的，称 $\mathfrak{L}$ 为概念类 $\mathcal{C}$ 的 PAC 学习算法。

假定学习算法 $\mathfrak{L}$ 处理每个样本的时间为常数, 则 $\mathfrak{L}$ 的时间复杂度等价于其样本复杂度。于是，我们对算法时间复杂度的分析可变为对样本复杂度的分析。

样本复杂度

满足 PAC 学习算法 $\mathfrak{L}$ 所需的最小的 $m$，称为学习算法 $\mathfrak{L}$ 的样本复杂度（sample complexity）。

PAC 学习的意义：

• 给出了一个抽象地刻画机器学习能力的框架，基于这个框架可以
  对很多重要问题进行理论探讨
  • 研究某任务在什么样的条件下可学得较好的模型？
  • 某算法在什么样的条件下可进行有效的学习？
  • 需要多少训练样例才能获得较好的模型？
• 把对复杂算法的时间复杂度的分析转为对样本复杂度的分析

假设空间 $\mathcal{H}$ 的复杂度是影响可学习性的重要因素：

• 一般而言 $\mathcal{H}$ 越大，其包含任意目标概念的可能性越大，但从中找到某个具体概念的难度也越大；
• $|\mathcal{H}|$ 有限时，称为「有限假设空间」，否则称为「无限假设空间」。

若假设空间 $\mathcal{H}$ 包含了学习算法 $\mathfrak{L}$ 所有可能输出的假设，在 PAC 学习中假设空间与概念类完全相同（即 $\mathcal{H} = \mathcal{C}$），则称该问题是「恰 PAC 可学习的」（properly PAC learnable）。

• 直观地看，这意味着学习算法的能力与学习任务「恰好匹配」，即所有候选假设都来自概念类。
• 然而在现实应用中我们对概念类通常一无所知，设计一个假设空间与概念类恰好相同的学习算法通常是不切实际的.

研究的重点在于假设空间与概念类不同时，即 $\mathcal{H} \neq \mathcal{C}$ 的情况。

有限假设空间

可分情况

目标概念 $c$ 属于假设空间 $\mathcal{H}$，即 $c \in \mathcal{H}$。

一种简单的学习策略：

• 由于 $c \in \mathcal{H}$，因此在训练集 $D$ 上出现标记错误的假设肯定不是 $c$；
• 保留与 $D$ 一致的概念，剔除与 $D$ 不一致的假设；
• 若 $D$ 足够大，则可不断借助 $D$ 中的样例剔除不一致的假设，直到 $\mathcal{H}$ 中仅剩下一个假设为止，这个假设就是目标概念 $c$。

通常情况下由于训练集规模有限，假设空间 $\mathcal{H}$ 可能存在不止一个与 $D$ 一致的等效假设，对于这些假设，无法根据 $D$ 来对它们的优劣进一步区分。

需要多少样例才能学得目标概念的有效近似？

训练集 $D$ 的规模使得学习算法 $\mathfrak{L}$ 以概率 $1 - \delta$ 找到目标假设的 $\epsilon$ 近似，则

$$m \ge \dfrac{1}{\epsilon} \left( \ln |\mathcal{H}| + \ln \dfrac{1}{\delta} \right)$$

可分情况下的有限假设空间 $\mathcal{H}$ 都是 PAC 可学习的，输出假设 $h$ 的泛化误差随样例数目的增多而收敛到 $0$，收敛速率为 $O\left(\dfrac{1}{m}\right)$。

不可分情况

对于较困难的学习任务，$c \notin \mathcal{H}$，即对任意 $h \in \mathcal{H}, \hat{E}(h) \ne 0$。

若 $\mathcal{H}$ 为有限假设空间，$0 < \delta < 1$，则对任意 $h \in \mathcal{H}$ 有

$$P\left(|E(h) - \hat{E}(h)| \le \sqrt{\dfrac{\ln |\mathcal{H}| + \ln (2 / \delta)}{2m}}\right) \ge 1 - \delta$$

这表明样本大小 $m$ 足够大时，$h$ 的经验误差是其泛化误差很好的近似。尽管此时 $c \notin \mathcal{H}$，若能找到 $\mathcal{H}$ 中返回误差最小的假设也是一个较好的选择。

因此这实际上指出了一种通用的学习原则，即经验风险最小化（Empirical Risk Minimization, ERM）原则：令 $h$ 表示学习算法 $\mathfrak{L}$ 输出的假设，若 $h$ 满足

$$\hat{E}(h) = \min_{h' \in \mathcal{H}} \hat{E}(h')$$

则称 $\mathfrak{L}$ 为满足经验风险最小化原则的算法。

$c \notin \mathcal{H}$ 时可对 PAC 学习的定义做推广

不可知 PAC 可学习（agnostic PAC learneable）

令 $m$ 表示从分布 $\mathcal{D}$ 中 i.i.d. 采样得到的样例数目，$0 < \epsilon, \delta < 1$，对所有分布 $\mathcal{D}$，若存在学习算法 $\mathfrak{L}$ 和多项式函数 $\operatorname{poly}$，使得对于任意 $m \ge \operatorname{poly}\left(\frac{1}{\epsilon}, \frac{1}{\delta}, \operatorname{size}(\bm{x}), \operatorname{size}(c), |\mathcal{H}|\right)$，$\mathfrak{L}$ 能从假设空间 $\mathcal{H}$ 中输出满足下式的假设

$$P(E(h) - \min_{h' \in \mathcal{H}} E(h') \le \epsilon) \ge 1 - \delta$$

则称假设空间 $\mathcal{H}$ 是不可知 PAC 可学习的。

有限假设集是不可知 PAC 可学习的。

无限假设空间

现实学习任务所面临的通常是无线假设空间，例如实数域的所有区间，$\R^d$ 空间的所有线性超平面等等。

这种情况下需要使用 $|\mathcal{H}|$ 之外的方法度量假设空间的复杂性：

• VC 维（Vapnik-Chervonenkis dimension）
• Rademacher 复杂度（Rademacher complexity）

VC 维

给定假设空间 $\mathcal{H}$ 和示例集 $\left\lbrace \bm{x}_i \right\rbrace_{i=1}^m$，$\mathcal{H}$ 中每个假设 $h$ 都能对 $D$ 中示例赋予标记，标记结果可表示为

$$h|_D = \left\lbrace \left(h(\bm{x}_1), h(\bm{x}_2), \dots, h(\bm{x}_m) \right)\right\rbrace$$

假设空间 $\mathcal{H}$ 中不同假设对于 $D$ 中示例赋予标记的结果可能相同，也可能不同。

尽管 $\mathcal{H}$ 可能包含无穷多个假设，但是其对 $D$ 中示例赋予标记的可能结果是有限的：对于 $m$ 个示例的二分类任务，最多可能有 $2^m$ 个可能结果。

增长函数（growth function）

对所有 $m \in \N$，假设空间 $\mathcal{H}$ 的增长函数 $\Pi_{\mathcal{H}}$ 定义为

$$\Pi_{\mathcal{H}}(m) = \max_{\left\lbrace \bm{x}_i \right\rbrace_{i=1}^m} \left| \left\lbrace h|_D : h \in \mathcal{H} \right\rbrace \right|$$

增长函数表示假设空间对 $m$ 个示例所能赋予标记的最大可能结果数。

$\mathcal{H}$ 对示例赋予标记的可能结果数越大，$\mathcal{H}$ 的表示能力越强，对学习任务的适应能力也越强。

增长函数表述了 $\mathcal{H}$ 的表示能力，由此反映出假设空间的复杂度。

可利用增长函数估计经验误差与泛化误差之间的关系：

对假设空间 $\mathcal{H}$ 与 $m \in \N, 0 < \epsilon < 1$ 和任意 $h \in \mathcal{H}$ 有

$$P\left( |E(h) - \hat{E}(h)| > \epsilon \right) \le 4 \Pi_{\mathcal{H}}(2m) \exp\left(-\dfrac{m\epsilon^2}{8}\right)$$

对二分类任务来说，$\mathcal{H}$ 中的假设对 $D$ 中示例赋予标记的每种可能结果称为对 $D$ 的一种对分（dichotomy）。

若 $\mathcal{H}$ 能实现 $D$ 上的所有对分，则称 $D$ 能被 $\mathcal{H}$ 打散（shattered）。

VC 维（Vapnik-Chervonenkis dimension）

假设空间 $\mathcal{H}$ 的 VC 维是能被 $\mathcal{H}$ 打散的最大示例集的大小，即

$$\operatorname{VC}(\mathcal{H}) = \max\left\lbrace m \colon \Pi_{\mathcal{H}}(m) = 2^m \right\rbrace$$

$\operatorname{VC}(\mathcal{H}) = d$ 意味着存在一个大小为 $d$ 的示例集能被 $\mathcal{H}$ 打散，所有大小超过 $d$ 的示例集都不能被 $\mathcal{H}$ 打散。

例子：

令 $\mathcal{H}$ 表示实数域的所有闭区间构成的集合 $\left\lbrace h_{[a, b]}\colon a, b \in \R,\, a \le b\right\rbrace$，有 $\mathcal{X} = \R$，对 $x \in \mathcal{X}$，若 $x \in [a, b]$，则 $h_{[a, b]}(x) = 1$，否则 $h_{[a, b]}(x) = -1$。

令 $x_1 = 0.5, x_2 = 1.5$，则 $\mathcal{H}$ 中存在假设 $\left\lbrace h_{[0, 1]},\, h_{[0, 2]},\, h_{[1, 2]},\, h_{[2, 3]} \right\rbrace$ 将 $\left\lbrace x_1, x_2 \right\rbrace$ 打散，所以假设空间 $\mathcal{H}$ 的 VC 维至少为 $2$。

对任意大小为 $3$ 的示例集 $\left\lbrace x_3, x_4, x_5 \right\rbrace$，不妨令 $x_3 < x_4 < x_5$，则 $\mathcal{H}$ 中不存在任何假设 $h_{[a, b]}$ 能实现对分结果 $\left\lbrace (x_3, 1),\, (x_4, -1),\, (x_5, 1) \right\rbrace$。

因此 $\mathcal{H}$ 的 VC 维为 $2$。

下面是另一个例子，二维实平面的线性划分。

对于 VC 维与增长函数之间的定量关系，有

Sauer 引理

若 $\mathcal{H}$ 的 VC 维为 $d$，则对任意 $m \in \N$ 有

$$\pi_{\mathcal{H}}(m) \le \sum_{i=0}^d \binom{m}{i}$$

由此可计算出增长函数的上界，有引理

对任意整数 $m \ge d$ 有

$$\Pi_{\mathcal{H}}(m) \le \left( \dfrac{\e m}{d} \right)^d$$

基于 VC 维的泛化误差界：

若假设空间 $\mathcal{H}$ 的 VC 维为 $d$，则对任意 $m > d, 0 < \delta < 1$ 和 $h \in \mathcal{H}$ 有

$$P\left( |E(h) - \hat{E}(h)| \le \sqrt{\dfrac{8d \ln(2 \e m / d) + 8 \ln (4 / \delta)}{m}} \right) \ge 1 - \delta$$

上式的泛化误差界仅与样例数目 $m$ 有关，与数据分布 $\mathcal{D}$ 及样例集 $D$ 无关，收敛速率为 $O\left( \dfrac{1}{\sqrt{m}} \right)$。

因此基于 VC 维的泛化误差界有分布无关（distribution-free）性与数据独立（data-independent）性。

类似地，上面的定理能看出，当假设空间的 VC 维有限且样本大小 $m$ 足够大时，$h$ 的经验误差是其泛化误差的较好近似。

因此对于满足经验风险最小化原则的学习算法 $\mathfrak{L}$ 有定理

任何 VC 维有限的假设空间 $\mathcal{H}$ 都是（不可知）PAC 可学习的。

Rademacher 复杂度

由于基于 VC 维的泛化误差界是分布无关与数据独立的，因此基于 VC 维的可学习性分析结果具有一定的普适性，但同时因为没有考虑数据自身，因此得到的泛化误差界比较松。

Rademacher 复杂度是另一种刻画假设空间复杂的的途径，它在一定程度上考虑了数据分布。

给定数据集 $D = \left\lbrace (\bm{x}_i, y_i) \right\rbrace_{i=1}^m$，则假设 $h$ 的经验误差

$$\begin{aligned} \hat{E}(h) &= \dfrac{1}{m} \sum_{i=1}^m \mathbb{I}(h(\bm{x}_i) \ne y_i) \\ &= \dfrac{1}{m} \sum_{i=1}^{m} \dfrac{1 - y_i h(\bm{x}_i)}{2}\\ &= \dfrac{1}{2} - \dfrac{1}{2m} \sum_{i=1}^m y_i h(\bm{x}_i) \end{aligned}$$

其中 $\displaystyle \dfrac{1}{m}\sum_{i=1}^{m}y_ih(\bm{x}_i)$ 体现了预测值 $h(\bm{x}_i)$ 与样例真实标记 $y_i$ 之间的一致性。

若对任意 $i \in \left\lbrace 1, 2, \dots, m \right\rbrace$ 都有 $h(\bm{x}_i) = y_i$，则 $\dfrac{1}{m} \displaystyle \sum_{i=1}^{m}y_i h(\bm{x}_i)$ 取最大值 $1$，经验误差的的最小假设为

$$\argmax_{h \in \mathcal{H}} \dfrac{1}{m} \sum_{i=1}^m y_i h(\bm{x}_i)$$

若假设标签 $y_i$ 收到随机因素的影响，不再是 $\bm{x}_i$ 的真实标记，则应该选择 $\mathcal{H}$ 中事先已经考虑了随机噪声影响的假设

$$\sup_{h \in \mathcal{H}} \dfrac{1}{m} \sum_{i=1}^m \sigma_i h(\bm{x}_i)$$

其中 $\sigma_i$ 为 Rademacher 随机变量，其以 $0.5$ 的概率取 $1$，以 $0.5$ 的概率取 $-1$。

考虑 $\mathcal{H}$ 中所有假设，取期望可得

$$\mathbb{E}_{\bm{\sigma}} \left[ \sup_{h \in \mathcal{H}} \dfrac{1}{m} \sum_{i=1}^m \sigma_i h(\bm{x}_i) \right]$$

其中 $\bm{\sigma} = \left\lbrace \sigma_i \right\rbrace_{i=1}^m$。

这个式子的取值范围为 $[0, 1]$，体现了假设空间 $\mathcal{H}$ 的表达能力：

• 当 $|\mathcal{H}| = 1$ 时，$\mathcal{H}$ 中仅有一个假设，期望为 $0$；
• 当 $|\mathcal{H}| = 2^m$ 且 $\mathcal{H}$ 能打散 $D$ 时，则对于任意 $\bm{\sigma}$ 总有一个假设使得 $h(\bm{x}_i) = \sigma_i$，此时可计算出期望值为 $1$。

Rademacher 复杂度定义为

Rademacher 复杂度（Rademacher complexity）

函数空间 $\mathcal{F}$ 关于 $Z$ 的经验 Rademacher 复杂度为

$$\hat{R}_{Z}(\mathcal{F}) = \mathbb{E}_{\bm{\sigma}} \left[ \sup_{f \in \mathcal{F}} \dfrac{1}{m} \sum_{i=1}^m \sigma_i f(\bm{x}_i) \right]$$

其中 $\mathcal{F}\colon \mathcal{Z} \to\R$ 为实值函数空间，$Z = \left\lbrace z_i \right\rbrace_{i=1}^m$，$z_i \in \mathcal{Z}$。

函数空间 $\mathcal{F}$ 关于 $Z$ 上分布 $\mathcal{D}$ 的经验 Rademacher 复杂度为

$$R_m(\mathcal{F}) = \mathbb{E}_{Z \subseteq \mathcal{Z}\colon |Z| = m} \left[ \hat{R}_{Z}(\mathcal{F}) \right]$$

经验 Rademacher 复杂度衡量了函数空间 $\mathcal{F}$ 与随机噪声在集合 $Z$ 中的相关性。当 $\hat{R}_{Z}(\mathcal{F})$ 较大时，说明 $\mathcal{F}$ 能很好地拟合 $Z$ 中的随机噪声，即 $\mathcal{F}$ 的表达能力较强，具有较高的复杂度，有高的过拟合风险。

基于 Rademacher 复杂度可得关于函数空间 $\mathcal{F}$ 的泛化误差界。

对实值函数空间 $\mathcal{F}\colon \mathcal{Z} \to[0, 1]$，根据分布 $\mathcal{D}$ 从 $\mathcal{Z}$ 中 i.i.d. 采样得到示例 $Z = \left\lbrace z_1, z_2, \dots, z_m \right\rbrace$，其中 $z_i \in \mathcal{Z}, 0 < \delta < 1$，对任意 $f \in \mathcal{F}$，以至少 $1 - \delta$ 概率有

$$\begin{aligned} \mathbb{E}[f(z)] &\le \dfrac{1}{m} \sum_{i=1}^{m}f(z_i) + 2R_m(\mathcal{F}) + \sqrt{\dfrac{\ln(1 / \delta)}{2 m}}\\ \mathbb{E}[f(z)] &\le \dfrac{1}{m} \sum_{i=1}^{m}f(z_i) + 2\hat{R}_{Z}(\mathcal{F}) + 3\sqrt{\dfrac{\ln(2 / \delta)}{2 m}} \end{aligned}$$

上面的函数空间 $\mathcal{F}$ 是区间 $[0, 1]$ 上的实值函数，因此只适合回归问题。

对假设空间 $\mathcal{H}\colon \mathcal{X} \to \left\lbrace -1, 1 \right\rbrace$，根据分布 $\mathcal{D}$ 从 $\mathcal{X}$ 中 i.i.d. 采样得到示例 $D = \left\lbrace \bm{x}_i \right\rbrace_{i=1}^m$，其中 $\bm{x}_i \in \mathcal{X}, 0 < \delta < 1$，对任意 $h \in \mathcal{H}$，以至少 $1 - \delta$ 概率有

$$\begin{aligned} E(h) &\le \hat{E}(h) + R_m(\mathcal{H}) + \sqrt{\dfrac{\ln(1 / \delta)}{2 m}}\\ E(h) &\le \hat{E}(h) + \hat{R}_{D}(\mathcal{H}) + 3\sqrt{\dfrac{\ln(2 / \delta)}{2 m}} \end{aligned}$$

上面的定理就适合二分类问题。

Rademacher 复杂度与增长函数之间的关系有

假设空间 $\mathcal{H}$ 的 Rademacher 复杂度为 $R_m(\mathcal{H})$ 与增长函数 $\Pi_{\mathcal{H}}(m)$，满足

$$R_m(\mathcal{H}) \le \sqrt{\dfrac{2 \ln\Pi_{\mathcal{H}}(m)}{m}}$$

综合可得

$$E(h) \le \hat{E}(h) + \sqrt{\dfrac{2d \ln(\e m / d)}{m}} + \sqrt{\dfrac{\ln(1 / \delta)}{2m}}$$

稳定性

基于 VC 维和 Rademacher 复杂度分析泛化性能，得到的结果均与具体的学习算法无关，可使得人们脱离具体的学习算法考虑学习问题本身的性质。

为了获得与算法有关的分析结果，可以考察算法在输入（训练集）发生变化时，输出是否发生较大的变化，即「稳定性」。

给定 $D = \left\lbrace \bm{z}_i = (\bm{x}_i, y_i) \right\rbrace_{i=1}^m$，其中 $\bm{x}_i \in \mathcal{X}$ 是来自分布 $\mathcal{D}$ 的 i.i.d. 示例，$y_i \in \mathcal{Y} = \left\lbrace -1, 1 \right\rbrace$。

对假设空间 $\mathcal{H}\colon \mathcal{X} \to \left\lbrace -1, 1 \right\rbrace$ 和学习算法 $\mathfrak{L}$，令 $\mathfrak{L}_D \in \mathcal{H}$ 表示基于训练集 $D$ 从假设空间 $\mathcal{H}$ 中学得的假设，定义

• $D^{\setminus i}$ 表示移除 $D$ 中第 $i$ 个样例得到的集合 $\left\lbrace \bm{z}_1, \dots, \bm{z}_{i-1}, \bm{z}_{i+1}, \dots, \bm{z}_m \right\rbrace$；
• $D^i$ 表示替换 $D$ 中第 $i$ 个样例得到的集合 $\left\lbrace \bm{z}_1, \dots, \bm{z}_{i-1}, \bm{z}', \bm{z}_{i+1}, \dots, \bm{z}_m \right\rbrace$，其中 $\bm{z}' = (\bm{x}', y')$，$\bm{x}_i'$ 服从分布 $\mathcal{D}$ 并独立于 $D$。

损失函数 $\ell(\mathfrak{L}_D(\bm{x}), y)\colon \mathcal{Y} \times \mathcal{Y} \to \R^{+}$ 刻画假设 $\mathfrak{L}_D$ 的预测标记 $\mathfrak{L}_D(\bm{x})$ 与真实标记 $y$ 之间的差别，简记为 $\ell(\mathfrak{L}_D, \bm{z})$。

• 泛化损失：$\ell(\mathfrak{L}, D) = \mathbb{E}_{\bm{x} \in \mathcal{X}, \bm{z} = (\bm{x}, y)}\left[ \ell(\mathfrak{L}_D, \bm{z}) \right]$
• 经验损失：$\hat{\ell}(\mathfrak{L}_D, D) = \dfrac{1}{m} \sum_{i=1}^m \ell(\mathfrak{L}_D, \bm{z}_i)$
• 留一（leave-one-out）损失：$\ell_{\text{loo}}(\mathfrak{L}_D, D) = \dfrac{1}{m} \sum_{i=1}^m \ell(\mathfrak{L}_{D^{\setminus i}}, \bm{z}_i)$

算法的均匀稳定性（uniform stability）

对任何 $\bm{x} \in \mathcal{X}, \bm{z} = (\bm{x}, y)$，若学习算法 $\mathfrak{L}$ 满足

$$\left\lvert \ell(\mathfrak{L}_D, \bm{z}) - \ell(\mathfrak{L}_{D^{\setminus i}}, \bm{z}) \right\rvert \le \beta$$

则称 $\mathfrak{L}$ 关于损失函数 $\ell$ 满足 $\beta$-均匀性。

若算法 $\mathfrak{L}$ 关于损失函数 $\ell$ 满足 $\beta$-均匀性，则

$$\begin{aligned} \left\lvert \ell(\mathfrak{L}_D, \bm{z}) - \ell(\mathfrak{L}_{D^{i}}, \bm{z}) \right\rvert &\le \left\lvert \ell(\mathfrak{L}_D, \bm{z}) - \ell(\mathfrak{L}_{D^{\setminus i}}, \bm{z}) \right\rvert + \left\lvert \ell(\mathfrak{L}_{D^{\setminus i}}, \bm{z}) - \ell(\mathfrak{L}_{D^{i}}, \bm{z}) \right\rvert \\ &\le 2 \beta \end{aligned}$$

也即，移除示例的稳定性包含替换示例的稳定性。

若损失函数 $\ell$ 有界，对所有 $D$ 和 $\bm{z} = (\bm{x}, y)$ 有 $0 \le \ell(\mathfrak{L}_D, \bm{z}) \le M$，则有

给定从分布 $\mathcal{D}$ 上 i.i.d. 采样得到的大小为 $m$ 的示例集 $D$，若学习算法 $\mathfrak{L}$ 满足关于损失函数 $\ell$ 的 $\beta$-均匀稳定性，且损失函数 $\ell$ 的上界为 $M$，同时 $0 < \delta < 1$，则对任意 $m \ge 1$，以至少 $1 - \delta$ 的概率有

$$\begin{aligned} \ell(\mathfrak{L}, \mathcal{D}) &\le \hat{\ell}(\mathfrak{L}, D) + 2\beta + (4 m \beta + M) \sqrt{\dfrac{\ln(1 / \delta)}{2m}}\\ \ell(\mathfrak{L}, \mathcal{D}) &\le \ell_{\text{loo}}(\mathfrak{L}, D) + \beta + (4 m \beta + M) \sqrt{\dfrac{\ln(1 / \delta)}{2m}} \end{aligned}$$

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

经验误差与泛化损失之间差别的收敛率为 $\beta \sqrt{m}$，若 $\beta = O\left(\dfrac{1}{m}\right)$ 则可保证收敛率为 $O\left(\dfrac{1}{\sqrt{m}}\right)$。该收敛率与基于 VC 维和 Rademacher 复杂度得到的收敛率一致。

学习算法的稳定性分析关注的是 $|\hat{\ell}(\mathfrak{L}, D) - \ell(\mathfrak{L}, \mathcal{D})|$，即学习算法在训练集上的表现与在整个数据分布上的表现之间的差异；假设空间复杂度分析关注的是 $\sup\limits_{h \in \mathcal{H}} |E(h) - \hat{E}(h)|$，即假设空间中不同假设的泛化误差与经验误差之间的差异。

因此稳定性分析不必考虑假设空间中所有可能的假设，只需根据分析算法自身的特性（稳定性）来讨论输出假设 $\mathfrak{L}_D$ 的泛化稳定误差界。

必须假设 $\beta \sqrt{m} \to 0$ 才能保证稳定的学习算法具有一定的泛化能力，即经验损失收敛于泛化损失，否则可学习性无从谈起。

对于满足 ERM（即经验风险最小化）原则的学习算法，有

若学习算法是 ERM 且稳定的，则假设空间 $\mathcal{H}$ 可学习。

学习算法的稳定性能导出假设空间的可学习性。稳定性和假设空间可通过损失函数 $\ell$ 联系起来。