30分钟了解PAC学习理论——计算学习理论第一讲.pdfVIP

30分钟了解PAC学习理论——计算学习理论第⼀讲

马瘦⽑长蹄⼦肥，

搞机器学习的谁也不服谁，

⾃从⼆狗学了PAC，

见谁都拿拳往别⼈⼩胸胸上捶。

啪！今天给⼤家说⼀段PAC理论

 先放PAC学习相关理论的⼀个总结：同等条件下，模型越复杂泛化误差越⼤。同⼀模型在样本满⾜⼀定条件的情况下，其数量越⼤，模型

泛化误差越⼩，因此还可以说模型越复杂越吃样本。本⽂旨在让⼤家快速了解这句话的含义。您只需要提前了解假设空间、泛化误差、经验

误差的概念（不明⽩的百度20分钟）及任何⼀本概率论教材前两章内容就能看懂这篇⽂章。

为什么要学习PAC学习理论？

 此理论可以帮助我们更深⼊的了解机器学习的学习机制。

 已经⼊门或者从事过⼀段时间机器学习相关⼯作的你有没有想过为什么在训练样本上学习了⼀个假设(函数？模型？下⽂统⼀叫假设)就能

保证这个假设在训练样本之外的数据上有效？看完这篇⽂章你就会明⽩有效性是有严谨的理论保证的。

 ⼏千条样本数据就敢⽤CNN/RNN？你⼼也够⼤的。如果你⾮要这么做，⽼司机会语重⼼长的教育你：“数据太少，会导致过拟合”。看

完这篇⽂章就会明⽩为什么了。

 如果看完这篇⽂章后你能回答这两个问题，那么恭喜你，你已经对PAC学习理论有了⼤致的了解了。

什么是PAC学习理论？

 先说⼀下机器学习。机器学习有两个元素：模型与数据。其中模型⼜包含两部分：优化算法与假设空间。所谓机器学习就是⽤优化算法从

假设空间中选择⼀个假设，使此假设能符合给定的数据描述。因此优化算法通俗的讲就是假设选择算法。

 ⽽PAC学习理论不关⼼假设选择算法，他关⼼的是能否从假设空间中学习⼀个好的假设。看到能否⼆字了没？此理论不关⼼怎样在假设空

间中寻找好的假设，只关⼼能不能找得到。现在我们在来看⼀下什么叫“好假设”？只要满⾜两个条件(PAC辨识条件)即可

近似正确：泛化误差⾜够⼩

越⼩越好，最好泛化误差能能于0，但⼀般是不可能的。那我们就把限定在⼀个很⼩的数之内，即只要假设满⾜，我们就认为是正

确的。

可能正确

不指望选择的假设百分之百是近似正确的（按上段所述，即），只要很可能是近似正确的就可以，即我们给定⼀个值，假设满

⾜。

 综上两点，就得到了PAC（可能近似正确，probablyapproximatecorrect）可学习的定义。简单的讲就是模型在短时间内利⽤少

量的(多项式级别)样本能够找到⼀个假设，使其满⾜。

什么条件能满⾜PAC可学习？

 先介绍下Hoeffding不等式

Hoeffding不等式：给定m个取值之间的独⽴随机变量，对任意有如下等式成⽴：

 由泛化误差与经验误差的定义易知，因此可推出公式（1）：

 根据不等式（1）可推出公式（2）:

证明过程如下（看不懂也没关系，不会影响你对理论的理解，直觉⽐证明过程更重要）：

 公式（2）说明了什么？说明了对于任意，只要样本数量⾜够⼤，发⽣的可能性就⾮常⼤，此时我们可以⽤经验误差近似泛化误差。

回到⼀开始我们提出的那两个问题：

 1.为什么在训练样本上学习得到的假设会在真实样本上有效？公式（2）很好的说明了这⼀问题。只要样本数量⾜够⼤或者假设空间

的⼤⼩⾜够⼩，公式（2）就能保证学到的假设的泛化误差与经验误差⾜够接近。在训练样本上的表现与在真实样本上⼀致。

 2.为什么少量样本能⽤CNN/RNN等复杂模型会导致过拟合？还是看公式（2）。样本数量m太⼩的话发⽣的可能性变⼩。即学到

的在训练样本上的表现与在真实样本上不⼀致，这是过拟合直接的表现形式。

对以上两点的解释没有考虑为⽆穷⼤情况，但不影响⼤家理解。实际上如果为⽆穷⼤，下⼀节的VC维照样可以给出类似解释。

 现在开始解决我们本⼩节提出的问题。什么条件才能满⾜PAC可学习?还是看公式（2），另，即:

 本⼩节结论：只要样本数量⼤于公式（3）中的，就能保证模型在当前条件下是PAC可学习的。

VC维理论：更紧的条件

先说⼀下什么是紧。简单的讲，紧的意思就是恰好满⾜条件。

 为了保证PAC可学习，根据公式（3），需要样本数量⼤于等于。此值越⼩，PAC条件越有可能达到。那么有没有⽐script

type=math/texid=MathJax-Element-55M/script更紧也就是更⼩的值呢？这就引出了VC维理论。

 欲知VC维理论为何物，且听下篇⽂章分解。