机器学习基石-Validation

Validation

回顾

lecture14我们主要介绍一regularization，我们的思路是在损失函数中加上一个regularizer然后最小化augmented error，本节课我们介绍另一个方法—validation。

Model Selection Problem

随着我们学习的模型和方法越来越多，我们面临的选择越来越多，不同的方法间的组合就更多了。

即使是我们现在做最简单的二元分类的问题，我们需要做的选择有：采用哪种演算法、迭代的次数、学习率的选定、变换方式的选定正则化方式的选定以及λ的选定。在这样的情况下，我们需要做validation。

然后我们来思考，我们应该通过什么指标来选择model呢，我们给出几个候选人：Eout、Ein和Etest。

首先Eout是未知的，所以我们不能使用它来选择model；那么Ein呢，回顾我们之前学习的内容我们知道，如果我们通过最小化Ein的方式来选择有可能会导致overfitting和付出过多model complexity的代价的问题；那么我们新取一批资料昨晚Etest来选择model会怎么样呢？通过hoeffding我们容易得到上面的公式，可见Etest是一个比较好的候选人，但是有一个比较致命的问题是我们取得测试集是存在相当大的难度的。

然后我们总结下Ein和Etest的特点，Ein是由我们手头的资料计算得来的，因此它是被污染了的，这个时候那他去做模型的选择是比较危险的；Etest可以用来做选择但是问题是我们取不到这些资料，于是我们取了二者的一个中间状态，我们从资料D中取出部分资料不用于建模，然后最后用这部分资料计算Eval来选择模型，这样Eval就兼有了可以取得并且验证模型的特征。

Validation

接着我们来看看validation的整个流程，我们将资料集D拆分成一个训练集Dtrain和一个验证集Dval，其中验证集的大小为K，首先我们要做的一件事是将Eval和Eout联系起来，达到这个目的等价于Dval是iid来自于我们的目标分布P的，于是我们只需要从D中随机抽取得到Dval即可满足条件。然后我们将Dtrain送到不同的hypothesis set H中得到相应的gm−，于是Eout满足上面的公式。

然后我们选择Eval最小的g作为我们的目标函数，结合前面学习过的learning flow的结论，我们知道资料量越多我们的Eout越小，因此我们可以将我们的validation的流程进一步优化。如上图所示，首先我们通过随机抽样的方式将资料集D拆分成Dtrain和Dval，然后通过Dtrain得到不同的gm−，接着通过Dval选择最好的模型，最后我们将D喂给这个最好的模型输出最后的gm，

接着我们看看validation在实践中的作用，我们使用验证集在5次多项式函数和10次多项式函数中做选择，我们可以得到上面的图形和与之相关的结论：1、如果我们使用Ein作为选择标准，我们一定会选择10次多项式函数，会得到最上面的那条线；2、使用Etest作为选择标准，会得到最下面的虚线（不可能实现）：3、直接通过选择的

gm−一般Eout要大于重新跑整体数据的gm。

我们可以发现gm和gm−都是先下降后升高，主要是由于K的增大导致N-K减小于是导致对g的选择影响增大。

我们关于validation的讨论可以说建立在上面的两个概略的等式上，但是两个等式对K的要求是相反的：当K比较大时Eval ≈ Eout，但是此时gm-和gm差距比较大；当K比较小时gm− ≈ gm，但是Eval会和Eout差距比较大。

于是选择适当的K是比较重要的，经过前辈的经验总结，K=N/5是一个还不错的选择。

Leave-One-Out Cross Validation

我们分析一个极端的validation的情形，我们取K=1，我们记某个验证集的error为en,一个这样的验证集肯定没法完成验证的任务，于是我们对资料集D中的每一笔资料都做这样一件事，最后定义一个leave-one-out cross validation estimate来描述这样的做法的整体的error，最后我们希望可以验证说Eloocv(H, A) ≈ Eout(g)是成立的。

我们上面给出Eloocv(H, A) ≈ Eout(g)的证明，刚兴趣的同学可以深究，下面再给出一个leave-one-out validation的实践例子。

V -Fold Cross Validation

上面我们介绍了leave-one-out的validation，必须要指出的是，这个方法一方面当我们的资料量很大时它的计算量是巨大的，并且这个方法的跳跃性比较大，因此实践上这并不是一个好的方法，于是我们在这个方法上做了一点点修改得到了更加合适的validation方法。

方法的改进主要是减少计算量上，我们将资料集不是拆分成N个而是拆分成更大的V个，我们同样可以实现验证的功能，实物上我们一般取V=10。

最后我们总结下：首先，交叉验证的效果会好于单次验证，然后实物上5次或者十次的交叉验证就堪用了。然后，我们需要明确validation的作用或者说地位，应该明确的是validation和我们的training类似，可以看成是一个model selection的复赛，但是因为他本质上还是一个选择，所以最终model的效果还是应以test为准。

小结

本节课我们主要介绍validation，我们从选择模型做切入，引入了Eval选择的选项，然后我们介绍了leave-one-out的validation，由于这个方法的劣势我们又介绍了V-fold validation，最后我们明确了validation的作用。