轉載自：http://www.cvchina.info/2010/05/31/manifold-learning/#more-1038
有時候經常會在 paper 裡看到“嵌入在高維空間中的低維流形”，不過高維的資料對于我們這些可憐的低維生物來說總是很難以想像，是以最直覺的例子通常都會是嵌入在三維空間中的二維或者一維流行。比如說一塊布，可以把它看成一個二維平面，這是一個二維的歐氏空間，現在我們（在三維）中把它扭一扭，它就變成了一個流形（當然，不扭的時候，它也是一個流形，歐氏空間是流形的一種特殊情況）。
是以，直覺上來講，一個流形好比是一個 d 維的空間，在一個 m 維的空間中 (m > d) 被扭曲之後的結果。需要注意的是，流形并不是一個“形狀”，而是一個“空間”，如果你覺得“扭曲的空間”難以想象，那麼請再回憶之前一塊布的例子。如果我沒弄錯的話，廣義相對論似乎就是把我們的時空當作一個四維流（空間三維加上時間一維）形來研究的，引力就是這個流形扭曲的結果。當然，這些都是直覺上的概念，其實流形并不需要依靠嵌入在一個“外圍空間”而存在，稍微正式一點來說，一個 d 維的流形就是一個在任意點出局部同胚于（簡單地說，就是正逆映射都是光滑的一一映射）歐氏空間
。實際上，正是這種局部與歐氏空間的同胚給我們帶來了很多好處，這使得我們在日常生活中許許多多的幾何問題都可以使用簡單的歐氏幾何來解決，因為和地球的尺度比起來，我們的日常生活就算是一個很小的局部啦——我突然想起《七龍珠》裡的那個界王住的那種私人小星球，走幾步就要繞一圈的感覺，看來界王不僅要體力好（那上面重力似乎是地球的十倍），而且腦力也要好，國中學的必須是黎曼幾何了！
那麼，除了地球這種簡單的例子，實際應用中的資料，怎麼知道它是不是一個流形呢？于是不妨又回歸直覺的感覺。再從球面說起，如果我們事先不知道球面的存在，那麼球面上的點，其實就是三維歐氏空間上的點，可以用一個三元組來表示其坐标。但是和空間中的普通點不一樣的是，它們允許出現的位置受到了一定的限制，具體到球面，可以可以看一下它的參數方程：
可以看到，這些三維的坐标實際上是由兩個變量
和
生成的，也可以說成是它的自由度是二，也正好對應了它是一個二維的流形。有了這樣的感覺之後，再來看流形學習裡經常用到的人臉的例子，就很自然了。下圖是 Isomap 論文裡的一個結果：
這裡的圖檔來自同一張人臉（好吧，其實是人臉模型），每張圖檔是 64×64 的灰階圖，如果把位圖按照列（或行）拼起來，就可以得到一個 4096 維的向量，這樣一來，每一張圖檔就可以看成是 4096 維歐氏空間中的一個點。很顯然，并不是 4096 維空間中任意一個點都可以對應于一張人臉圖檔的，這就類似于球面的情形，我們可以假定所有可以是人臉的 4096 維向量實際上分布在一個 d 維 (d < 4096) 的子空間中。而特定到 Isomap 的人臉這個例子，實際上我們知道所有的 698 張圖檔是拍自同一個人臉（模型），不過是在不同的 pose 和光照下拍攝的，如果把 pose （上下和左右）當作兩個自由度，而光照當作一個自由度，那麼這些圖檔實際隻有三個自由度，換句話說，存在一個類似于球面一樣的參數方程（當然，解析式是沒法寫出來的），給定一組參數（也就是上下、左右的 pose 和光照這三個值），就可以生成出對應的 4096 維的坐标來。換句話說，這是一個嵌入在 4096 維歐氏空間中的一個 3 維流形。
實際上，上面的那張圖就是 Isomap 将這個資料集從 4096 維映射到 3 維空間中，并顯示了其中 2 維的結果，圖中的小點就是每個人臉在這個二維空間中對應的坐标位置，其中一些标紅圈的點被選出來，并在旁邊畫上了該點對應的原始圖檔，可以很直覺地看出這兩個次元正好對應了 pose 的兩個自由度平滑變化的結果。
就我目前所知，把流形引入到機器學習領域來主要有兩種用途：一是将原來在歐氏空間中适用的算法加以改造，使得它工作在流形上，直接或間接地對流形的結構和性質加以利用；二是直接分析流形的結構，并試圖将其映射到一個歐氏空間中，再在得到的結果上運用以前适用于歐氏空間的算法來進行學習。
這裡 Isomap 正巧是一個非常典型的例子，因為它實際上是通過“改造一種原本适用于歐氏空間的算法”，達到了“将流形映射到一個歐氏空間”的目的。
Isomap 所改造的這個方法叫做 Multidimensional Scaling (MDS) ，MDS 是一種降維方法，它的目的就是使得降維之後的點兩兩之間的距離盡量不變（也就是和在原是空間中對應的兩個點之間的距離要差不多）。隻是 MDS 是針對歐氏空間設計的，對于距離的計算也是使用歐氏距離來完成的。如果資料分布在一個流形上的話，歐氏距離就不适用了。
讓我們再回到地球——這個在三維空間中的二維流形，假設我們要在三維空間中計算北極點和南極點的距離，這很容易，就是兩點相連的線段的長度，可是，如果要在這個流形上算距離就不能這樣子算了，我們總不能從北極打個洞鑽到南極去吧？要沿着地球表面走才行，當然，如果我随便沿着什麼路線走一遍，然後數出總共走了多少步作為距離，這是不成的，因為這樣一來如果我沿着不同的路線走，豈不是會得到不同的距離值？總而言之，我們現在需要一個新的定義在地球表面（流形）上的距離度量，理論上來說，任意滿足測度的 4 個條件的函數都可以被定義為距離，不過，為了和歐氏空間對應起來，這裡選擇一個直線距離的推廣定義。
還記得國中學的“兩點之間，線段最短”嗎？現在，我們反過來說，把線段的概念推廣一下，變成“兩點之間最短的曲線是線段”，于是流形上的距離定義也就等同于歐氏空間了：流形上兩個點之間的距離就是連接配接兩個點的“線段”的長度。雖然隻是置換了一個概念，但是現在兩者統一起來了，不過，在流形上的線段大概就不一定是“直”的了（于是直線也變成不一定是“直”的了），通常又稱作是“測地線”。對于球面這個簡單的流形來說，任意一條線段必定是在一個“大圓”上的，于是球面上的直線其實都是一些大圓，也造成了球面這個流形上沒有平行線等一系列尴尬的局面（任意兩條直線均相交），如果你看過一些數學科普八卦類的書，應該會回憶起不少東西啦！
回到 Isomap ，它主要做了一件事情，就是把 MDS 中原始空間中距離的計算從歐氏距離換為了流形上的測地距離。當然，如果流形的結構事先不知道的話，這個距離是沒法算的，于是 Isomap 通過講資料點連接配接起來構成一個鄰接 Graph 來離散地近似原來的流形，而測地距離也相應地通過 Graph 上的最短路徑來近似了。如下圖所示：
這個東西叫做 Swiss Roll ，姑且把它看作一塊卷起來的布好了。圖中兩個标黑圈的點，如果通過外圍歐氏空間中的歐氏距離來計算的話，會是挨得很近的點，可是在流形上它們實際上是距離很遠的點：紅色的線是 Isomap 求出來的流形上的距離。可以想像，如果是原始的 MDS 的話，降維之後肯定會是很暴力地直接把它投影到二維空間中，完全無視流形結構，而 Isomap 則可以成功地将流形“展開”之後再做投影。
除了 Isomap 之外，Manifold Embedding 的算法還有很多很多，包括 Locally Linear Embedding 、Laplacian Eigenmaps 、Hessian Eigenmaps 、Local Tangent Space Alignment、Semidefinite Embedding (Maximum Variance Unfolding) 等等等等。哪個好哪個壞也不好說，它們都各有特點，而且也各自有不少變種。網上有一個 Matlab 的 demo ，給出了幾種流行的 manifold embedding 算法在一些 synthetic manifold 上的結果和對比，可以有一個直覺的認識。
另一方面是改造現有算法使其适合流形結構甚至專門針對流形的特點來設計新的算法，比較典型的是 graph regularized semi-supervised learning 。簡單地說，在 supervised learning 中，我們隻能利用有 label 的資料，而（通常都會有很多的）沒有 label 的資料則白白浪費掉。在流形假設下，雖然這些資料沒有 label ，但是仍然是可以有助于 Learn 出流形的結構的，而學出了流形結構之後實際上我們就是對原來的問題又多了一些認識，于是理所當然地期望能得到更好的結果喽。
當然，所有的這些都是基于同一個假設，那就是資料是分布在一個流形上的（部分算法可能會有稍微寬松一些的假設），然而 real world 的資料，究竟哪些是分别在流形上的呢？這個卻是很難說。不過，除了典型的 face 和 hand written digit 之外，大家也有把基于流形的算法直接用在諸如 text 看起來好像也流形沒有什麼關系的資料上，效果似乎也還不錯。