章节思路

这章是关于机器学习的理论基础，目的是分析学习任务的困难本质，为学习算法提供理论保证，并根据分析结果指导算法设计。

简而言之就是分析：

①学习任务在什么条件可以学习

②它与真相能贴近到什么程度（泛化误差界）

③算法需要至少达到什么条件

12.1 基础知识

—— 介绍几个概念和需要用到的不等式

12.2 PAC学习

—— PAC学习给出一个抽象地刻画机器学习能力的框架，即以上①②③的基础框架

12.3 有限假设空间——12.5 Rademacher复杂度

—— 分析①学习任务在不同假设空间复杂度下的可学习，得出②③，其中③一般用样本复杂度表示

—— 这几节是层层递进，对假设空间的条件不断放开限制，最终证明都是可学习

—— 以上都是仅考虑学习任务的本质，对所有学习算法都适用

12.6 稳定性

—— 通过考虑算法的稳定性分析，得到①学习任务在具体学习算法下的可学习

—— 分析了即使算法的输入（训练集）改变，仍可证假设空间的可学习

12.1 基础知识

[1] 泛化误差：在新样本上的误差

$E(h ; \mathcal{D})=P_{\boldsymbol{x} \sim \mathcal{D}}(h(\boldsymbol{x}) \neq y)$

[2] 经验误差：学习器在训练集上的误差

$\widehat{E}(h ; D)=\frac{1}{m} \sum_{i=1}^{m} \mathbb{I}\left(h\left(\boldsymbol{x}_{i}\right) \neq y_{i}\right)$

[3] 两者联系：由于训练集D为样本分布的独立同分布采样，经验误差的期望等于其泛化误差

书内几个常用不等式在具体推算时会运用到，本章不多做推算过程，可自行了解

12.2 PAC可学习（概率近似正确）

12.2.1 有关概念:

[1] 概念 c ：从样本空间到标记空间的映射为概念 c

可以将所有实例按真实标记一致的方法完全分开则称 c 为目标概率，目标概率集合为概率类 C

[2] 假设空间 H ：学习算法学得的概念 h ，其集合为假设空间 H

学习算法：若 H 存在目标概率 c ，则称该问题对学习算法“可分的”和“一致的”；否则为“不可分的”和“不一致的”

[3] PAC概率近似正确：

因为受到因素制约（等效假设，采样偶然性）

只能以较大概率（用置信度 δ(0,1) 表示）——近似正确

在某种误差（用误差参数 ε(0,1) 表示）下接近目标概率 c ——可能正确

这些概念下文会直接用字母表示，不记得就回到这里看

12.2.2 有关定义：

[1] PAC辨识：

$P(E(h) \leqslant \epsilon) \geqslant 1-\delta$
① h 的泛化误差在 ε 以内——学的 c 的 ε 近似

②可能性大于等于 1-δ——较大概率学得

【学习算法能从 H 中PAC辨识 C】

[原理]——为什么h的泛化误差在 ε 以内

因为只要 h 的泛化误差尽可能接近于 c 的泛化误差就好
$P\{E(h)-E(c) \leq \varepsilon \} \geqq 1-\sigma$

c 的泛化误差一定为0，即 E(c)=0

$P(E(h) \leqslant \epsilon) \geqslant 1-\delta$

[2] PAC可学习：

①若学习算法能从 H 中PAC辨识 C

②样本数目满足多项式函数（与 ε 、 δ 、 x 和 c 的复杂度有关）

【C 对 H 是PAC可学习的】

[3] PAC学习算法：

①若 C 对 H 而言是PAC可学习的

②学习算法运行时间满足多项式函数（当处理每个样本的时间为常数，则等价于样本复杂度）

【C 是高效PAC可学习的，学习算法为 C 的PAC学习算法】

[4] 样本复杂度：

①满足PAC学习算法

【多项式函数的最小 m 为样本复杂度】

12.2.3 结论：

PAC学习给出了一个抽象地刻画机器学习能力的框架，基于框架对问题进行理论探讨

其中一个问题是H的复杂度

H 的复杂度：

H 与 C 一致：学习算法能力与学习任务恰好匹配，即“恰PAC可学习”，但这是不可能的啦

H 与 C 不一致： H 越大其包含任意目标概念的概率也越大，但从中找到某个具体的目标概念的难度也越大，分为“有限假设空间”和“无限假设空间”

12.3 有限假设空间

12.3.1 可分情形

c 在 H 内——存在 h 在 D 上不会出现标记错误，即为 c

[1] 策略：

①排除任何在 D 上出现标记错误的的 h ，得到若干个训练误差为0的等效假设

②为了得到唯一假设，至少需要样本 $\frac{1}{\epsilon}\left(\ln |\mathcal{H}|+\ln \frac{1}{\delta}\right)$

[原理]——为什么样本需要这么多

保证泛化误差大于 ε 且在训练集表现完美的所有假设出现概率之和不大于 δ，可得

$P(h \in \mathcal{H}: E(h)>\epsilon \wedge \widehat{E}(h)=0) 即可推出所需样本数量</blockquote>[2] 结论：【可分的有限假设空间都是PAC可学习】h 泛化误差随着样本 m 增多而收敛到0，收敛速度为<img class=$
即是让那些等效假设中在小误差以内接近 c 的概率大一点
为满足这样的概率，求出 m 的所需

[2] 结论：

【可分的有限假设空间都是PAC可学习】

h 泛化误差随着样本 m 增多而收敛到0，收敛速度为 $O\left(\frac{1}{m}\right)$

12.3.2 不可分情形

c 在 H 外——所有 h 在 D 上都会出现标记错误

[1] 策略：

①计算 H 所有 h 的泛化误差

②找出泛化误差最小的 h* ，学得 h* 的 ϵ 近似

[原理]——为什么学得 h* 的 ϵ 近似

我们可以看回PAC可学习，他是因为 C 存在于 H 中，c 就是最好的近似目标

但当 c 在 H 外，我们就要另寻能够近似的目标，于是选择 H 中表现最好的 h ，即近似泛化误差最小的 h*

[原理]——为什么可以用经验误差近似泛化误差

①通过Hoeffding不等式和经验误差的期望等于其泛化误差结合，再进行转换可得

$\widehat{E}(h)-\sqrt{\frac{\ln (2 / \delta)}{2 m}} \leqslant E(h) \leqslant \widehat{E}(h)+\sqrt{\frac{\ln (2 / \delta)}{2 m}}$
阐明了当观测集样本数量 m 足够大的时候，h 的经验误差是其泛化误差很好的近似

②其中在有限假设空间中，对 H 也有要求

$P(|E(h)-\widehat{E}(h)| \leqslant \sqrt{\frac{\ln |\mathcal{H}|+\ln (2 / \delta)}{2 m}}) \geqslant 1-\delta$

其泛化误差界关于 H 和 m，解释了当模型很复杂（H很大），就需要很多样本（m也要大）才能保证经验误差是泛化误差很好的近似

[2] 结论：

【不可分的有限假设空间都是不可知PAC可学习】

[3] 不可知PAC可学习:（不可知—— c 不在 H 内）

①若学习算法满足 $P\left(E(h)-\min _{h^{\prime} \in \mathcal{H}} E\left(h^{\prime}\right) \leqslant \epsilon\right) \geqslant 1-\delta$

h 的泛化误差 与其 H 中最小泛化误差的差值不大于 ε 的可能不小于 1-δ

②样本数目满足多项式函数（与 ε 、 δ 、 x 和 c 的复杂度有关）

【C 对 H 是不可知PAC可学习的】

12.4 无限假设空间——VC维

12.4.1 有关概念

[1] 增长函数：假设空间 H 对 m 个示例所能赋予标记的最大可能结果数，表示 H 的复杂度

$\Pi_{\mathcal{H}}(m)=\max _{\left\{x_{1}, \ldots, x_{m}\right\} \subseteq \mathcal{X}}\left|\left\{\left(h\left(\boldsymbol{x}_{1}\right), \ldots, h\left(\boldsymbol{x}_{m}\right)\right) | h \in \mathcal{H}\right\}\right|$

显然，H 对样本所能赋予标签的可能结果数越多， H 的表示能力就越强，增长函数可以用来反映 H 的复杂度

注意的是不同数据集，增长函数可能不同

[原理]——为什么要用标记的最大可能结果数表示 H 的复杂度

因为在无限假设空间下，H 无法计算，但增长函数描述的标记的可能结果是有限的，所以用增长函数刻画 H 的复杂度

比如：只有两个样本A和B，有多少 h 对其标记，最终也只有①A和B都是好瓜②A是好瓜，B是坏瓜③A是坏瓜，B是好瓜④A和B都是坏瓜。这四种情况

[2] 估计经验误差与泛化误差之间的关系：

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

即使在无限假设空间下，在一定条件下，经验误差也可以近似泛化误差

[3] 对分：二分类问题中，H 中 h 对 D 中示例赋予标记的每种可能结果成为 D 的一种对分

比如：只有A和B，h 标记A是好瓜B是坏瓜，这就是一种对分

[4] 打散：若 H 能实现 D 所有对分，即可以产生所有的预测结果，则 D 能被 H 打散

12.4.2 VC维

H 的 VC维是能被 H 打散的最大示例集大小 d

书中例子能较好解释

[1] VC维与增长函数的定量关系

[2] 增长函数的上界

[3] VC维的泛化误差界

[1]-[3] 的推导过程可自行了解

其中VC维的泛化误差界只与 m 有关，收敛速度为 $O\left(\frac{1}{\sqrt{m}}\right)$ ，与数据分布和样例集无关，因此，基于VC维的泛化误差界是分布无关、数据独立，使得其可学习型分析结果具有一定的普适性

[原理]——为什么要用VC维推出泛化误差界

在12.4.1中我们得到经验误差与泛化误差之间的关系，其泛化误差界是有关增长函数的。于是我们特意定义VC维，用VC维与增长函数的关系，使得可以用具体数值 d 表示增长函数，以便我们求出更具体的泛化误差界

[4] 结论：

【任何VC维有限的假设空间 H 都是（不可知）PAC可学习的】

①学习算法满足经验风险最小化原则（ERM）

②若假设空间的最小泛化误差为0 ，即 c 包含在假设空间中，则是PAC可学习；若最小泛化误差不为0，则称为不可知PAC可学习

经验风险最小化原则（ERM）

经验风险最小的模型是最优的模型

12.5 Rademacher复杂度

12.5.1 Rademacher复杂度

[1] 函数空间关于集合的Rademacher复杂度

[2] 函数空间关于分布的Rademacher复杂度

衡量了函数空间与随机噪音在集合/分布的相关性

[原理]——为什么要引入Rademacher复杂度

①与VC维中引入增长函数相似，是一种刻画假设空间复杂度的途径

②VC维的泛化误差界是分布无关、数据独立不同，因此缺少普适性。Rademacher复杂度则考虑了数据分布，能让泛化误差更紧一点

[原理]——为什么引入随机噪音

考虑了数据分布，会发现样例中有因为随机因素，变得不真实的标记，于是我们与其选择 H 中在训练集表现最好的 h ，不如选择事先考虑随即噪音影响的 h

12.5.2 基于Rademacher复杂度的泛化误差界

[1] 回归问题

[2] 二分类问题

我们由以上基于Rademacher复杂度的泛化误差界与基于VC维泛化误差界比较，明显发现Rademacher复杂度的泛化误差界考虑了数据分布和样例集，类似对问题“量身定制”，因此通常比VC维泛化误差更紧一点

12.5.3 Rademacher复杂度与增长函数的关系

由此又可推断出基于VC维得泛化误差界

12.6 稳定性

12.6.1 有关概念

[1] 训练集D的变化：

[2] 损失函数

[原理]——为什么要引入稳定性
无论基于VC维还是Rademacher复杂度推导泛化误差界，结果都与具体算法无关，使得能够脱离学习算法设计考虑学习问题本质，但希望获得算法有关分析结果，就要引用稳定性

[原理]——怎么测量稳定性

稳定性考察算法在输入（训练集）发生变化时，输出是否会随之发生较大的变化。

[1]——考察算法在输入（训练集）发生变化时

[2] ——输出是否会随之发生较大的变化

12.6.2 均匀稳定性

$\left|\ell\left(\mathfrak{L}_{D}, \boldsymbol{z}\right)-\ell\left(\left.\mathfrak{L}_{D}\right|_{\mathfrak{t}}, \boldsymbol{z}\right)\right| \leqslant \beta, \quad i=1,2, \ldots, m$

若学习算法满足以上式子，则称之为关于损失函数满足 β-均匀稳定性，给出了稳定性的判断依据

[原理]——为什么不计算替代示例的稳定性

$\begin{equation}\begin{array}{l}\quad\left|\ell\left(\mathfrak{L}_{D}, \boldsymbol{z}\right)-\ell\left(\mathfrak{L}_{D^{i}}, \boldsymbol{z}\right)\right| \\\leqslant\left|\ell\left(\mathfrak{L}_{D}, \boldsymbol{z}\right)-\ell\left(\mathfrak{L}_{D} | i, \boldsymbol{z}\right)\right|+\left|\ell\left(\mathfrak{L}_{D^{i}, z}\right)-\ell\left(\mathfrak{L}_{D} | i, z\right)\right| \\\leqslant 2 \beta\end{array}\end{equation}$
移除示例的稳定性包含替代示例的稳定性，所以我们直接用移除示例的稳定性就同时包含了训练集的两者变化

12.6.3 基于稳定性的泛化误差界

$\begin{aligned}&\ell(\mathcal{L}, \mathcal{D}) \leq \hat{\ell}(\mathcal{L}, D)+2 \beta+(4 m \beta+M) \sqrt{\frac{\ln (1 / \delta)}{2 m}}\\&\ell(\mathcal{L}, \mathcal{D}) \leq \ell_{l o o}(\mathcal{L}, D)+\beta+(4 m \beta+M) \sqrt{\frac{\ln (1 / \delta)}{2 m}}\end{aligned}$

①损失函数有界 $0 \leqslant l\left(\mathfrak{L}_{D}, z\right) \leqslant M$
②算法满足损失函数的β-均匀稳定性
③对存在样本的示例集

至少有1-δ的概率满足以上泛化误差界

若 $\beta=O\left(\frac{1}{m}\right)$ ，可保证收敛率为 $O\left(\frac{1}{\sqrt{m}}\right)$ ，即与基于VC维和Rademacher复杂度一样

12.6.4 结论

【学习算法是ERM且稳定的，则假设空间可学习】

①假设 $β\sqrt{m} \rightarrow 0$ 且 $β=\frac{1}{m}$ ，保证稳定的学习算法具有一定的泛化能力，即经验损失收敛于泛化损失
②学习算法是ERM

[原理]——为什么学习算法稳定性能导出假设空间的可学习性

两者通过损失函数联系

《西瓜书》第12章计算学习理论

《西瓜书》第12章计算学习理论

章节思路

12.1 基础知识

12.2 PAC学习

12.3 有限假设空间——12.5 Rademacher复杂度

12.6 稳定性

12.1 基础知识