在上一篇笔记中，我们讨论了NFL定理，该定理指出不结合具体问题去比较学习算法之间的优劣是没有意义的。那么如果针对具体的问题我们又可能会提出如下的一些问题：

1. 为了获得一个好的模型，需要多少训练数据呢？

2. 在某个训练集上机器学习方法针对某个具体问题得到的模型在作预测时能达到多好的效果呢？

3. 针对具体的问题，如果去比较使用不同的学习算法产生的模型的优劣呢？

在这一篇文章中我们将试图讨论这些问题。

        首先引入一个概念：泛化能力

        学习方法泛化能力是指由该方法学习到的模型对未知数据的预测能力。我们使用模型在测试集上的测试误差来评价学习方法的泛化能力，这个测试误差又称为“泛化误差”。如果A算法学习到的模型的泛化误差比B算法学习到的模型的泛化误差小，那么A算法就比B算法更有效。

        使用泛化误差来评价模型的预测能力有个问题，泛化误差依赖于测试数据集，而相对于整个样本空间来说测试数据集是有限的，很有可能得到的评价结果是不可靠的，真的可以用泛化误差去衡量模型的预测能力吗？下面讨论的计算学习理论将从理论上来分析这个问题，这些理论的正式的分析和证明的数学味道有点重，但是其中的数学原理并不难，在笔记中我会以大白话的方式来描述。

        计算学习理论的原理是这样的：在输入少量的样本后，任何包含严重错误的假设都几乎一定会以较高的概率被发现，因为它将做不正确的预测。因此，与足够大的训练数据集一致的任何假设都不可能包含严重错误，也就是说它必定是概率近似正确的（probably approximately correct, PAC）。这个原理又叫“PAC学习理论”，接下来将通过PAC理论来回答笔记开头提出的几个问题。

一、“需要多少训练数据”

        “PAC学习理论”的内涵还是比较多的，其中之一就是解答了为了获得一个好的模型我们需要多少训练数据的问题，内容可以描述如下：

        存在一个数量N，使得在容量为N的训练集上训练出的所有假设在预测新的数据集时其错误率error(h)能以至少1-𝛿的概率小于等于ℇ，其中ℇ和𝛿均为小常量。也就是说与N个训练样本一致的假设，能以较高的概率（至少1-𝛿）近似正确（预测新数据集时错误率小于等于ℇ）。

        在做简单的证明之前，需要说明的是我们这里假设我们所面对的输入空间（即我们的训练数据和未来要预测的数据）是稳定的（即输入的分布规律不会变化，如果说输入空间不是稳定的，那么我们在训练数据集上学习到的模型就是过时的了，我们要做机器学习那么至少要确定输入空间最多是缓慢变化的，不然学习就没有意义了）。

        简单的证明：

        在假设空间H中存在很多的假设函数，我们虽然不知道它们的预测性能，但是我们知道我们可以将假设空间中的假设函数分为两类，一类是所有近似正确的假设的集合Hg，Hg中的每个假设hg的预测错误率error(hg)小于等于我们给定的小常量ℇ，另一类是严重错误的假设的集合Hb，Hb中的每个假设hb的预测错误率error(hb)都大于ℇ。

        假定我们有N个训练样本构成的训练数据集，我们的学习算法的任务是从假设空间中搜索出与N个训练数据相一致的假设函数，那么这个被搜索出来的与N个训练数据一致的假设函数有多大的概率是在Hb中呢？我们当然希望这个概率越小越好，因为在Hb中意味着它的预测错误率大于ℇ，是个严重错误的假设。下面我们来计算下这个概率：

        已知对于Hb中的假设hb有error(hb)﹥ℇ，因此它与一个给定的样本一致的概率最多为1- ℇ，因为样本之间是相互独立的，对于N个样本，hb能同时与它们都一致的概率边界为：

        考虑最好的情况，即Hb中所有的假设函数都能以上面的概率上界与N个样本一致，并令：

        那么，因为Hb中的假设函数之间相互独立，所以整个Hb中与N个样本一致的假设的个数c服从二项分布c~B(|Hb|, p)，

        那么E(c) = |Hb|p，同时按照求期望的公式我们有：

        再看Hb中至少包含一个假设hb与N个样本都一致的概率：

不难看出:

        进一步，我们利用不等式（引入这个不等式，一是为了找出后面说的概率的上界，二是可以方便求出N，因为N是一个指数，不好求解，引入e后就可以求对数把N从指数中拿出来。这个不等式很好证明，简单的证法可以是，用不等式两边的函数的商构成一个新的函数，对新的函数对ℇ求导可以发现导数小于等于0，所以新函数是减函数，再令ℇ＝0可以得到新函数的值为1，因为0<＝ℇ<＝1，所以新函数的值f(ℇ) <= f(0)＝1，即新函数的分子小于等于分母，即不等式得证）

        进一步找到P(Hb中至少包含一个一致假设)的一个上界：

        如果我们希望Hb中至少包含一个一致假设的概率很小（即，我们希望与N个样本一致的假设尽量不要出现在Hb中，因为如果在Hb中那么这个一致假设将是严重错误的），小于某个给定的小常量𝛿，那么我们就应该使这个概率的上界小于𝛿，即：

        对上式两边取对数，进行简单的整理后可以得到：

        上面的证明过程也就是寻找N的过程，我们可以看到，对于任意给定的ℇ和𝛿，我们找到了一个N，当训练数据集中至少有N个训练样本时，学习算法得到的假设函数可以以至少1-𝛿的概率有至多ℇ的错误率。

二、“模型的泛化能力能有多好”

        PAC学习定理除了告诉我们需要多大的训练数据集外，还告诉了我们一个算法的泛化误差上界是多少，即它能有多准确。

        泛化误差上界通常具有以下性质：它是训练数据集中样本容量的函数，当样本容量增加时，泛化上界趋于0；它是假设空间容量的函数，假设空间容量越大，模型就越难学，泛化误差上界就越大。

        为了简化问题，这里只看二分类问题且假设空间包含有限个函数时的泛化误差上界。

        对于一个二分类问题，一个训练数据集T = {(x1, y1), (x2, y2), ..., (xN, yN)}，X属于n维实数空间，Y∈{-1, 1}。假设空间是函数的有限集合F={f1, f2, f3, ..., fd}，d是函数的个数。设f是从F中选取的函数，我们使用0-1损失作为损失函数，即损失函数L(Y, f(X))的取值为：当预测值f(X)和真实值Y相等时为0，不等时为1。那么关于f的期望风险和经验风险分别是：

        那么我们的机器学习算法按照经验风险最小化原则搜索出来的假设函数就是：

        我们现在关心的就是这个被搜索出来的假设函数fN的泛化能力：

        这里直接给出关于这个泛化误差上界的结论，其证明的关键点是用到Hoeffding不等式，其余的推导很简单，具体可以查阅《统计学习方法》这本书。

二分类问题的泛化误差上界：

        对二分类问题，当假设空间是有限个函数的集合F={f1, f2, f3, ..., fd}时，对任意一个函数f∈F，至少以概率1- 𝛿，以下不等式成立：

其中，

从上面的结论可以看出：

1. 模型的泛化误差是有上界的，对于这里讨论的假设空间有限的二分类问题，只要给出一个训练数据集和假设空间大小，再给定一个任意的0<𝛿<1我们就能找到模型的泛化误差上界；

2. 对于这里讨论的问题，泛化误差上界由两部分构成，第一部分是训练误差，训练误差越小，泛化误差也越小；第二部分是一个关于训练样本容量N的单调减函数，N越大这部分的值越小，N趋于无穷时值趋于0，也就是说如果我们的训练数据已经包含了所有可能的输入输出对情况，那么我们在训练数据集上的训练误差就是泛化误差了；同时第二部分还是关于假设空间容量d的函数，d越大即假设空间包含的函数越多，第二部分的值就越大，泛化误差可能就越大。

三、“如何比较不同学习方法的优劣”

        这个问题就简单了，可以通过比较两种学习方法的泛化误差上界的大小来比较它们的优劣。

至此我们就解答了笔记开头提出的几个问题了，这篇笔记主要介绍了机器学习中的计算学习理论，的确比较枯燥，但是它是机器学习的基石，它确定了机器学习的可行性。

参考资料：

Stuart J. Russelll《人工智能 一种现代的方法》

李航《统计学习方法》