机器学习中的Overfitting

浅谈机器学习中的Overfitting在机器学习中，常会出现这样一种的现象：一个假设在训练数据上表现很好(in-sampleerror很小，即inE很小)，但是在训练数据外的数据集上却变现很差(out-of-sampleerror很大，即outE很大)，这时，我们称发生了过度拟合(overfitting)。1.Overfitting的原因Overfitting，字面上讲，就是“fittingthedatamorethaniswarranted.”。overfitting自然是我们不愿意看到的，那么是什么原因导致了overfitting呢？如果我们的训练数据中含有noise，那么我们在拟合时，为了追求最小inE(in-sampleerror)，一不小心，就可能用了过于复杂的模型不仅fit了data，还fit了noise，也恰恰是因为overfit了noise，造成学习出来的函数其实出现了很大的偏差，因此在新的数据上变现不好(outE很大)也就不足为奇了。可见，数据中含有noise是造成overfitting的一个原因。其实，造成overfitting的原因远不只是数据中noise一种，即使数据中没有noise，也有可能造成overfitting。例如，我们来看下面一个例子，目标函数是一个50阶多项式，数据如下面左图所示(这里没有任何noise),我们分别用2阶和10阶的多项式来拟合，拟合结果如下面右图所示。10阶的多项式的拟合结果竟然比2阶多项式的差，结果多少让人意外。我们想象两个人来解决同一个拟合问题，一个人比较聪明，会10阶的多项式，而令一个人只会2阶的多项式，但是，结果很奇怪，一个笨笨的人最后居然赢了，聪明人好像“聪明反被聪明误”。其实如果你知道VCtheory,就不难理解，用10阶的函数来拟合得到较差outE的概率要比用2阶的函数来拟合得到一个同样差outE的概率要大的多。如果你不知道VCtheory，我们可以来看下面两个曲线，我们称之为学习曲线，表示了用2阶和10阶多项式拟合时错误率随测试数据量的大小的变化情况(左面的图是用2阶多项式的结果，右面的图是10阶多项式的结果)。我们上面的例子中，数据量不够多，这时候从曲线可以看出，10阶多项式拟合后虽然inE很小，但是outE很大。但是，我们也应该注意到，当数据足够多时(datasizeN足够大)，用10阶函数拟合会比2阶函数好（outE小）。因此，我们可以得到结论，overfitting跟目标函数的复杂度有关，复杂的目标函数更容易发生overfitting，另外，overfitting还跟datasize有关，当数据量较小时，我们应该选取较简单的模型来拟合，选择复杂的模型就容易产生overfitting。于是，我们得到了产生overfitting的三个最主要的原因：Datasize，noise和targetcomplexity。上面例子中，如果我们将10阶多项式的值和2阶多项式的值的差作为overfitting的一种度量，那么ovefiting与Datasize，noise和targetcomplexity的关系可以表示为如下两个图(图中由蓝色边到红色表示overfitting的概率逐渐变大)：我们再次回头看刚才的例子，里面真的没有“noise”吗？如果目标函数太复杂，那么对于每一个模型来说，都没有办法来描述好目标函数，但是每一个模型的假设函数集中一定有一个对目标函数f(x)的最好的近似h*，他们之间的差异可以看做是一种noise，为了与data中的那种randomnoise(stochasticnoise)区分，我们称这种noise为deterministicnoise。右图中,蓝线表示targetfunction，红线表示bestfittof,阴影部分就表示deterministicnoise。Deterministicnoise和stochasticnoise对overfitting的影响非常相似（由上面的两个图形对比可以看出）。2.Overfitting的对策如何尽量避免overfitting呢？方法有很多，有一些简单的技巧，比如，从简单的模型开始尝试；数据清洗等；还有非常重要的两个手段，就是regularization和validation。2.1RegularizationRegularization是通过添加约束的方式来寻找一个简单的假设来拟合目标函数，从而避免过度拟合。以上面10阶多项式拟合的问题为例，可以表示为如下无约束的优化问题：)(min110wEinRw那么利用2次多项式拟合，可以表示为一个有约束的优化问题，如下：0.....)(min103110wwtswEinRw将这个问题的约束放松一点，则有：3]0[..)(min100110iiinRwwtswE将这个问题在进一步放松，得到如下形式：CwtswEiiinRw1002..)(min110最后的式子，虽然仍然是使用10阶多项式在做拟合，但是它的约束却可以使得权重w比较小，或者说非0的w的分量的个数少，这就是Regularization，它在一定程度上尽量避免了overfitting。更一般地，Regularized的回归问题可以表示如下：CwtsyzwNwEQiiNnnnTinRwQ1221..)(1)(min1或者矩阵形式CwwtsyZwyZwNwETTinRwQ..)()(1)(min1下面要讲如何来解这个有约束的规划了，那就是利用拉格朗日乘子法，上述问题等价于无约束优化问题：)()()(1)(min1CwwyZwyZwNwETTRwQ其中叫做lagrange乘子，为了一下表示方便，我们把上面的式子写成如下形式：)()()(1)(min1CwwNyZwyZwNwETTRwQ对w求导，令其等于0，得yZIZZwwNyZZwZNTTregTTT1)(02)(2(RidgeRegression)注意只要0，IZZT总是可逆的(ZZT是半正定的，IZZT正定的，正定矩阵总是可逆的)。我们称这种上面这种形如2212||||wwQii的regularizer为weight-decayregularizer(weightdecay就是指让weight变小),或者叫L2regularizer,它是凸的，处处可微，并且很容易最优化。另外，还有一种常见的regularizer，叫做L1regularizer，也叫Lassoregularizer，形如:11||||||wwQii，它也是凸的，几乎处处可微，解释稀疏的。我们希望指出的是，如果做polynomialregression,QiNnnnTinRwiQwNyxwNwE0221))((1)(min1通常选择Legendrepolynomial，即))(),...,(,1()(1xLxLxQn比一般的polynomial，即),...,,,1()(2Qnxxxx效果会好一些。选择了合适的regularizer之后，还有一个问题就是如何选择？那就需要用到下面将要介绍的validation。2.2Validation机器学习中，我们常常会把数据集D分为互不相交的两部分，一部分叫做训练集trainD，一部分叫做验证集valD（通常取1/5的数据量来作验证）。trainD用来学习出一个最终的假设函数，valD来评估这个学习结果的好坏（近似估计学习出来的假设函数在新的数据上的表现）。其实，验证集的作用不仅仅是用来评估最终的学习结果的好坏，还有一个重要的作用，那就是指导我们学习过程中模型的选择。例如，选择线性模型还是飞线性模型，选择多项式的阶数，选择regularization中的参数（不同的对应不同的模型）等等。当有很多模型可以选择时，可以用训练集分别学习得到不同的最终假设，我们再用验证集来分别估计各个模型学习出来的假设函数的好坏，从中选择出最好的一个假设对应的模型；这时候我们用选出来的模型在整个数据集D上重新学习，得到最终的假设（注意用整个数据集D学习出来的假设往往比仅仅用训练集trainD学习出来的假设要好一些）。为了近可能准确地评估学习结果的好坏，我们希望训练集trainDvalD尽可能地大；然而，训练集trainDvalD大就会导致训练集trainD小，使得学习结果不好。如何选择训练集才能既满足评估学习结果的要求，又满足有足够的训练数据呢？一种方法就是CrossValidation。Leave-one-outCrossValidation：每次从数据集}...,{,1NxxD中取一个数据),(iiyx作为validationdata,其余作为trainingdata。显然，用一个数据评估的结果)),(()(iiiivaliyxgegEe并不能反映出学习结果的好坏，但是，这里选取),(iiyx的方式有N种，我们可以用所有的ie的平均值NiicveNE11来估计学习结果的好坏。V-foldCrossValidation：上面模型的推广。如果数据量很大时，我们用Leave-one-out就太浪费时间了（有多少数据，Leave-one-out就做多少遍）。这时，把数据集D分成大小相等并且互不相交的V份（通常取10V），每次取一份（不是仅仅一个数据）拿来做validation，其余的做training。其余的跟Leave-one-out完全一样。实际中,我们通常用V-foldCrossValidation,而不是Leave-one-outCrossValidation。最后，我们简单比较一下training,testing和validation：Training：selectamonghypothesisValidation：selectamongfinalistsTesting:justevaluate可见，虽然validation比起training来说，可能没有污染那么多，但是比起真正的testing来说，仍然是一个比较乐观的数字。