关于 PAC 学习理论的一点思考

来自 2019年7月对机器学习理论整理时的思考：

1. 第一章中给出了轴平行矩形这一概念类，并且推导出了样本复杂度，从而说明了是 PAC 可学习的。但后面 VC维章节可以分析一下这一概念类的VC 维，在泛化界章节，可以给出基于VC维的泛化界，并且与这里的泛化界进行对比。

2. 在泛化界章节，最好再强调一下泛化误差界 和 PAC 可学习的关系。有了泛化界，并没有完全解决 PAC 可学习这一问题。泛化界是假设以及假设空间的性质，只是给出了 经验误差逼近泛化误差的衡量。但PAC 可学习需要刻画 输出假设的泛化误差 和 最优假设的泛化误差的差别。因此通常 PAC 可学习是 ERM + 泛化误差界。

3. 可以参考 Understanding ML 一书把 approximate error, estimation error, excess risk 写进去

4. 在稳定性一章也要强调一下， PAC 可学习是 算法的稳定性 + 算法的ERM+ 算法的损失函数有上界 联合导致的。另外稳定性隐含要求了假设空间不会太大。

5. Understanding Machine Learning 上要求了 稳定性 等价于 不会过拟合，这相当于另一种解释，可以想办法结合进去。

6. 可以写一点 统计学习理论，各种 risk 的理论，以及 结构风险极小化，SRM

7. 可以写 PAC model for noisy label ,PAC model for semi-supervised learning

8. 可以写一点主动学习的理论

9. 在 PAC理论中，把 stochestical learning scenario 以及 bayes risk 写进去

另外还有很多思考记录在了纸质材料上，例如

1. 有限可分情况下其实也是可以用 Hoeffding 不等式bound，但此bound 则太松了，从 O(1/m) 变为 O(1/\sqrt{m})
2. P(|E-\hat{E}|) 与 P(E-\hat{E}) 差一个 2 的关系，(Union Bound)
3. approximate error, estimation error, excess risk 而泛化界是用来 bound 经验误差与期望误差的

关于 PAC 学习理论的一点思考

原文：https://www.cnblogs.com/Gelthin2017/p/12254969.html