機(jī)器學(xué)習(xí)中的 Overfitting

淺談機(jī)器學(xué)習(xí)中的Overfitting在機(jī)器學(xué)習(xí)中，常會(huì)出現(xiàn)這樣一種的現(xiàn)象：一個(gè)假設(shè)在訓(xùn)練數(shù)據(jù)上表現(xiàn)很好（in-sampleerror很小，即E很?。?，但是在訓(xùn)練數(shù)據(jù)外的數(shù)據(jù)集上卻變現(xiàn)很差（out-of-sampleerror很大，即Eout很大），這時(shí)，我們稱發(fā)生了過度擬合（overfitting）o1.Overfitting的原因Overfitting，字面上講，就是“fittingthedatamorethaniswarranted.”。overfitting自然是我們不愿意看到的，那么是什么原因?qū)е铝薿verfitting呢？如果我們的訓(xùn)練數(shù)據(jù)中含有noise，那么我們?cè)跀M合時(shí)，為了追求最小E,（in-sampleerror），一不小心，就可能用了過于復(fù)雜的模型不僅fit了data，還fit了noise，也恰恰是因?yàn)閛verfit了noise，造成學(xué)習(xí)出來(lái)的函數(shù)其實(shí)出現(xiàn)了很大的偏差，因此在新的數(shù)據(jù)上變現(xiàn)不好（E很大）也就不足為奇了?？蒾ut見，數(shù)據(jù)中含有noise是造成overfitting的一個(gè)原因。其實(shí)，造成overfitting的原因遠(yuǎn)不只是數(shù)據(jù)中noise一種，即使數(shù)據(jù)中沒有noise，也有可能造成overfitting。例如，我們來(lái)看下面一個(gè)例子，目標(biāo)函數(shù)是一個(gè)50階多項(xiàng)式，數(shù)據(jù)如下面左圖所示（這里沒有任何noise）,我們分別用2階和10階的多項(xiàng)式來(lái)擬合，擬合結(jié)果如下面右圖所示。10階的多項(xiàng)式的擬合結(jié)果竟然比2階多項(xiàng)式的差，結(jié)果多少讓人意外。我們想象兩個(gè)人來(lái)解決同一個(gè)擬合問題，一個(gè)人比較聰明，會(huì)10階的多項(xiàng)式，而令一個(gè)人只會(huì)2階的多項(xiàng)式，但是，結(jié)果很奇怪，一個(gè)笨笨的人最后居然贏了，聰明人好像“聰明反被聰明誤”。其實(shí)如果你知道VCtheory,就不難理解，用10階的函數(shù)來(lái)擬合得到較差E仙的概率要比用2階的函數(shù)來(lái)擬合得到一個(gè)同樣差Eout的概率要大的多。如果你不知道VCtheory，我們可以來(lái)看下面兩個(gè)曲線，我們稱之為學(xué)習(xí)曲線，表示了用2階和10階多項(xiàng)式擬合時(shí)錯(cuò)誤率隨測(cè)試數(shù)據(jù)量的大小的變化情況（左面的圖是用2階多項(xiàng)式的結(jié)果，右面的圖是10階多項(xiàng)式的結(jié)果）。我們上面的例子中，數(shù)據(jù)量不夠多，這時(shí)候從曲線可以看出，10階多項(xiàng)式擬合后雖然氣很小，但是Eg很大。但是，我們也應(yīng)該注意到，當(dāng)數(shù)據(jù)足夠多時(shí)（datasizeN足夠大），用當(dāng)數(shù)據(jù)足夠多時(shí)（datasizeN足夠大），用10階函數(shù)擬合會(huì)比2階函數(shù)好（E小）。out因此，我們可以得到結(jié)論，overfitting跟目標(biāo)函數(shù)的復(fù)雜度有關(guān)，復(fù)雜的目標(biāo)函數(shù)更容易發(fā)生overfitting，另夕卜，overfitting還跟datasize有關(guān)，當(dāng)數(shù)據(jù)量較小時(shí)，我們應(yīng)該選取較簡(jiǎn)單的模型來(lái)擬合，選擇復(fù)雜的模型就容易產(chǎn)生overfitting。于是，我們得到了產(chǎn)生overfitting的三個(gè)最主要的原因：Datasize，noise和targetcomplexity。上面例子中，如果我們將10階多項(xiàng)式的值和2階多項(xiàng)式的值的差作為overfitting的一種度量，那么ovefiting與Datasize，noise和targetcomplexity的關(guān)系可以表示為如下兩個(gè)圖（圖中由藍(lán)色邊到紅色表示overfitting的概率逐漸變大）：我們?cè)俅位仡^看剛才的例子，里面真的沒有“noisg”？如果目標(biāo)函數(shù)太復(fù)雜，那么對(duì)于每一個(gè)模型來(lái)說，都沒有辦法來(lái)描述好目標(biāo)函數(shù)，但是每一個(gè)模型的假設(shè)函數(shù)集中一定有一個(gè)對(duì)目標(biāo)函數(shù)f（x）的最好的近似鏟，他們之間的差異可以看做是一種noise，為了與data中的那種randomnoise（stochasticnoise）區(qū)分，我們稱這種noise為deterministicnoiseo右圖中，藍(lán)線表示targetfunction，紅線表示bestfitto萬(wàn)陰影部分就表示deterministicnoiseoDeterministicnoise和stochasticnoise對(duì)overfitting的影響非常相似（由上面的兩個(gè)圖形對(duì)比可以看出）。2.Overfitting的對(duì)策

如何盡量避免overfitting呢？方法有很多，有一些簡(jiǎn)單的技巧，比如，從簡(jiǎn)單的模型開始嘗試；數(shù)據(jù)清洗等；還有非常重要的兩個(gè)手段，就是regularization和validation。2.1RegularizationRegularization是通過添加約束的方式來(lái)尋找一個(gè)簡(jiǎn)單的假設(shè)來(lái)擬合目標(biāo)函數(shù)，從而避免過度擬合。以上面10階多項(xiàng)式擬合的問題為例，可以表示為如下無(wú)約束的優(yōu)化問題：minE(w)weR10+1 '"s.t. s.t. w=...=w=0minE(w)weR10+1m將這個(gè)問題的約束放松一點(diǎn)，則有:minE(minE(w)weRio+iins.t.雙W^0]<3ii=0將這個(gè)問題在進(jìn)一步放松，得到如下形式:minE(w) stweR10+1m:EminE(w) stweR10+1m最后的式子，雖然仍然是使用10階多項(xiàng)式在做擬合，但是它的約束卻可以使得權(quán)重w比較小，或者說非0的w的分量的個(gè)數(shù)少，這就是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下面要講如何來(lái)解這個(gè)有約束的規(guī)劃了，那就是利用拉格朗日乘子法，上述問題等價(jià)于無(wú)約束優(yōu)化問題：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人 八對(duì)w求導(dǎo)，令其等于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變?。蛘呓蠰2regularizer,它是凸的，處處可微，并且很容易最優(yōu)化。另外，還有一種常見的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）效果會(huì)好一些。n選擇了合適的regularizer之后，還有一個(gè)問題就是如何選擇人？那就需要用到下面將要介紹的validation。2.2Validation機(jī)器學(xué)習(xí)中，我們常常會(huì)把數(shù)據(jù)集D分為互不相交的兩部分，一部分叫做訓(xùn)練集Dtrain一部分叫做驗(yàn)證集D訕（通常取1/5的數(shù)據(jù)量來(lái)作驗(yàn)證）。D用來(lái)學(xué)習(xí)出一個(gè)最終的假設(shè)函數(shù)，Da^來(lái)評(píng)估這個(gè)學(xué)習(xí)結(jié)果的好壞（近似估計(jì)學(xué)習(xí)出來(lái)的假設(shè)函數(shù)在新的數(shù)據(jù)上的表現(xiàn)）。其實(shí)，驗(yàn)證集的作用不僅僅是用來(lái)評(píng)估最終的學(xué)習(xí)結(jié)果的好壞，還有一個(gè)重要的作用，那就是指導(dǎo)我們學(xué)習(xí)過程中模型的選擇。例如，選擇線性模型還是飛線性模型，選擇多項(xiàng)式的階數(shù)，選擇regularization中的參數(shù)人（不同的人對(duì)應(yīng)不同的模型）等等。當(dāng)有很多模型可以選擇時(shí)，可以用訓(xùn)練集分別學(xué)習(xí)得到不同的最終假設(shè)，我們?cè)儆抿?yàn)證集來(lái)分別估計(jì)各個(gè)模型學(xué)習(xí)出來(lái)的假設(shè)函數(shù)的好壞，從中選擇出最好的一個(gè)假設(shè)對(duì)應(yīng)的模型；這時(shí)候我們用選出來(lái)的模型在整個(gè)數(shù)據(jù)集D上重新學(xué)習(xí)，得到最終的假設(shè)（注意用整個(gè)數(shù)據(jù)集D學(xué)習(xí)出來(lái)的假設(shè)往往比僅僅用訓(xùn)練集Dtan學(xué)習(xí)出來(lái)的假設(shè)要好一些）。為了近可能準(zhǔn)確地評(píng)估學(xué)習(xí)結(jié)果的好壞，我們希望訓(xùn)練集。皿/皿盡可能地大;然而，訓(xùn)練集DraamDa^大就會(huì)導(dǎo)致訓(xùn)練集D頒n小，使得學(xué)習(xí)結(jié)果不好。如何選擇訓(xùn)練集才能既滿足評(píng)估學(xué)習(xí)結(jié)果的要求，又滿足有足夠的訓(xùn)練數(shù)據(jù)呢？一種方法就是CrossValidationoLeave-one-outCrossValidation:每次從數(shù)據(jù)集D={x...,x}中取一個(gè)數(shù)據(jù)（x,y）作1,N ii為validationdata,其余作為trainingdata。顯然，用一個(gè)數(shù)據(jù)評(píng)估的結(jié)果e=E（g）=e（g（x）,j）并不能反映出學(xué)習(xí)結(jié)果的好壞，但是，這里選取3.,>.）的方ivali iii ii式有N種，我們可以用所有的ei的平均值E/N研ei來(lái)估計(jì)學(xué)習(xí)結(jié)果的好壞。i=1V-foldCrossValidation：上面模型的推廣。如果數(shù)據(jù)量很大時(shí)，我們用Leave-one-out就太浪費(fèi)時(shí)間了（有多少數(shù)據(jù)，Leave-one-out就做多少遍）。這時(shí)，把數(shù)據(jù)集。分成大小相等并且互不相交的V份（通常取V=10），每次取一份（不是僅僅一個(gè)數(shù)據(jù)）拿來(lái)做validation，其余的做training。其余的跟Leave-one-out完全一樣。實(shí)際中,我們通常用V-foldCrossValidation,而不是Lea