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学习理论我们可以去计算学习算法的样本复杂度。在介绍具体的理论前首先要引入一些相关的概念:假设样本X都是从某个分别D中采样得到的;D可以是任意的分布同时学习器L无法得知D的信息;学习器L的目标是从假设空间H中学习到正确的概念c,同时c存在于假设空间H中。设学习器学习到的假设为h,我们定义h在分布D上的误差为:

errorD(h)=PrxD[c(x)h(x)]

需要说明的是学习器L是从样本X中进行学习的,因此无法直接计算在分布D上误差errorD(h)而只能计算h在训练数据上的误差。我们把在训练样本X上与正确的概念c表现一致的假设h称为是一致的(consistent),一致假设构成的集合称为版本空间(version space)

VSH,X={hH|h(x)=c(x),x,c(x)X}

显然在给定样本X的条件下可能存在多个一致的假设,它们在训练样本X上的误差为0。同时由于X都是从D中采样得到的,X自身可能会对学习器产生一些误导使得学习器学到一些不存在于分布D中的信息。

因此直接学习到正确的假设c是比较困难的,我们放宽要求只要学习到误差足够小的假设即可。此外我们不要求学习器对于任意采样出来的样本X都能够进行学习,只要学习失败的概率很小就可以。换句话说,学习器只要能够以一定的概率学习到近似正确的假设即可,这也是PAC学习理论得名的原因。PAC学习严格的定义如下:

设正确概念的集合C,大小为n的样本集合为X,学习器为L,假设空间为H。称CPAC可学习(PAC-learnable)的当且仅当C中的任意正确概念cC能够被学习器L以概率(1δ)X中进行学习,学习到的假设h在分布D上的误差满足errorD(h)ε,且学习所需的时间为1ε1δn以及|c|的多项式函数。

PAC学习对于学习器L提出了两个要求:首先学习器要有足够高的成功概率(1δ)以及足够低的误差errorD(h)ε;同时学习算法要保证足够的效率,必须是1ε1δ的多项式函数。

Sample Complexity

假设学习器处理每个样本所需的时间为常数,那么PAC可学习实际上暗示了学习器的样本复杂度同样是多项式函数,这样我们就把学习算法的时间复杂度转化为样本复杂度。在推导PAC可学习的样本复杂度前我们还需要补充一些相关的知识。对于版本空间VSH,X,我们称它是ε-exhausted如果其中的任意假设h在分布D上的误差小于ε

errorD(h)ε, hVSH,X

如果假设空间中存在k个假设,它们的泛化误差都大于ε。那么它们中如果有1个位于版本空间VSH,X中的话,版本空间就不再是ε-exhausted。我们设这个泛化误差大于ε且位于版本空间的假设为h,在这样的情况下每个样本从分布D中抽样出的概率最大为(1ε),否则h就不再是一致假设了。由于训练数据是独立同分布的,抽样出样本集X的概率最大为(1ε)n,也就是说h在样本集X上是一致假设的概率最大为(1ε)n。由于我们一共有k个这样假设,它们中至少有一个位于版本空间的概率小于等于k(1ε)n。在大多数情况下我们无法得知k的具体值,因此进一步对概率进行缩放得到版本空间不满足ε-exhausted条件的概率上界:

k(1ε)n|H|(1ε)n|H|eεn

其中|H|表示假设空间的大小。上式说明学习器L学习失败的概率一定小于等于|H|eεn,我们再令这个上界小于等于某个小量δ就能得到PAC学习的样本复杂度:

|H|eεnδ n1ε(ln|H|+ln1δ)

上式也被称为Haussler定理(Haussler theorem),它说明我们至少需要n=1ε(ln|H|+ln1δ)数量的样本才能保证学习到的一致假设h满足泛化误差errorD(h)ε

VC Dimension

Haussler定理的一个主要缺陷在于它过于高估了样本复杂度。当假设空间H存在无穷多假设时,按照Haussler定理我们需要无穷多的样本才能保证PAC可学习,这与我们的认知是相违背的。实际上对于包含无穷多假设的假设空间,其中很多的假设是相互等价的,显然将它们视作不同的假设会极大地增加样本复杂度。因此我们需要缩小|H|来获得样本复杂度的一个更紧的界。

对于二分问题,假设空间H中的假设对样本赋予标记的每种可能结果称为对样本的一种对分(dichotomy)。显然对于包含n个样本的数据集所有可能的标记总共有2n种可能性。如果假设空间H能够实现样本上的所有对分,则称样本能被假设空间H打散(shattering)。在此基础上我们给出VC维(Vapnik and Chervonenkis dimension)的定义:

假设空间H的VC维是能被H打散的最大样本集的大小,即VC(H)=max{m:ΠH(m)=2m}

VC(H)=d表示存在大小为d的样本集能被假设空间H打散,但这并不意味着任意大小为d的样本集都能被H打散。同时VC维与样本分布D无关,仅与假设空间H有关。因此在数据未知的情况下仍然能够计算出VC维。

以平面上的二分类问题为例,对于线性分类器当我们有3个样本时无论样本如何布置都可以实现对分,但对于4个样本的情况则会出现无法对分的情况。因此二分问题中线性分类器的VC维为3,同时可以证明n维情况下的VC维为n+1

使用VC维来代替假设空间的模可以得到更准确的样本复杂度:

n1ε(4log2(2δ)+8VC(H)log2(13ε))

利用VC维还可以证明假设空间H是可学习的当且仅当它的VC维有限。

Reference