OMSCS-ML课程笔记07-Computational Learning Theory
这个系列是Gatech OMSCS 机器学习课程(CS 7641: Machine Learning)的同步课程笔记。课程内容涉及监督学习、无监督学习和强化学习三个部分,本节主要介绍监督学习中计算学习理论的相关内容。
Learning to Learn
到目前为止我们已经介绍了很多类型的机器学习算法,而本节介绍的计算学习理论(computational learning theory)不涉及任何具体地算法,而是尝试去解决为什么机器学习是可行的以及我们需要多少样本才能保证学习算法是可靠的这样的问题。
如果将机器学习比作现实生活中的学习过程,那么机器学习算法实际上是使用自然学习(natural learning)的模式。在这样的模式下我们只会给学习器提供一系列样本,然后由模型自己来进行学习。我们关心的是需要多少样本才能保证学习器能够学习到正确的假设,称为样本复杂度(sample complexity)。
PAC Learning
PAC Learnable
计算学习理论的主要成果是概率近似正确理论(probably approximately correct, PAC),基于PAC学习理论我们可以去计算学习算法的样本复杂度。在介绍具体的理论前首先要引入一些相关的概念:假设样本
需要说明的是学习器
显然在给定样本
因此直接学习到正确的假设
设正确概念的集合
,大小为 的样本集合为 ,学习器为 ,假设空间为 。称 是PAC可学习(PAC-learnable)的当且仅当 中的任意正确概念 能够被学习器 以概率 从 中进行学习,学习到的假设 在分布 上的误差满足 ,且学习所需的时间为 、 、 以及 的多项式函数。
PAC学习对于学习器
Sample Complexity
假设学习器处理每个样本所需的时间为常数,那么PAC可学习实际上暗示了学习器的样本复杂度同样是多项式函数,这样我们就把学习算法的时间复杂度转化为样本复杂度。在推导PAC可学习的样本复杂度前我们还需要补充一些相关的知识。对于版本空间
如果假设空间中存在
其中
上式也被称为Haussler定理(Haussler theorem),它说明我们至少需要
VC Dimension
Haussler定理的一个主要缺陷在于它过于高估了样本复杂度。当假设空间
对于二分问题,假设空间
假设空间
的VC维是能被 打散的最大样本集的大小,即
以平面上的二分类问题为例,对于线性分类器当我们有3个样本时无论样本如何布置都可以实现对分,但对于4个样本的情况则会出现无法对分的情况。因此二分问题中线性分类器的VC维为3,同时可以证明

使用VC维来代替假设空间的模可以得到更准确的样本复杂度:
利用VC维还可以证明假设空间
Reference
- Chapter 7: COMPUTATIONAL LEARNING THEORY, Machine Learning, Tom Mitchell, McGraw Hill, 1997.