林轩田机器学习基石课程个人笔记-第十五讲

上一讲学习了一个避免过拟合的方法：正则化，通过正则化来减小模型的复杂度，从而达到避免过拟合的效果。这一讲介绍了另一种很常用的方法，那就是验证（Validation）

在机器学习中，模型的学习过程是很复杂的，它最终的效果受很多东西的影响，即使是最简单的二分类也要考虑很多东西。比如我们针对这个问题，选择哪一种适合分类的算法；选择好算法后，迭代的回合数是多少；以及选择多大的步长；在非线性的数据集上，要选择哪一种线性转换；为了避免过拟合的出现，，使用正则化时要选择哪一种正则化方式，以及正则化的强度……

上面的这些因素都需要我们做出合适的选择，通过不同的组合来训练模型，最终得到我们可以得到的最好的g

例如之前提到的一个例子，数据分布如图所示，我们希望找到一条拟合的线，左图采用了一条直线，而右图是多条曲线的组合。直线方式看似简单，也有分错的点，但是泛化能力强；曲线的方式看似对每一个点都分对了，但是发生了过拟合。这就要求我们考虑多方面的因素，衡量好不同的标准，做出最好的选择。假设我们有不同的模型，每一个模型都有不同的演算法，学习的目标就是从中选择一个模型Hm*，通过它的演算法Am得到一个最好的gm，从而使的Eout(gm*)最小。那么根据什么标准来选择模型，可以得到理想的效果呢？

根据之前的理论知识我们知道，要使Eout最小，可以使得Ein最小，所以自然就想到一种方法：在众多的模型中选择可以得到最小的Ein的那个。但是这其中就存在一些问题，比如高阶多项式得到的Ein总是比低阶多项式得到的结果好，而且不使用正则化的结果也比使用正则化的好，这就不可避免模型复杂度的提高，从而避免不了过拟合的出现；另一个问题就是，分别使用不同的模型不同的演算法计算Ein，然后在结果中在进行比较，这样做实际上也是提高了模型的复杂度，导致泛化能力差。显然这些问题和选择的原则是不可调和的矛盾，所以使用最小的Ein作为选择模型的标准是不可行的

另一种想法就是我们来找一批测试资料，然后在不同的模型上计算Etest，然后选择那个Etest最小的模型，那么根据Hoeffding不等式，Eout和Etest就存在着如下的关系，如果Etest很小，相应的Eout应该也就会很小，问题不就解决了吗？不！首先有时我们很难得到用来测试的新数据，另一方面即使可以得到测试数据，但我们希望模型的泛化能力强，可以在新数据中效果同样的好，如果把测试数据用来训练选择模型，这不就自相矛盾了吗？这是一种为了达到目的的自我欺骗

下面再总结一下上面的两个想法，看看能不能有新的思路。以得到最小的Ein为标准，只需要在现有的数据集上学习，它是容易获取的，但是同一数据集既用来训练模型又用来选择模型，最终得到的模型的泛化能力就不一定好；如果以最小的Etest作为标准，虽然它只用来选择模型，得到的效果更加好，但数据是不易得到的。

这两种方法都有一定的优缺点，所以可以结合起来选择一种折中的办法：在已有的训练集D来选出一部分数据Dval做为验证集validation set，另外的部分作为训练模型使用， Dval是独立的用来选择最好的模型，通过最小化Eval来得到最佳的gm*

下面我们来具体的看一下上面的这种折中的想法是否可行。数据集D含有N个数据，从D中随即平均的选出K个做为验证集Dval，其余的作为训练集Dtrain，在Dval上来计算Eval(h)，在D上计算Ein(h)，两者之间就会存在某种联系。然后使用Dtrain训练得到gm-，而在D上训练得到的为gm

gm和gm-根据Hodffding不等式存在如下的关系

那么如何来操作呢？假设我们有M中模型H1……HM，将数据集划分后，在Dtrain上训练分别得到最好的gi-，然后在Dval上计算Eval，选择Eval最小的那个模型得到的gm做为最终最优的gm*。现在由于数量为N的总样本D中选出K个数据作为验证集，那么只有N-k个样本可供训练。从Dtrain中得到最好的gm-，而D对应的最好的矩为gm。根据leraning curve知道：训练样本越多，得到的模型越准确，其得到的h越接近目标函数，即D的Eout小于Dtrain的Eout

所以常见的做法是使用Dval得到最终的模型后，再在D上进行训练，得到最优的gm*。结合之前的谈论，以下三者就存在如下的大小关系

下面通过例子来解释这种模型选择的方法的好处，假设有两个模型：一个是5阶多项式，一个是10阶多项式。通过不使用验证集和使用验证集两种方法对模型选择结果进行比较，分析结果如下：横坐标是验证集的大小K，纵坐标是Eout的大小，其中黑色的实线表示表示不使用验证集时Eout的情况，那么自然和K的大小无关了，是一条平行于横轴的线；黑色的虚线是表示使用的测试数据接近真实情况，它Eout自然很小也于K无关，这是一种理想的情况；红色曲线表示使用验证集得到的gm-的情况，它是先下降后上升，当K大于某一值时，就会超过黑色实线；蓝色的线表示在使用验证集时，使用上面的做法得到的最终的gm的情况，它是先缓慢减小再缓慢增大，但始终处于红线和黑色实线之下，黑色虚线之上。通过分析我们可以看出，蓝色的线所代表的情况最小，虽然达不到理想的情况，但比上面两种要好很多，这和之前的讨论也是符合的。

其中当K大于一定的值时，红色曲线会超过黑色直线。这是因为随着K的增大，可供模型训练的数据量在减小，那得到的模型不具有很好的泛化能力，即对应的Eout就会会增大，甚至当K增大到一定值时，比Ein模型更差

那么K值得选择就是一个很重要得问题，我们要使Eout(g)和Eout(g-)足够的接近，就要使K比较的小，但是要使Eout(g-)和Eval(g-)足够的接近，就要K足够的大。为了权衡两种效果，只能取折中的值，比如通常可以取1/5的数据做为验证集

那么如果我们的验证数据只取一个会是一种怎样的情况呢？这样做可以保证Eout(g)和Eout(g-)足够的接近，但是Eout(g-)和Eval(g-)就相差很大，如何来避免这种结果呢？那就是多次的取验证集，每次取一个，分开后进行学习；然后再在剩下的取一个再学习，直到所有的数据都当过验证集，对所有的误差求平均值得到Eloocv(H,A)。这种方法称为留一交叉验证法

比如我们的数据只有三个点，先使用线性的方式，每次取一个点做验证数据，然后使用留一交叉验证法计算一个平均误差Eloocv(linear)；然后使用常数模型再同样的计算一个平均误差Eloocv(constant)。

比较结果的大小，从中选择最优的模型，

直观上我们看这种做法是可行的，那么理论上是否站的住呢，即Eloocv(H,A)小能否保证Eout就足够的小呢？假设有不同的数据集D，它的期望分布记为εD，则Eloocv(H,A)可以通过推导，等于Eout(N-1)的平均值。由于N-1近似为N，Eout(N-1)的平均值也近似等于Eout(N)的平均值，具体推导过程如下。最终证明了这种做法是可行的，Eloocv(H,A)和Eout(g-)是接近的

比如在识别手写数字的例子中，使用留一交叉验证法得到的拟合曲线更加的光滑，模型的泛化能力也更强，所以在实际中使用最小化Eloocv比使用最小化Ein更加的好

但是留一交叉验证法也存在问题，首先是计算量的问题：每次只取一个数据做为验证集，大部分的数据用于训练，在数据量很大的情况下，这种计算量是很大的；其次就是稳定性的问题：例如对于二分类问题，取值只有0和1两种，预测本身存在不稳定的因素，那么对所有的计算平均值可能会带来很大的数值跳动。故在实际的应用中，更多使用的是将N个数据分为V份，其他的过程和留一交叉验证法类似，这样就可以很好的解决它存在的问题，又可以得到较好的g，称之为V折交叉验证法

所以一般的验证使用V折交叉验证来选择最佳的模型。但验证的数据来源也是样本集中的，所以并不能保证交叉验证的效果好，它的模型一定好。只有样本数据越多，越广泛，那么Validation的结果越可信，其选择的模型泛化能力越强。通常使用中，可以取5折或是10折，就可以有比较好的效果了

最后总结一下，这一讲学习了验证的相关知识，讲了用什么来做为模型选择的标准、如何使用验证集的方法来选择模型，最后介绍了留一交叉验证法、V折交叉验证法两种方法