怎樣理解"curse of dimensionality"?

01-21

如何形象地說明這個問題。

維數增多主要會帶來的高維空間數據稀疏化問題。簡單地說：

p=1，則單位球(簡化為正值的情況）變為一條[0,1]之間的直線。如果我們有N個點，則在均勻分布的情況下，兩點之間的距離為1/N。其實平均分布和完全隨機分布的兩兩點之間平均距離這個概念大致是等價的，大家可稍微想像一下這個過程。
p=2，單位球則是邊長為1的正方形，如果還是只有N個點，則兩點之間的平均距離為 $sqrt{frac{1}{n}}$ 。換言之，如果我們還想維持兩點之間平均距離為1/N，那麼則需 $N^2$ 個點。
以此類題，在p維空間，N個點兩兩之間的平均距離為 $N^{-frac{1}{p}}$ ，或者需要 $N^p$ 個點來維持1/N的平均距離。

由此可見，高維空間使得數據變得更加稀疏。這裡有一個重要的定理：N個點在p維單位球內隨機分布，則隨著p的增大，這些點會越來越遠離單位球的中心，轉而往外緣分散。這個定理源於各點距單位球中心距離的中間值計算公式：

$d(p,N)=(1-frac{1}{2}^{frac{1}{N}})^frac{1}{p}$

當p→∞時，d(p,N)→1。

很顯然，當N變大時，這個距離趨近於0。直觀的理解就是，想像我們有一堆氣體分子，p變大使得空間變大，所以這些分子開始遠離彼此；而N變大意味著有更多氣體分子進來，所以兩兩之間難免更擠一些。

總之，當維數增大時，空間數據會變得更稀疏，這將導致bias和variance的增加，最後影響模型的預測效果。下圖以KNN演算法為例：

來自於《The Elements of Statistical Learning》

簡單談談自己的理解，拋磚引玉僅供參考，如有理解不當、偏頗之處，不吝賜教。

Dimension在機器學習中是描述數據的特徵向量的維度。隨著特徵向量維度的增長，不同特徵的組合會指數級增長，特徵空間急劇增長，而在樣本數據較少時會影響到一些機器學習演算法的效果。

舉個例子，假設建立模型，通過人體的生理指標預測該人是否健康（只是假設舉例），只考慮血壓時，每個數據的特徵向量維度為1，模型僅通過樣本數據的血壓，判斷是否健康；增加考慮血糖，特徵向量維度為2，這樣不同的血壓、血糖組合使得特徵空間維度增加至二維；繼續增加其它特徵，會使得特徵空間進一步指數級增長。

上圖引自《Deep Learning》5.11.1，如最左邊一圖，只考慮一個特徵的情況下，將該特徵劃分為10個cell，對新樣本數據判斷其處於哪個cell中，再根據滿足該cell的訓練數據進行多數投票決定新樣本數據的類別；當特徵維度增加後，不同的特徵進行組合後，特徵空間中的數據會變得更加稀疏。這樣，對於剛好出現在上圖中空白cell的測試數據，可能就束手無策了。

為了解決特徵維度增加導致的特徵空間中數據樣本分布稀疏的問題，可以通過增加更多的訓練數據，但是隨著維度增長，需要的數據量將會指數級增長，進而導致如KNN的預測更加耗費計算資源，這便是curse of dimensionality。

隨著維數的增高演算法的收斂率(rate of convergence)以指數級下降

換句話就是說有可能估計一維變數只要20個樣本，三圍（維）就需要8000個了

而且這個問題是幾乎不可能改變的，可以用RKHS把一個sample space投影到某個高維feature space

然並卵因為在這個過程中要麼減小維度讓模型不那麼精確要麼保存所有的feature情況下維度依然保持不變

話說要是把這個問題方方面面寫清楚都可以發一篇小paper了233333

nearest neighbor演算法，維數越高，需要的數據越多，才能保證在一點的附近有足夠多的neighbor。所以一般來說當特徵很多時KNN的效果會下降。

當然也有例外，某次做一個20個特徵的KNN時候，結果居然比隨機森林還要好_(:з」∠)_場面一度十分尷尬…

首先，在同等範圍的區間內，觀察值越多，信息越多。比如，y等於2到5這個範圍內有100個y的觀察值，必然比只有10個觀察值能產生更好的估計。現在假設，同樣是100個觀察值，但每個觀察值對應的x變數從一維變成二維的，這其實等價於y的分布區域也從分散在平面變成一個立方體了，所以雖然還是100個觀察值，但每個y之間的距離比原來y在平面上的距離變大了，這對於我們的估計來說是一件壞事，因為現在每個y之間有更多不確定性。這就是curse of dimension。不是所有多元變數的模型都有這個問題，因為有的模型可以避開這個問題。比如你只關心某個特定x的係數，你可以把其它的多元x變數轉換成一個一元變數，這樣就把本來是大於二元的空間變成了二元空間，y之間的距離相對來說變短了。即便再增加多餘的x變數，轉換之後的y之間還是不變的。