上一章介绍了讲了EMR的误差主要分为两种，一种是approximation error，另一种是estimation error。其中approximation error衡量了所选择假设h是不是适合这个问题，里面有没有包含足够的先验知识。对于一个假设，如果要满足PAC可学习的情况下，那么其estimation error需要被限制在一定的范围之内。

本章的目的是，能够满足PAC可学习的假设。之前的章节中提到过，有限假设集一定是PAC可学习的。

在无限假设集上怎么保证PAC可学习呢？

可以举这么一个例子，使假设集，可以看作是一个值域区间从0-1上的函数，表示当0<x<a时，ha(x) = 1，当x>a时，ha(x) = 0。

很明显这个假设集是一个无限集，因为a可以取0-1中的任意数。

假设我们的最优解是当a = a*时，这时候a*左右两边分别有一个对称的bound，正好使得分别在这两个bound之内的数的概率被限制在epsilon之内。

看到epsilon之后，立马想到了PAC可学习性，那么在这里是怎么跟PAC建立联系的呢？

在如上的例子中，如果我们给出了一个训练集，给出两个bound，使得最终的最优假设的阈值在这两个bound之内，那么如果这两个bound正好在a0和a1之内的话，就能够使得这个最优假设的误差小于epsilon。

利用这点经过一系列的推导可以推出,也就是说在这种采样复杂度的情况下，能够使得一个无限集问题成为一个PAC可学习问题。

VC维

关于具体介绍VC维的内容建议参考https://baike.baidu.com/item/vc维/2947135?fr=aladdin

= =

VC维主要主要衡量了假设集的学习能力，越大假设集空间越大，学习的复杂度也就越高。这个说起来很容易理解，但是在具体看这块内容数学推导时，有一种回到研一学习np问题的日子的感觉。确实是很硬核的知识点，理论推导以后有机会再啃书吧。