机器学习中的 Overfitting

浅谈机器学习中的Overfitting在机器学习中，常会出现这样一种的现象：一个假设在训练数据上表现很好（in-sampleerror很小，即E很小），但是在训练数据外的数据集上却变现很差（out-of-sampleerror很大，即Eout很大），这时，我们称发生了过度拟合（overfitting）o1.Overfitting的原因Overfitting，字面上讲，就是“fittingthedatamorethaniswarranted.”。overfitting自然是我们不愿意看到的，那么是什么原因导致了overfitting呢？如果我们的训练数据中含有noise，那么我们在拟合时，为了追求最小E,（in-sampleerror），一不小心，就可能用了过于复杂的模型不仅fit了data，还fit了noise，也恰恰是因为overfit了noise，造成学习出来的函数其实出现了很大的偏差，因此在新的数据上变现不好（E很大）也就不足为奇了。可out见，数据中含有noise是造成overfitting的一个原因。其实，造成overfitting的原因远不只是数据中noise一种，即使数据中没有noise，也有可能造成overfitting。例如，我们来看下面一个例子，目标函数是一个50阶多项式，数据如下面左图所示（这里没有任何noise）,我们分别用2阶和10阶的多项式来拟合，拟合结果如下面右图所示。10阶的多项式的拟合结果竟然比2阶多项式的差，结果多少让人意外。我们想象两个人来解决同一个拟合问题，一个人比较聪明，会10阶的多项式，而令一个人只会2阶的多项式，但是，结果很奇怪，一个笨笨的人最后居然赢了，聪明人好像“聪明反被聪明误”。其实如果你知道VCtheory,就不难理解，用10阶的函数来拟合得到较差E仙的概率要比用2阶的函数来拟合得到一个同样差Eout的概率要大的多。如果你不知道VCtheory，我们可以来看下面两个曲线，我们称之为学习曲线，表示了用2阶和10阶多项式拟合时错误率随测试数据量的大小的变化情况（左面的图是用2阶多项式的结果，右面的图是10阶多项式的结果）。我们上面的例子中，数据量不够多，这时候从曲线可以看出，10阶多项式拟合后虽然气很小，但是Eg很大。但是，我们也应该注意到，当数据足够多时（datasizeN足够大），用当数据足够多时（datasizeN足够大），用10阶函数拟合会比2阶函数好（E小）。out因此，我们可以得到结论，overfitting跟目标函数的复杂度有关，复杂的目标函数更容易发生overfitting，另夕卜，overfitting还跟datasize有关，当数据量较小时，我们应该选取较简单的模型来拟合，选择复杂的模型就容易产生overfitting。于是，我们得到了产生overfitting的三个最主要的原因：Datasize，noise和targetcomplexity。上面例子中，如果我们将10阶多项式的值和2阶多项式的值的差作为overfitting的一种度量，那么ovefiting与Datasize，noise和targetcomplexity的关系可以表示为如下两个图（图中由蓝色边到红色表示overfitting的概率逐渐变大）：我们再次回头看刚才的例子，里面真的没有“noisg”？如果目标函数太复杂，那么对于每一个模型来说，都没有办法来描述好目标函数，但是每一个模型的假设函数集中一定有一个对目标函数f（x）的最好的近似铲，他们之间的差异可以看做是一种noise，为了与data中的那种randomnoise（stochasticnoise）区分，我们称这种noise为deterministicnoiseo右图中，蓝线表示targetfunction，红线表示bestfitto万阴影部分就表示deterministicnoiseoDeterministicnoise和stochasticnoise对overfitting的影响非常相似（由上面的两个图形对比可以看出）。2.Overfitting的对策

如何尽量避免overfitting呢？方法有很多，有一些简单的技巧，比如，从简单的模型开始尝试；数据清洗等；还有非常重要的两个手段，就是regularization和validation。2.1RegularizationRegularization是通过添加约束的方式来寻找一个简单的假设来拟合目标函数，从而避免过度拟合。以上面10阶多项式拟合的问题为例，可以表示为如下无约束的优化问题：minE(w)weR10+1 '"s.t. s.t. w=...=w=0minE(w)weR10+1m将这个问题的约束放松一点，则有:minE(minE(w)weRio+iins.t.双W^0]<3ii=0将这个问题在进一步放松，得到如下形式:minE(w) stweR10+1m:EminE(w) stweR10+1m最后的式子，虽然仍然是使用10阶多项式在做拟合，但是它的约束却可以使得权重w比较小，或者说非0的w的分量的个数少，这就是Regularization，它在一定程度上尽量避免了overfitting。更一般地，Regularized的回归问题可以表示如下：minE(w)=1E(wtz-y)2w*+iin N.=1 nns.t.Ew2<Cii=1或者矩阵形式minE(w)=N(Zw-y)t(Zw-y)s.t.wtw<C下面要讲如何来解这个有约束的规划了，那就是利用拉格朗日乘子法，上述问题等价于无约束优化问题：minE(w)=—(Zw-y)t(Zw-y)+入(wtw-C)TOC\o"1-5"\h\zweRO+i N其中人叫做lagrange乘子，为了一下表示方便，我们把上面的式子写成如下形式：.… 1 一、人，八、minE(w)=—(Zw-y)t(Zw-y)+—(wtw-C)weE N N2,… r、 2人 八对w求导，令其等于0，得N(ZtZw-ZTy)T+^w=0=>w=(ZtZ+XI)-1ZTy(RidgeRegression)注意只要人〉0,ZtZ+XI总是可逆的（ZTZ是半正定的，ZtZ+XI正定的，正定矩阵总是可逆的）。我们称这种上面这种形如Yw=||wII2的regularizer为weight-decayregularizer（weighti=1decay就是指让weight变小），或者叫L2regularizer,它是凸的，处处可微，并且很容易最优化。另外，还有一种常见的regularizer，叫做L1regularizer，也叫Lassoregularizer，形如：YIwI=IIwII，它也是凸的，几乎处处可微，解释稀疏的。i 1i=1我们希望指出的是，如果做polynomialregression,minE(w)=-1Y(wT^(尤)-y)2+箜w2n=1 i=0通常选择Legendrepolynomial，即4(x)=(1,L](x),...,Lq(x))比一般的polynomial，即通常选择Legendrepolynomial，4（x）=（1,x,x2,...,xQ）效果会好一些。n选择了合适的regularizer之后，还有一个问题就是如何选择人？那就需要用到下面将要介绍的validation。2.2Validation机器学习中，我们常常会把数据集D分为互不相交的两部分，一部分叫做训练集Dtrain一部分叫做验证集D讪（通常取1/5的数据量来作验证）。D用来学习出一个最终的假设函数，Da^来评估这个学习结果的好坏（近似估计学习出来的假设函数在新的数据上的表现）。其实，验证集的作用不仅仅是用来评估最终的学习结果的好坏，还有一个重要的作用，那就是指导我们学习过程中模型的选择。例如，选择线性模型还是飞线性模型，选择多项式的阶数，选择regularization中的参数人（不同的人对应不同的模型）等等。当有很多模型可以选择时，可以用训练集分别学习得到不同的最终假设，我们再用验证集来分别估计各个模型学习出来的假设函数的好坏，从中选择出最好的一个假设对应的模型；这时候我们用选出来的模型在整个数据集D上重新学习，得到最终的假设（注意用整个数据集D学习出来的假设往往比仅仅用训练集Dtan学习出来的假设要好一些）。为了近可能准确地评估学习结果的好坏，我们希望训练集。皿/皿尽可能地大;然而，训练集DraamDa^大就会导致训练集D颁n小，使得学习结果不好。如何选择训练集才能既满足评估学习结果的要求，又满足有足够的训练数据呢？一种方法就是CrossValidationoLeave-one-outCrossValidation:每次从数据集D={x...,x}中取一个数据（x,y）作1,N ii为validationdata,其余作为trainingdata。显然，用一个数据评估的结果e=E（g）=e（g（x）,j）并不能反映出学习结果的好坏，但是，这里选取3.,>.）的方ivali iii ii式有N种，我们可以用所有的ei的平均值E/N研ei来估计学习结果的好坏。i=1V-foldCrossValidation：上面模型的推广。如果数据量很大时，我们用Leave-one-out就太浪费时间了（有多少数据，Leave-one-out就做多少遍）。这时，把数据集。分成大小相等并且互不相交的V份（通常取V=10），每次取一份（不是仅仅一个数据）拿来做validation，其余的做training。其余的跟Leave-one-out完全一样。实际中,我们通常用V-foldCrossValidation,而不是Lea