PAC（probably approximately correct）学习架构介绍_综合

PAC学习框架（模型）

PAC 模型的作者是Leslie Valiant ，因此获得2010 年图灵奖。

最初PAC（probably approximately correct）学习框架针对的是二元分类问题（原装版），用严格的数学语言描述了可“学习”性。

对于一个输入空间 $X$ （instance space）， $X$ 上的一个概念（conception） $C$ 是 $X$ 上的一个子集。或者说 $C$ 是 $X$ 到集合 $\{0,1\}$ 的映射（或函数），这样用 $C^{-1}(1)$ 来表示 $X$ 中函数值为1的全体（注意：这里只是一个记号，不等同于数学中的逆函数，因为逆函数有更严格的条件，扯远了））。显然这些元素的全体是 $X$ 的子集。这样就把子集和X到{0,1}的映射一一对应了。
如果有另外一个函数 $C^{'}：X->\{0,1\}$ ，那么我们如何度量两个函数之间的“差异”，或者用数学的语言描述就是“距离”。（用“距离”过于严格，想想应该用“度量”，引入距离概念疑似给函数集合引入拓扑结构，扯远了）。在函数集合上引入度量的概念，更一般，应该用《测度论》中的“测度”这个词。由于集合和函数对等，其实就是集合上我们引入了测度的概念。
这样我们在 $X$ 的子集空间上引入了测度 $μ$ 。那么两个函数的差异就可以写成：

$μ (C, C') = μ (C (X) \neq C' (X))$ $μ(C,C^{'}) = μ(C(X) ≠ C^{'}(X))$

写成集合的形式： $μ(C,C^{'}) = μ(CΔC^{'})$

这样“学习”的问题就转换成：对于了二元分类目标函数： $C：X->\{0,1\}$ ，给定一个误差范围 $?_{0}$ ，找一个近似于目标函数的近似函数 $C^{'}$ 。使得： $μ(CΔC^{'})<?_{0}$

这里写图片描述

对于任意的 $f \in C$ （假设空间）,任意的测度（概率分布） $D$ ,任意的 $? \in [0,1/2)$ ,任意 $δ \in [0,1)$ ,存在算法 $L$ 使得有 $1-δ$ 的几率（概率）得到一个近似 $h$ ,满足 $D(f,h)<?$ 。
（2）有效PAC可学习性的定义。这里限制了算法复杂度。

算法 $L$ 的运行时间复杂度关于 $n$ (输入空间的维度)、 $1/?$ 、 $1/δ$ 以及 $C$ 的大小是多项式的。

新建位图图像 (2)

1、PAC对算法引入了成功率的属性，即允许算法在一定几率下可以失败，这和统计学习中经验误差的要求很类似。但是统计学习中对经验误差有最小化要求（目标化）。而PAC是给定这个阀值要求，然后去学习寻找近似函数（前提、条件化）。

2、方法论上的差异：PAC学习没有统计学习中的训练集和测试集的概念。统计学习在训练集上刻画和度量目标函数和学习函数的差异。

? 在PAC学习架构下有两个概念。
新建位图图像 (3)

1、强可学习。在PAC定义中，如果 $C$ 是有效PAC可学习的（efficient PAC learnability），这里 $δ \in [0,1/2)$ 。所以说学习成功率很高，至少大于0.5。
2、弱可学习。强可学习的条件下，对错误率有了限定。错误率必须低于0.5（就是至少要比随机猜测要强吧）。
3、后来证明在PAC学习架构下强可学习和弱可学习是充分必要条件（即等价）。

现在很多材料就说统计学习中的Boosting方法是受这一等价条件的启发。其实两个是不同的学习架构。而且Boosting这种朴素的思想是容易被考虑（比如我们中国就有俗语：三个臭皮匠抵上一个诸葛亮），只是形成具体算法需要巧妙构思。当然是不是真的受这个等价条件启发，还是要问Adaboosting算法设计作者（Yoav Freund 和 Robert Schapire）。
写这篇文章起因也是想看看Adaboosting算法的思想起源。