在看機器學習的論文時，經常會看到有作者提到“curse of dimensionality”，中文譯為“維數災難”，這到底是一個什麼樣的“災難”？本文將通過一個例子來介紹這令人討厭的“curse of dimensionality”以及它在分類問題中的重要性。
假設現在有一組照片，每一張照片裡有一只貓或者一條狗。我們希望設計一個分類器可以自動地將照片中的動物辨別開來。為了實現這個目標，首先需要考慮如何將照片中的動物的特征用數字的形式表達出來。貓與狗的最大區別是什麼？有人可能首先想到貓與狗的顏色不一樣，有人則可能想到貓與狗的大小不一樣。假設從顏色來辨別貓與狗，可以設計三個特征：紅色的平均值，綠色的平均值和藍色的平均值，來決定照片中的動物屬於哪一個類：
1 if 0.5 * red + 0.3 * green + 0.2 * blue > 0.6: 2 return cat 3 else: 4 return dog
但是，僅僅通過這三個特征進行分類可能無法得到一個令人滿意的結果。因此，可以再增加一些特征：大小，紋理等。也許增加特征之後，分類的結果會有所提高。但是，特征是不是越多越好？
圖1 過了某一個值後，分類器的性能隨著維數的增加不升反降
從圖1可以看到分類器的性能隨著特征個數的變化不斷增加，過了某一個值後，性能不升反降。這種現象稱為“維數災難”。
繼續之前的例子。假設地球上貓和狗的數量是無限的。由於有限的時間和計算能力，我們僅僅選取了10張照片作為訓練樣本。我們的目的是基於這10張照片來訓練一個線性分類器，使得這個線性分類器可以對剩余的貓或狗的照片進行正確分類。我們從只用一個特征來辨別貓和狗開始：
圖2
從圖2可以看到，如果僅僅只有一個特征的話，貓和狗幾乎是均勻分布在這條線段上，很難將10張照片線性分類。那麼，增加一個特征後的情況會怎麼樣：
圖3
增加一個特征後，我們發現仍然無法找到一條直線將貓和狗分開。所以，考慮需要再增加一個特征：
圖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)也常常被用於檢測與避免過擬合問題。
參考資料：
[1] Vincent Spruyt. The Curse of Dimensionality in classification. Computer vision for dummies. 2014. [Link]
