PAC 学习框架

PAC 学习模型

基础定义

Probably Approximately Correct (PAC)，即概率近似正确。PAC 学习可以分为两部分：

1. 近似正确（ Approximately Correct ）：一个假设 是“近似正确”的，是指其在泛化错误 #card=math&code=R%28h%29) 小于一个界限 ， 一般为趋于0的一个数，如果 #card=math&code=R%28h%29) 比较大，说明模型不能用来做正确的“预测”．
2. 可能（ Probably ）：一个学习算法 有“可能”以 的概率学习到这样一个“近似正确”的假设．

一个 PAC 可学习（ PAC-Learnable ）的算法是指该学习算法能够在多项式时间内从合理数量的训
练数据中学习到一个近似正确的假设 ．

表示在样本 上学习到的假设 ，#card=math&code=R%28h_S%29) 表示 的泛化误差。

该公式表明：对于任意小的 ， 只要样本个数 足够大（能被关于 #card=math&code=1%2F%5Cepsilon%2C1%2F%5Cdelta%2Csize%28c%29) 的多项式表示），就能以 的概率使 %5Cleq%20%5Cepsilon#card=math&code=R%28h_S%29%5Cleq%20%5Cepsilon) 成立.

这样的概念类 称为PAC可学的（PAC-learnable）

沿轴矩形的学习(axis-aligned rectangles)

是我们要学习的矩形框，矩形框内的样本为正例，框外的样本为负例， 是可能的一个假设.

我们可以证明这种矩形框是PAC可学的——我们设定一个简单的算法：取包裹所有正例样本的最小矩形框，就像这样：

首先，我们先假设样本点由随机分布 产生，用 表示 区域的概率质量，即一个样本点落在 中的概率.

我们先定义假设框 的泛化误差 #card=math&code=%5Cmathcal%7BR%7D%28R_S%29)：样本点落在 区域的期望.

之后我们做一个假设 ：

否则， %3C%5Cepsilon#card=math&code=%5Cmathcal%7BR%7D%28R_S%29%3C%5Cepsilon) 显然恒成立.

然后，我们在矩形的四边构建4个小矩形 ，使得 .

我们记周围这一圈阴影部分为 ，显然有：

如果我们的假设框 的四条边都在阴影部分 中，即 ，那么有：

%3D%5Cmathbb%7BP%7D%5Cleft%5B%20r-R_S%20%5Cright%5D%20%3C%5Cmathbb%7BP%7D%5Cleft%5B%20r%20%5Cright%5D%20%5Cle%20%5Cepsilon%0A#card=math&code=%5Cmathcal%7BR%7D%28R_S%29%3D%5Cmathbb%7BP%7D%5Cleft%5B%20r-R_S%20%5Cright%5D%20%3C%5Cmathbb%7BP%7D%5Cleft%5B%20r%20%5Cright%5D%20%5Cle%20%5Cepsilon%0A)

那么我们考虑其逆否命题：

若 ，可推出 ，也就是说 至少与 中的某一个相交为空集，即：

说明 ，即 .

于是上述命题可转化为公式形式：

%20%5Em%5C%5C%0A%09%26%5Cleq%204%5Cexp%20%5Cleft(%20-m%5Cepsilon%20%2F4%20%5Cright)%0A%5Cend%7Baligned%7D%0A#card=math&code=%5Cbegin%7Baligned%7D%0A%09%5Cunderset%7BS%5Csim%20%5Cmathcal%7BD%7D%5Em%7D%7B%5Cmathbb%7BP%7D%7D%5Cleft%5B%20%5Cmathcal%7BR%7D%5BRS%5D%3E%5Cepsilon%20%5Cright%5D%20%26%5Cleq%20%5Cunderset%7BS%5Csim%20%5Cmathcal%7BD%7D%5Em%7D%7B%5Cmathbb%7BP%7D%7D%5Cleft%5B%20%5Cbigcup%7Bi%3D1%7D%5E4%7B%5Cleft%5C%7B%20RS%5Ccap%20r_i%3D%5Cemptyset%20%5Cright%5C%7D%7D%20%5Cright%5D%5C%5C%0A%09%26%5Cleq%20%5Csum%7Bi%3D1%7D%5E4%7B%5Cunderset%7BS%5Csim%20%5Cmathcal%7BD%7D%5Em%7D%7B%5Cmathbb%7BP%7D%7D%5Cleft%5B%20%5Cleft%5C%7B%20R_S%5Ccap%20r_i%3D%5Cemptyset%20%5Cright%5C%7D%20%5Cright%5D%7D%5C%5C%0A%09%26%5Cleq%204%5Cleft%28%201-%5Cfrac%7B%5Cepsilon%7D%7B4%7D%20%5Cright%29%20%5Em%5C%5C%0A%09%26%5Cleq%204%5Cexp%20%5Cleft%28%20-m%5Cepsilon%20%2F4%20%5Cright%29%0A%5Cend%7Baligned%7D%0A)

其中第3行到第4行的转化是重点：我们的假设框 是由样本 生成的，如果假设框与 不相交，那么必然没有样本点落在 内，对于 个样本点都没落进的概率为 %20%5Em#card=math&code=%5Cleft%28%201-%5Cfrac%7B%5Cepsilon%7D%7B4%7D%20%5Cright%29%20%5Em).

如果我们要使 恒成立，那么需使：

%20%3C%5Cdelta%20%0A#card=math&code=4%5Cexp%20%5Cleft%28%20-m%5Cepsilon%20%2F4%20%5Cright%29%20%3C%5Cdelta%20%0A)

解得：

最终得出结论：

当 ，时，有 成立.

泛化界

除此之外，PAC可学性的另一种等价描述可以由泛化界（generalization bound）表示：

在 的概率下，泛化误差有关于 表示的上界：

有限假设集上的学习保证——一致情况

参考【Mohri-机器学习基础】第2章: PAC学习框架

一致（consistent）

有限假说集的学习问题划分为两大类：

• 一致
• 不一致

对于有限假设集 ，我们要学习的目标概念 可能在 中，也可能不在.

如果 ，那么称为一致情况（consistent case）.

对于一致性的情况，我们能找到假设 使得其在 上的经验误差为0，即 %3D0#card=math&code=%5Cwidehat%7BR%7D%28h_S%29%3D0) .

上面那个矩形学习的例子明显是一致的：学到的假设框 在样本 上没有误差.

学习界（Learning bound）

该定理给出了一般性的结论：对于有限假设集 ，如果学习算法 每次学到的假设 都是一致的——经验误差为0，那么 为 PAC可学算法，并且给出了样本复杂度与泛化界.

可以看到，随着样本数 的增大，泛化误差减少的速率为 #card=math&code=O%281%2Fm%29).

证明： 定义 ， 对于单个样本 ，有： %20%3Dc%5Cleft(%20x%20%5Cright)%20%5Cmid%20h%5Cin%20%5Cmathcal%7BH%7D%7B%5Cepsilon%7D%20%5Cright%5D%20%5Cle%201-%5Cepsilon%0A#card=math&code=%5Cmathbb%7BP%7D%5Cleft%5B%20h%5Cleft%28%20x%20%5Cright%29%20%3Dc%5Cleft%28%20x%20%5Cright%29%20%5Cmid%20h%5Cin%20%5Cmathcal%7BH%7D%7B%5Cepsilon%7D%20%5Cright%5D%20%5Cle%201-%5Cepsilon%0A) 那么对于样本 ，有： %20%3D0%5Cmid%20h%5Cin%20%5Cmathcal%7BH%7D%7B%5Cepsilon%7D%20%5Cright%5D%20%5Cle%20%5Cleft(%201-%5Cepsilon%20%5Cright)%20%5Em%0A#card=math&code=%5Cmathbb%7BP%7D%5Cleft%5B%20%5Cwidehat%7BR%7D_S%5Cleft%28%20h%20%5Cright%29%20%3D0%5Cmid%20h%5Cin%20%5Cmathcal%7BH%7D%7B%5Cepsilon%7D%20%5Cright%5D%20%5Cle%20%5Cleft%28%201-%5Cepsilon%20%5Cright%29%20%5Em%0A) 那么存在 使得 的概率为： %3D0%5Cright%5D%20%26%3D%5Cmathbb%7BP%7D%5Cleft%5B%5Cwidehat%7BR%7D%7BS%7D%5Cleft(h%7B1%7D%5Cright)%3D0%20%5Cvee%20%5Ccdots%20%5Cvee%20%5Cwidehat%7BR%7D%7BS%7D%5Cleft(h%7B%5Cleft%7C%5Cmathcal%7BH%7D%7B%5Cepsilon%7D%5Cright%7C%7D%5Cright)%3D0%5Cright%5D%20%5C%5C%0A%26%20%5Cleq%20%5Csum%7Bh%20%5Cin%20%5Cmathcal%7BH%7D%7B%5Cepsilon%7D%7D%20%5Cmathbb%7BP%7D%5Cleft%5B%5Cwidehat%7BR%7D%7BS%7D(h)%3D0%5Cright%5D%20%5C%5C%0A%26%20%5Cleq%20%5Csum%7Bh%20%5Cin%20%5Cmathcal%7BH%7D%7B%5Cepsilon%7D%7D(1-%5Cepsilon)%5E%7Bm%7D%20%5Cleq%7C%5Cmathcal%7BH%7D%7C(1-%5Cepsilon)%5E%7Bm%7D%20%5Cleq%7C%5Cmathcal%7BH%7D%7C%20e%5E%7B-m%20%5Cepsilon%7D%0A%5Cend%7Baligned%7D%0A#card=math&code=%5Cbegin%7Baligned%7D%0A%5Cmathbb%7BP%7D%5Cleft%5B%5Cexists%20h%20%5Cin%20%5Cmathcal%7BH%7D%7B%5Cepsilon%7D%3A%20%5Cwidehat%7BR%7D%7BS%7D%28h%29%3D0%5Cright%5D%20%26%3D%5Cmathbb%7BP%7D%5Cleft%5B%5Cwidehat%7BR%7D%7BS%7D%5Cleft%28h%7B1%7D%5Cright%29%3D0%20%5Cvee%20%5Ccdots%20%5Cvee%20%5Cwidehat%7BR%7D%7BS%7D%5Cleft%28h%7B%5Cleft%7C%5Cmathcal%7BH%7D%7B%5Cepsilon%7D%5Cright%7C%7D%5Cright%29%3D0%5Cright%5D%20%5C%5C%0A%26%20%5Cleq%20%5Csum%7Bh%20%5Cin%20%5Cmathcal%7BH%7D%7B%5Cepsilon%7D%7D%20%5Cmathbb%7BP%7D%5Cleft%5B%5Cwidehat%7BR%7D%7BS%7D%28h%29%3D0%5Cright%5D%20%5C%5C%0A%26%20%5Cleq%20%5Csum%7Bh%20%5Cin%20%5Cmathcal%7BH%7D%7B%5Cepsilon%7D%7D%281-%5Cepsilon%29%5E%7Bm%7D%20%5Cleq%7C%5Cmathcal%7BH%7D%7C%281-%5Cepsilon%29%5E%7Bm%7D%20%5Cleq%7C%5Cmathcal%7BH%7D%7C%20e%5E%7B-m%20%5Cepsilon%7D%0A%5Cend%7Baligned%7D%0A) 由于：学到的一致假设 的概率 存在一致假设 的概率 %3D0%20%5Cright%5D%20%5Cle%20%7C%5Cmathcal%7BH%7D%7Ce%5E%7B-m%5Cepsilon%7D%0A#card=math&code=%5Cmathbb%7BP%7D%5Cleft%5B%20hS%5Cin%20%5Cmathcal%7BH%7D%7B%5Cepsilon%7D%20%5Cright%5D%20%5Cle%20%5Cmathbb%7BP%7D%5Cleft%5B%20%5Cexists%20h%5Cin%20%5Cmathcal%7BH%7D%7B%5Cepsilon%7D%3A%5Cwidehat%7BR%7D_S%28h%29%3D0%20%5Cright%5D%20%5Cle%20%7C%5Cmathcal%7BH%7D%7Ce%5E%7B-m%5Cepsilon%7D%0A) 要使：  需使： 解得： %0A#card=math&code=m%5Cge%20%5Cfrac%7B1%7D%7B%5Cepsilon%7D%5Cleft%28%20%5Cln%20%7C%5Cmathcal%7BH%7D%7C%2B%5Cln%20%5Cfrac%7B1%7D%7B%5Cdelta%7D%20%5Cright%29%0A)

布尔变量的组合

假如我们需要学习的概念类 为 个布尔变量（Boolean literals）的组合，例如当 时，目标概念可以是 ，那么对于这个目标概念而言，#card=math&code=%281%2C0%2C0%2C1%29) 是一个正样本，而 #card=math&code=%281%2C0%2C0%2C0%29) 是一个负样本.

首先，每个布尔变量有3种状态：0、1或不包含，因此样本空间大小为 .

这时，我们给出一个算法去根据样本预测原目标（具体算法略去），保证得到的假设是一致的.

那么，对于任意的 ，我们可以算出其样本复杂度：

%0A#card=math&code=m%5Cge%20%5Cfrac%7B1%7D%7B%5Cepsilon%7D%5Cleft%28%20n%5Cln3%2B%5Cln%20%5Cfrac%7B1%7D%7B%5Cdelta%7D%20%5Cright%29%0A)

当 时，我们可算出 .

也就是说，在至少149个样本的训练后，我们有98%的概率保证，算法习得假设的泛化误差小于 0.1，即精确度可达到 90% 以上。

有限假设集上的学习保证——不一致情况

对于一致情况，我们能找到 使得 %3D0#card=math&code=%5Cwidehat%7BR%7D%28h_S%29%3D0) ，那么学习保证（Guarantees）可以由 来刻画.

对于不一致的情况，我们不一定能找到使得这样的 ，学习保证就只能由 来刻画：

该推论可以直接由 Hoeffding’s inequality 得到：

对于 0-1分类问题，我们将第 次分类正确记为 ，那么

%20%3D%5Cfrac%7B1%7D%7Bm%7D%5Csum%7Bi%3D1%7D%5Em%7BY_i%7D%2C%5Cquad%20R%5Cleft(%20h%20%5Cright)%20%3D%5Cmathbb%7BE%7D%5Cleft%5B%20%5Cfrac%7B1%7D%7Bm%7D%5Csum%7Bi%3D1%7D%5Em%7BYi%7D%20%5Cright%5D%20%0A#card=math&code=%5Cwidehat%7BR%7D_S%5Cleft%28%20h%20%5Cright%29%20%3D%5Cfrac%7B1%7D%7Bm%7D%5Csum%7Bi%3D1%7D%5Em%7BYi%7D%2C%5Cquad%20R%5Cleft%28%20h%20%5Cright%29%20%3D%5Cmathbb%7BE%7D%5Cleft%5B%20%5Cfrac%7B1%7D%7Bm%7D%5Csum%7Bi%3D1%7D%5Em%7BY_i%7D%20%5Cright%5D%20%0A)

注意到 ，代入即可得证.

学习界

从式 (2.20) 可以看出，当样本量 增大时，误差界是在减小的，但比一致的情况要慢一些.

此外，还能看出一个在经验误差和假设集之间的权衡（trade-off）：

• 假设集越大，那么拟合能力越强，经验误差就越小
• 但假设集增大的同时，本身会使误差界增大

两道习题

习题 2.3

习题2.4

该证明的前提条件是：若学到的假设圆 与 都相交，那么必然有 %3C%20%5Cepsilon#card=math&code=R%28h_S%29%3C%20%5Cepsilon).

我们知道其泛化误差就是一个样本点落在图中阴影部分的概率.

对于上一题的同心圆来说，我们知道点落在错误区域的概率一定会小于 .

但对于非同心圆的情况，在已知条件仅有 的情况下，由于不知道其他区域样本的分布情况，因此无法证明点落在阴影部分的概率小于 .