13.2 有限假设空间

13.2.1 可分情形

可分或一致的情形指的是：目标概念包含在算法的假设空间中。对于目标概念，在训练集D中的经验误差一定为0，因此首先我们可以想到的是：不断地剔除那些出现预测错误的假设，直到找到经验误差为0的假设即为目标概念。但由于样本集有限，可能会出现多个假设在D上的经验误差都为0，因此问题转化为：需要多大规模的数据集D才能让学习算法以置信度的概率从这些经验误差都为0的假设中找到目标概念的有效近似。

通过上式可以得知：对于可分情形的有限假设空间，目标概念都是PAC可学习的，即当样本数量满足上述条件之后，在与训练集一致的假设中总是可以在1-σ概率下找到目标概念的有效近似。

13.2.2 不可分情形

不可分或不一致的情形指的是：目标概念不存在于假设空间中，这时我们就不能像可分情形时那样从假设空间中寻找目标概念的近似。但当假设空间给定时，必然存一个假设的泛化误差最小，若能找出此假设的有效近似也不失为一个好的目标，这便是不可知学习(agnostic learning)的来源。

这时候便要用到Hoeffding不等式：

对于假设空间中的所有假设，出现泛化误差与经验误差之差大于e的概率和为：

因此，可令不等式的右边小于（等于）σ，便可以求出满足泛化误差与经验误差相差小于e所需的最少样本数，同时也可以求出泛化误差界。