求簡要介紹一下流形學習的基本思想?

一直聽說有這麼一個領域,求科普!


流形學習(manifold learning)是機器學習、模式識別中的一種方法,在維數約簡方面具有廣泛的應用。它的主要思想是將高維的數據映射到低維,使該低維的數據能夠反映原高維數據的某些本質結構特徵。流形學習的前提是有一種假設,即某些高維數據,實際是一種低維的流形結構嵌入在高維空間中。流形學習的目的是將其映射回低維空間中,揭示其本質。

以下圖為例[1],左邊是一個三維數據的分布,右邊是降低到二維後的結果。我們可以發現二維的數據更能直觀地表示其流形結構。

通過流形學習來實現降維的方法有很多,其基本思想也類似:假設數據在高維具有某種結構特徵,希望降到低維後,仍能保持該結構。

比較常見的有
1. 局部改線嵌入(Local Linear Embedding, LLE)[1]
假設數據中每個點可以由其近鄰的幾個點重構出來。降到低維,使樣本仍能保持原來的重構關係,且重構係數也一樣。

2. 拉普拉斯特徵映射(Laplacian Eigenmaps, LE)[2]
將數據映射到低維,且保持點之間的(相似度)距離關係。即在原空間中相距較遠的點,投影到低維空間中,希望它們之間仍相距較遠。反之亦然。

3. 局部保持投影(LPP)[3]

4. 等距映射(Isomap)[4]

等等。。。

浙江大學何曉飛老師有個關於流形學習的報告,有興趣可以看下。
http://www.cad.zju.edu.cn/reports/%C1%F7%D0%CE%D1%A7%CF%B0.pdf

[1] Roweis, Sam T and Saul, Lawrence K. Nonlinear dimensionality reduction by locally linear embedding. Science, 290(5500). 2000: 2323-2326.
[2] Belkin, Mikhail and Niyogi, Partha. Laplacian eigenmaps for dimensionality reduction and data representation. Neural computation. 15(6). 2003:1373-1396.
[3] He, Xiaofei and Niyogi, Partha. Locality preserving projections. NIPS. 2003:234-241.
[4] Tenenbaum, Joshua B and De Silva, Vin and Langford, John C. A global geometric framework for nonlinear dimensionality reduction. Science, 290(5500). 2000: 2319-2323.


最高票解釋的很學術~我就說個定性而非定量的解釋。

流形學習的觀點是認為,我們所能觀察到的數據實際上是由一個低維流形映射到高維空間上的。由於數據內部特徵的限制,一些高維中的數據會產生維度上的冗餘,實際上只需要比較低的維度就能唯一地表示。

舉個例子,比如說我們在平面上有個圓,如何表示這個圓呢?如果我們把圓放在一個平面直角坐標系中,那一個圓實際上就是由一堆二維點構成的。

比如一個單位圓: (1, 0) 是一個在圓上的點, (0, 1) 也是一個在圓上的點,但 (0,0)(2,3) 等等很多點是不在這個圓上的。

顯然如果用二維坐標來表示,我們沒有辦法讓這個二維坐標系的所有點都是這個圓上的點。也就是說,用二維坐標來表示這個圓其實是有冗餘的。

我們希望,如果能建立某一種描述方法,讓這個描述方法所確定的所有點的集合都能在圓上,甚至能連續不間斷地表示圓上的點,那就好了!

有沒有這種方法呢?對於圓來說,當然有!那就是用極坐標。在極坐標的表示方法下,圓心在原點的圓,只需要一個參數就能確定:半徑。

當你連續改變半徑的大小,就能產生連續不斷的「能被轉換成二維坐標表示」的圓。所以說,實際上二維空間中的圓就是一個一維流形。

與之相似的,三維空間中一個球面,用x, y, z三個坐標軸確定時會產生冗餘(很多在三維空間中的數據點並不在球面上)。但其實只需要用兩個坐標就可以確定了,比如經度和維度。

只要給定任何合法的精度和維度,我們就都能保證這個點肯定在球面上!


那麼,流形學習有什麼用呢?我現在能想到的主要有兩個方面。

先說第一個方面。高維空間有冗餘,低維空間沒冗餘。也就是說,流形可以作為一種數據降維的方式。傳統很多降維演算法都是用歐氏距離作為評價兩個點之間的距離函數的。但是仔細想想這種歐氏距離直覺上並不靠譜。「我們只是看到了三維數據,就要用三維坐標系內的尺度去對事物進行評價?」總覺得有些怪怪的。

舉個例子,從北京到上海有多遠?你可以找一個地球儀,然後用一把能彎曲的軟軟的尺子,經過地球儀錶面然後測量一下這兩個點的距離。

但是如果我用一個直直的線,將地球儀從北京到上海洞穿,測量出一個更短的距離,你一定會覺得我瘋了。顯然對於「從北京到上海的距離」這件事,我們關注的是把三維地球展開成二維平面,然後測量的地表上的距離,而不是三維空間中球面上兩個點的空間直線距離(相信沒有人從北京到上海會挖一條直通上海的地道的!

將這個問題推廣一些,假如說決策部門打算把一些離得比較近的城市聚成一堆,然後組建個大城市。這時候「遠近」這個概念顯然是指地表上的距離,因為說空間直線距離並沒有什麼意義。

而對於降維演算法來說,如果使用傳統的歐氏距離來作為距離尺度,顯然會拋棄「數據的內部特徵」。如果測量球面兩點距離採用空間歐氏距離,那就會忽略掉「這是個球面」這個信息。

其實用一幅圖就都明白了,那就是傳說中的瑞士卷(圖轉自 淺談流形學習 quot; Free Mind ,侵刪):

如果我們觀察到的數據是三維的,但其本質是一個二維流形。圖上所標註的兩個圈圈,在流形(把卷展開)上本距離非常遠,但是用三維空間的歐氏距離來計算則它們的距離要近得多。

所以說,流形學習的一個主要應用就是「非線性降維」 (參見Wikipedia: Nonlinear dimensionality reduction)。而非線性降維因為考慮到了流形的問題,所以降維的過程中不但考慮到了距離,更考慮到了生成數據的拓撲結構。


第二個方面,流形能夠刻畫數據的本質。這方面也是深度學習一直在搞的事情。深度學習主要的特點就是「特徵學習」,所謂特徵,就是能「表示事物本質的內容」,一般來說特徵的維度應該小於數據本身。有一些實證證實,大腦處理數據其實是通過記憶、重現的方式。數據那麼多,大腦怎麼能一一記住?那就可以只記住「特徵」!例如我們直到「人」都是兩隻眼睛一個鼻子一張嘴。而具體到每一個人則是再這個基本特徵之上添加了一些其他的特異性的內容僅此而已。

深度學習一直以來就是在模仿大腦的結構,或者說在模仿大腦對數據的處理能力:從底層感受器輸入原始數據,逐步求精得到特徵。

所謂的特徵,在一定程度上就可以用流形的概念來解釋。我們希望我們的模型能夠學習到「數據在流行空間中的表示」。如果能做到這一點,則說明我們的模型離「模擬大腦」又前進了一步。

拓展一下,有一個有趣的事情:

我們如何來說明「模型學習到了流形」?前面提到了高維數據其實是由低維流形生成的。如果我們能模擬這個生成過程,再通過對低維流形的微調,應該能得到對應的「有意義且有道理」的高維數據。

下面是利用生成對抗網路(GAN)生成的人臉:

如果對GAN不了解的話,就可以把生成過程看作:輸入一個特徵空間的低維編碼,得到一個輸出空間的高維圖像。如何證明我們學習到的這個生成過程就是像人腦一樣從低維流形映射到高維空間呢?還記得我們之前說過,流行空間一般應該是連續的,而映射到的高維空間的數據也應該在流形連續調整時變得連續且有意義。

再另一篇介紹了GAN的一個擴展的DCGAN的文章中,做了這樣一件事:

尋找兩個編碼,這兩個編碼都能生成有意義的內容,將這兩個編碼插值得到好多編碼。也就是說這些編碼實際上描述了從編碼A到編碼B緩慢轉變的過程。編碼A是起點,編碼B是目標,A和B之間的連續轉變的編碼則應該讓生成的圖像處於「從A向B」的過渡過程!事實如何呢?請看下圖:

參考資料

[1] Manifold - Wikipedia
[2] Nonlinear dimensionality reduction
[3] Goodfellow I, Pouget-Abadie J, Mirza M, et al. Generative adversarial nets[C]//Advances in neural information processing systems. 2014: 2672-2680.
[4] Radford A, Metz L, Chintala S. Unsupervised representation learning with deep convolutional generative adversarial networks[J]. arXiv preprint arXiv:1511.06434, 2015.


後記

DCGAN這篇文章除了通過插值方法以外,還用了其他很多方法來驗證編碼空間是不是流型空間。我覺得這篇文章的貢獻不只在於DCGAN這個模型,而在於後面很多實驗的分析,畢竟是發在ICLR上的文章,搞的都是「特徵工程」。其中的實驗部分非常值得一看~


其實就是把數據點之間歐式距離、kernel距離等換成其他幾種距離。比如說,把數據點作為graph的頂點,把每個頂點與其最近的幾個頂點連起來,再算一個all pair shortest path,用來作為兩點之間的距離。

有了數據點兩兩之間距離,做分類、聚類、降維都可以,跟一般的kernel方法沒什麼區別。

想法很巧妙,但是跟數學裡的manifold沒什麼關係。


流形學習中一個大的假設就是極高維的空間中數據實際上都分布在一個潛在的流形上。有人測定MNIST數據分布在一個6維的流形上,而且你從不同角度拍的不管多大像素的關於某一個物體的照片,潛在流形的維度和運動自由度一樣。我們通過各種演算法,或線性或者非線性來恢復這個流形,達到降維的目的。一般情況下,現在的演算法對非凸的流形面(有空洞),以及雜訊環境下的數據魯棒性都不是很理想。

流形學習可以說是用來理解機器學習(尤其是表徵學習)的另一個工具,當然最大的一個工具是貝葉斯理論,在這個框架下大部分機器學習演算法甚至是機器學習理論都可以說得通。

絕大多數的流行學習演算法都可以統一到S-K-PCA框架下(我記得是統一到KPCA框架下,but KPCA也是SKPCA的最特殊的一種情況啊),也就是說,PCA,ISOmap,LLE,LE,SC,SDE等等等等都是在尋找一個恰當的kernel來度量data points間的距離(相似度)。當然這個kernel並不一定是像PCA,KPCA中的一樣closed form的,有可能是geodesic distance構造的,即通過最開始構造一個連接圖得到的,最後都會轉化成為一個最大最小化Trace的問題,solution自然是最大的幾個特徵值了,或者最小的幾個特徵值對應的特徵向量(一般這種情況下我們都構造了一個圖的Laplacian,最小的特徵值肯定是0,必須忽略這個特徵向量)。當然Isomap等等作者並不想看到他們的作品被規划到一個幾個世紀前的演算法框架裡面去,所以他們也會說我不是我不是。一個隱層的 linear AE其實是和PCA 張成了同一個空間的,這也就是說,自動編碼機也可以劃分到流形學習的框架中去。AE很少用來預訓練了,一般都是用來降維以及採樣P(x|z)了。

當然,Manifold Learning中也有奇葩,比如SNE。根本就不適合套用Generalized Eigenvalue Problem求解,而是用GD來最小化某個KL散度。他的假設以及初衷已經不僅僅是恢復一個流形了,他的數據鄰域從娘胎里就是圓形的,也就是說它的輸出也就不大可能恢復原有的流形了,都是一團一團的,一簇一簇的,尤其是TSNE,在例如瑞士卷上表現特別差。SNE不僅僅用來可視化原數據,甚至用來可視化高維流形。他已經不再是一個流形演算法了


地圖學的各種投影,將球展現在面上,也是一種3維到2維的變換映射方法。流行主要是一種非線性降維方法,3維到2維就可以簡單理解為把一塊捲曲的布,鋪開放平的過程,這個過程要保留原來高維空間中的拓撲關係。更高維可參照這個思路。


推薦閱讀:

複雜系統領域的經典書籍有哪些?
我們離電影《終結者》中的人形機器人還有多遠?
生物或者人腦神經元是有專門分工還是完全是通用的,也就是每個神經元可以做任何一件事情?
人臉識別如何自學?

TAG:人工智慧 | 機器學習 | 流形學習 |