PAC概率近似正确学习模型

• 《Understanding Machine Learning-From Theory to Algorithms》
• 第二章，最后一段关于predictor 失败的分析

一个upper bound的推导和理解

有了精度参数, 我们就可以定义失败的假设 . 我们有m个训练样本，是通过采样产生的，组成了样本集合。不同人/时间，采样的结果是不一样的，就有不同的样本集合，比如有. 这些样本集合有多大概率产生失败的predictor呢？记训练实例集为. 我们关心的是下面概率的上界。

#m-组实例采样中 导致失败预测器的 概率。

怎么算这个上界 upper bound?

1. 引入bad hypothesis set的集合
   .
2. 从bad hypothesis出发，定义数据误导集
   
   也就是误导集是依赖bad hypothesis的，不同的会有不同的误导集，整个误导集是所有bad hypothesis的并集。
3. 回到关注的问题中的集合, 这个集合等价于：
   ,继续等价于：
   ，子集关系就出来了：
   , 这个集合只是误导集的子集而已。
4. 概率不等关系也就出来了：
   
5. 从第2点中可以看出还是个并集。。利用联合界的方式缩放：
   .
6. 固定某个"bad"假设，展开：
   
7. 对于每个sample, ， 注意第6步中使用的bad hypothesis, 所以不等式成立。
8. 所以整个的上界upper bound
   
   说明：

• 假设空间很小, 训练样本量只需要很少；但是由于实际问题的复杂性，必须要很大(比如深度学习)。为了控制这个upper bound, 就必然要求大的，大数据量。
• 精度参数是一个要求指标，精度需求越高，越小，实现相同的upper bound， 就需要更大的，数据量和精度有关系。通过数据增强提高分类精度，这个公式也可以看出端倪。
• 算法理论分析的牛逼之处在于：给定少量的假设条件，就能够分析出关键配置对性能影响关系。

推论2.3

假设

说明：在m足够大的时候，在独立同分布的样本集S上，最少以的大概率保证有效，即 .