討論維數(shù)災(zāi)難問(wèn)題并且了解在高維空間的數(shù)據(jù)

很多機(jī)器學(xué)習(xí)的問(wèn)題都會(huì)涉及到有著幾千甚至數(shù)百萬(wàn)維的特征的訓(xùn)練實(shí)例。這不僅讓訓(xùn)練過(guò)程變得非常緩慢，同時(shí)還很難找到一個(gè)很好的解，我們接下來(lái)就會(huì)遇到這種情況。這種問(wèn)題通常被稱為維數(shù)災(zāi)難（curse of dimentionality）。

幸運(yùn)的是，在現(xiàn)實(shí)生活中我們經(jīng)?？梢詷O大的降低特征維度，將一個(gè)十分棘手的問(wèn)題轉(zhuǎn)變成一個(gè)可以較為容易解決的問(wèn)題。例如，對(duì)于 MNIST 圖片集（第 3 章中提到）：圖片四周邊緣部分的像素幾乎總是白的，因此你完全可以將這些像素從你的訓(xùn)練集中扔掉而不會(huì)丟失太多信息。圖 7-6 向我們證實(shí)了這些像素的確對(duì)我們的分類任務(wù)是完全不重要的。同時(shí)，兩個(gè)相鄰的像素往往是高度相關(guān)的：如果你想要將他們合并成一個(gè)像素（比如取這兩個(gè)像素點(diǎn)的平均值）你并不會(huì)丟失很多信息。

警告：降維肯定會(huì)丟失一些信息（這就好比將一個(gè)圖片壓縮成 JPEG 的格式會(huì)降低圖像的質(zhì)量），因此即使這種方法可以加快訓(xùn)練的速度，同時(shí)也會(huì)讓你的系統(tǒng)表現(xiàn)的稍微差一點(diǎn)。降維會(huì)讓你的工作流水線更復(fù)雜因而更難維護(hù)。所有你應(yīng)該先嘗試使用原始的數(shù)據(jù)來(lái)訓(xùn)練，如果訓(xùn)練速度太慢的話再考慮使用降維。在某些情況下，降低訓(xùn)練集數(shù)據(jù)的維度可能會(huì)篩選掉一些噪音和不必要的細(xì)節(jié)，這可能會(huì)讓你的結(jié)果比降維之前更好（這種情況通常不會(huì)發(fā)生；它只會(huì)加快你訓(xùn)練的速度）。

降維除了可以加快訓(xùn)練速度外，在數(shù)據(jù)可視化方面（或者 DataViz）也十分有用。降低特征維度到 2（或者 3）維從而可以在圖中畫出一個(gè)高維度的訓(xùn)練集，讓我們可以通過(guò)視覺(jué)直觀的發(fā)現(xiàn)一些非常重要的信息，比如聚類。

在這一章里，我們將會(huì)討論維數(shù)災(zāi)難問(wèn)題并且了解在高維空間的數(shù)據(jù)。然后，我們將會(huì)展示兩種主要的降維方法：投影（projection）和流形學(xué)習(xí)（Manifold Learning），同時(shí)我們還會(huì)介紹三種流行的降維技術(shù)：主成分分析（PCA），核主成分分析（Kernel PCA）和局部線性嵌入（LLE）。

維數(shù)災(zāi)難

我們已經(jīng)習(xí)慣生活在一個(gè)三維的世界里，以至于當(dāng)我們嘗試想象更高維的空間時(shí)，我們的直覺(jué)不管用了。即使是一個(gè)基本的 4D 超正方體也很難在我們的腦中想象出來(lái)（見(jiàn)圖 8-1），更不用說(shuō)一個(gè) 200 維的橢球彎曲在一個(gè) 1000 維的空間里了。

圖 8-1 點(diǎn)，線，方形，立方體和超正方體（0D 到 4D 超正方體）

這表明很多物體在高維空間表現(xiàn)的十分不同。比如，如果你在一個(gè)正方形單元中隨機(jī)取一個(gè)點(diǎn)（一個(gè)1×1的正方形），那么隨機(jī)選的點(diǎn)離所有邊界大于 0.001（靠近中間位置）的概率為 0.4%（1 - 0.998^2）（換句話說(shuō)，一個(gè)隨機(jī)產(chǎn)生的點(diǎn)不大可能嚴(yán)格落在某一個(gè)維度上。但是在一個(gè) 1,0000 維的單位超正方體（一個(gè)1×1×...×1的立方體，有 10,000 個(gè) 1），這種可能性超過(guò)了 99.999999%。在高維超正方體中，大多數(shù)點(diǎn)都分布在邊界處。

還有一個(gè)更麻煩的區(qū)別：如果你在一個(gè)平方單位中隨機(jī)選取兩個(gè)點(diǎn)，那么這兩個(gè)點(diǎn)之間的距離平均約為 0.52。如果您在單位 3D 立方體中選取兩個(gè)隨機(jī)點(diǎn)，平均距離將大致為 0.66。但是，在一個(gè) 1,000,000 維超立方體中隨機(jī)抽取兩點(diǎn)呢？那么，平均距離，信不信由你，大概為 408.25（大致）！這非常違反直覺(jué)：當(dāng)它們都位于同一單元超立方體內(nèi)時(shí)，兩點(diǎn)是怎么距離這么遠(yuǎn)的？這一事實(shí)意味著高維數(shù)據(jù)集有很大風(fēng)險(xiǎn)分布的非常稀疏：大多數(shù)訓(xùn)練實(shí)例可能彼此遠(yuǎn)離。當(dāng)然，這也意味著一個(gè)新實(shí)例可能遠(yuǎn)離任何訓(xùn)練實(shí)例，這使得預(yù)測(cè)的可靠性遠(yuǎn)低于我們處理較低維度數(shù)據(jù)的預(yù)測(cè)，因?yàn)樗鼈儗⒒诟蟮耐茰y(cè)（extrapolations）。簡(jiǎn)而言之，訓(xùn)練集的維度越高，過(guò)擬合的風(fēng)險(xiǎn)就越大。

理論上來(lái)說(shuō)，維數(shù)爆炸的一個(gè)解決方案是增加訓(xùn)練集的大小從而達(dá)到擁有足夠密度的訓(xùn)練集。不幸的是，在實(shí)踐中，達(dá)到給定密度所需的訓(xùn)練實(shí)例的數(shù)量隨著維度的數(shù)量呈指數(shù)增長(zhǎng)。如果只有 100 個(gè)特征（比 MNIST 問(wèn)題要少得多）并且假設(shè)它們均勻分布在所有維度上，那么如果想要各個(gè)臨近的訓(xùn)練實(shí)例之間的距離在 0.1 以內(nèi)，您需要比宇宙中的原子還要多的訓(xùn)練實(shí)例。

降維的主要方法

在我們深入研究具體的降維算法之前，我們來(lái)看看降低維度的兩種主要方法：投影和流形學(xué)習(xí)。

投影（Projection）

在大多數(shù)現(xiàn)實(shí)生活的問(wèn)題中，訓(xùn)練實(shí)例并不是在所有維度上均勻分布的。許多特征幾乎是常數(shù)，而其他特征則高度相關(guān)（如前面討論的 MNIST）。結(jié)果，所有訓(xùn)練實(shí)例實(shí)際上位于（或接近）高維空間的低維子空間內(nèi)。這聽(tīng)起來(lái)有些抽象，所以我們不妨來(lái)看一個(gè)例子。在圖 8-2 中，您可以看到由圓圈表示的 3D 數(shù)據(jù)集。

圖 8-2 一個(gè)分布接近于2D子空間的3D數(shù)據(jù)集

注意到所有訓(xùn)練實(shí)例的分布都貼近一個(gè)平面：這是高維（3D）空間的較低維（2D）子空間?，F(xiàn)在，如果我們將每個(gè)訓(xùn)練實(shí)例垂直投影到這個(gè)子空間上（就像將短線連接到平面的點(diǎn)所表示的那樣），我們就可以得到如圖8-3所示的新2D數(shù)據(jù)集。鐺鐺鐺！我們剛剛將數(shù)據(jù)集的維度從 3D 降低到了 2D。請(qǐng)注意，坐標(biāo)軸對(duì)應(yīng)于新的特征z1和z2（平面上投影的坐標(biāo)）。

圖 8-3 一個(gè)經(jīng)過(guò)投影后的新的 2D 數(shù)據(jù)集

但是，投影并不總是降維的最佳方法。在很多情況下，子空間可能會(huì)扭曲和轉(zhuǎn)動(dòng)，比如圖 8-4 所示的著名瑞士滾動(dòng)玩具數(shù)據(jù)集。

圖 8-4 瑞士滾動(dòng)數(shù)玩具數(shù)據(jù)集

簡(jiǎn)單地將數(shù)據(jù)集投射到一個(gè)平面上（例如，直接丟棄x3）會(huì)將瑞士卷的不同層疊在一起，如圖 8-5 左側(cè)所示。但是，你真正想要的是展開瑞士卷所獲取到的類似圖 8-5 右側(cè)的 2D 數(shù)據(jù)集。

圖 8-5 投射到平面的壓縮（左）vs 展開瑞士卷（右）

流形學(xué)習(xí)

瑞士卷一個(gè)是二維流形的例子。簡(jiǎn)而言之，二維流形是一種二維形狀，它可以在更高維空間中彎曲或扭曲。更一般地，一個(gè)d維流形是類似于d維超平面的n維空間（其中d < n）的一部分。在我們?nèi)鹗烤磉@個(gè)例子中，d = 2，n = 3：它有些像 2D 平面，但是它實(shí)際上是在第三維中卷曲。

許多降維算法通過(guò)對(duì)訓(xùn)練實(shí)例所在的流形進(jìn)行建模從而達(dá)到降維目的；這叫做流形學(xué)習(xí)。它依賴于流形猜想（manifold assumption），也被稱為流形假設(shè)（manifold hypothesis），它認(rèn)為大多數(shù)現(xiàn)實(shí)世界的高維數(shù)據(jù)集大都靠近一個(gè)更低維的流形。這種假設(shè)經(jīng)常在實(shí)踐中被證實(shí)。

讓我們?cè)倩氐?MNIST 數(shù)據(jù)集：所有手寫數(shù)字圖像都有一些相似之處。它們由連線組成，邊界是白色的，大多是在圖片中中間的，等等。如果你隨機(jī)生成圖像，只有一小部分看起來(lái)像手寫數(shù)字。換句話說(shuō)，如果您嘗試創(chuàng)建數(shù)字圖像，那么您的自由度遠(yuǎn)低于您生成任何隨便一個(gè)圖像時(shí)的自由度。這些約束往往會(huì)將數(shù)據(jù)集壓縮到較低維流形中。

流形假設(shè)通常包含著另一個(gè)隱含的假設(shè)：你現(xiàn)在的手上的工作（例如分類或回歸）如果在流形的較低維空間中表示，那么它們會(huì)變得更簡(jiǎn)單。例如，在圖 8-6 的第一行中，瑞士卷被分為兩類：在三維空間中（圖左上），分類邊界會(huì)相當(dāng)復(fù)雜，但在二維展開的流形空間中（圖右上），分類邊界是一條簡(jiǎn)單的直線。

但是，這個(gè)假設(shè)并不總是成立。例如，在圖 8-6 的最下面一行，決策邊界位于x1 = 5（圖左下）。這個(gè)決策邊界在原始三維空間（一個(gè)垂直平面）看起來(lái)非常簡(jiǎn)單，但在展開的流形中卻變得更復(fù)雜了（四個(gè)獨(dú)立線段的集合）（圖右下）。

簡(jiǎn)而言之，如果在訓(xùn)練模型之前降低訓(xùn)練集的維數(shù)，那訓(xùn)練速度肯定會(huì)加快，但并不總是會(huì)得出更好的訓(xùn)練效果；這一切都取決于數(shù)據(jù)集。

希望你現(xiàn)在對(duì)于維數(shù)爆炸以及降維算法如何解決這個(gè)問(wèn)題有了一定的理解，特別是對(duì)流形假設(shè)提出的內(nèi)容。本章的其余部分將介紹一些最流行的降維算法。

圖 8-6 決策邊界并不總是會(huì)在低維空間中變的簡(jiǎn)單