本章主要讨论二分类问题，若无特别说明，\( y_i \in \lbrace-1, +1\rbrace \)。
12.1 基础知识
-
泛化误差：E(h), 预测不符的概率
-
经验误差：\( \hat{E}(h) \), 数据集上预测不符的频率
几个常用不等式：
-
Jensen 不等式：期望的凸函数 f(E) <= 凸函数的期望 E(f)
-
HoefIding 不等式：如果\( 0<=x_i<=1 \)，样本均值和期望之间差得超过\( \epsilon \)的概率有上界。
-
McDiarmid 不等式：如果更换函数中的一个参数（随机变量）产生的变化有上限，那么该函数与其期望之间差得超过\( \epsilon \)的概率有上界。
12.2 PAC 学习
-
目标概念：c, 对任何样例 (x, y) 有 c(X) = y 成立。
-
概念类：C, 对于同一类问题，所有我们希望学得的目标概念所构成的集合称为”概念类” (concept class)
-
假设空间：所有可能概念h(不一定是目标概念)构成的集合。如果 H = C，称为”恰 PAC 可学习” (properly PAC learnable)
-
可分的：若目标概念\( c \in H \)，则 H 中存在假设能将所有示例按与真实标记一致的方式完全分开，我们称该问题对学习算法是”可分的” (separable) ，亦称”一致的” (consistent)
训练集 D 往往仅包含有限数量的样例，因此，通常会存在一些在 D 上”等效”的假设，学习算法对它们无法区别; 再如，从分布 Ð 采样得到 D 的过程有一定偶然性，可以想象，即便对同样大小的不同训练集，学得结果也可能有所不同。
所以用概率近似正确 (Probably Approximately Correct，简称 PAC) 这一套去衡量算法好坏，以较大的概率学得误差满足预设上限的模型。
- PAC 可学习：只要数据量 m >= 某个多项式时（最小的 m，称为学习算法 ￡ 的样本复杂度），学习算法 ￡ 能从假设空间 H 中 PAC 辨识概念类 C ，则称概念类 C 对假设空间 H 而言是 PAC 可学习的，有时也简称概念类 C 是 PAC 可学习的。如果算法的运行时间也是多项式函数，则称概念类 C 是高效 PAC 可学习 (efficiently PAC learnable) 的，称￡为概念类 C 的 PAC 学习算法。
12.3 有限假设空间
12.3.1 可分情形
对 PAC 学习来说，只要训练集 D 的规模能使学习算法 ￡ 以概率\( 1-\delta \)找到目标概念的\( \epsilon \)近似即可.
若训练集 D 足够大，则可不断借助 D 中的样例剔除不一致的假设，直到究中仅剩下一个假设为止，这个假设就是目标概念 c。在这种策略下，只需要控制“泛化误差大于\( \epsilon \)但是又完美符合训练集”的概率不大于\( \delta \)即可。
此概率 < (12.12) < \( \delta \)，通过不等式可以解出具体的 m 。由此可知，有限假设空间 H 都是 PAC 可学习的。
12.3.2 不可分情形
由Hoeffding 不等式（样本均值和期望不会差太多）可得(12.17)，将其右项等于\( \delta \)可得(12.18)。考虑假设空间中的每一个 h 都可能被输出，可得(12.19)。即 h 的经验误差是其泛化误差很好的近似。
不可知PAC可学习：当 h = c，E(h) = 0; 可当 c 不在 H 中，只好找泛化误差最小的假设的近似。只要数据量 m >= 某个多项式时，学习算法 ￡ 能从假设空间 H 中以概率\( 1-\delta \)找到泛化误差最小假设的\( \epsilon \)近似，则称假设空间句是不可知 PAC 可学习的。
12.4 VC 维
度量假设空间的复杂度。
- 增长函数： 表示假设空间 H 对 m 个示例所能赋予标记的最大可能结果数。
定理 12.2 给出了在无限假设空间中，经验误差和其泛化误差差距很大的概率有上限，且这个上限正比于增长函数。
若假设空间对能实现示例集 D 上的所有对分，即能给出\(2^m \)个可能标记则称示例集 D 能被假设空间 H “打散”。
假设空间的 VC 维是能被 H 打散的最大示例集的大小。
对于二维实平面上所有线性划分构成的假设空间，如果示例集大小为4就不能实现所有16中标记结果，所以它的假设空间的 VC 维为3.
已知 VC 维，可以知道增长函数的上界，见引理12.2和推论12.2。关于引理12.2一开始的证明，d = VC 维，d = 0, m = 1, 则增长函数取值为1；d = 1, m = 1, 则增长函数取值为2；都符合不等式，可以作为数学归纳法的基。而推论12.2的证明最后一步对\( (1+d/m)^m \)放缩为\( e^d \)。
至此，替换定理12.2中的关于增长函数的部分，可以用VC维刻画经验误差和其泛化误差的差距。进一步可以得到基于 vc 维的泛化误差界是**分布无关(distribution-free) 、数据独立 (data- independent) **的。
而如果我们能找到使经验损失最小化的学习算法，可以得到定理 12.4：任何 VC 维有限的假设空间 H 都是 (不可知) PAC 可学习的。具体来说，对于我们找到的使经验损失最小的假设h，和实际泛化误差最小的假设g，\(E(h)\)和\(\hat{E}(h)\)之间不会差太远，\(E(g)\)和\(\hat{E}(g)\)之间不会差太远，而\(\hat{E}(h)\)会比\(\hat{E}(g)\)小，所以\(E(h)\)比\(E(g)\)也不会差太多。
12.5 Rademacher复杂度
由于y只能取±1，所以经验误差最小可以简化为使\(\sum_1^m{y_i h(x_i)}\)最大。
然而，现实任务中样例的标记有时会受到噪声影响，即对某些样例 (Xi ， Yi) , 其 Yi 或许己受到随机因素的影响，不再是 Xi 的真实标记。在此情形下，选择假设空间 H 中在训练集上表现最好的假设，有时还不如选择 H 中事先己考虑了 随机噪声影响的假设。
因此将上式中的\(y_i\)替换为随机变量\(\sigma_i\)，为了迎合这一随机的情况，需要假设空间的灵活程度更强，产生各种各样的h：如果能打散训练集D，对任意 σ 总有一个假设使得\(h(x_i) = \sigma_i (i=1 ， 2 ，.… ， m) \)，就可以一直产生经验误差为0的假设。
将假设空间 H 替换为函数空间 F 即可得到关于某一个特定数据集 Z 的经验Rademacher复杂度，而考虑 Z 的分布后求期望就可以得到 Rademacher 复杂度。
关于定理12.5，要注意它改变了一直以来的值域，不再是±1而是[0, 1]，因此只改变一条数据的话，对于经验误差最多差1/m，根据 McDiarmid 不等式 可以得到一个上界(12.44)，再套入一个从期望性质得到的不等式可以证得(12.42)。(12.44)结合本身 Rademacher 复杂度和经验 Rademacher 复杂度间的关系，可以得到(12.42)的变形(12.43)。
至于原来的二分类问题，可以用\(f_h(x, y) = I(h(x) \neq y)\)与上面的值域[0, 1]情形连接，并得到类似的结论定理12.6。它用来衡量泛化误差和经验误差的差距。
基于 Rademacher 复杂度的泛化误差界依赖于具体学习问题上的数据分布，有点类似于为该学习问题”量身定制”的，因此它通常比基于 vc 维的泛化误差界更紧一些。这一点从定理12.7也能看出， Rademacher 复杂度小于等于某个包含增长函数的表达式，再结合推论12.2，增长函数小于等于某个包含VC维的表达式，可知 Rademacher 复杂度小于等于某个包含VC维的表达式。将之代入定理12.6，我们可以从 Rademacher 复杂度和增长函数能推导出基于 vc 维的泛化误差界。
12.6 稳定性
对于任何数据点，删去数据集中任意一条数据后所产生的假设和原来的数据集产生的假设给出的预测都小于\(\beta\)，则称算法￡关于损失函数 l 满足 ß-均匀稳定性。同时移除示例的稳定性包含替换示例的稳定性。
定理12.8告诉我们，满足 ß-均匀稳定性的算法的泛化损失以一定概率小于经验损失加某个表达式，泛化损失不会比经验损失差太多。
若学习学法是ERM（输出的假设经验风险最小化）且满足 ß-均匀稳定性的，首先令 g 表示 H 中具有最小泛化损失的假设。由 Hoeffding 不等式 (12.6) 可知，当m够大，g的经验损失不会离泛化损失差太远；同时ß-均匀稳定性使得算法的输出假设的泛化和经验损失也不会差得太远。通过类似于定理 12.4的证明思路可以得到算法的输出假设和 g 的泛化误差之间也不会差得太远。这就是定理12.9的证明。
由于稳定性也在讨论经验损失，这使得稳定性可以和可学习性联系起来。
