雷鋒網(wǎng)按：本文原載于英文網(wǎng)站“computer visiion for dummies”，譯者紅色石頭，原載于譯者個(gè)人博客，雷鋒網(wǎng)已獲授權(quán)。

  一、介紹

本篇文章，我們將討論所謂的“維度災(zāi)難”，并解釋在設(shè)計(jì)一個(gè)分類器時(shí)它為何如此重要。在下面幾節(jié)中我將對(duì)這個(gè)概念進(jìn)行直觀的解釋，并通過一個(gè)由于維度災(zāi)難導(dǎo)致的過擬合的例子來講解。

考慮這樣一個(gè)例子，我們有一些圖片，每張圖片描繪的是小貓或者小狗。我們?cè)噲D構(gòu)建一個(gè)分類器來自動(dòng)識(shí)別圖片中是貓還是狗。要做到這一點(diǎn)，我們首先需要考慮貓、狗的量化特征，這樣分類器算法才能利用這些特征對(duì)圖片進(jìn)行分類。例如我們可以通過毛皮顏色特征對(duì)貓狗進(jìn)行識(shí)別，即通過圖片的紅色程度、綠色程度、藍(lán)色程度不同，設(shè)計(jì)一個(gè)簡(jiǎn)單的線性分類器：

If 0.5*red+0.3*green+0.2*blue>0.6: 

    return cat;

else:

    return dog;

紅、綠、藍(lán)三種顏色我們稱之為特征Features，但僅僅利用這三個(gè)特征，還不能得到一個(gè)完美的分類器。因此，我們可以增加更多的特征來描述圖片。例如計(jì)算圖片X和Y方向的平均邊緣或者梯度密度?，F(xiàn)在總共有5個(gè)特征來構(gòu)建我們的分類器了。

為了得到更好的分類效果，我們可以增加更多特征，例如顏色、紋理分布和統(tǒng)計(jì)信息等。也許我們能得到上百個(gè)特征，但是分類器的效果會(huì)變得更好嗎？答案有些令人沮喪：并不能！事實(shí)上，特征數(shù)量超過一定值的時(shí)候，分類器的效果反而下降。圖1顯示了這種變化趨勢(shì)，這就是“維度災(zāi)難”。

圖1. 隨著維度增加，分類器性能提升；維度增加到某值后，分類器性能下降

下一節(jié)我們將解釋為什么產(chǎn)生這條曲線并討論如何避免這種情況發(fā)生。

  二、維度災(zāi)難與過擬合

在之前引入的貓和狗的例子中，我們假設(shè)有無窮多的貓和狗的圖片，然而，由于時(shí)間和處理能力限制，我們只得到10張圖片（貓的圖片或者狗的圖片）。我們的最終目標(biāo)是基于這10張圖片構(gòu)建一個(gè)分類器，能夠正確對(duì)10個(gè)樣本之外的無限多的圖片進(jìn)行正確分類。

現(xiàn)在，讓我們使用一個(gè)簡(jiǎn)單的線性分類器來嘗試得到一個(gè)好的分類器。如果只使用一個(gè)特征，例如使用圖片的平均紅色程度red。

圖2. 單個(gè)特征對(duì)訓(xùn)練樣本分類效果不佳

圖2展示了只使用一個(gè)特征并不能得到一個(gè)最佳的分類結(jié)果。因此，我們覺得增加第二個(gè)特征：圖片的平均綠色程度green。

圖3. 增加第二個(gè)特征仍然不能線性分割，即不存在一條直線能夠?qū)⒇埡凸吠耆珠_。

最后，我們決定再增加第三個(gè)特征：圖片的平均藍(lán)色程度，得到了三維特征空間：

圖4. 增加第三個(gè)特征實(shí)現(xiàn)了線性可分，即存在一個(gè)平面完全將貓和狗分開來。

在三維特征空間，我們可以找到一個(gè)平面將貓和狗完全分開。這意味著三個(gè)特征的線性組合可以對(duì)10個(gè)訓(xùn)練樣本進(jìn)行最佳的分類。

圖5. 特征越多，越有可能實(shí)現(xiàn)正確分類

以上的例子似乎證明了不斷增加特征數(shù)量，直到獲得最佳分類效果，是構(gòu)建一個(gè)分類器的最好方法。但是，之前圖1中，我們認(rèn)為情況并非如此。我們需要注意一個(gè)問題：隨著特征維度的增加，訓(xùn)練樣本的在特征空間的密度是如何呈指數(shù)型下降的？

在1D空間中（圖2所示），10個(gè)訓(xùn)練樣本完全覆蓋了1D特征空間，特征空間寬度為5。因此，1D下的樣本密度是10/2=5。而在2D空間中（圖3所示），同樣是10個(gè)訓(xùn)練樣本，它構(gòu)成的2D特征空間面積為5x5=25.因此，2D下的樣本密度是10/25=0.4。最后在3D空間中，10個(gè)訓(xùn)練樣本構(gòu)成的特征空間大小為5x5x5=125，因此，3D下的樣本密度為10/125=0.08。

如果我們繼續(xù)增加特征，整個(gè)特征空間維度增加，并變得越來越稀疏。由于稀疏性，我們更加容易找到一個(gè)超平面來實(shí)現(xiàn)分類。這是因?yàn)殡S著特征數(shù)量變得無限大，訓(xùn)練樣本在最佳超平面的錯(cuò)誤側(cè)的可能性將會(huì)變得無限小。然而，如果我們將高維的分類結(jié)果投影到低維空間中，將會(huì)出現(xiàn)一個(gè)嚴(yán)重的問題：

圖6. 使用太多特征導(dǎo)致過擬合。分類器學(xué)習(xí)了過多樣本數(shù)據(jù)的異常特征（噪聲），而對(duì)新數(shù)據(jù)的泛化能力不好。

圖6展示了3D的分類結(jié)果投影到2D特征空間的樣子。樣本數(shù)據(jù)在3D是線性可分的，但是在2D卻并非如此。事實(shí)上，增加第三個(gè)維度來獲得最佳的線性分類效果，等同于在低維特征空間中使用非線性分類器。其結(jié)果是，分類器學(xué)習(xí)了訓(xùn)練數(shù)據(jù)的噪聲和異常，而對(duì)樣本外的數(shù)據(jù)擬合效果并不理想，甚至很差。

這個(gè)概念稱為過擬合，是維度災(zāi)難的一個(gè)直接后果。圖7展示了一個(gè)只用2個(gè)特征進(jìn)行分類的線性分類器的二維平面圖。

圖7. 盡管訓(xùn)練樣本不能全都分類正確，但這個(gè)分類器的泛化能力比圖5要好。

盡管圖7中的簡(jiǎn)單的線性分類器比圖5中的非線性分類器的效果差，但是圖7的分類器的泛化能力強(qiáng)。這是因?yàn)榉诸惼鳑]有把樣本數(shù)據(jù)的噪聲和異常也進(jìn)行學(xué)習(xí)。另一方面說，使用更少的特征，維度災(zāi)難就能避免，就不會(huì)出現(xiàn)對(duì)訓(xùn)練樣本過擬合的現(xiàn)象。

圖8用不同的方式解釋上面的內(nèi)容。假設(shè)我們只使用一個(gè)特征來訓(xùn)練分類器，1D特征值的范圍限定在0到1之間，且每只貓和狗對(duì)應(yīng)的特征值是唯一的。如果我們希望訓(xùn)練樣本的特征值占特征值范圍的20%，那么訓(xùn)練樣本的數(shù)量就要達(dá)到總體樣本數(shù)的20%?，F(xiàn)在，如果增加第二個(gè)特征，也就是從直線變?yōu)槠矫?D特征空間，這種情況下，如果要覆蓋特征值范圍的20%，那么訓(xùn)練樣本數(shù)量就要達(dá)到總體樣本數(shù)的45%（0.450.45=0.2）。而在3D空間中，如果要覆蓋特征值范圍的20%，就需要訓(xùn)練樣本數(shù)量達(dá)到總體樣本數(shù)的58%（0.580.58*0.58=0.2）。

圖8. 覆蓋特征值范圍20%所需的訓(xùn)練樣本數(shù)量隨著維度增加呈指數(shù)型增長(zhǎng)

換句話說，如果可用的訓(xùn)練樣本數(shù)量是固定的，那么如果增加特征維度的話，過擬合就會(huì)發(fā)生。另一方面，如果增加特征維度，為了覆蓋同樣的特征值范圍、防止過擬合，那么所需的訓(xùn)練樣本數(shù)量就會(huì)成指數(shù)型增長(zhǎng)。

在上面的例子中，我們展示了維度災(zāi)難會(huì)引起訓(xùn)練數(shù)據(jù)的稀疏化。使用的特征越多，數(shù)據(jù)就會(huì)變得越稀疏，從而導(dǎo)致分類器的分類效果就會(huì)越差。維度災(zāi)難還會(huì)造成搜索空間的數(shù)據(jù)稀疏程度分布不均。事實(shí)上，圍繞原點(diǎn)的數(shù)據(jù)（在超立方體的中心）比在搜索空間的角落處的數(shù)據(jù)要稀疏得多。這可以用下面這個(gè)例子來解釋：

想象一個(gè)單位正方形代表了2D的特征空間，特征空間的平均值位于這個(gè)單位正方形的中心處，距中心處單位距離的所有點(diǎn)構(gòu)成了正方形的內(nèi)接圓。沒有落在單位圓的訓(xùn)練樣本距離搜索空間的角落處更距離中心處更近，而這些樣本由于特征值差異很大（樣本分布在正方形角落處），所有難以分類。因此，如果大部分樣本落在單位內(nèi)接圓里，就會(huì)更容易分類。如圖9所示：

圖9. 落在單位圓之外的訓(xùn)練樣本位于特征空間角落處，比位于特征空間中心處的樣本更難進(jìn)行分類。

一個(gè)有趣的問題是當(dāng)我們?cè)黾犹卣骺臻g的維度時(shí)，隨著正方形（超立方體）的體積變化，圓形（超球體）的體積是如何變化的？無論維度如何變化，超立方體的體積都是1，而半徑為0.5的超球體的體積隨著維度d的變化為：

圖10展示了隨著維度d的增加，超球面的體積是如何變化的：

圖10. 維度d很大時(shí)，超球面的體積趨于零

這表明了隨著維度變得越來越大，超球體的體積趨于零，而超立方體的體積是不變的。這種令人驚訝的反直覺發(fā)現(xiàn)部分解釋了在分類中維度災(zāi)難的問題：在高維空間中，大部分的訓(xùn)練數(shù)據(jù)分布在定義為特征空間的超立方體的角落處。就像之前提到的，特征空間角落處的樣本比超球體內(nèi)的樣本更加難以進(jìn)行正確分類。圖11分別從2D、3D和可視化的8D超立方體（2^8=256個(gè)角落）的例子論證了這個(gè)結(jié)論。

圖11. 隨著維度增加，大部分?jǐn)?shù)量數(shù)據(jù)分布在角落處

對(duì)于8維的超球體，大約98%的數(shù)據(jù)集中在它256個(gè)角落處。其結(jié)果是，當(dāng)特征空間的維度變得無限大時(shí)，從樣本點(diǎn)到質(zhì)心的最大、最小歐氏距離的差值與其最小歐式距離的比值趨于零：

因此，距離測(cè)量在高維空間中逐漸變得無效。因?yàn)榉诸惼魇腔谶@些距離測(cè)量的（例如Euclidean距離、Mahalanobis距離、Manhattan距離），所以低維空間特征更少，分類更加容易。同樣地，在高維空間的高斯分布會(huì)變平坦且尾巴更長(zhǎng)。

  三、如何避免維度災(zāi)難

圖1展示了隨著維度變得很大，分類器的性能是下降的。那么問題是“很大”意味著什么？過擬合如何避免？很遺憾，在分類問題中，沒有固定的規(guī)則來指定應(yīng)該使用多少特征。事實(shí)上，這依賴于訓(xùn)練樣本的數(shù)量、決策邊界的復(fù)雜性和使用的是哪個(gè)分類器。

如果理論上訓(xùn)練樣本時(shí)無限多的，那么維度災(zāi)難不會(huì)發(fā)生，我們可以使用無限多的特征來獲得一個(gè)完美的分類器。訓(xùn)練數(shù)據(jù)越少，使用的特征就要越少。如果N個(gè)訓(xùn)練樣本覆蓋了1D特征空間的范圍，那么在2D中，覆蓋同樣密度就需要NN個(gè)數(shù)據(jù)，同樣在3D中，就需要NN*N個(gè)數(shù)據(jù)。也就是說，隨著維度增加，訓(xùn)練樣本的數(shù)量要求隨指數(shù)增加。

此外，那些非線性決策邊界的分類器（例如神經(jīng)網(wǎng)絡(luò)、KNN分類器、決策樹等）分類效果好但是泛化能力差且容易發(fā)生過擬合。因此，當(dāng)使用這些分類器的時(shí)候，維度不能太高。如果使用泛化能力好的分類器（例如貝葉斯分類器、線性分類器），可以使用更多的特征，因?yàn)榉诸惼髂Ｐ筒⒉粡?fù)雜。圖6展示了高維中的簡(jiǎn)單分類器對(duì)應(yīng)于地位空間的復(fù)雜分類器。

因此，過擬合只在高維空間中預(yù)測(cè)相對(duì)少的參數(shù)和低維空間中預(yù)測(cè)多參數(shù)這兩種情況下發(fā)生。舉個(gè)例子，高斯密度函數(shù)有兩類參數(shù)：均值和協(xié)方差矩陣。在3D空間中，協(xié)方差矩陣是3x3的對(duì)稱陣，總共有6個(gè)值（3個(gè)主對(duì)角線值和3個(gè)非對(duì)角線值），還有3個(gè)均值，加在一起，一共要求9個(gè)參數(shù)；而在1D，高斯密度函數(shù)只要求2個(gè)參數(shù)（1個(gè)均值，1個(gè)方差）；在2D中，高斯密度函數(shù)要求5個(gè)參數(shù)（2個(gè)均值，3個(gè)協(xié)方差參數(shù)）。我們可以發(fā)現(xiàn)，隨著維度增加，參數(shù)數(shù)量呈平方式增長(zhǎng)。

在之前的文章里我們發(fā)現(xiàn)，如果參數(shù)數(shù)量增加，那么參數(shù)的方差就會(huì)增大（前提是估計(jì)偏差和訓(xùn)練樣本數(shù)量保持不變）。這就意味著，如果圍度增加，估計(jì)的參數(shù)方差增大，導(dǎo)致參數(shù)估計(jì)的質(zhì)量下降。分類器的方差增大意味著出現(xiàn)過擬合。

另一個(gè)有趣的問題是：應(yīng)該選擇哪些特征。如果有N個(gè)特征，我們應(yīng)該如何選取M個(gè)特征？一種方法是在圖1曲線中找到性能最佳的位置。但是，由于很難對(duì)所有的特征組合進(jìn)行訓(xùn)練和測(cè)試，所以有一些其他辦法來找到最佳選擇。這些方法稱之為特征選擇算法，經(jīng)常用啟發(fā)式方法（例如貪心算法、best-first方法等）來定位最佳的特征組合和數(shù)量。

還有一種方法是用M個(gè)特征替換N個(gè)特征，M個(gè)特征由原始特征組合而成。這種通過對(duì)原始特征進(jìn)行優(yōu)化的線性或非線性組合來減少問題維度的算法稱為特征提取。一個(gè)著名的維度降低技術(shù)是主成分分析法（PCA），它去除不相關(guān)維度，對(duì)N個(gè)原始特征進(jìn)行線性組合。PCA算法試著找到低維的線性子空間，保持原始數(shù)據(jù)的最大方差。然而，數(shù)據(jù)方差最大不一定代表數(shù)據(jù)最顯著的分類信息。

最后，一項(xiàng)非常有用的被用來測(cè)試和避免過擬合的技術(shù)是交叉驗(yàn)證。交叉驗(yàn)證將原始訓(xùn)練數(shù)據(jù)分成多個(gè)訓(xùn)練樣本子集。在分類器進(jìn)行訓(xùn)練過程中，一個(gè)樣本子集被用來測(cè)試分類器的準(zhǔn)確性，其他樣本用來進(jìn)行參數(shù)估計(jì)。如果交叉驗(yàn)證的結(jié)果與訓(xùn)練樣本子集得到的結(jié)果不一致，那么就表示發(fā)生了過擬合。如果訓(xùn)練樣本有限，那么可以使用k折法或者留一發(fā)進(jìn)行交叉驗(yàn)證。

  四、結(jié)論

這篇文章我們討論了特征選擇、特征提取、交叉驗(yàn)證的重要性，以及避免由維度災(zāi)難導(dǎo)致的過擬合。通過一個(gè)過擬合的簡(jiǎn)單例子，我們復(fù)習(xí)了維度災(zāi)難的重要影響。

雷鋒網(wǎng)相關(guān)閱讀：

手把手教你用 TensorFlow 實(shí)現(xiàn)文本分類（上）

手把手教你用 TensorFlow 實(shí)現(xiàn)文本分類（下）

雷峰網(wǎng)版權(quán)文章，未經(jīng)授權(quán)禁止轉(zhuǎn)載。詳情見轉(zhuǎn)載須知。