3.6　计算学习理论

计算学习理论（Computational Learning Theory）是机器学习的理论基础，其研究的是通过“计算”来进行“学习”的理论，其目的是分析学习任务的困难本质，为学习算法提供理论保证，并根据分析结果指导算法设计[15,16]。计算学习理论最基本的理论模型称为“概率近似正确”（Probably Approximately Correct，PAC）模型。虽然这个模型很简单，但非常重要。机器学习已经无处不在，如利用计算机以数据驱动的方式去解决人们现实生活中碰到的分类、预测、预报等各种各样的问题。机器学习虽然能力很强，但它并不是万能的，如下两种情况不适合用机器学习来处理：一是处理的数据特征信息不够充分；二是数据样本的信息不充分。

机器学习中的“无免费午餐”（No Free Lunch，NFL）定理：所有算法，无论高级、初级，它们的期望表现相同。这个定理告诉我们，如果算法A在某个问题上比算法B更好一些，那么，一定在另外某个问题上，两个算法的优劣是反过来的，即算法B更好。这个理论对任何一个算法都是成立的，换言之，任何一个模型可能只适用于一部分任务，而对另一部分任务不适用。所以，在面对一个具体的任务时，要使用什么算法或技术，一定要具体问题具体分析。机器学习中的问题与一般理解的“问题”意义不同，机器学习中的一个“问题”，一定是由输入描述的属性确定的。例如，文本推荐和各电商用自己数据做的推荐，从机器学习的角度来看可能是不一样的“问题”。人们用机器学习解决问题时，要针对某个问题专门设计有效的方法，这样才能得到一个更好的结果。所以，按需设计、量身定制在应用机器学习时特别重要。

3.6.1　基本的PAC模型

PAC模型是由Valiant于1984年首先提出来的，是由统计模式识别、决策理论中的一些简单的概念结合计算复杂理论的方法而得到的学习模型[17-20]。它是研究学习及泛化问题的一个概率框架，不仅可用于神经网络的分类问题，而且可广泛应用于人工智能中的学习问题。PAC模型研究的主要问题包括：什么问题是可以高效学习的？什么问题本质上就难以学习？需要多少实例才能完成学习？是否存在一个通用的学习模型？

PAC模型关注更多的是算法能产生的数据与结果之间的映射同实际映射的贴近程度和稳定程度，而不是具体算法的优劣。这是一个在更高层面审视机器学习算法有效性的理论。PAC模型的数学表示为

机器学习根据已知数据，建立模型。我们希望这个模型特别准确，也就是和真实结果非常接近，那么怎么算接近呢？我们希望和的差别很小，小于一个很小的值；我们不能保证每次预测都完美，只能希望以大概率得到好结果。所谓大概率，就是比更大的概率，这里，是个很小的值。我们希望以比较大的把握学得比较好的模型，即以较大概率学得误差满足预设上限的模型。

所以，可以看出，机器学习针对给定数据，希望以很高的概率给出一个好模型。从这个意义上来说，我们做的很多事情是可以有理论保证的。例如，人们可以估算需要多大规模的数据样本才能将某个问题做到某种程度。如果对某个问题的要求非常高，而要达到这个效果所需要的样本规模大到无法满足，那么，这个问题就是不可学习的。所以，在概率近似正确的理论中，一个模型能把问题解决得多好，是可以从理论上去探讨的，并且是可以有理论保证的。在学习概率近似正确理论之前，先理解以下这些基本概念。

3.6.2　基本概念

PAC模型最初是根据二分类问题提出来的。输入空间称为实例空间或样本空间，指学习器能见到的所有实例（样本）。

概念（Concept）：令c表示概念，它代表从样本空间X 到标记空间Y的映射。若对任何样例（x,y）有c(x)=y成立，则称 c为目标概念。所有目标概念的集合称为概念类（Concept Class），用符号C表示。

假设空间（Hypothesis Space）：给定学习算法A，它所考虑的所有可能概念的集合称为假设空间，用符号 H表示。对于假设空间中的任一概念，用符号h表示，由于不能确定它是否真是目标概念，因此称其为假设（Hypothesis）。

可分的（Separable）：由于学习算法事先并不知道概念类的真实存在，因此，H和C通常是不同的。若目标概念c属于H，则说明H中存在能将所有实例与真实标记按一致的方式完全分开的假设，称该问题对学习算法A是可分的，也称为一致的（Consistent）；反之，若c不属于H，则称该问题对学习算法A是不可分的（Non-Separable），也称为不一致的（Non-Consistent）。

学习过程可以视为学习算法在假设空间中进行搜索的过程。

给定训练集D，人们训练机器学习模型的目的是希望基于学习算法A学得的模型所对应的假设h尽可能地接近目标概念c。这种希望以较大概率学得误差满足预设上限的模型，这就是“概率”“近似正确”的含义。

样本复杂度指学习器收敛到成功假设时至少所需的训练样本数。

计算复杂度指学习器收敛到成功假设时所需的计算量。

3.6.3　问题框架

在清楚了上述概念后，给定置信度t、误差参数e，则有如下定义。

PAC辨识（PAC Identify）：对t > 0、e<1，所有c属于C和分布D，若存在学习算法A，其输出假设h 使得泛化误差E(h)小于e的概率大于置信空间1−t，则可以说学习算法A能从假设空间H中PAC辨识概念类C。

PAC可学习（PAC Learnable）：令m是从分布D中独立同分布采样的样例数目，t > 0、e<1，所有c属于C和分布D，若存在学习算法A和多项式函数poly(·,·,·,·)，使得对于任意m≥poly(1/e,1/t,size(X),size(c))，算法A能从假设空间H中PAC辨识出概念类C，则称概念类C对假设空间H而言是PAC可学习的。

PAC学习算法（PAC Learning Algorithm）：若学习算法A使概念类C为PAC可学习，且算法A的运行时间是多项式函数poly(1/e,1/t,size(X),size(c))，则称概念类C是高效 PAC可学习（Efficiently PAC Learnable）的，称算法A为概念类C的PAC学习算法。

假定学习算法对每个样本的处理时间为常数，则算法的时间复杂度等同于样本复杂度。于是，人们对算法的时间复杂度的关心可转换为对样本复杂度的关心。

样本复杂度（Sample Complexity）：满足PAC学习算法A所需的m≥ poly(1/e,1/t,size(X),size(c))中最小的m，称为算法A的样本复杂度。

将上述4个概念转换为以下表述，理解起来更简单。

如果学习算法A足够优秀，使得误差大概率（在置信空间 1−t范围内）足够小（误差小于误差参数e），那么，目标概念类C对于学习算法A来说是PAC可辨识的。

如果当采样数目m大于一定值时（多项式函数poly），概念类C一定能被PAC辨识，那么，概念类C对于学习算法A来说是PAC可学习的。

如果此时学习算法A的时间复杂度在一定范围内（多项式函数poly），那么，学习算法A就是概念类C的PAC学习算法。

显然，PAC学习给出了一个抽象地刻画机器学习能力的框架，基于这个框架能对很多重要的问题进行理论探讨。例如，研究某任务在什么样的条件下可学得较好的模型，研究某算法在什么条件下可进行有效的学习，以及需要多少训练样例才能获得较好的模型。

PAC学习中的一个关键因素是假设空间H的复杂度。一般而言，H越大，其包含任意目标概念的概率也越大，从中找到某个具体的目标概念的难度也越大。

3.6.4　小结

机器学习理论研究的是关于通过“计算”来进行“学习”的理论，即关于机器学习的理论基础。其目的是分析学习任务的困难本质，为学习算法提供理论保证，并根据分析结果指导算法设计。机器学习理论研究的一个关键是研究算法对应的假设空间是不是可以学习的。对于具体的假设空间，其可学习性指该假设空间泛化误差小于误差参数的概率是否在置信空间内。通过分析不同情况下假设空间泛化误差界的范围，可以了解该假设空间是否可以学习。