13.1 PAC学习

在高中课本中，我们将函数定义为：从自变量到因变量的一种映射；对于机器学习算法，学习器也正是为了寻找合适的映射规则，即如何从条件属性得到目标属性。从样本空间到标记空间存在着很多的映射，我们将每个映射称之为概念（concept），定义：

若概念c对任何样本x满足c(x)=y，则称c为目标概念，即最理想的映射，所有的目标概念构成的集合称为“概念类”；给定学习算法，它所有可能映射/概念的集合称为“假设空间”，其中单个的概念称为“假设”（hypothesis）；若一个算法的假设空间包含目标概念，则称该数据集对该算法是可分（separable）的，亦称一致（consistent）的；若一个算法的假设空间不包含目标概念，则称该数据集对该算法是不可分（non-separable）的，或称不一致（non-consistent）的。

举个简单的例子：对于非线性分布的数据集，若使用一个线性分类器，则该线性分类器对应的假设空间就是空间中所有可能的超平面，显然假设空间不包含该数据集的目标概念，所以称数据集对该学习器是不可分的。给定一个数据集D，我们希望模型学得的假设h尽可能地与目标概念一致，这便是概率近似正确 (Probably Approximately Correct，简称PAC)的来源，即以较大的概率学得模型满足误差的预设上限。

上述关于PAC的几个定义层层相扣：定义12.1表达的是对于某种学习算法，如果能以一个置信度学得假设满足泛化误差的预设上限，则称该算法能PAC辨识概念类，即该算法的输出假设已经十分地逼近目标概念。定义12.2则将样本数量考虑进来，当样本超过一定数量时，学习算法总是能PAC辨识概念类，则称概念类为PAC可学习的。定义12.3将学习器运行时间也考虑进来，若运行时间为多项式时间，则称PAC学习算法。

显然，PAC学习中的一个关键因素就是假设空间的复杂度，对于某个学习算法，若假设空间越大，则其中包含目标概念的可能性也越大，但同时找到某个具体概念的难度也越大，一般假设空间分为有限假设空间与无限假设空间。