javascript:void(0)
在看機器學習的論文時，經常會看到有作者提到“curse of dimensionality”，中文譯為“維數災難”，這到底是一個什麼樣的“災難”？本文将通過一個例子來介紹這令人讨厭的“curse of dimensionality”以及它在分類問題中的重要性。
假設現在有一組照片，每一張照片裡有一隻貓或者一條狗。我們希望設計一個分類器可以自動地将照片中的動物辨識開來。為了實作這個目标，首先需要考慮如何将照片中的動物的特征用數字的形式表達出來。貓與狗的最大差別是什麼？有人可能首先想到貓與狗的顔色不一樣，有人則可能想到貓與狗的大小不一樣。假設從顔色來辨識貓與狗，可以設計三個特征：紅色的平均值，綠色的平均值和藍色的平均值，來決定照片中的動物屬于哪一個類：
但是，僅僅通過這三個特征進行分類可能無法得到一個令人滿意的結果。是以，可以再增加一些特征：大小，紋理等。也許增加特征之後，分類的結果會有所提高。但是，特征是不是越多越好？
圖1 過了某一個值後，分類器的性能随着維數的增加不升反降
從圖1可以看到分類器的性能随着特征個數的變化不斷增加，過了某一個值後，性能不升反降。這種現象稱為“維數災難”。
繼續之前的例子。假設地球上貓和狗的數量是無限的。由于有限的時間和計算能力，我們僅僅選取了10張照片作為訓練樣本。我們的目的是基于這10張照片來訓練一個線性分類器，使得這個線性分類器可以對剩餘的貓或狗的照片進行正确分類。我們從隻用一個特征來辨識貓和狗開始：
圖2
從圖2可以看到，如果僅僅隻有一個特征的話，貓和狗幾乎是均勻分布在這條線段上，很難将10張照片線性分類。那麼，增加一個特征後的情況會怎麼樣：
圖3
增加一個特征後，我們發現仍然無法找到一條直線将貓和狗分開。是以，考慮需要再增加一個特征：
圖4
此時，我們終于找到了一個平面将貓和狗分開。需要注意的是，隻有一個特征時，假設特征空間是長度為5的線段，則樣本密度是10/5=2。有兩個特征時，特征空間大小是5*5=25，樣本密度是10/25=0.4。有三個特征時，特征空間大小是5*5*5=125，樣本密度是10/125=0.08。如果繼續增加特征數量，樣本密度會更加稀疏，也就更容易找到一個超平面将訓練樣本分開。因為随着特征數量趨向于無限大，樣本密度非常稀疏，訓練樣本被分錯的可能性趨向于零。當我們将高維空間的分類結果映射到低維空間時，一個嚴重的問題出現了：
圖5
從圖5可以看到将三維特征空間映射到二維特征空間後的結果。盡管在高維特征空間時訓練樣本線性可分，但是映射到低維空間後，結果正好相反。事實上，增加特征數量使得高維空間線性可分，相當于在低維空間内訓練一個複雜的非線性分類器。不過，這個非線性分類器太過“聰明”，僅僅學到了一些特例。如果将其用來辨識那些未曾出現在訓練樣本中的測試樣本時，通常結果不太理想。這其實就是我們在機器學習中學過的過拟合問題。
圖6
盡管圖6所示的隻采用2個特征的線性分類器分錯了一些訓練樣本，準确率似乎沒有圖4的高，但是，采用2個特征的線性分類器的泛化能力比采用3個特征的線性分類器要強。因為，采用2個特征的線性分類器學習到的不隻是特例，而是一個整體趨勢，對于那些未曾出現過的樣本也可以比較好地辨識開來。換句話說，通過減少特征數量，可以避免出現過拟合問題，進而避免“維數災難”。
圖7
圖7從另一個角度诠釋了“維數災難”。假設隻有一個特征時，特征的值域是0到1，每一隻貓和狗的特征值都是唯一的。如果我們希望訓練樣本覆寫特征值值域的20%，那麼就需要貓和狗總數的20%。我們增加一個特征後，為了繼續覆寫特征值值域的20%就需要貓和狗總數的45%(0.45^2=0.2)。繼續增加一個特征後，需要貓和狗總數的58%(0.58^3=0.2)。随着特征數量的增加，為了覆寫特征值值域的20%，就需要更多的訓練樣本。如果沒有足夠的訓練樣本，就可能會出現過拟合問題。
通過上述例子，我們可以看到特征數量越多，訓練樣本就會越稀疏，分類器的參數估計就會越不準确，更加容易出現過拟合問題。“維數災難”的另一個影響是訓練樣本的稀疏性并不是均勻分布的。處于中心位置的訓練樣本比四周的訓練樣本更加稀疏。
圖8
假設有一個二維特征空間，如圖8所示的矩形，在矩形内部有一個内切的圓形。由于越接近圓心的樣本越稀疏，是以，相比于圓形内的樣本，那些位于矩形四角的樣本更加難以分類。那麼，随着特征數量的增加，圓形的面積會不會變化呢？這裡我們假設超立方體(hypercube)的邊長d=1，那麼計算半徑為0.5的超球面(hypersphere)的體積(volume)的公式為：
公式1
圖9
從圖9可以看出随着特征數量的增加，超球面的體積逐漸減小直至趨向于零，然而超立方體的體積卻不變。這個結果有點出乎意料，但部分說明了分類問題中的“維數災難”：在高維特征空間中，大多數的訓練樣本位于超立方體的角落。
圖10
圖10顯示了不同次元下，樣本的分布情況。在8維特征空間中，共有2^8=256個角落，而98%的樣本分布在這些角落。随着次元的不斷增加，公式2将趨向于0，其中dist_max和dist_min分别表示樣本到中心的最大與最小距離。
公式2
是以，在高維特征空間中對于樣本距離的度量失去意義。由于分類器基本都依賴于如Euclidean距離，Manhattan距離等，是以在特征數量過大時，分類器的性能就會出現下降。
是以，我們如何避免“維數災難”？圖1顯示了分類器的性能随着特征個數的變化不斷增加，過了某一個值後，性能不升反降。這裡的某一個值到底是多少呢？目前，還沒有方法來确定分類問題中的這個門檻值是多少，這依賴于訓練樣本的數量，決策邊界的複雜性以及分類器的類型。理論上，如果訓練樣本的數量無限大，那麼就不會存在“維數災難”，我們可以采用任意多的特征來訓練分類器。事實上，訓練樣本的數量是有限的，是以不應該采用過多的特征。此外，那些需要精确的非線性決策邊界的分類器，比如neural network，knn，decision trees等的泛化能力往往并不是很好，更容易發生過拟合問題。是以，在設計這些分類器時應當慎重考慮特征的數量。相反，那些泛化能力較好的分類器，比如naive Bayesian，linear classifier等，可以适當增加特征的數量。
如果給定了N個特征，我們該如何從中選出M個最優的特征？最簡單粗暴的方法是嘗試所有特征的組合，從中挑出M個最優的特征。事實上，這是非常花時間的，或者說不可行的。其實，已經有許多特征選擇算法(feature selection algorithms)來幫助我們确定特征的數量以及選擇特征。此外，還有許多特征抽取方法(feature extraction methods)，比如PCA等。交叉驗證(cross-validation)也常常被用于檢測與避免過拟合問題。