有關(guān)流形學(xué)習(xí)論文
流形學(xué)習(xí)
流形學(xué)習(xí)是個(gè)很廣泛的概念。這里我主要談的是自從2000年以后形成的流形學(xué)習(xí)概念和其主要代表方法。自從2000年以后，流形學(xué)習(xí)被認(rèn)為屬于非線性降維的一個(gè)分支。眾所周知，引導(dǎo)這一領(lǐng)域迅速發(fā)展的是2000年Science雜志上的兩篇文章: Isomap and LLE (Locally Linear Embedding)。
1. 流形學(xué)習(xí)的基本概念
那流形學(xué)習(xí)是什莫呢？為了好懂，我盡可能應(yīng)用少的數(shù)學(xué)概念來解釋這個(gè)東西。所謂流形（manifold）就是一般的幾何對(duì)象的總稱。比如人，有中國人、美國人等等；流形就包括各種維數(shù)的曲線曲面等。和一般的降維分析一樣，流形學(xué)習(xí)把一組在高維空間中的數(shù)據(jù)在低維空間中重新表示。和以往方法不同的是，在流形學(xué)習(xí)中有一個(gè)假設(shè)，就是所處理的數(shù)據(jù)采樣于一個(gè)潛在的流形上，或是說對(duì)于這組數(shù)據(jù)存在一個(gè)潛在的流形。 對(duì)于不同的方法，對(duì)于流形性質(zhì)的要求各不相同，這也就產(chǎn)生了在流形假設(shè)下的各種不同性質(zhì)的假設(shè)，比如在Laplacian
Eigenmaps中要假設(shè)這個(gè)流形是緊致黎曼流形等。對(duì)于描述流形上的點(diǎn)，我們要用坐標(biāo)，而流形上本身是沒有坐標(biāo)的，所以為了表示流形上的點(diǎn)，必須把流形放入外圍空間（ambient space）中，那末流形上的點(diǎn)就可以用外圍空間的坐標(biāo)來表示。比如R^3中的球面是個(gè)2維的曲面，因?yàn)榍蛎嫔现挥袃蓚�(gè)自由度，但是球面上的點(diǎn)一般是用外圍R^3空間中的坐標(biāo)表示的，所以我們看到的R^3中球面上的點(diǎn)有3個(gè)數(shù)來表示的。當(dāng)然球面還有柱坐標(biāo)球坐標(biāo)等表示。對(duì)于R^3中的球面來說，那末流形學(xué)習(xí)可以粗略的概括為給出R^3中的表示，在保持球面上點(diǎn)某些幾何性質(zhì)的條件下，找出找到一組對(duì)應(yīng)的內(nèi)蘊(yùn)坐標(biāo)（intrinsic coordinate）表示，顯然這個(gè)表示應(yīng)該是兩維的，因?yàn)榍蛎娴木S數(shù)是兩維的。這個(gè)過程也叫參數(shù)化（parameterization）。直觀上來說，就是把這個(gè)球面盡量好的展開在通過原點(diǎn)的平面上。在PAMI中，這樣的低維表示也叫內(nèi)蘊(yùn)特征（intrinsic feature）。一般外圍空間的維數(shù)也叫觀察維數(shù)，其表示也叫自然坐標(biāo)（外圍空間是歐式空間）表示,在統(tǒng)計(jì)中一般叫observation。
了解了流形學(xué)習(xí)的這個(gè)基礎(chǔ)，那末流形學(xué)習(xí)中的一些是非也就很自然了，這個(gè)下面穿插來說。由此，如果你想學(xué)好流形學(xué)習(xí)里的方法，你至少要了解一些微分流形和黎曼幾何的基本知識(shí)。
2. 代表方法
a) Isomap。
Josh Tenenbaum的Isomap開創(chuàng)了一個(gè)數(shù)據(jù)處理的新戰(zhàn)場。在沒有具體說Isomap之前，有必要先說說MDS（Multidimensional Scaling）這個(gè)方法。我們國內(nèi)的很多人知道PCA，卻很多人不知道MDS。PCA和MDS是相互對(duì)偶的兩個(gè)方法。MDS就是理論上保持歐式距離的一個(gè)經(jīng)典方法，MDS最早主要用于做數(shù)據(jù)的可視化。由于MDS得到的低維表示中心在原點(diǎn)，所以又可以說保持內(nèi)積。也就是說，用低維空間中的內(nèi)積近似高維空間中的距離。經(jīng)典的MDS方法，高維空間中的距離一般用歐式距離。
Isomap就是借窩生蛋。他的理論框架就是MDS，但是放在流形的理論框架內(nèi)，原始的距離換成了流形上的測地線（geodesic）距離。其它一模一樣。所謂的測地線，就是流形上加速度為零的曲線，等同于歐式空間中的直線。我們經(jīng)常聽到說測地線是流形上兩點(diǎn)之間距離最短的線。其實(shí)這末說是不嚴(yán)謹(jǐn)?shù)�。流形上兩點(diǎn)之間距離最短的線是測地線，但是反過來不一定對(duì)。另外，如果任意兩個(gè)點(diǎn)之間都存在一個(gè)測地線，那末這個(gè)流形必須是連通的鄰域都是凸的。Isomap就是把任意兩點(diǎn)的測地線距離（準(zhǔn)確地說是最短距離）作為流形的幾何描述，用MDS理論框架
理論上保持這個(gè)點(diǎn)與點(diǎn)之間的最短距離。在Isomap中，測地線距離就是用兩點(diǎn)之間圖上的最短距離來近似的，這方面的算法是一般計(jì)算機(jī)系中用的圖論中的經(jīng)典算法。
如果你曾細(xì)致地看過Isomap主頁上的matlab代碼，你就會(huì)發(fā)現(xiàn)那個(gè)代碼的實(shí)現(xiàn)復(fù)雜度遠(yuǎn)超與實(shí)際論文中敘述的算法。在那個(gè)代碼中，除了論文中寫出的算法外，還包括了 outlier detection和embedding scaling。這兩樣?xùn)|西，保證了運(yùn)行他們的程序得到了結(jié)果一般來說相對(duì)比較理想。但是，這在他們的算法中并沒有敘述。如果你直接按照他論文中的方法來實(shí)現(xiàn)，你可以體會(huì)一下這個(gè)結(jié)果和他們結(jié)果的差距。從此我們也可以看出，那幾個(gè)作者做學(xué)問的嚴(yán)謹(jǐn)態(tài)度，這是值得我們好好學(xué)習(xí)的。
另外比較有趣的是，Tenenbaum根本不是做與數(shù)據(jù)處理有關(guān)算法的人，他是做計(jì)算認(rèn)知科學(xué)（computational cognition science）的。在做這個(gè)方法的時(shí)候，他還在stanford，02年就去了
MIT開創(chuàng)一派，成了CoCoSci 的掌門人，他的組成長十分迅速。但是有趣的是，在Isomap之后，他包括他在MIT帶的學(xué)生就從來再也沒有做過類似的工作。其原因我今年夏天有所耳聞。他在今年參加 UCLA Alan Yuille 組織的一個(gè)summer school上說，（不是原文，是大意）我們經(jīng)常忘了做研究的原始出發(fā)點(diǎn)是什莫。他做Isomap就是為了找一個(gè)好的visual perception的方法，他還堅(jiān)持了他的方向和信仰，computational cognition，他沒有隨波逐流。而由他引導(dǎo)起來的 manifold learning 卻快速的發(fā)展成了一個(gè)新的方向。
這是一個(gè)值得我們好好思考的問題。我們做一個(gè)東西，選擇一個(gè)研究方向究竟是為了什莫。你考慮過嗎？
�。ó�(dāng)然，此問題也在問我自己）
b) LLE (Locally linear Embedding)
LLE在作者寫出的表達(dá)式看,是個(gè)具有十分對(duì)稱美的方法. 這種看上去的對(duì)稱對(duì)于啟發(fā)人很重要。LLE的思想就是，一個(gè)流形在很小的局部鄰域上可以近似看成歐式的，就是局部線性的。那末，在小的局部鄰域上，一個(gè)點(diǎn)就可以用它周圍的點(diǎn)在最小二乘意義下最優(yōu)的線性表示。LLE把這個(gè)線性擬合的系數(shù)當(dāng)成這個(gè)流形局部幾何性質(zhì)的刻畫。那末一個(gè)好的低維表示，就應(yīng)該也具有同樣的局部幾何，所以利用同樣的線性表示的表達(dá)式，最終寫成一個(gè)二次型的形式，十分自然優(yōu)美。
注意在LLE出現(xiàn)的兩個(gè)加和優(yōu)化的線性表達(dá)，第一個(gè)是求每一點(diǎn)的線性表示系數(shù)的。雖然原始公式中是寫在一起的，但是求解時(shí)，是對(duì)每一個(gè)點(diǎn)分別來求得。第二個(gè)表示式，是已知所有點(diǎn)的線性表示系數(shù)，來求低維表示（或嵌入embedding）的，他是一個(gè)整體求解的過程。這兩個(gè)表達(dá)式的轉(zhuǎn)化正好中間轉(zhuǎn)了個(gè)彎，使一些人困惑了，特別后面一個(gè)公式寫成一個(gè)二次型的過程并不是那末直觀，很多人往往在此卡住，而阻礙了全面的理解。我推薦大家去精讀 Saul 在
JMLR上的那篇LLE的長文。那篇文章無論在方法表達(dá)還是英文書寫，我認(rèn)為都是精品，值得好好玩味學(xué)習(xí)。
另外值得強(qiáng)調(diào)的是，對(duì)于每一點(diǎn)處擬合得到的系數(shù)歸一化的操作特別重要，如果沒有這一步，這個(gè)算法就沒有效果。但是在原始論文中，他們是為了保持?jǐn)?shù)據(jù)在平行移動(dòng)下embedding不變。 LLE的matlab代碼寫得簡潔明了，是一個(gè)樣板。
在此有必要提提Lawrence Saul這個(gè)人。在Isomap和LLE的作者們中，Saul算是唯一一個(gè)以流形學(xué)習(xí)（并不限于）為研究對(duì)象開創(chuàng)學(xué)派的人。Saul早年主要做參數(shù)模型有關(guān)的算法。自從LLE以后，坐陣UPen創(chuàng)造了一個(gè)個(gè)佳績。主要成就在于他的兩個(gè)出色學(xué)生，Kilian Weinberger和 Fei Sha，做的方法。拿了很多獎(jiǎng)，在此不多說，可以到他主頁上去看。Weinberger把學(xué)習(xí)核矩陣引入到流形學(xué)習(xí)中來。他的這個(gè)方法在流形學(xué)習(xí)中影響到不是很顯著，卻是在 convex optimization 中人人得知。Fei Sha不用多說了，machine learning中一個(gè)閃亮的新星，中國留學(xué)生之驕傲�，F(xiàn)在他們一個(gè)在Yahoo,一個(gè)在Jordan手下做PostDoc。
c) Laplacian Eigenmaps
要說哪一個(gè)方法被做的全面，那莫非LE莫屬。如果只說LE這個(gè)方法本身，是不新的，許多年前在做mesh相關(guān)的領(lǐng)域就開始這莫用。但是放在黎曼幾何的框架內(nèi)，給出完整的幾何分析的，應(yīng)該是Belkin和Niyogi（LE作者）的功勞。
LE的基本思想就是用一個(gè)無向有權(quán)圖來描述一個(gè)流形，然后通過用圖的嵌入（graph
embedding）來找低維表示。說白了，就是保持圖的局部鄰接關(guān)系的情況把這個(gè)圖從高維空間中重新畫在一個(gè)低維空間中（graph drawing）。
在至今為止的流行學(xué)習(xí)的典型方法中，LE是速度最快、效果相對(duì)來說不怎莫樣的。但是LE有一個(gè)其他方法沒有的特點(diǎn)，就是如果出現(xiàn)outlier情況下，它的魯棒性（robustness）特別好。 后來Belkin和Niyogi又分析了LE的收斂性。大家不要忽視這個(gè)問題，很重要。鼓勵(lì)有興趣數(shù)學(xué)功底不錯(cuò)的人好好看看這篇文章。
d) Hessian Eigenmaps
如果你對(duì)黎曼幾何不懂，基本上看不懂這個(gè)方法。又加作者表達(dá)的抽象，所以絕大多數(shù)人對(duì)這個(gè)方法了解不透徹。在此我就根據(jù)我自己的理解說說這個(gè)方法。
這個(gè)方法有兩個(gè)重點(diǎn)：（1）如果一個(gè)流形是局部等距（isometric）歐式空間中一個(gè)開子集的，那末它的Hessian矩陣具有d+1維的零空間。（2）在每一點(diǎn)處，Hessian系數(shù)的估計(jì)。
首先作者是通過考察局部Hessian的二次型來得出結(jié)論的，如果一個(gè)流形局部等距于歐式空間中的一個(gè)開子集，那末由這個(gè)流形patch 到開子集到的映射函數(shù)是一個(gè)線性函數(shù)，線性函數(shù)的二次混合導(dǎo)數(shù)為零，所以局部上由Hessian系數(shù)構(gòu)成的二次型也為零，這樣把每一點(diǎn)都考慮到，過渡到全局的Hessian矩陣就有d+1維的零空間，其中一維是常函數(shù)構(gòu)成的，也就是1向量。其它的d維子空間構(gòu)成等距坐標(biāo)。這就是理論基礎(chǔ)的大意，當(dāng)然作者在介紹的時(shí)候，為了保持理論嚴(yán)謹(jǐn)，作了一個(gè)由切坐標(biāo)到等距坐標(biāo)的過渡。
另外一個(gè)就是局部上Hessian系數(shù)的估計(jì)問題。我在此引用一段話：
If you approximate a function f(x) by a quadratic expansion
f(x) = f(0) + (grad f)^T x + x^T Hf x + rem
then the hessian is what you get for the quadratic component. So simply over a given neighborhood, develop the operator that approximates a function by its projection on 1, x_1,...,x_k, x_1^2,...,x_k^2, x_1*x_2,... ,x_{k-1}*x_{k}. Extract the component of the operator that delivers the projection on x_1^2,...,x_k^2, x_1*x_2,... ,x_{k-1}*x_{k}.
這段話是我在初學(xué)HE時(shí)候，寫信問Dave Donoho，他給我的回信。希望大家領(lǐng)會(huì)。如果你了解了上述基本含義，再去細(xì)看兩遍原始論文，也許會(huì)有更深的理解。由于HE牽扯到二階導(dǎo)數(shù)的估計(jì)，所以對(duì)噪聲很敏感。另外，HE的原始代碼中在計(jì)算局部切坐標(biāo)的時(shí)候，用的是奇異值分解(SVD)，所以如果想用他們的原始代碼跑一下例如圖像之類的真實(shí)數(shù)據(jù)，就特別的慢。其實(shí)把他們的代碼改一下就可以了，利用一般PCA的快速計(jì)算方法，計(jì)算小尺寸矩陣的特征向量即可。還有，在原始代碼中，他把Hessian系數(shù)歸一化了，這也就是為什莫他們叫這個(gè)方法為 Hessian LLE 的原因之一。
Dave Dohono是學(xué)術(shù)界公認(rèn)的大牛，在流形學(xué)習(xí)這一塊，是他帶著他的一個(gè)學(xué)生做的，Carrie Grimes。現(xiàn)在這個(gè)女性研究員在Google做 project leader，學(xué)術(shù)界女生同學(xué)的楷模 : )
e) LTSA (Local tangent space alignment)
很榮幸，這個(gè)是國內(nèi)學(xué)者（浙江大學(xué)數(shù)學(xué)系的老師ZHANG Zhenyue）為第一作者做的一個(gè)在流行學(xué)習(xí)中最出色的方法。由于這個(gè)方法是由純數(shù)學(xué)做數(shù)值分析出身的老師所做，所以原始論文看起來公式一大堆，好像很難似的。其實(shí)這個(gè)方法非常直觀簡單。
象 Hessian Eigenmaps 一樣，流形的局部幾何表達(dá)先用切坐標(biāo)，也就是PCA的主子空間中的坐標(biāo)。那末對(duì)于流形一點(diǎn)處的切空間，它是線性子空間，所以可以和歐式空間中的一個(gè)開子集建立同構(gòu)關(guān)系，最簡單的就是線性變換。在微分流形中，就叫做切映射 (tangential map)，是個(gè)很自然很基礎(chǔ)的概念。把切坐標(biāo)求出來，建立出切映射，剩下的就是數(shù)值計(jì)算了。最終這個(gè)算法劃歸為一個(gè)很簡單的跌代加和形式。如果你已經(jīng)明白了MDS，那末你就很容易明白，這個(gè)算法本質(zhì)上就是MDS的從局部到整體的組合。
這里主要想重點(diǎn)強(qiáng)調(diào)一下，那個(gè)論文中使用的一個(gè)從局部幾何到整體性質(zhì)過渡的alignment技術(shù)。在spectral method（特征分解的）中，這個(gè)alignment方法特別有用。只要在數(shù)據(jù)的局部鄰域上你的方法可以寫成一個(gè)二次項(xiàng)的形式，就可以用。
其實(shí)LTSA最早的版本是在02年的DOCIS上。這個(gè)alignment方法在02年底Brand的 charting a manifold 中也出現(xiàn)，隱含在Hessian Eigenmaps中。在HE中，作者在從局部的Hessian矩陣過渡到全局的Hessian矩陣時(shí)，用了兩層加號(hào)，其中就隱含了這個(gè) alignment方法。后來國內(nèi)一個(gè)叫 ZHAO Deli 的學(xué)生用這個(gè)方法重新寫了LLE，發(fā)在Pattern Recognition上，一個(gè)短文。可以預(yù)見的是，這個(gè)方法還會(huì)被發(fā)揚(yáng)光大。
ZHA Hongyuan 后來專門作了一篇文章來分析 alignment matrix 的譜性質(zhì)，有興趣地可以找來看看。
f) MVU (Maximum variance unfolding)
這個(gè)方法剛發(fā)出來以后，名字叫做Semi-definite Embedding (SDE)。構(gòu)建一個(gè)局部的稀疏歐式距離矩陣以后，作者通過一定約束條件（主要是保持距離）來學(xué)習(xí)到一個(gè)核矩陣，對(duì)這個(gè)核矩陣做PCA就得到保持距離的 embedding，就這莫簡單。但是就是這個(gè)方法得了多少獎(jiǎng)，自己可以去找找看。個(gè)人觀點(diǎn)認(rèn)為，這個(gè)方法之所以被如此受人賞識(shí)，無論在vision還是在learning，除了給流形學(xué)習(xí)這一領(lǐng)域帶來了一個(gè)新的解決問題的工具之外，還有兩個(gè)重點(diǎn)，一是核方法（kernel），二是半正定規(guī)劃（semi-definite programming），這兩股風(fēng)無論在哪個(gè)方向（learning and Vision）上都吹得正猛。
g) S-Logmaps
這個(gè)方法不太被人所知，但是我認(rèn)為這個(gè)是流形學(xué)習(xí)發(fā)展中的一個(gè)典型的方法（其實(shí)其他還有很多人也這莫認(rèn)為）。就效果來說，這個(gè)方法不算好，說它是一個(gè)典型的方法，是因?yàn)檫@個(gè)方法應(yīng)用了黎曼幾何中一個(gè)很直觀的性質(zhì)。這個(gè)性質(zhì)和法坐標(biāo)(normal coordinate)、指數(shù)映射(exponential map)和距離函數(shù)(distance function)有關(guān)。
如果你了解黎曼幾何，你會(huì)知道，對(duì)于流形上的一條測地線，如果給定初始點(diǎn)和初始點(diǎn)處測地線的切方向，那莫這個(gè)測地線就可以被唯一確定。這是因?yàn)樵谶@些初始條件下，描述測地線的偏微分方程的解是唯一的。那末流形上的一條測地線就可以和其起點(diǎn)處的切平面上的點(diǎn)建立一個(gè)對(duì)應(yīng)關(guān)系。我們可以在這個(gè)切平面上找到一點(diǎn)，這個(gè)點(diǎn)的方向就是這個(gè)測地線在起點(diǎn)處的切方向，其長度等于這個(gè)測地線上的長。這樣的一個(gè)對(duì)應(yīng)關(guān)系在局部上是一一對(duì)應(yīng)的。那末這個(gè)在切平面上的對(duì)應(yīng)點(diǎn)在切平面中就有一個(gè)坐標(biāo)表示，這個(gè)表示就叫做測地線上對(duì)應(yīng)點(diǎn)的法坐標(biāo)表示（有的也叫指數(shù)坐標(biāo)）。那末反過來，我們可以把切平面上的點(diǎn)映射到流形上，這個(gè)映射過程就叫做指數(shù)映射（Logmap就倒過來）。如果流形上每一個(gè)點(diǎn)都可以這樣在同一個(gè)切平面上表示出來，那末我們就可以得到保持測地線長度的低維表示。如果這樣做得到，流形必須可以被單坐標(biāo)系統(tǒng)所覆蓋。
如果給定流形上的采樣點(diǎn)，如果要找到法坐標(biāo)，我們需要知道兩個(gè)東西，一是測地線距離，二是每個(gè)測地線在起點(diǎn)處的切方向。第一個(gè)東西好弄，利用Isomap中的方法直接就可以解決，關(guān)鍵是第二個(gè)。第二個(gè)作者利用了距離函數(shù)的梯度，這個(gè)梯度和那個(gè)切方向是一個(gè)等價(jià)的關(guān)系，一般的黎曼幾何書中都有敘述。作者利用一個(gè)局部切坐標(biāo)的二次泰勒展開來近似距離函數(shù)，而距離是知道的，就是測地線距離，局部切坐標(biāo)也知道，那末通過求一個(gè)簡單的最小二乘問題就可以估計(jì)出梯度方向。
如果明白這個(gè)方法的幾何原理，你再去看那個(gè)方法的結(jié)果，你就會(huì)明白為什莫在距離中心點(diǎn)比較遠(yuǎn)的點(diǎn)的embedding都可以清楚地看到在一條條線上，效果不太好。
最近這個(gè)思想被北大的一個(gè)年輕的老師 LIN Tong 發(fā)揚(yáng)光大，就是ECCV‘06上的那篇，還有即將刊登出的TPAMI上的 Riemannian Manifold Learning，實(shí)為國內(nèi)研究學(xué)者之榮幸。Lin的方法效果非常好，但是雖然取名叫Riemannian，沒有應(yīng)用到黎曼幾何本身的性質(zhì)，這樣使他的方法更容易理解。
Lin也是以一個(gè)切空間為基準(zhǔn)找法坐標(biāo)，這個(gè)出發(fā)點(diǎn)和思想和Brun（S-Logmaps）的是一樣的。但是Lin全是在局部上操作的，在得出切空間原點(diǎn)處局部鄰域的法坐標(biāo)以后，Lin采用逐步向外擴(kuò)展的方法找到其他點(diǎn)的法坐標(biāo)，在某一點(diǎn)處，保持此點(diǎn)到它鄰域點(diǎn)的歐式距離和夾角，然后轉(zhuǎn)化成一個(gè)最小二乘問題求出此點(diǎn)的法坐標(biāo)，這樣未知的利用已知的逐步向外擴(kuò)展。說白了就像縫網(wǎng)一樣，從幾個(gè)臨近的已知點(diǎn)開始，逐漸向外擴(kuò)散的縫。效果好是必然的。
淺談流形學(xué)習(xí)
bypluskid, on 2010-05-29, in Machine Learning76 comments
總覺得即使是“淺談”兩個(gè)字，還是讓這個(gè)標(biāo)
題有些過大了，更何況我自己也才剛剛接觸這么一個(gè)領(lǐng)域。不過懶得想其他標(biāo)題了，想起來要扯一下這個(gè)話題，也是因?yàn)楹团笥蚜钠鹞易约鹤罱谧龅姆较�。Manifold Learning 或者僅僅 Manifold 本身通常就聽起來頗有些深?yuàn)W的感覺，不過如果并不是想要進(jìn)行嚴(yán)格的理論推導(dǎo)的話，也可以從許多直觀的例子得到一些感性的認(rèn)識(shí)，正好我也就借這個(gè)機(jī)會(huì)來簡單地談一下這個(gè)話題吧，或者說至少是我到目前為止對(duì)這它的認(rèn)識(shí)。 這兩個(gè)詞，在談 Manifold 之前，不妨先說說 Learning ，也就是 Machine Learning 。而說道 Machine Learning 而不提一下 Artificial Intelligence 的話似乎又顯得有些不厚道。人說 AI 是一門最悲劇的學(xué)科，因?yàn)槊慨?dāng)它的一個(gè)子領(lǐng)域發(fā)展得像模像樣之后，就立馬自立門戶，從此和 AI “再無瓜葛”了，而 Machine Learning 大概要算是最新的一個(gè)典型吧。這就讓人有點(diǎn)奇怪，比如說數(shù)學(xué)，分門別類總算是夠多了吧？可以不管怎么分，大家兄弟姐妹也都還承認(rèn)自己是叫“數(shù)學(xué)”的。那 AI 呢？我覺得這里有很大一部分
是它自身定位的問題。
反正現(xiàn)在我是不太清楚 AI 是做什么的，不知道其他人到底清楚不清楚。Wikipedia 上
說 Artificial intelligence (AI) is the intelligence of machines and the branch of computer
science that aims to create it.
可是這相當(dāng)于一個(gè) tautology ，因?yàn)榈降资裁从质莟he intelligence of machines呢？一開始的時(shí)候，大牛們都野心勃勃，而且好像也是信心滿滿，就好像曾經(jīng)廣泛認(rèn)為“牛頓定理揭示了宇宙真理，科學(xué)剩下的事情只要按照公式來做計(jì)算就可以了”一樣，大家可能覺得，不出幾十年，人類就可以不用思考，交給 AI 來做了。不過我這里并不想再多說諸如什么是“思考”，什么是“智能”之類的以及隨之而來的“圖靈測試”之類的話題。我想說的是，到頭來，AI 到底是什么，這還是一個(gè)問題，或者說，AI 在一開始定了一個(gè)過高的目標(biāo)，幾十年后，發(fā)現(xiàn)情況并不像當(dāng)年那么樂觀，卻又有些下不了臺(tái)了。
這個(gè)時(shí)候，AI 的一些旁枝或者子領(lǐng)域果斷放下面子，丟掉了那個(gè)近乎玄幻的目標(biāo)，逐漸發(fā)展成為“正�！钡膶W(xué)科，所以也就不再好稱為 AI 了�；蛘哒f現(xiàn)在的 AI 有兩個(gè)意思，一個(gè)廣義的 AI ，包括了所有相關(guān)的以及派生的領(lǐng)域，另一個(gè)則是狹義的或者經(jīng)典的 AI ，專門指那些仍然在執(zhí)著地追求著真正的“智能”的部分，或者說得不好聽一點(diǎn)，就
是剩下的部分。
Machine Learning 作為離家出走的典型，雖然名字里帶了 Learning 一個(gè)詞，讓人乍一看覺得和 Intelligence 相比不過是換了個(gè)說法而已，然而事實(shí)上這里的 Learning 的意義要樸素得多。我們來看一看 Machine Learning 的典型的流程就知道了，其實(shí)有時(shí)候覺得和應(yīng)用數(shù)學(xué)或者更通俗的數(shù)學(xué)建模有些類似，通常我們會(huì)有需要分析或者處理的數(shù)據(jù)，根據(jù)一些經(jīng)驗(yàn)和一些假設(shè)，我們可以構(gòu)建一個(gè)模型，這個(gè)模型會(huì)有一些參數(shù)（即使是非參數(shù)化方法，也是可以類似地看待的），根據(jù)數(shù)據(jù)來求解模型參數(shù)的過程，就叫做 Parameter Estimation ，或者 Model Fitting ，但是搞機(jī)器學(xué)習(xí)的人，通常把它叫做 Learning （或者，換一個(gè)角度，叫 Training）——因?yàn)楦鶕?jù)數(shù)據(jù)歸納出一個(gè)有用的模型，這和我們?nèi)祟悺皩W(xué)習(xí)”的過程還是挺類似的吧。不過，如果拋開無聊的摳字眼游戲的話，我們可以看到，Machine Learning 已經(jīng)拋棄了“智能”的高帽子，它的目的就是要解決具
體的問題——而并不關(guān)心是否是通過一種“智能”的方式類解決的。
說到這里，其實(shí)我們構(gòu)造模型就類似于寫一個(gè)類，數(shù)據(jù)就是構(gòu)造函數(shù)的參數(shù)，Learning 就是構(gòu)造函數(shù)運(yùn)行的過程，成功構(gòu)造一個(gè)對(duì)象之后，我們就完成了學(xué)習(xí)。一些 Machine Learning 的問題到這一步就結(jié)束了，另一些情況還會(huì)使用得到的模型（對(duì)象）對(duì)后來的數(shù)據(jù)進(jìn)行一些處理，通常會(huì)是Inferencing。到這個(gè)時(shí)候，又有些像統(tǒng)計(jì)里的東西了，所謂“統(tǒng)計(jì)推斷”嘛。其實(shí)原本統(tǒng)計(jì)和機(jī)器學(xué)習(xí)研究的不少問題就是交叉在一起的，不過兩派人從不同的角度來看待同樣的問題。而且，也確實(shí)有 Statistical Learning 這么一個(gè)說法存在的，可以把他看成是 Machine Learning 的一個(gè)子領(lǐng)域（或者是一個(gè)分子或
者甚至就是 Machine Learning 本身）。
到這里，如果你還沒有因?yàn)椴粩嗟負(fù)缸盅鄱鵁┰甑脑挘?/p>
我已經(jīng)忍無可忍了。所以，我就假定你已經(jīng)了解了什么叫 Learning ，或者是已經(jīng)惡心到懶得去了解了。于是我們轉(zhuǎn)入下一個(gè)話題：流形，也就是 Manifold 。不知道你有沒有為我在本文開頭放上的那個(gè)地球的圖片感到困惑？這是因?yàn)榍蛎媸且粋�(gè)很典型的流
形的例子，而地球就是一個(gè)很典型的“球面”啦（姑且當(dāng)作球面好啦）。
有時(shí)候經(jīng)常會(huì)在 paper 里看到“嵌入在高維空間中的低維流形”，不過高維的數(shù)據(jù)對(duì)于我們這些可憐的低維生物來說總是很難以想像，所以最直觀的例子通常都會(huì)是嵌入在三維空間中的二維或者一維流行。比如說一塊布，可以把它看成一個(gè)二維平面，這是一個(gè)
二維的歐氏空間，現(xiàn)在我們（在三維）中把它扭一扭，它就變成了一個(gè)流形（當(dāng)然，不
扭的時(shí)候，它也是一個(gè)流形，歐氏空間是流形的一種特殊情況）。
所以，直觀上來講，一個(gè)流形好比是一個(gè) d 維的空間，在一個(gè) m 維的空間中 (m > d) 被扭曲之后的結(jié)果。需要注意的是，流形并不是一個(gè)“形狀”，而是一個(gè)“空間”，如果你覺得“扭曲的空間”難以想象，那么請(qǐng)?jiān)倩貞浿耙粔K布的例子。如果我沒弄錯(cuò)的話，廣義相對(duì)論似乎就是把我們的時(shí)空當(dāng)作一個(gè)四維流（空間三維加上時(shí)間一維）形來研究的，引力就是這個(gè)流形扭曲的結(jié)果。當(dāng)然，這些都是直觀上的概念，其實(shí)流形并不需要依靠嵌入在一個(gè)“外圍空間”而存在，稍微正式一點(diǎn)來說，一個(gè) d 維的流形就是一個(gè)在任意點(diǎn)出局部同胚于（簡單地說，就是正逆映射都是光滑的一一映射）歐氏空間。
實(shí)際上，正是這種局部與歐氏空間的同
胚給我們帶來了很多好處，這使得我們在日常生活中許許多多的幾何問題都可以使用簡單的歐氏幾何來解決，因?yàn)楹偷厍虻某叨缺绕饋�，我們的日常生活就算是一個(gè)很小的局部啦——我突然想起《七龍珠》里的那個(gè)界王住的那種私人小星球，走幾步就要繞一圈的感覺，看來界王不僅要體力好（那上面重力似乎是地球的十倍），而且腦力也要好，
初中學(xué)的必須是黎曼幾何了！
那么，除了地球這種簡單的例子，實(shí)際應(yīng)用中的數(shù)據(jù)，怎么知道它是不是一個(gè)流形呢？于是不妨又回歸直觀的感覺。再從球面說起，如果我們事先不知道球面的存在，那么球面上的點(diǎn)，其實(shí)就是三維歐氏空間上的點(diǎn)，可以用一個(gè)三元組來表示其坐標(biāo)。但是和空間中的普通點(diǎn)不一樣的是，它們允許出現(xiàn)的位置受到了一定的限制，具體到球面，可以
可以看一下它的參數(shù)方程：
可以看到，這些三維的坐標(biāo)實(shí)際上是由兩個(gè)變量和生成的，也可以說成是它的自由度是二，也正好對(duì)應(yīng)了它是一個(gè)二維的流形。有了這樣的感覺之后，再來看流形學(xué)習(xí)里經(jīng)
常用到的人臉的例子，就很自然了。下圖是Isomap論文里的一個(gè)結(jié)果：
這里的圖片來自同一張人臉（好吧，其實(shí)是人臉模型），每張圖片是 64×64 的灰度圖，如果把位圖按照列（或行）拼起來，就可以得到一個(gè) 4096 維的向量，這樣一來，每一張圖片就可以看成是 4096 維歐氏空間中的一個(gè)點(diǎn)。很顯然，并不是 4096 維空間中任意一個(gè)點(diǎn)都可以對(duì)應(yīng)于一張人臉圖片的，這就類似于球面的情形，我們可以假定所有可以是人臉的 4096 維向量實(shí)際上分布在一個(gè) d 維 (d < 4096) 的子空間中。而特定到Isomap的人臉這個(gè)例子，實(shí)際上我們知道所有的 698 張圖片是拍自同一個(gè)人臉（模型），不過是在不同的 pose 和光照下拍攝的，如果把 pose （上下和左右）當(dāng)作兩個(gè)自由度，而光照當(dāng)作一個(gè)自由度，那么這些圖片實(shí)際只有三個(gè)自由度，換句話說，存在一個(gè)類似于球面一樣的參數(shù)方程（當(dāng)然，解析式是沒法寫出來的），給定一組參數(shù)（也就是上下、左右的 pose 和光照這三個(gè)值），就可以生成出對(duì)應(yīng)的 4096 維的坐標(biāo)來。
換句話說，這是一個(gè)嵌入在 4096 維歐氏空間中的一個(gè) 3 維流形。
實(shí)際上，上面的那張圖就是Isomap將這個(gè)數(shù)據(jù)集從 4096 維映射到 3 維空間中，并顯示了其中 2 維的結(jié)果，圖中的小點(diǎn)就是每個(gè)人臉在這個(gè)二維空間中對(duì)應(yīng)的坐標(biāo)位置，其中一些標(biāo)紅圈的點(diǎn)被選出來，并在旁邊畫上了該點(diǎn)對(duì)應(yīng)的原始圖片，可以很直觀地看
出這兩個(gè)維度正好對(duì)應(yīng)了 pose 的兩個(gè)自由度平滑變化的結(jié)果。
就我目前所知，把流形引入到機(jī)器學(xué)習(xí)領(lǐng)域來主要有兩種用途：一是將原來在歐氏空間中適用的算法加以改造，使得它工作在流形上，直接或間接地對(duì)流形的結(jié)構(gòu)和性質(zhì)加以利用；二是直接分析流形的結(jié)構(gòu)，并試圖將其映射到一個(gè)歐氏空間中，再在得到的結(jié)果
上運(yùn)用以前適用于歐氏空間的算法來進(jìn)行學(xué)習(xí)。
這里Isomap正巧是一個(gè)非常典型的例子，因?yàn)樗鼘?shí)際上是通過“改造一種原本適用于歐
氏空間的算法”，達(dá)到了“將流形映射到一個(gè)歐氏空間”的目的。
Isomap所改造的這個(gè)方法叫做Multidimensional Scaling (MDS)，MDS 是一種降維方法，它的目的就是使得降維之后的點(diǎn)兩兩之間的距離盡量不變（也就是和在原是空間中對(duì)應(yīng)的兩個(gè)點(diǎn)之間的距離要差不多）。只是 MDS 是針對(duì)歐氏空間設(shè)計(jì)的，對(duì)于距離的計(jì)算也是使用歐氏距離來完成的。如果數(shù)據(jù)分布在一個(gè)流形上的話，歐氏距離就不適用了。 讓我們再回到地球——這個(gè)在三維空間中的二維流形，假設(shè)我們要在三維空間中計(jì)算北極點(diǎn)和南極點(diǎn)的距離，這很容易，就是兩點(diǎn)相連的線段的長度，可是，如果要在這個(gè)流形上算距離就不能這樣子算了，我們總不能從北極打個(gè)洞鉆到南極去吧？要沿著地球表面走才行，當(dāng)然，如果我隨便沿著什么路線走一遍，然后數(shù)出總共走了多少步作為距離，這是不成的，因?yàn)檫@樣一來如果我沿著不同的路線走，豈不是會(huì)得到不同的距離值？總而言之，我們現(xiàn)在需要一個(gè)新的定義在地球表面（流形）上的距離度量，理論上來說，任意滿足測度的 4 個(gè)條件的函數(shù)都可以被定義為距離，不過，為了和歐氏空間對(duì)應(yīng)起
來，這里選擇一個(gè)直線距離的推廣定義。
還記得初中學(xué)的“兩點(diǎn)之間，線段最短”嗎？現(xiàn)在，我們反過來說，把線段的概念推廣一下，變成“兩點(diǎn)之間最短的曲線是線段”，于是流形上的距離定義也就等同于歐氏空間了：流形上兩個(gè)點(diǎn)之間的距離就是連接兩個(gè)點(diǎn)的“線段”的長度。雖然只是置換了一個(gè)概念，但是現(xiàn)在兩者統(tǒng)一起來了，不過，在流形上的線段大概就不一定是“直”的了（于是直線也變成不一定是“直”的了），通常又稱作是“測地線”。對(duì)于球面這個(gè)簡單的流形來說，任意一條線段必定是在一個(gè)“大圓”上的，于是球面上的直線其實(shí)都是一些大圓，也造成了球面這個(gè)流形上沒有平行線等一系列尷尬的局面（任意兩條直線均相交），如果你看
過一些數(shù)學(xué)科普八卦類的書，應(yīng)該會(huì)回憶起不少東西啦！
回到Isomap，它主要做了一件事情，就是把 MDS 中原始空間中距離的計(jì)算從歐氏距離換為了流形上的測地距離。當(dāng)然，如果流形的結(jié)構(gòu)事先不知道的話，這個(gè)距離是沒法算的，于是Isomap通過將數(shù)據(jù)點(diǎn)連接起來構(gòu)成一個(gè)鄰接 Graph 來離散地近似原來的流形，而測地距離也相應(yīng)地通過 Graph 上的最短路徑來近似了。
流形學(xué)習(xí)
流形學(xué)習(xí)是個(gè)很廣泛的概念。這里我主要談的是自從2000年以后形成的流形學(xué)習(xí)概念和其主要代表方法。自從2000年以后，流形學(xué)習(xí)被認(rèn)為屬于非線性降維的一個(gè)分支。眾所周知，引導(dǎo)這一領(lǐng)域迅速發(fā)展的是2000年Science雜志上的兩篇文章: Isomap and LLE (Locally Linear Embedding)。
1. 流形學(xué)習(xí)的基本概念
那流形學(xué)習(xí)是什莫呢？為了好懂，我盡可能應(yīng)用少的數(shù)學(xué)概念來解釋這個(gè)東西。所謂流形（manifold）就是一般的幾何對(duì)象的總稱。比如人，有中國人、美國人等等；流形就包括各種維數(shù)的曲線曲面等。和一般的降維分析一樣，流形學(xué)習(xí)把一組在高維空間中的數(shù)據(jù)在低維空間中重新表示。和以往方法不同的是，在流形學(xué)習(xí)中有一個(gè)假設(shè)，就是所處理的數(shù)據(jù)采樣于一個(gè)潛在的流形上，或是說對(duì)于這組數(shù)據(jù)存在一個(gè)潛在的流形。 對(duì)于不同的方法，對(duì)于流形性質(zhì)的要求各不相同，這也就產(chǎn)生了在流形假設(shè)下的各種不同性質(zhì)的假設(shè)，比如在Laplacian
Eigenmaps中要假設(shè)這個(gè)流形是緊致黎曼流形等。對(duì)于描述流形上的點(diǎn)，我們要用坐標(biāo)，而流形上本身是沒有坐標(biāo)的，所以為了表示流形上的點(diǎn)，必須把流形放入外圍空間（ambient space）中，那末流形上的點(diǎn)就可以用外圍空間的坐標(biāo)來表示。比如R^3中的球面是個(gè)2維的曲面，因?yàn)榍蛎嫔现挥袃蓚�(gè)自由度，但是球面上的點(diǎn)一般是用外圍R^3空間中的坐標(biāo)表示的，所以我們看到的R^3中球面上的點(diǎn)有3個(gè)數(shù)來表示的。當(dāng)然球面還有柱坐標(biāo)球坐標(biāo)等表示。對(duì)于R^3中的球面來說，那末流形學(xué)習(xí)可以粗略的概括為給出R^3中的表示，在保持球面上點(diǎn)某些幾何性質(zhì)的條件下，找出找到一組對(duì)應(yīng)的內(nèi)蘊(yùn)坐標(biāo)（intrinsic coordinate）表示，顯然這個(gè)表示應(yīng)該是兩維的，因?yàn)榍蛎娴木S數(shù)是兩維的。這個(gè)過程也叫參數(shù)化（parameterization）。直觀上來說，就是把這個(gè)球面盡量好的展開在通過原點(diǎn)的平面上。在PAMI中，這樣的低維表示也叫內(nèi)蘊(yùn)特征（intrinsic feature）。一般外圍空間的維數(shù)也叫觀察維數(shù)，其表示也叫自然坐標(biāo)（外圍空間是歐式空間）表示,在統(tǒng)計(jì)中一般叫observation。
了解了流形學(xué)習(xí)的這個(gè)基礎(chǔ)，那末流形學(xué)習(xí)中的一些是非也就很自然了，這個(gè)下面穿插來說。由此，如果你想學(xué)好流形學(xué)習(xí)里的方法，你至少要了解一些微分流形和黎曼幾何的基本知識(shí)。
2. 代表方法
a) Isomap。
Josh Tenenbaum的Isomap開創(chuàng)了一個(gè)數(shù)據(jù)處理的新戰(zhàn)場。在沒有具體說Isomap之前，有必要先說說MDS（Multidimensional Scaling）這個(gè)方法。我們國內(nèi)的很多人知道PCA，卻很多人不知道MDS。PCA和MDS是相互對(duì)偶的兩個(gè)方法。MDS就是理論上保持歐式距離的一個(gè)經(jīng)典方法，MDS最早主要用于做數(shù)據(jù)的可視化。由于MDS得到的低維表示中心在原點(diǎn)，所以又可以說保持內(nèi)積。也就是說，用低維空間中的內(nèi)積近似高維空間中的距離。經(jīng)典的MDS方法，高維空間中的距離一般用歐式距離。
Isomap就是借窩生蛋。他的理論框架就是MDS，但是放在流形的理論框架內(nèi)，原始的距離換成了流形上的測地線（geodesic）距離。其它一模一樣。所謂的測地線，就是流形上加速度為零的曲線，等同于歐式空間中的直線。我們經(jīng)常聽到說測地線是流形上兩點(diǎn)之間距離最短的線。其實(shí)這末說是不嚴(yán)謹(jǐn)?shù)�。流形上兩點(diǎn)之間距離最短的線是測地線，但是反過來不一定對(duì)。另外，如果任意兩個(gè)點(diǎn)之間都存在一個(gè)測地線，那末這個(gè)流形必須是連通的鄰域都是凸的。Isomap就是把任意兩點(diǎn)的測地線距離（準(zhǔn)確地說是最短距離）作為流形的幾何描述，用MDS理論框架
理論上保持這個(gè)點(diǎn)與點(diǎn)之間的最短距離。在Isomap中，測地線距離就是用兩點(diǎn)之間圖上的最短距離來近似的，這方面的算法是一般計(jì)算機(jī)系中用的圖論中的經(jīng)典算法。
如果你曾細(xì)致地看過Isomap主頁上的matlab代碼，你就會(huì)發(fā)現(xiàn)那個(gè)代碼的實(shí)現(xiàn)復(fù)雜度遠(yuǎn)超與實(shí)際論文中敘述的算法。在那個(gè)代碼中，除了論文中寫出的算法外，還包括了 outlier detection和embedding scaling。這兩樣?xùn)|西，保證了運(yùn)行他們的程序得到了結(jié)果一般來說相對(duì)比較理想。但是，這在他們的算法中并沒有敘述。如果你直接按照他論文中的方法來實(shí)現(xiàn)，你可以體會(huì)一下這個(gè)結(jié)果和他們結(jié)果的差距。從此我們也可以看出，那幾個(gè)作者做學(xué)問的嚴(yán)謹(jǐn)態(tài)度，這是值得我們好好學(xué)習(xí)的。
另外比較有趣的是，Tenenbaum根本不是做與數(shù)據(jù)處理有關(guān)算法的人，他是做計(jì)算認(rèn)知科學(xué)（computational cognition science）的。在做這個(gè)方法的時(shí)候，他還在stanford，02年就去了
MIT開創(chuàng)一派，成了CoCoSci 的掌門人，他的組成長十分迅速。但是有趣的是，在Isomap之后，他包括他在MIT帶的學(xué)生就從來再也沒有做過類似的工作。其原因我今年夏天有所耳聞。他在今年參加 UCLA Alan Yuille 組織的一個(gè)summer school上說，（不是原文，是大意）我們經(jīng)常忘了做研究的原始出發(fā)點(diǎn)是什莫。他做Isomap就是為了找一個(gè)好的visual perception的方法，他還堅(jiān)持了他的方向和信仰，computational cognition，他沒有隨波逐流。而由他引導(dǎo)起來的 manifold learning 卻快速的發(fā)展成了一個(gè)新的方向。
這是一個(gè)值得我們好好思考的問題。我們做一個(gè)東西，選擇一個(gè)研究方向究竟是為了什莫。你考慮過嗎？
�。ó�(dāng)然，此問題也在問我自己）
b) LLE (Locally linear Embedding)
LLE在作者寫出的表達(dá)式看,是個(gè)具有十分對(duì)稱美的方法. 這種看上去的對(duì)稱對(duì)于啟發(fā)人很重要。LLE的思想就是，一個(gè)流形在很小的局部鄰域上可以近似看成歐式的，就是局部線性的。那末，在小的局部鄰域上，一個(gè)點(diǎn)就可以用它周圍的點(diǎn)在最小二乘意義下最優(yōu)的線性表示。LLE把這個(gè)線性擬合的系數(shù)當(dāng)成這個(gè)流形局部幾何性質(zhì)的刻畫。那末一個(gè)好的低維表示，就應(yīng)該也具有同樣的局部幾何，所以利用同樣的線性表示的表達(dá)式，最終寫成一個(gè)二次型的形式，十分自然優(yōu)美。
注意在LLE出現(xiàn)的兩個(gè)加和優(yōu)化的線性表達(dá)，第一個(gè)是求每一點(diǎn)的線性表示系數(shù)的。雖然原始公式中是寫在一起的，但是求解時(shí)，是對(duì)每一個(gè)點(diǎn)分別來求得。第二個(gè)表示式，是已知所有點(diǎn)的線性表示系數(shù)，來求低維表示（或嵌入embedding）的，他是一個(gè)整體求解的過程。這兩個(gè)表達(dá)式的轉(zhuǎn)化正好中間轉(zhuǎn)了個(gè)彎，使一些人困惑了，特別后面一個(gè)公式寫成一個(gè)二次型的過程并不是那末直觀，很多人往往在此卡住，而阻礙了全面的理解。我推薦大家去精讀 Saul 在
JMLR上的那篇LLE的長文。那篇文章無論在方法表達(dá)還是英文書寫，我認(rèn)為都是精品，值得好好玩味學(xué)習(xí)。
另外值得強(qiáng)調(diào)的是，對(duì)于每一點(diǎn)處擬合得到的系數(shù)歸一化的操作特別重要，如果沒有這一步，這個(gè)算法就沒有效果。但是在原始論文中，他們是為了保持?jǐn)?shù)據(jù)在平行移動(dòng)下embedding不變。 LLE的matlab代碼寫得簡潔明了，是一個(gè)樣板。
在此有必要提提Lawrence Saul這個(gè)人。在Isomap和LLE的作者們中，Saul算是唯一一個(gè)以流形學(xué)習(xí)（并不限于）為研究對(duì)象開創(chuàng)學(xué)派的人。Saul早年主要做參數(shù)模型有關(guān)的算法。自從LLE以后，坐陣UPen創(chuàng)造了一個(gè)個(gè)佳績。主要成就在于他的兩個(gè)出色學(xué)生，Kilian Weinberger和 Fei Sha，做的方法。拿了很多獎(jiǎng)，在此不多說，可以到他主頁上去看。Weinberger把學(xué)習(xí)核矩陣引入到流形學(xué)習(xí)中來。他的這個(gè)方法在流形學(xué)習(xí)中影響到不是很顯著，卻是在 convex optimization 中人人得知。Fei Sha不用多說了，machine learning中一個(gè)閃亮的新星，中國留學(xué)生之驕傲�，F(xiàn)在他們一個(gè)在Yahoo,一個(gè)在Jordan手下做PostDoc。
c) Laplacian Eigenmaps
要說哪一個(gè)方法被做的全面，那莫非LE莫屬。如果只說LE這個(gè)方法本身，是不新的，許多年前在做mesh相關(guān)的領(lǐng)域就開始這莫用。但是放在黎曼幾何的框架內(nèi)，給出完整的幾何分析的，應(yīng)該是Belkin和Niyogi（LE作者）的功勞。
LE的基本思想就是用一個(gè)無向有權(quán)圖來描述一個(gè)流形，然后通過用圖的嵌入（graph
embedding）來找低維表示。說白了，就是保持圖的局部鄰接關(guān)系的情況把這個(gè)圖從高維空間中重新畫在一個(gè)低維空間中（graph drawing）。
在至今為止的流行學(xué)習(xí)的典型方法中，LE是速度最快、效果相對(duì)來說不怎莫樣的。但是LE有一個(gè)其他方法沒有的特點(diǎn)，就是如果出現(xiàn)outlier情況下，它的魯棒性（robustness）特別好。 后來Belkin和Niyogi又分析了LE的收斂性。大家不要忽視這個(gè)問題，很重要。鼓勵(lì)有興趣數(shù)學(xué)功底不錯(cuò)的人好好看看這篇文章。
d) Hessian Eigenmaps
如果你對(duì)黎曼幾何不懂，基本上看不懂這個(gè)方法。又加作者表達(dá)的抽象，所以絕大多數(shù)人對(duì)這個(gè)方法了解不透徹。在此我就根據(jù)我自己的理解說說這個(gè)方法。
這個(gè)方法有兩個(gè)重點(diǎn)：（1）如果一個(gè)流形是局部等距（isometric）歐式空間中一個(gè)開子集的，那末它的Hessian矩陣具有d+1維的零空間。（2）在每一點(diǎn)處，Hessian系數(shù)的估計(jì)。
首先作者是通過考察局部Hessian的二次型來得出結(jié)論的，如果一個(gè)流形局部等距于歐式空間中的一個(gè)開子集，那末由這個(gè)流形patch 到開子集到的映射函數(shù)是一個(gè)線性函數(shù)，線性函數(shù)的二次混合導(dǎo)數(shù)為零，所以局部上由Hessian系數(shù)構(gòu)成的二次型也為零，這樣把每一點(diǎn)都考慮到，過渡到全局的Hessian矩陣就有d+1維的零空間，其中一維是常函數(shù)構(gòu)成的，也就是1向量。其它的d維子空間構(gòu)成等距坐標(biāo)。這就是理論基礎(chǔ)的大意，當(dāng)然作者在介紹的時(shí)候，為了保持理論嚴(yán)謹(jǐn)，作了一個(gè)由切坐標(biāo)到等距坐標(biāo)的過渡。
另外一個(gè)就是局部上Hessian系數(shù)的估計(jì)問題。我在此引用一段話：
If you approximate a function f(x) by a quadratic expansion
f(x) = f(0) + (grad f)^T x + x^T Hf x + rem
then the hessian is what you get for the quadratic component. So simply over a given neighborhood, develop the operator that approximates a function by its projection on 1, x_1,...,x_k, x_1^2,...,x_k^2, x_1*x_2,... ,x_{k-1}*x_{k}. Extract the component of the operator that delivers the projection on x_1^2,...,x_k^2, x_1*x_2,... ,x_{k-1}*x_{k}.
這段話是我在初學(xué)HE時(shí)候，寫信問Dave Donoho，他給我的回信。希望大家領(lǐng)會(huì)。如果你了解了上述基本含義，再去細(xì)看兩遍原始論文，也許會(huì)有更深的理解。由于HE牽扯到二階導(dǎo)數(shù)的估計(jì)，所以對(duì)噪聲很敏感。另外，HE的原始代碼中在計(jì)算局部切坐標(biāo)的時(shí)候，用的是奇異值分解(SVD)，所以如果想用他們的原始代碼跑一下例如圖像之類的真實(shí)數(shù)據(jù)，就特別的慢。其實(shí)把他們的代碼改一下就可以了，利用一般PCA的快速計(jì)算方法，計(jì)算小尺寸矩陣的特征向量即可。還有，在原始代碼中，他把Hessian系數(shù)歸一化了，這也就是為什莫他們叫這個(gè)方法為 Hessian LLE 的原因之一。
Dave Dohono是學(xué)術(shù)界公認(rèn)的大牛，在流形學(xué)習(xí)這一塊，是他帶著他的一個(gè)學(xué)生做的，Carrie Grimes。現(xiàn)在這個(gè)女性研究員在Google做 project leader，學(xué)術(shù)界女生同學(xué)的楷模 : )
e) LTSA (Local tangent space alignment)
很榮幸，這個(gè)是國內(nèi)學(xué)者（浙江大學(xué)數(shù)學(xué)系的老師ZHANG Zhenyue）為第一作者做的一個(gè)在流行學(xué)習(xí)中最出色的方法。由于這個(gè)方法是由純數(shù)學(xué)做數(shù)值分析出身的老師所做，所以原始論文看起來公式一大堆，好像很難似的。其實(shí)這個(gè)方法非常直觀簡單。
象 Hessian Eigenmaps 一樣，流形的局部幾何表達(dá)先用切坐標(biāo)，也就是PCA的主子空間中的坐標(biāo)。那末對(duì)于流形一點(diǎn)處的切空間，它是線性子空間，所以可以和歐式空間中的一個(gè)開子集建立同構(gòu)關(guān)系，最簡單的就是線性變換。在微分流形中，就叫做切映射 (tangential map)，是個(gè)很自然很基礎(chǔ)的概念。把切坐標(biāo)求出來，建立出切映射，剩下的就是數(shù)值計(jì)算了。最終這個(gè)算法劃歸為一個(gè)很簡單的跌代加和形式。如果你已經(jīng)明白了MDS，那末你就很容易明白，這個(gè)算法本質(zhì)上就是MDS的從局部到整體的組合。
這里主要想重點(diǎn)強(qiáng)調(diào)一下，那個(gè)論文中使用的一個(gè)從局部幾何到整體性質(zhì)過渡的alignment技術(shù)。在spectral method（特征分解的）中，這個(gè)alignment方法特別有用。只要在數(shù)據(jù)的局部鄰域上你的方法可以寫成一個(gè)二次項(xiàng)的形式，就可以用。
其實(shí)LTSA最早的版本是在02年的DOCIS上。這個(gè)alignment方法在02年底Brand的 charting a manifold 中也出現(xiàn)，隱含在Hessian Eigenmaps中。在HE中，作者在從局部的Hessian矩陣過渡到全局的Hessian矩陣時(shí)，用了兩層加號(hào)，其中就隱含了這個(gè) alignment方法。后來國內(nèi)一個(gè)叫 ZHAO Deli 的學(xué)生用這個(gè)方法重新寫了LLE，發(fā)在Pattern Recognition上，一個(gè)短文。可以預(yù)見的是，這個(gè)方法還會(huì)被發(fā)揚(yáng)光大。
ZHA Hongyuan 后來專門作了一篇文章來分析 alignment matrix 的譜性質(zhì)，有興趣地可以找來看看。
f) MVU (Maximum variance unfolding)
這個(gè)方法剛發(fā)出來以后，名字叫做Semi-definite Embedding (SDE)。構(gòu)建一個(gè)局部的稀疏歐式距離矩陣以后，作者通過一定約束條件（主要是保持距離）來學(xué)習(xí)到一個(gè)核矩陣，對(duì)這個(gè)核矩陣做PCA就得到保持距離的 embedding，就這莫簡單。但是就是這個(gè)方法得了多少獎(jiǎng)，自己可以去找找看。個(gè)人觀點(diǎn)認(rèn)為，這個(gè)方法之所以被如此受人賞識(shí)，無論在vision還是在learning，除了給流形學(xué)習(xí)這一領(lǐng)域帶來了一個(gè)新的解決問題的工具之外，還有兩個(gè)重點(diǎn)，一是核方法（kernel），二是半正定規(guī)劃（semi-definite programming），這兩股風(fēng)無論在哪個(gè)方向（learning and Vision）上都吹得正猛。
g) S-Logmaps
這個(gè)方法不太被人所知，但是我認(rèn)為這個(gè)是流形學(xué)習(xí)發(fā)展中的一個(gè)典型的方法（其實(shí)其他還有很多人也這莫認(rèn)為）。就效果來說，這個(gè)方法不算好，說它是一個(gè)典型的方法，是因?yàn)檫@個(gè)方法應(yīng)用了黎曼幾何中一個(gè)很直觀的性質(zhì)。這個(gè)性質(zhì)和法坐標(biāo)(normal coordinate)、指數(shù)映射(exponential map)和距離函數(shù)(distance function)有關(guān)。
如果你了解黎曼幾何，你會(huì)知道，對(duì)于流形上的一條測地線，如果給定初始點(diǎn)和初始點(diǎn)處測地線的切方向，那莫這個(gè)測地線就可以被唯一確定。這是因?yàn)樵谶@些初始條件下，描述測地線的偏微分方程的解是唯一的。那末流形上的一條測地線就可以和其起點(diǎn)處的切平面上的點(diǎn)建立一個(gè)對(duì)應(yīng)關(guān)系。我們可以在這個(gè)切平面上找到一點(diǎn)，這個(gè)點(diǎn)的方向就是這個(gè)測地線在起點(diǎn)處的切方向，其長度等于這個(gè)測地線上的長。這樣的一個(gè)對(duì)應(yīng)關(guān)系在局部上是一一對(duì)應(yīng)的。那末這個(gè)在切平面上的對(duì)應(yīng)點(diǎn)在切平面中就有一個(gè)坐標(biāo)表示，這個(gè)表示就叫做測地線上對(duì)應(yīng)點(diǎn)的法坐標(biāo)表示（有的也叫指數(shù)坐標(biāo)）。那末反過來，我們可以把切平面上的點(diǎn)映射到流形上，這個(gè)映射過程就叫做指數(shù)映射（Logmap就倒過來）。如果流形上每一個(gè)點(diǎn)都可以這樣在同一個(gè)切平面上表示出來，那末我們就可以得到保持測地線長度的低維表示。如果這樣做得到，流形必須可以被單坐標(biāo)系統(tǒng)所覆蓋。
如果給定流形上的采樣點(diǎn)，如果要找到法坐標(biāo)，我們需要知道兩個(gè)東西，一是測地線距離，二是每個(gè)測地線在起點(diǎn)處的切方向。第一個(gè)東西好弄，利用Isomap中的方法直接就可以解決，關(guān)鍵是第二個(gè)。第二個(gè)作者利用了距離函數(shù)的梯度，這個(gè)梯度和那個(gè)切方向是一個(gè)等價(jià)的關(guān)系，一般的黎曼幾何書中都有敘述。作者利用一個(gè)局部切坐標(biāo)的二次泰勒展開來近似距離函數(shù)，而距離是知道的，就是測地線距離，局部切坐標(biāo)也知道，那末通過求一個(gè)簡單的最小二乘問題就可以估計(jì)出梯度方向。
如果明白這個(gè)方法的幾何原理，你再去看那個(gè)方法的結(jié)果，你就會(huì)明白為什莫在距離中心點(diǎn)比較遠(yuǎn)的點(diǎn)的embedding都可以清楚地看到在一條條線上，效果不太好。
最近這個(gè)思想被北大的一個(gè)年輕的老師 LIN Tong 發(fā)揚(yáng)光大，就是ECCV‘06上的那篇，還有即將刊登出的TPAMI上的 Riemannian Manifold Learning，實(shí)為國內(nèi)研究學(xué)者之榮幸。Lin的方法效果非常好，但是雖然取名叫Riemannian，沒有應(yīng)用到黎曼幾何本身的性質(zhì)，這樣使他的方法更容易理解。
Lin也是以一個(gè)切空間為基準(zhǔn)找法坐標(biāo)，這個(gè)出發(fā)點(diǎn)和思想和Brun（S-Logmaps）的是一樣的。但是Lin全是在局部上操作的，在得出切空間原點(diǎn)處局部鄰域的法坐標(biāo)以后，Lin采用逐步向外擴(kuò)展的方法找到其他點(diǎn)的法坐標(biāo)，在某一點(diǎn)處，保持此點(diǎn)到它鄰域點(diǎn)的歐式距離和夾角，然后轉(zhuǎn)化成一個(gè)最小二乘問題求出此點(diǎn)的法坐標(biāo)，這樣未知的利用已知的逐步向外擴(kuò)展。說白了就像縫網(wǎng)一樣，從幾個(gè)臨近的已知點(diǎn)開始，逐漸向外擴(kuò)散的縫。效果好是必然的。
淺談流形學(xué)習(xí)
bypluskid, on 2010-05-29, in Machine Learning76 comments
總覺得即使是“淺談”兩個(gè)字，還是讓這個(gè)標(biāo)
題有些過大了，更何況我自己也才剛剛接觸這么一個(gè)領(lǐng)域。不過懶得想其他標(biāo)題了，想起來要扯一下這個(gè)話題，也是因?yàn)楹团笥蚜钠鹞易约鹤罱谧龅姆较�。Manifold Learning 或者僅僅 Manifold 本身通常就聽起來頗有些深?yuàn)W的感覺，不過如果并不是想要進(jìn)行嚴(yán)格的理論推導(dǎo)的話，也可以從許多直觀的例子得到一些感性的認(rèn)識(shí)，正好我也就借這個(gè)機(jī)會(huì)來簡單地談一下這個(gè)話題吧，或者說至少是我到目前為止對(duì)這它的認(rèn)識(shí)。 這兩個(gè)詞，在談 Manifold 之前，不妨先說說 Learning ，也就是 Machine Learning 。而說道 Machine Learning 而不提一下 Artificial Intelligence 的話似乎又顯得有些不厚道。人說 AI 是一門最悲劇的學(xué)科，因?yàn)槊慨?dāng)它的一個(gè)子領(lǐng)域發(fā)展得像模像樣之后，就立馬自立門戶，從此和 AI “再無瓜葛”了，而 Machine Learning 大概要算是最新的一個(gè)典型吧。這就讓人有點(diǎn)奇怪，比如說數(shù)學(xué)，分門別類總算是夠多了吧？可以不管怎么分，大家兄弟姐妹也都還承認(rèn)自己是叫“數(shù)學(xué)”的。那 AI 呢？我覺得這里有很大一部分
是它自身定位的問題。
反正現(xiàn)在我是不太清楚 AI 是做什么的，不知道其他人到底清楚不清楚。Wikipedia 上
說 Artificial intelligence (AI) is the intelligence of machines and the branch of computer
science that aims to create it.
可是這相當(dāng)于一個(gè) tautology ，因?yàn)榈降资裁从质莟he intelligence of machines呢？一開始的時(shí)候，大牛們都野心勃勃，而且好像也是信心滿滿，就好像曾經(jīng)廣泛認(rèn)為“牛頓定理揭示了宇宙真理，科學(xué)剩下的事情只要按照公式來做計(jì)算就可以了”一樣，大家可能覺得，不出幾十年，人類就可以不用思考，交給 AI 來做了。不過我這里并不想再多說諸如什么是“思考”，什么是“智能”之類的以及隨之而來的“圖靈測試”之類的話題。我想說的是，到頭來，AI 到底是什么，這還是一個(gè)問題，或者說，AI 在一開始定了一個(gè)過高的目標(biāo)，幾十年后，發(fā)現(xiàn)情況并不像當(dāng)年那么樂觀，卻又有些下不了臺(tái)了。
這個(gè)時(shí)候，AI 的一些旁枝或者子領(lǐng)域果斷放下面子，丟掉了那個(gè)近乎玄幻的目標(biāo)，逐漸發(fā)展成為“正常”的學(xué)科，所以也就不再好稱為 AI 了�；蛘哒f現(xiàn)在的 AI 有兩個(gè)意思，一個(gè)廣義的 AI ，包括了所有相關(guān)的以及派生的領(lǐng)域，另一個(gè)則是狹義的或者經(jīng)典的 AI ，專門指那些仍然在執(zhí)著地追求著真正的“智能”的部分，或者說得不好聽一點(diǎn)，就
是剩下的部分。
Machine Learning 作為離家出走的典型，雖然名字里帶了 Learning 一個(gè)詞，讓人乍一看覺得和 Intelligence 相比不過是換了個(gè)說法而已，然而事實(shí)上這里的 Learning 的意義要樸素得多。我們來看一看 Machine Learning 的典型的流程就知道了，其實(shí)有時(shí)候覺得和應(yīng)用數(shù)學(xué)或者更通俗的數(shù)學(xué)建模有些類似，通常我們會(huì)有需要分析或者處理的數(shù)據(jù)，根據(jù)一些經(jīng)驗(yàn)和一些假設(shè)，我們可以構(gòu)建一個(gè)模型，這個(gè)模型會(huì)有一些參數(shù)（即使是非參數(shù)化方法，也是可以類似地看待的），根據(jù)數(shù)據(jù)來求解模型參數(shù)的過程，就叫做 Parameter Estimation ，或者 Model Fitting ，但是搞機(jī)器學(xué)習(xí)的人，通常把它叫做 Learning （或者，換一個(gè)角度，叫 Training）——因?yàn)楦鶕?jù)數(shù)據(jù)歸納出一個(gè)有用的模型，這和我們?nèi)祟悺皩W(xué)習(xí)”的過程還是挺類似的吧。不過，如果拋開無聊的摳字眼游戲的話，我們可以看到，Machine Learning 已經(jīng)拋棄了“智能”的高帽子，它的目的就是要解決具
體的問題——而并不關(guān)心是否是通過一種“智能”的方式類解決的。
說到這里，其實(shí)我們構(gòu)造模型就類似于寫一個(gè)類，數(shù)據(jù)就是構(gòu)造函數(shù)的參數(shù)，Learning 就是構(gòu)造函數(shù)運(yùn)行的過程，成功構(gòu)造一個(gè)對(duì)象之后，我們就完成了學(xué)習(xí)。一些 Machine Learning 的問題到這一步就結(jié)束了，另一些情況還會(huì)使用得到的模型（對(duì)象）對(duì)后來的數(shù)據(jù)進(jìn)行一些處理，通常會(huì)是Inferencing。到這個(gè)時(shí)候，又有些像統(tǒng)計(jì)里的東西了，所謂“統(tǒng)計(jì)推斷”嘛。其實(shí)原本統(tǒng)計(jì)和機(jī)器學(xué)習(xí)研究的不少問題就是交叉在一起的，不過兩派人從不同的角度來看待同樣的問題。而且，也確實(shí)有 Statistical Learning 這么一個(gè)說法存在的，可以把他看成是 Machine Learning 的一個(gè)子領(lǐng)域（或者是一個(gè)分子或
者甚至就是 Machine Learning 本身）。
到這里，如果你還沒有因?yàn)椴粩嗟負(fù)缸盅鄱鵁┰甑脑挘?/p>
我已經(jīng)忍無可忍了。所以，我就假定你已經(jīng)了解了什么叫 Learning ，或者是已經(jīng)惡心到懶得去了解了。于是我們轉(zhuǎn)入下一個(gè)話題：流形，也就是 Manifold 。不知道你有沒有為我在本文開頭放上的那個(gè)地球的圖片感到困惑？這是因?yàn)榍蛎媸且粋�(gè)很典型的流
形的例子，而地球就是一個(gè)很典型的“球面”啦（姑且當(dāng)作球面好啦）。
有時(shí)候經(jīng)常會(huì)在 paper 里看到“嵌入在高維空間中的低維流形”，不過高維的數(shù)據(jù)對(duì)于我們這些可憐的低維生物來說總是很難以想像，所以最直觀的例子通常都會(huì)是嵌入在三維空間中的二維或者一維流行。比如說一塊布，可以把它看成一個(gè)二維平面，這是一個(gè)
二維的歐氏空間，現(xiàn)在我們（在三維）中把它扭一扭，它就變成了一個(gè)流形（當(dāng)然，不
扭的時(shí)候，它也是一個(gè)流形，歐氏空間是流形的一種特殊情況）。
所以，直觀上來講，一個(gè)流形好比是一個(gè) d 維的空間，在一個(gè) m 維的空間中 (m > d) 被扭曲之后的結(jié)果。需要注意的是，流形并不是一個(gè)“形狀”，而是一個(gè)“空間”，如果你覺得“扭曲的空間”難以想象，那么請(qǐng)?jiān)倩貞浿耙粔K布的例子。如果我沒弄錯(cuò)的話，廣義相對(duì)論似乎就是把我們的時(shí)空當(dāng)作一個(gè)四維流（空間三維加上時(shí)間一維）形來研究的，引力就是這個(gè)流形扭曲的結(jié)果。當(dāng)然，這些都是直觀上的概念，其實(shí)流形并不需要依靠嵌入在一個(gè)“外圍空間”而存在，稍微正式一點(diǎn)來說，一個(gè) d 維的流形就是一個(gè)在任意點(diǎn)出局部同胚于（簡單地說，就是正逆映射都是光滑的一一映射）歐氏空間。
實(shí)際上，正是這種局部與歐氏空間的同
胚給我們帶來了很多好處，這使得我們在日常生活中許許多多的幾何問題都可以使用簡單的歐氏幾何來解決，因?yàn)楹偷厍虻某叨缺绕饋恚覀兊娜粘Ｉ罹退闶且粋�(gè)很小的局部啦——我突然想起《七龍珠》里的那個(gè)界王住的那種私人小星球，走幾步就要繞一圈的感覺，看來界王不僅要體力好（那上面重力似乎是地球的十倍），而且腦力也要好，
初中學(xué)的必須是黎曼幾何了！
那么，除了地球這種簡單的例子，實(shí)際應(yīng)用中的數(shù)據(jù)，怎么知道它是不是一個(gè)流形呢？于是不妨又回歸直觀的感覺。再從球面說起，如果我們事先不知道球面的存在，那么球面上的點(diǎn)，其實(shí)就是三維歐氏空間上的點(diǎn)，可以用一個(gè)三元組來表示其坐標(biāo)。但是和空間中的普通點(diǎn)不一樣的是，它們允許出現(xiàn)的位置受到了一定的限制，具體到球面，可以
可以看一下它的參數(shù)方程：
可以看到，這些三維的坐標(biāo)實(shí)際上是由兩個(gè)變量和生成的，也可以說成是它的自由度是二，也正好對(duì)應(yīng)了它是一個(gè)二維的流形。有了這樣的感覺之后，再來看流形學(xué)習(xí)里經(jīng)
常用到的人臉的例子，就很自然了。下圖是Isomap論文里的一個(gè)結(jié)果：
這里的圖片來自同一張人臉（好吧，其實(shí)是人臉模型），每張圖片是 64×64 的灰度圖，如果把位圖按照列（或行）拼起來，就可以得到一個(gè) 4096 維的向量，這樣一來，每一張圖片就可以看成是 4096 維歐氏空間中的一個(gè)點(diǎn)。很顯然，并不是 4096 維空間中任意一個(gè)點(diǎn)都可以對(duì)應(yīng)于一張人臉圖片的，這就類似于球面的情形，我們可以假定所有可以是人臉的 4096 維向量實(shí)際上分布在一個(gè) d 維 (d < 4096) 的子空間中。而特定到Isomap的人臉這個(gè)例子，實(shí)際上我們知道所有的 698 張圖片是拍自同一個(gè)人臉（模型），不過是在不同的 pose 和光照下拍攝的，如果把 pose （上下和左右）當(dāng)作兩個(gè)自由度，而光照當(dāng)作一個(gè)自由度，那么這些圖片實(shí)際只有三個(gè)自由度，換句話說，存在一個(gè)類似于球面一樣的參數(shù)方程（當(dāng)然，解析式是沒法寫出來的），給定一組參數(shù)（也就是上下、左右的 pose 和光照這三個(gè)值），就可以生成出對(duì)應(yīng)的 4096 維的坐標(biāo)來。
換句話說，這是一個(gè)嵌入在 4096 維歐氏空間中的一個(gè) 3 維流形。
實(shí)際上，上面的那張圖就是Isomap將這個(gè)數(shù)據(jù)集從 4096 維映射到 3 維空間中，并顯示了其中 2 維的結(jié)果，圖中的小點(diǎn)就是每個(gè)人臉在這個(gè)二維空間中對(duì)應(yīng)的坐標(biāo)位置，其中一些標(biāo)紅圈的點(diǎn)被選出來，并在旁邊畫上了該點(diǎn)對(duì)應(yīng)的原始圖片，可以很直觀地看
出這兩個(gè)維度正好對(duì)應(yīng)了 pose 的兩個(gè)自由度平滑變化的結(jié)果。
就我目前所知，把流形引入到機(jī)器學(xué)習(xí)領(lǐng)域來主要有兩種用途：一是將原來在歐氏空間中適用的算法加以改造，使得它工作在流形上，直接或間接地對(duì)流形的結(jié)構(gòu)和性質(zhì)加以利用；二是直接分析流形的結(jié)構(gòu)，并試圖將其映射到一個(gè)歐氏空間中，再在得到的結(jié)果
上運(yùn)用以前適用于歐氏空間的算法來進(jìn)行學(xué)習(xí)。
這里Isomap正巧是一個(gè)非常典型的例子，因?yàn)樗鼘?shí)際上是通過“改造一種原本適用于歐
氏空間的算法”，達(dá)到了“將流形映射到一個(gè)歐氏空間”的目的。
Isomap所改造的這個(gè)方法叫做Multidimensional Scaling (MDS)，MDS 是一種降維方法，它的目的就是使得降維之后的點(diǎn)兩兩之間的距離盡量不變（也就是和在原是空間中對(duì)應(yīng)的兩個(gè)點(diǎn)之間的距離要差不多）。只是 MDS 是針對(duì)歐氏空間設(shè)計(jì)的，對(duì)于距離的計(jì)算也是使用歐氏距離來完成的。如果數(shù)據(jù)分布在一個(gè)流形上的話，歐氏距離就不適用了。 讓我們再回到地球——這個(gè)在三維空間中的二維流形，假設(shè)我們要在三維空間中計(jì)算北極點(diǎn)和南極點(diǎn)的距離，這很容易，就是兩點(diǎn)相連的線段的長度，可是，如果要在這個(gè)流形上算距離就不能這樣子算了，我們總不能從北極打個(gè)洞鉆到南極去吧？要沿著地球表面走才行，當(dāng)然，如果我隨便沿著什么路線走一遍，然后數(shù)出總共走了多少步作為距離，這是不成的，因?yàn)檫@樣一來如果我沿著不同的路線走，豈不是會(huì)得到不同的距離值？總而言之，我們現(xiàn)在需要一個(gè)新的定義在地球表面（流形）上的距離度量，理論上來說，任意滿足測度的 4 個(gè)條件的函數(shù)都可以被定義為距離，不過，為了和歐氏空間對(duì)應(yīng)起
來，這里選擇一個(gè)直線距離的推廣定義。
還記得初中學(xué)的“兩點(diǎn)之間，線段最短”嗎？現(xiàn)在，我們反過來說，把線段的概念推廣一下，變成“兩點(diǎn)之間最短的曲線是線段”，于是流形上的距離定義也就等同于歐氏空間了：流形上兩個(gè)點(diǎn)之間的距離就是連接兩個(gè)點(diǎn)的“線段”的長度。雖然只是置換了一個(gè)概念，但是現(xiàn)在兩者統(tǒng)一起來了，不過，在流形上的線段大概就不一定是“直”的了（于是直線也變成不一定是“直”的了），通常又稱作是“測地線”。對(duì)于球面這個(gè)簡單的流形來說，任意一條線段必定是在一個(gè)“大圓”上的，于是球面上的直線其實(shí)都是一些大圓，也造成了球面這個(gè)流形上沒有平行線等一系列尷尬的局面（任意兩條直線均相交），如果你看
過一些數(shù)學(xué)科普八卦類的書，應(yīng)該會(huì)回憶起不少東西啦！
回到Isomap，它主要做了一件事情，就是把 MDS 中原始空間中距離的計(jì)算從歐氏距離換為了流形上的測地距離。當(dāng)然，如果流形的結(jié)構(gòu)事先不知道的話，這個(gè)距離是沒法算的，于是Isomap通過將數(shù)據(jù)點(diǎn)連接起來構(gòu)成一個(gè)鄰接 Graph 來離散地近似原來的流形，而測地距離也相應(yīng)地通過 Graph 上的最短路徑來近似了。
流形學(xué)習(xí)
流形學(xué)習(xí)是個(gè)很廣泛的概念。這里我主要談的是自從2000年以后形成的流形學(xué)習(xí)概念和其主要代表方法。自從2000年以后，流形學(xué)習(xí)被認(rèn)為屬于非線性降維的一個(gè)分支。眾所周知，引導(dǎo)這一領(lǐng)域迅速發(fā)展的是2000年Science雜志上的兩篇文章: Isomap and LLE (Locally Linear Embedding)。
1. 流形學(xué)習(xí)的基本概念
那流形學(xué)習(xí)是什莫呢？為了好懂，我盡可能應(yīng)用少的數(shù)學(xué)概念來解釋這個(gè)東西。所謂流形（manifold）就是一般的幾何對(duì)象的總稱。比如人，有中國人、美國人等等；流形就包括各種維數(shù)的曲線曲面等。和一般的降維分析一樣，流形學(xué)習(xí)把一組在高維空間中的數(shù)據(jù)在低維空間中重新表示。和以往方法不同的是，在流形學(xué)習(xí)中有一個(gè)假設(shè)，就是所處理的數(shù)據(jù)采樣于一個(gè)潛在的流形上，或是說對(duì)于這組數(shù)據(jù)存在一個(gè)潛在的流形。 對(duì)于不同的方法，對(duì)于流形性質(zhì)的要求各不相同，這也就產(chǎn)生了在流形假設(shè)下的各種不同性質(zhì)的假設(shè)，比如在Laplacian
Eigenmaps中要假設(shè)這個(gè)流形是緊致黎曼流形等。對(duì)于描述流形上的點(diǎn)，我們要用坐標(biāo)，而流形上本身是沒有坐標(biāo)的，所以為了表示流形上的點(diǎn)，必須把流形放入外圍空間（ambient space）中，那末流形上的點(diǎn)就可以用外圍空間的坐標(biāo)來表示。比如R^3中的球面是個(gè)2維的曲面，因?yàn)榍蛎嫔现挥袃蓚�(gè)自由度，但是球面上的點(diǎn)一般是用外圍R^3空間中的坐標(biāo)表示的，所以我們看到的R^3中球面上的點(diǎn)有3個(gè)數(shù)來表示的。當(dāng)然球面還有柱坐標(biāo)球坐標(biāo)等表示。對(duì)于R^3中的球面來說，那末流形學(xué)習(xí)可以粗略的概括為給出R^3中的表示，在保持球面上點(diǎn)某些幾何性質(zhì)的條件下，找出找到一組對(duì)應(yīng)的內(nèi)蘊(yùn)坐標(biāo)（intrinsic coordinate）表示，顯然這個(gè)表示應(yīng)該是兩維的，因?yàn)榍蛎娴木S數(shù)是兩維的。這個(gè)過程也叫參數(shù)化（parameterization）。直觀上來說，就是把這個(gè)球面盡量好的展開在通過原點(diǎn)的平面上。在PAMI中，這樣的低維表示也叫內(nèi)蘊(yùn)特征（intrinsic feature）。一般外圍空間的維數(shù)也叫觀察維數(shù)，其表示也叫自然坐標(biāo)（外圍空間是歐式空間）表示,在統(tǒng)計(jì)中一般叫observation。
了解了流形學(xué)習(xí)的這個(gè)基礎(chǔ)，那末流形學(xué)習(xí)中的一些是非也就很自然了，這個(gè)下面穿插來說。由此，如果你想學(xué)好流形學(xué)習(xí)里的方法，你至少要了解一些微分流形和黎曼幾何的基本知識(shí)。
2. 代表方法
a) Isomap。
Josh Tenenbaum的Isomap開創(chuàng)了一個(gè)數(shù)據(jù)處理的新戰(zhàn)場。在沒有具體說Isomap之前，有必要先說說MDS（Multidimensional Scaling）這個(gè)方法。我們國內(nèi)的很多人知道PCA，卻很多人不知道MDS。PCA和MDS是相互對(duì)偶的兩個(gè)方法。MDS就是理論上保持歐式距離的一個(gè)經(jīng)典方法，MDS最早主要用于做數(shù)據(jù)的可視化。由于MDS得到的低維表示中心在原點(diǎn)，所以又可以說保持內(nèi)積。也就是說，用低維空間中的內(nèi)積近似高維空間中的距離。經(jīng)典的MDS方法，高維空間中的距離一般用歐式距離。
Isomap就是借窩生蛋。他的理論框架就是MDS，但是放在流形的理論框架內(nèi)，原始的距離換成了流形上的測地線（geodesic）距離。其它一模一樣。所謂的測地線，就是流形上加速度為零的曲線，等同于歐式空間中的直線。我們經(jīng)常聽到說測地線是流形上兩點(diǎn)之間距離最短的線。其實(shí)這末說是不嚴(yán)謹(jǐn)?shù)�。流形上兩點(diǎn)之間距離最短的線是測地線，但是反過來不一定對(duì)。另外，如果任意兩個(gè)點(diǎn)之間都存在一個(gè)測地線，那末這個(gè)流形必須是連通的鄰域都是凸的。Isomap就是把任意兩點(diǎn)的測地線距離（準(zhǔn)確地說是最短距離）作為流形的幾何描述，用MDS理論框架
理論上保持這個(gè)點(diǎn)與點(diǎn)之間的最短距離。在Isomap中，測地線距離就是用兩點(diǎn)之間圖上的最短距離來近似的，這方面的算法是一般計(jì)算機(jī)系中用的圖論中的經(jīng)典算法。
如果你曾細(xì)致地看過Isomap主頁上的matlab代碼，你就會(huì)發(fā)現(xiàn)那個(gè)代碼的實(shí)現(xiàn)復(fù)雜度遠(yuǎn)超與實(shí)際論文中敘述的算法。在那個(gè)代碼中，除了論文中寫出的算法外，還包括了 outlier detection和embedding scaling。這兩樣?xùn)|西，保證了運(yùn)行他們的程序得到了結(jié)果一般來說相對(duì)比較理想。但是，這在他們的算法中并沒有敘述。如果你直接按照他論文中的方法來實(shí)現(xiàn)，你可以體會(huì)一下這個(gè)結(jié)果和他們結(jié)果的差距。從此我們也可以看出，那幾個(gè)作者做學(xué)問的嚴(yán)謹(jǐn)態(tài)度，這是值得我們好好學(xué)習(xí)的。
另外比較有趣的是，Tenenbaum根本不是做與數(shù)據(jù)處理有關(guān)算法的人，他是做計(jì)算認(rèn)知科學(xué)（computational cognition science）的。在做這個(gè)方法的時(shí)候，他還在stanford，02年就去了
MIT開創(chuàng)一派，成了CoCoSci 的掌門人，他的組成長十分迅速。但是有趣的是，在Isomap之后，他包括他在MIT帶的學(xué)生就從來再也沒有做過類似的工作。其原因我今年夏天有所耳聞。他在今年參加 UCLA Alan Yuille 組織的一個(gè)summer school上說，（不是原文，是大意）我們經(jīng)常忘了做研究的原始出發(fā)點(diǎn)是什莫。他做Isomap就是為了找一個(gè)好的visual perception的方法，他還堅(jiān)持了他的方向和信仰，computational cognition，他沒有隨波逐流。而由他引導(dǎo)起來的 manifold learning 卻快速的發(fā)展成了一個(gè)新的方向。
這是一個(gè)值得我們好好思考的問題。我們做一個(gè)東西，選擇一個(gè)研究方向究竟是為了什莫。你考慮過嗎？
（當(dāng)然，此問題也在問我自己）
b) LLE (Locally linear Embedding)
LLE在作者寫出的表達(dá)式看,是個(gè)具有十分對(duì)稱美的方法. 這種看上去的對(duì)稱對(duì)于啟發(fā)人很重要。LLE的思想就是，一個(gè)流形在很小的局部鄰域上可以近似看成歐式的，就是局部線性的。那末，在小的局部鄰域上，一個(gè)點(diǎn)就可以用它周圍的點(diǎn)在最小二乘意義下最優(yōu)的線性表示。LLE把這個(gè)線性擬合的系數(shù)當(dāng)成這個(gè)流形局部幾何性質(zhì)的刻畫。那末一個(gè)好的低維表示，就應(yīng)該也具有同樣的局部幾何，所以利用同樣的線性表示的表達(dá)式，最終寫成一個(gè)二次型的形式，十分自然優(yōu)美。
注意在LLE出現(xiàn)的兩個(gè)加和優(yōu)化的線性表達(dá)，第一個(gè)是求每一點(diǎn)的線性表示系數(shù)的。雖然原始公式中是寫在一起的，但是求解時(shí)，是對(duì)每一個(gè)點(diǎn)分別來求得。第二個(gè)表示式，是已知所有點(diǎn)的線性表示系數(shù)，來求低維表示（或嵌入embedding）的，他是一個(gè)整體求解的過程。這兩個(gè)表達(dá)式的轉(zhuǎn)化正好中間轉(zhuǎn)了個(gè)彎，使一些人困惑了，特別后面一個(gè)公式寫成一個(gè)二次型的過程并不是那末直觀，很多人往往在此卡住，而阻礙了全面的理解。我推薦大家去精讀 Saul 在
JMLR上的那篇LLE的長文。那篇文章無論在方法表達(dá)還是英文書寫，我認(rèn)為都是精品，值得好好玩味學(xué)習(xí)。
另外值得強(qiáng)調(diào)的是，對(duì)于每一點(diǎn)處擬合得到的系數(shù)歸一化的操作特別重要，如果沒有這一步，這個(gè)算法就沒有效果。但是在原始論文中，他們是為了保持?jǐn)?shù)據(jù)在平行移動(dòng)下embedding不變。 LLE的matlab代碼寫得簡潔明了，是一個(gè)樣板。
在此有必要提提Lawrence Saul這個(gè)人。在Isomap和LLE的作者們中，Saul算是唯一一個(gè)以流形學(xué)習(xí)（并不限于）為研究對(duì)象開創(chuàng)學(xué)派的人。Saul早年主要做參數(shù)模型有關(guān)的算法。自從LLE以后，坐陣UPen創(chuàng)造了一個(gè)個(gè)佳績。主要成就在于他的兩個(gè)出色學(xué)生，Kilian Weinberger和 Fei Sha，做的方法。拿了很多獎(jiǎng)，在此不多說，可以到他主頁上去看。Weinberger把學(xué)習(xí)核矩陣引入到流形學(xué)習(xí)中來。他的這個(gè)方法在流形學(xué)習(xí)中影響到不是很顯著，卻是在 convex optimization 中人人得知。Fei Sha不用多說了，machine learning中一個(gè)閃亮的新星，中國留學(xué)生之驕傲。現(xiàn)在他們一個(gè)在Yahoo,一個(gè)在Jordan手下做PostDoc。
c) Laplacian Eigenmaps
要說哪一個(gè)方法被做的全面，那莫非LE莫屬。如果只說LE這個(gè)方法本身，是不新的，許多年前在做mesh相關(guān)的領(lǐng)域就開始這莫用。但是放在黎曼幾何的框架內(nèi)，給出完整的幾何分析的，應(yīng)該是Belkin和Niyogi（LE作者）的功勞。
LE的基本思想就是用一個(gè)無向有權(quán)圖來描述一個(gè)流形，然后通過用圖的嵌入（graph
embedding）來找低維表示。說白了，就是保持圖的局部鄰接關(guān)系的情況把這個(gè)圖從高維空間中重新畫在一個(gè)低維空間中（graph drawing）。
在至今為止的流行學(xué)習(xí)的典型方法中，LE是速度最快、效果相對(duì)來說不怎莫樣的。但是LE有一個(gè)其他方法沒有的特點(diǎn)，就是如果出現(xiàn)outlier情況下，它的魯棒性（robustness）特別好。 后來Belkin和Niyogi又分析了LE的收斂性。大家不要忽視這個(gè)問題，很重要。鼓勵(lì)有興趣數(shù)學(xué)功底不錯(cuò)的人好好看看這篇文章。
d) Hessian Eigenmaps
如果你對(duì)黎曼幾何不懂，基本上看不懂這個(gè)方法。又加作者表達(dá)的抽象，所以絕大多數(shù)人對(duì)這個(gè)方法了解不透徹。在此我就根據(jù)我自己的理解說說這個(gè)方法。
這個(gè)方法有兩個(gè)重點(diǎn)：（1）如果一個(gè)流形是局部等距（isometric）歐式空間中一個(gè)開子集的，那末它的Hessian矩陣具有d+1維的零空間。（2）在每一點(diǎn)處，Hessian系數(shù)的估計(jì)。
首先作者是通過考察局部Hessian的二次型來得出結(jié)論的，如果一個(gè)流形局部等距于歐式空間中的一個(gè)開子集，那末由這個(gè)流形patch 到開子集到的映射函數(shù)是一個(gè)線性函數(shù)，線性函數(shù)的二次混合導(dǎo)數(shù)為零，所以局部上由Hessian系數(shù)構(gòu)成的二次型也為零，這樣把每一點(diǎn)都考慮到，過渡到全局的Hessian矩陣就有d+1維的零空間，其中一維是常函數(shù)構(gòu)成的，也就是1向量。其它的d維子空間構(gòu)成等距坐標(biāo)。這就是理論基礎(chǔ)的大意，當(dāng)然作者在介紹的時(shí)候，為了保持理論嚴(yán)謹(jǐn)，作了一個(gè)由切坐標(biāo)到等距坐標(biāo)的過渡。
另外一個(gè)就是局部上Hessian系數(shù)的估計(jì)問題。我在此引用一段話：
If you approximate a function f(x) by a quadratic expansion
f(x) = f(0) + (grad f)^T x + x^T Hf x + rem
then the hessian is what you get for the quadratic component. So simply over a given neighborhood, develop the operator that approximates a function by its projection on 1, x_1,...,x_k, x_1^2,...,x_k^2, x_1*x_2,... ,x_{k-1}*x_{k}. Extract the component of the operator that delivers the projection on x_1^2,...,x_k^2, x_1*x_2,... ,x_{k-1}*x_{k}.
這段話是我在初學(xué)HE時(shí)候，寫信問Dave Donoho，他給我的回信。希望大家領(lǐng)會(huì)。如果你了解了上述基本含義，再去細(xì)看兩遍原始論文，也許會(huì)有更深的理解。由于HE牽扯到二階導(dǎo)數(shù)的估計(jì)，所以對(duì)噪聲很敏感。另外，HE的原始代碼中在計(jì)算局部切坐標(biāo)的時(shí)候，用的是奇異值分解(SVD)，所以如果想用他們的原始代碼跑一下例如圖像之類的真實(shí)數(shù)據(jù)，就特別的慢。其實(shí)把他們的代碼改一下就可以了，利用一般PCA的快速計(jì)算方法，計(jì)算小尺寸矩陣的特征向量即可。還有，在原始代碼中，他把Hessian系數(shù)歸一化了，這也就是為什莫他們叫這個(gè)方法為 Hessian LLE 的原因之一。
Dave Dohono是學(xué)術(shù)界公認(rèn)的大牛，在流形學(xué)習(xí)這一塊，是他帶著他的一個(gè)學(xué)生做的，Carrie Grimes�，F(xiàn)在這個(gè)女性研究員在Google做 project leader，學(xué)術(shù)界女生同學(xué)的楷模 : )
e) LTSA (Local tangent space alignment)
很榮幸，這個(gè)是國內(nèi)學(xué)者（浙江大學(xué)數(shù)學(xué)系的老師ZHANG Zhenyue）為第一作者做的一個(gè)在流行學(xué)習(xí)中最出色的方法。由于這個(gè)方法是由純數(shù)學(xué)做數(shù)值分析出身的老師所做，所以原始論文看起來公式一大堆，好像很難似的。其實(shí)這個(gè)方法非常直觀簡單。
象 Hessian Eigenmaps 一樣，流形的局部幾何表達(dá)先用切坐標(biāo)，也就是PCA的主子空間中的坐標(biāo)。那末對(duì)于流形一點(diǎn)處的切空間，它是線性子空間，所以可以和歐式空間中的一個(gè)開子集建立同構(gòu)關(guān)系，最簡單的就是線性變換。在微分流形中，就叫做切映射 (tangential map)，是個(gè)很自然很基礎(chǔ)的概念。把切坐標(biāo)求出來，建立出切映射，剩下的就是數(shù)值計(jì)算了。最終這個(gè)算法劃歸為一個(gè)很簡單的跌代加和形式。如果你已經(jīng)明白了MDS，那末你就很容易明白，這個(gè)算法本質(zhì)上就是MDS的從局部到整體的組合。
這里主要想重點(diǎn)強(qiáng)調(diào)一下，那個(gè)論文中使用的一個(gè)從局部幾何到整體性質(zhì)過渡的alignment技術(shù)。在spectral method（特征分解的）中，這個(gè)alignment方法特別有用。只要在數(shù)據(jù)的局部鄰域上你的方法可以寫成一個(gè)二次項(xiàng)的形式，就可以用。
其實(shí)LTSA最早的版本是在02年的DOCIS上。這個(gè)alignment方法在02年底Brand的 charting a manifold 中也出現(xiàn)，隱含在Hessian Eigenmaps中。在HE中，作者在從局部的Hessian矩陣過渡到全局的Hessian矩陣時(shí)，用了兩層加號(hào)，其中就隱含了這個(gè) alignment方法。后來國內(nèi)一個(gè)叫 ZHAO Deli 的學(xué)生用這個(gè)方法重新寫了LLE，發(fā)在Pattern Recognition上，一個(gè)短文。可以預(yù)見的是，這個(gè)方法還會(huì)被發(fā)揚(yáng)光大。
ZHA Hongyuan 后來專門作了一篇文章來分析 alignment matrix 的譜性質(zhì)，有興趣地可以找來看看。
f) MVU (Maximum variance unfolding)
這個(gè)方法剛發(fā)出來以后，名字叫做Semi-definite Embedding (SDE)。構(gòu)建一個(gè)局部的稀疏歐式距離矩陣以后，作者通過一定約束條件（主要是保持距離）來學(xué)習(xí)到一個(gè)核矩陣，對(duì)這個(gè)核矩陣做PCA就得到保持距離的 embedding，就這莫簡單。但是就是這個(gè)方法得了多少獎(jiǎng)，自己可以去找找看。個(gè)人觀點(diǎn)認(rèn)為，這個(gè)方法之所以被如此受人賞識(shí)，無論在vision還是在learning，除了給流形學(xué)習(xí)這一領(lǐng)域帶來了一個(gè)新的解決問題的工具之外，還有兩個(gè)重點(diǎn)，一是核方法（kernel），二是半正定規(guī)劃（semi-definite programming），這兩股風(fēng)無論在哪個(gè)方向（learning and Vision）上都吹得正猛。
g) S-Logmaps
這個(gè)方法不太被人所知，但是我認(rèn)為這個(gè)是流形學(xué)習(xí)發(fā)展中的一個(gè)典型的方法（其實(shí)其他還有很多人也這莫認(rèn)為）。就效果來說，這個(gè)方法不算好，說它是一個(gè)典型的方法，是因?yàn)檫@個(gè)方法應(yīng)用了黎曼幾何中一個(gè)很直觀的性質(zhì)。這個(gè)性質(zhì)和法坐標(biāo)(normal coordinate)、指數(shù)映射(exponential map)和距離函數(shù)(distance function)有關(guān)。
如果你了解黎曼幾何，你會(huì)知道，對(duì)于流形上的一條測地線，如果給定初始點(diǎn)和初始點(diǎn)處測地線的切方向，那莫這個(gè)測地線就可以被唯一確定。這是因?yàn)樵谶@些初始條件下，描述測地線的偏微分方程的解是唯一的。那末流形上的一條測地線就可以和其起點(diǎn)處的切平面上的點(diǎn)建立一個(gè)對(duì)應(yīng)關(guān)系。我們可以在這個(gè)切平面上找到一點(diǎn)，這個(gè)點(diǎn)的方向就是這個(gè)測地線在起點(diǎn)處的切方向，其長度等于這個(gè)測地線上的長。這樣的一個(gè)對(duì)應(yīng)關(guān)系在局部上是一一對(duì)應(yīng)的。那末這個(gè)在切平面上的對(duì)應(yīng)點(diǎn)在切平面中就有一個(gè)坐標(biāo)表示，這個(gè)表示就叫做測地線上對(duì)應(yīng)點(diǎn)的法坐標(biāo)表示（有的也叫指數(shù)坐標(biāo)）。那末反過來，我們可以把切平面上的點(diǎn)映射到流形上，這個(gè)映射過程就叫做指數(shù)映射（Logmap就倒過來）。如果流形上每一個(gè)點(diǎn)都可以這樣在同一個(gè)切平面上表示出來，那末我們就可以得到保持測地線長度的低維表示。如果這樣做得到，流形必須可以被單坐標(biāo)系統(tǒng)所覆蓋。
如果給定流形上的采樣點(diǎn)，如果要找到法坐標(biāo)，我們需要知道兩個(gè)東西，一是測地線距離，二是每個(gè)測地線在起點(diǎn)處的切方向。第一個(gè)東西好弄，利用Isomap中的方法直接就可以解決，關(guān)鍵是第二個(gè)。第二個(gè)作者利用了距離函數(shù)的梯度，這個(gè)梯度和那個(gè)切方向是一個(gè)等價(jià)的關(guān)系，一般的黎曼幾何書中都有敘述。作者利用一個(gè)局部切坐標(biāo)的二次泰勒展開來近似距離函數(shù)，而距離是知道的，就是測地線距離，局部切坐標(biāo)也知道，那末通過求一個(gè)簡單的最小二乘問題就可以估計(jì)出梯度方向。
如果明白這個(gè)方法的幾何原理，你再去看那個(gè)方法的結(jié)果，你就會(huì)明白為什莫在距離中心點(diǎn)比較遠(yuǎn)的點(diǎn)的embedding都可以清楚地看到在一條條線上，效果不太好。
最近這個(gè)思想被北大的一個(gè)年輕的老師 LIN Tong 發(fā)揚(yáng)光大，就是ECCV‘06上的那篇，還有即將刊登出的TPAMI上的 Riemannian Manifold Learning，實(shí)為國內(nèi)研究學(xué)者之榮幸。Lin的方法效果非常好，但是雖然取名叫Riemannian，沒有應(yīng)用到黎曼幾何本身的性質(zhì)，這樣使他的方法更容易理解。
Lin也是以一個(gè)切空間為基準(zhǔn)找法坐標(biāo)，這個(gè)出發(fā)點(diǎn)和思想和Brun（S-Logmaps）的是一樣的。但是Lin全是在局部上操作的，在得出切空間原點(diǎn)處局部鄰域的法坐標(biāo)以后，Lin采用逐步向外擴(kuò)展的方法找到其他點(diǎn)的法坐標(biāo)，在某一點(diǎn)處，保持此點(diǎn)到它鄰域點(diǎn)的歐式距離和夾角，然后轉(zhuǎn)化成一個(gè)最小二乘問題求出此點(diǎn)的法坐標(biāo)，這樣未知的利用已知的逐步向外擴(kuò)展。說白了就像縫網(wǎng)一樣，從幾個(gè)臨近的已知點(diǎn)開始，逐漸向外擴(kuò)散的縫。效果好是必然的。
淺談流形學(xué)習(xí)
bypluskid, on 2010-05-29, in Machine Learning76 comments
總覺得即使是“淺談”兩個(gè)字，還是讓這個(gè)標(biāo)
題有些過大了，更何況我自己也才剛剛接觸這么一個(gè)領(lǐng)域。不過懶得想其他標(biāo)題了，想起來要扯一下這個(gè)話題，也是因?yàn)楹团笥蚜钠鹞易约鹤罱谧龅姆较颉anifold Learning 或者僅僅 Manifold 本身通常就聽起來頗有些深?yuàn)W的感覺，不過如果并不是想要進(jìn)行嚴(yán)格的理論推導(dǎo)的話，也可以從許多直觀的例子得到一些感性的認(rèn)識(shí)，正好我也就借這個(gè)機(jī)會(huì)來簡單地談一下這個(gè)話題吧，或者說至少是我到目前為止對(duì)這它的認(rèn)識(shí)。 這兩個(gè)詞，在談 Manifold 之前，不妨先說說 Learning ，也就是 Machine Learning 。而說道 Machine Learning 而不提一下 Artificial Intelligence 的話似乎又顯得有些不厚道。人說 AI 是一門最悲劇的學(xué)科，因?yàn)槊慨?dāng)它的一個(gè)子領(lǐng)域發(fā)展得像模像樣之后，就立馬自立門戶，從此和 AI “再無瓜葛”了，而 Machine Learning 大概要算是最新的一個(gè)典型吧。這就讓人有點(diǎn)奇怪，比如說數(shù)學(xué)，分門別類總算是夠多了吧？可以不管怎么分，大家兄弟姐妹也都還承認(rèn)自己是叫“數(shù)學(xué)”的。那 AI 呢？我覺得這里有很大一部分
是它自身定位的問題。
反正現(xiàn)在我是不太清楚 AI 是做什么的，不知道其他人到底清楚不清楚。Wikipedia 上
說 Artificial intelligence (AI) is the intelligence of machines and the branch of computer
science that aims to create it.
可是這相當(dāng)于一個(gè) tautology ，因?yàn)榈降资裁从质莟he intelligence of machines呢？一開始的時(shí)候，大牛們都野心勃勃，而且好像也是信心滿滿，就好像曾經(jīng)廣泛認(rèn)為“牛頓定理揭示了宇宙真理，科學(xué)剩下的事情只要按照公式來做計(jì)算就可以了”一樣，大家可能覺得，不出幾十年，人類就可以不用思考，交給 AI 來做了。不過我這里并不想再多說諸如什么是“思考”，什么是“智能”之類的以及隨之而來的“圖靈測試”之類的話題。我想說的是，到頭來，AI 到底是什么，這還是一個(gè)問題，或者說，AI 在一開始定了一個(gè)過高的目標(biāo)，幾十年后，發(fā)現(xiàn)情況并不像當(dāng)年那么樂觀，卻又有些下不了臺(tái)了。
這個(gè)時(shí)候，AI 的一些旁枝或者子領(lǐng)域果斷放下面子，丟掉了那個(gè)近乎玄幻的目標(biāo)，逐漸發(fā)展成為“正�！钡膶W(xué)科，所以也就不再好稱為 AI 了。或者說現(xiàn)在的 AI 有兩個(gè)意思，一個(gè)廣義的 AI ，包括了所有相關(guān)的以及派生的領(lǐng)域，另一個(gè)則是狹義的或者經(jīng)典的 AI ，專門指那些仍然在執(zhí)著地追求著真正的“智能”的部分，或者說得不好聽一點(diǎn)，就
是剩下的部分。
Machine Learning 作為離家出走的典型，雖然名字里帶了 Learning 一個(gè)詞，讓人乍一看覺得和 Intelligence 相比不過是換了個(gè)說法而已，然而事實(shí)上這里的 Learning 的意義要樸素得多。我們來看一看 Machine Learning 的典型的流程就知道了，其實(shí)有時(shí)候覺得和應(yīng)用數(shù)學(xué)或者更通俗的數(shù)學(xué)建模有些類似，通常我們會(huì)有需要分析或者處理的數(shù)據(jù)，根據(jù)一些經(jīng)驗(yàn)和一些假設(shè)，我們可以構(gòu)建一個(gè)模型，這個(gè)模型會(huì)有一些參數(shù)（即使是非參數(shù)化方法，也是可以類似地看待的），根據(jù)數(shù)據(jù)來求解模型參數(shù)的過程，就叫做 Parameter Estimation ，或者 Model Fitting ，但是搞機(jī)器學(xué)習(xí)的人，通常把它叫做 Learning （或者，換一個(gè)角度，叫 Training）——因?yàn)楦鶕?jù)數(shù)據(jù)歸納出一個(gè)有用的模型，這和我們?nèi)祟悺皩W(xué)習(xí)”的過程還是挺類似的吧。不過，如果拋開無聊的摳字眼游戲的話，我們可以看到，Machine Learning 已經(jīng)拋棄了“智能”的高帽子，它的目的就是要解決具
體的問題——而并不關(guān)心是否是通過一種“智能”的方式類解決的。
說到這里，其實(shí)我們構(gòu)造模型就類似于寫一個(gè)類，數(shù)據(jù)就是構(gòu)造函數(shù)的參數(shù)，Learning 就是構(gòu)造函數(shù)運(yùn)行的過程，成功構(gòu)造一個(gè)對(duì)象之后，我們就完成了學(xué)習(xí)。一些 Machine Learning 的問題到這一步就結(jié)束了，另一些情況還會(huì)使用得到的模型（對(duì)象）對(duì)后來的數(shù)據(jù)進(jìn)行一些處理，通常會(huì)是Inferencing。到這個(gè)時(shí)候，又有些像統(tǒng)計(jì)里的東西了，所謂“統(tǒng)計(jì)推斷”嘛。其實(shí)原本統(tǒng)計(jì)和機(jī)器學(xué)習(xí)研究的不少問題就是交叉在一起的，不過兩派人從不同的角度來看待同樣的問題。而且，也確實(shí)有 Statistical Learning 這么一個(gè)說法存在的，可以把他看成是 Machine Learning 的一個(gè)子領(lǐng)域（或者是一個(gè)分子或
者甚至就是 Machine Learning 本身）。
到這里，如果你還沒有因?yàn)椴粩嗟負(fù)缸盅鄱鵁┰甑脑挘?/p>
我已經(jīng)忍無可忍了。所以，我就假定你已經(jīng)了解了什么叫 Learning ，或者是已經(jīng)惡心到懶得去了解了。于是我們轉(zhuǎn)入下一個(gè)話題：流形，也就是 Manifold 。不知道你有沒有為我在本文開頭放上的那個(gè)地球的圖片感到困惑？這是因?yàn)榍蛎媸且粋�(gè)很典型的流
形的例子，而地球就是一個(gè)很典型的“球面”啦（姑且當(dāng)作球面好啦）。
有時(shí)候經(jīng)常會(huì)在 paper 里看到“嵌入在高維空間中的低維流形”，不過高維的數(shù)據(jù)對(duì)于我們這些可憐的低維生物來說總是很難以想像，所以最直觀的例子通常都會(huì)是嵌入在三維空間中的二維或者一維流行。比如說一塊布，可以把它看成一個(gè)二維平面，這是一個(gè)
二維的歐氏空間，現(xiàn)在我們（在三維）中把它扭一扭，它就變成了一個(gè)流形（當(dāng)然，不
扭的時(shí)候，它也是一個(gè)流形，歐氏空間是流形的一種特殊情況）。
所以，直觀上來講，一個(gè)流形好比是一個(gè) d 維的空間，在一個(gè) m 維的空間中 (m > d) 被扭曲之后的結(jié)果。需要注意的是，流形并不是一個(gè)“形狀”，而是一個(gè)“空間”，如果你覺得“扭曲的空間”難以想象，那么請(qǐng)?jiān)倩貞浿耙粔K布的例子。如果我沒弄錯(cuò)的話，廣義相對(duì)論似乎就是把我們的時(shí)空當(dāng)作一個(gè)四維流（空間三維加上時(shí)間一維）形來研究的，引力就是這個(gè)流形扭曲的結(jié)果。當(dāng)然，這些都是直觀上的概念，其實(shí)流形并不需要依靠嵌入在一個(gè)“外圍空間”而存在，稍微正式一點(diǎn)來說，一個(gè) d 維的流形就是一個(gè)在任意點(diǎn)出局部同胚于（簡單地說，就是正逆映射都是光滑的一一映射）歐氏空間。
實(shí)際上，正是這種局部與歐氏空間的同
胚給我們帶來了很多好處，這使得我們在日常生活中許許多多的幾何問題都可以使用簡單的歐氏幾何來解決，因?yàn)楹偷厍虻某叨缺绕饋�，我們的日常生活就算是一個(gè)很小的局部啦——我突然想起《七龍珠》里的那個(gè)界王住的那種私人小星球，走幾步就要繞一圈的感覺，看來界王不僅要體力好（那上面重力似乎是地球的十倍），而且腦力也要好，
初中學(xué)的必須是黎曼幾何了！
那么，除了地球這種簡單的例子，實(shí)際應(yīng)用中的數(shù)據(jù)，怎么知道它是不是一個(gè)流形呢？于是不妨又回歸直觀的感覺。再從球面說起，如果我們事先不知道球面的存在，那么球面上的點(diǎn)，其實(shí)就是三維歐氏空間上的點(diǎn)，可以用一個(gè)三元組來表示其坐標(biāo)。但是和空間中的普通點(diǎn)不一樣的是，它們允許出現(xiàn)的位置受到了一定的限制，具體到球面，可以
可以看一下它的參數(shù)方程：
可以看到，這些三維的坐標(biāo)實(shí)際上是由兩個(gè)變量和生成的，也可以說成是它的自由度是二，也正好對(duì)應(yīng)了它是一個(gè)二維的流形。有了這樣的感覺之后，再來看流形學(xué)習(xí)里經(jīng)
常用到的人臉的例子，就很自然了。下圖是Isomap論文里的一個(gè)結(jié)果：
這里的圖片來自同一張人臉（好吧，其實(shí)是人臉模型），每張圖片是 64×64 的灰度圖，如果把位圖按照列（或行）拼起來，就可以得到一個(gè) 4096 維的向量，這樣一來，每一張圖片就可以看成是 4096 維歐氏空間中的一個(gè)點(diǎn)。很顯然，并不是 4096 維空間中任意一個(gè)點(diǎn)都可以對(duì)應(yīng)于一張人臉圖片的，這就類似于球面的情形，我們可以假定所有可以是人臉的 4096 維向量實(shí)際上分布在一個(gè) d 維 (d < 4096) 的子空間中。而特定到Isomap的人臉這個(gè)例子，實(shí)際上我們知道所有的 698 張圖片是拍自同一個(gè)人臉（模型），不過是在不同的 pose 和光照下拍攝的，如果把 pose （上下和左右）當(dāng)作兩個(gè)自由度，而光照當(dāng)作一個(gè)自由度，那么這些圖片實(shí)際只有三個(gè)自由度，換句話說，存在一個(gè)類似于球面一樣的參數(shù)方程（當(dāng)然，解析式是沒法寫出來的），給定一組參數(shù)（也就是上下、左右的 pose 和光照這三個(gè)值），就可以生成出對(duì)應(yīng)的 4096 維的坐標(biāo)來。
換句話說，這是一個(gè)嵌入在 4096 維歐氏空間中的一個(gè) 3 維流形。
實(shí)際上，上面的那張圖就是Isomap將這個(gè)數(shù)據(jù)集從 4096 維映射到 3 維空間中，并顯示了其中 2 維的結(jié)果，圖中的小點(diǎn)就是每個(gè)人臉在這個(gè)二維空間中對(duì)應(yīng)的坐標(biāo)位置，其中一些標(biāo)紅圈的點(diǎn)被選出來，并在旁邊畫上了該點(diǎn)對(duì)應(yīng)的原始圖片，可以很直觀地看
出這兩個(gè)維度正好對(duì)應(yīng)了 pose 的兩個(gè)自由度平滑變化的結(jié)果。
就我目前所知，把流形引入到機(jī)器學(xué)習(xí)領(lǐng)域來主要有兩種用途：一是將原來在歐氏空間中適用的算法加以改造，使得它工作在流形上，直接或間接地對(duì)流形的結(jié)構(gòu)和性質(zhì)加以利用；二是直接分析流形的結(jié)構(gòu)，并試圖將其映射到一個(gè)歐氏空間中，再在得到的結(jié)果
上運(yùn)用以前適用于歐氏空間的算法來進(jìn)行學(xué)習(xí)。
這里Isomap正巧是一個(gè)非常典型的例子，因?yàn)樗鼘?shí)際上是通過“改造一種原本適用于歐
氏空間的算法”，達(dá)到了“將流形映射到一個(gè)歐氏空間”的目的。
Isomap所改造的這個(gè)方法叫做Multidimensional Scaling (MDS)，MDS 是一種降維方法，它的目的就是使得降維之后的點(diǎn)兩兩之間的距離盡量不變（也就是和在原是空間中對(duì)應(yīng)的兩個(gè)點(diǎn)之間的距離要差不多）。只是 MDS 是針對(duì)歐氏空間設(shè)計(jì)的，對(duì)于距離的計(jì)算也是使用歐氏距離來完成的。如果數(shù)據(jù)分布在一個(gè)流形上的話，歐氏距離就不適用了。 讓我們再回到地球——這個(gè)在三維空間中的二維流形，假設(shè)我們要在三維空間中計(jì)算北極點(diǎn)和南極點(diǎn)的距離，這很容易，就是兩點(diǎn)相連的線段的長度，可是，如果要在這個(gè)流形上算距離就不能這樣子算了，我們總不能從北極打個(gè)洞鉆到南極去吧？要沿著地球表面走才行，當(dāng)然，如果我隨便沿著什么路線走一遍，然后數(shù)出總共走了多少步作為距離，這是不成的，因?yàn)檫@樣一來如果我沿著不同的路線走，豈不是會(huì)得到不同的距離值？總而言之，我們現(xiàn)在需要一個(gè)新的定義在地球表面（流形）上的距離度量，理論上來說，任意滿足測度的 4 個(gè)條件的函數(shù)都可以被定義為距離，不過，為了和歐氏空間對(duì)應(yīng)起
來，這里選擇一個(gè)直線距離的推廣定義。
還記得初中學(xué)的“兩點(diǎn)之間，線段最短”嗎？現(xiàn)在，我們反過來說，把線段的概念推廣一下，變成“兩點(diǎn)之間最短的曲線是線段”，于是流形上的距離定義也就等同于歐氏空間了：流形上兩個(gè)點(diǎn)之間的距離就是連接兩個(gè)點(diǎn)的“線段”的長度。雖然只是置換了一個(gè)概念，但是現(xiàn)在兩者統(tǒng)一起來了，不過，在流形上的線段大概就不一定是“直”的了（于是直線也變成不一定是“直”的了），通常又稱作是“測地線”。對(duì)于球面這個(gè)簡單的流形來說，任意一條線段必定是在一個(gè)“大圓”上的，于是球面上的直線其實(shí)都是一些大圓，也造成了球面這個(gè)流形上沒有平行線等一系列尷尬的局面（任意兩條直線均相交），如果你看
過一些數(shù)學(xué)科普八卦類的書，應(yīng)該會(huì)回憶起不少東西啦！
回到Isomap，它主要做了一件事情，就是把 MDS 中原始空間中距離的計(jì)算從歐氏距離換為了流形上的測地距離。當(dāng)然，如果流形的結(jié)構(gòu)事先不知道的`話，這個(gè)距離是沒法算的，于是Isomap通過將數(shù)據(jù)點(diǎn)連接起來構(gòu)成一個(gè)鄰接 Graph 來離散地近似原來的流形，而測地距離也相應(yīng)地通過 Graph 上的最短路徑來近似了。
流形學(xué)習(xí)
流形學(xué)習(xí)是個(gè)很廣泛的概念。這里我主要談的是自從2000年以后形成的流形學(xué)習(xí)概念和其主要代表方法。自從2000年以后，流形學(xué)習(xí)被認(rèn)為屬于非線性降維的一個(gè)分支。眾所周知，引導(dǎo)這一領(lǐng)域迅速發(fā)展的是2000年Science雜志上的兩篇文章: Isomap and LLE (Locally Linear Embedding)。
1. 流形學(xué)習(xí)的基本概念
那流形學(xué)習(xí)是什莫呢？為了好懂，我盡可能應(yīng)用少的數(shù)學(xué)概念來解釋這個(gè)東西。所謂流形（manifold）就是一般的幾何對(duì)象的總稱。比如人，有中國人、美國人等等；流形就包括各種維數(shù)的曲線曲面等。和一般的降維分析一樣，流形學(xué)習(xí)把一組在高維空間中的數(shù)據(jù)在低維空間中重新表示。和以往方法不同的是，在流形學(xué)習(xí)中有一個(gè)假設(shè)，就是所處理的數(shù)據(jù)采樣于一個(gè)潛在的流形上，或是說對(duì)于這組數(shù)據(jù)存在一個(gè)潛在的流形。 對(duì)于不同的方法，對(duì)于流形性質(zhì)的要求各不相同，這也就產(chǎn)生了在流形假設(shè)下的各種不同性質(zhì)的假設(shè)，比如在Laplacian
Eigenmaps中要假設(shè)這個(gè)流形是緊致黎曼流形等。對(duì)于描述流形上的點(diǎn)，我們要用坐標(biāo)，而流形上本身是沒有坐標(biāo)的，所以為了表示流形上的點(diǎn)，必須把流形放入外圍空間（ambient space）中，那末流形上的點(diǎn)就可以用外圍空間的坐標(biāo)來表示。比如R^3中的球面是個(gè)2維的曲面，因?yàn)榍蛎嫔现挥袃蓚�(gè)自由度，但是球面上的點(diǎn)一般是用外圍R^3空間中的坐標(biāo)表示的，所以我們看到的R^3中球面上的點(diǎn)有3個(gè)數(shù)來表示的。當(dāng)然球面還有柱坐標(biāo)球坐標(biāo)等表示。對(duì)于R^3中的球面來說，那末流形學(xué)習(xí)可以粗略的概括為給出R^3中的表示，在保持球面上點(diǎn)某些幾何性質(zhì)的條件下，找出找到一組對(duì)應(yīng)的內(nèi)蘊(yùn)坐標(biāo)（intrinsic coordinate）表示，顯然這個(gè)表示應(yīng)該是兩維的，因?yàn)榍蛎娴木S數(shù)是兩維的。這個(gè)過程也叫參數(shù)化（parameterization）。直觀上來說，就是把這個(gè)球面盡量好的展開在通過原點(diǎn)的平面上。在PAMI中，這樣的低維表示也叫內(nèi)蘊(yùn)特征（intrinsic feature）。一般外圍空間的維數(shù)也叫觀察維數(shù)，其表示也叫自然坐標(biāo)（外圍空間是歐式空間）表示,在統(tǒng)計(jì)中一般叫observation。
了解了流形學(xué)習(xí)的這個(gè)基礎(chǔ)，那末流形學(xué)習(xí)中的一些是非也就很自然了，這個(gè)下面穿插來說。由此，如果你想學(xué)好流形學(xué)習(xí)里的方法，你至少要了解一些微分流形和黎曼幾何的基本知識(shí)。
2. 代表方法
a) Isomap。
Josh Tenenbaum的Isomap開創(chuàng)了一個(gè)數(shù)據(jù)處理的新戰(zhàn)場。在沒有具體說Isomap之前，有必要先說說MDS（Multidimensional Scaling）這個(gè)方法。我們國內(nèi)的很多人知道PCA，卻很多人不知道MDS。PCA和MDS是相互對(duì)偶的兩個(gè)方法。MDS就是理論上保持歐式距離的一個(gè)經(jīng)典方法，MDS最早主要用于做數(shù)據(jù)的可視化。由于MDS得到的低維表示中心在原點(diǎn)，所以又可以說保持內(nèi)積。也就是說，用低維空間中的內(nèi)積近似高維空間中的距離。經(jīng)典的MDS方法，高維空間中的距離一般用歐式距離。
Isomap就是借窩生蛋。他的理論框架就是MDS，但是放在流形的理論框架內(nèi)，原始的距離換成了流形上的測地線（geodesic）距離。其它一模一樣。所謂的測地線，就是流形上加速度為零的曲線，等同于歐式空間中的直線。我們經(jīng)常聽到說測地線是流形上兩點(diǎn)之間距離最短的線。其實(shí)這末說是不嚴(yán)謹(jǐn)?shù)�。流形上兩點(diǎn)之間距離最短的線是測地線，但是反過來不一定對(duì)。另外，如果任意兩個(gè)點(diǎn)之間都存在一個(gè)測地線，那末這個(gè)流形必須是連通的鄰域都是凸的。Isomap就是把任意兩點(diǎn)的測地線距離（準(zhǔn)確地說是最短距離）作為流形的幾何描述，用MDS理論框架
理論上保持這個(gè)點(diǎn)與點(diǎn)之間的最短距離。在Isomap中，測地線距離就是用兩點(diǎn)之間圖上的最短距離來近似的，這方面的算法是一般計(jì)算機(jī)系中用的圖論中的經(jīng)典算法。
如果你曾細(xì)致地看過Isomap主頁上的matlab代碼，你就會(huì)發(fā)現(xiàn)那個(gè)代碼的實(shí)現(xiàn)復(fù)雜度遠(yuǎn)超與實(shí)際論文中敘述的算法。在那個(gè)代碼中，除了論文中寫出的算法外，還包括了 outlier detection和embedding scaling。這兩樣?xùn)|西，保證了運(yùn)行他們的程序得到了結(jié)果一般來說相對(duì)比較理想。但是，這在他們的算法中并沒有敘述。如果你直接按照他論文中的方法來實(shí)現(xiàn)，你可以體會(huì)一下這個(gè)結(jié)果和他們結(jié)果的差距。從此我們也可以看出，那幾個(gè)作者做學(xué)問的嚴(yán)謹(jǐn)態(tài)度，這是值得我們好好學(xué)習(xí)的。
另外比較有趣的是，Tenenbaum根本不是做與數(shù)據(jù)處理有關(guān)算法的人，他是做計(jì)算認(rèn)知科學(xué)（computational cognition science）的。在做這個(gè)方法的時(shí)候，他還在stanford，02年就去了
MIT開創(chuàng)一派，成了CoCoSci 的掌門人，他的組成長十分迅速。但是有趣的是，在Isomap之后，他包括他在MIT帶的學(xué)生就從來再也沒有做過類似的工作。其原因我今年夏天有所耳聞。他在今年參加 UCLA Alan Yuille 組織的一個(gè)summer school上說，（不是原文，是大意）我們經(jīng)常忘了做研究的原始出發(fā)點(diǎn)是什莫。他做Isomap就是為了找一個(gè)好的visual perception的方法，他還堅(jiān)持了他的方向和信仰，computational cognition，他沒有隨波逐流。而由他引導(dǎo)起來的 manifold learning 卻快速的發(fā)展成了一個(gè)新的方向。
這是一個(gè)值得我們好好思考的問題。我們做一個(gè)東西，選擇一個(gè)研究方向究竟是為了什莫。你考慮過嗎？
�。ó�(dāng)然，此問題也在問我自己）
b) LLE (Locally linear Embedding)
LLE在作者寫出的表達(dá)式看,是個(gè)具有十分對(duì)稱美的方法. 這種看上去的對(duì)稱對(duì)于啟發(fā)人很重要。LLE的思想就是，一個(gè)流形在很小的局部鄰域上可以近似看成歐式的，就是局部線性的。那末，在小的局部鄰域上，一個(gè)點(diǎn)就可以用它周圍的點(diǎn)在最小二乘意義下最優(yōu)的線性表示。LLE把這個(gè)線性擬合的系數(shù)當(dāng)成這個(gè)流形局部幾何性質(zhì)的刻畫。那末一個(gè)好的低維表示，就應(yīng)該也具有同樣的局部幾何，所以利用同樣的線性表示的表達(dá)式，最終寫成一個(gè)二次型的形式，十分自然優(yōu)美。
注意在LLE出現(xiàn)的兩個(gè)加和優(yōu)化的線性表達(dá)，第一個(gè)是求每一點(diǎn)的線性表示系數(shù)的。雖然原始公式中是寫在一起的，但是求解時(shí)，是對(duì)每一個(gè)點(diǎn)分別來求得。第二個(gè)表示式，是已知所有點(diǎn)的線性表示系數(shù)，來求低維表示（或嵌入embedding）的，他是一個(gè)整體求解的過程。這兩個(gè)表達(dá)式的轉(zhuǎn)化正好中間轉(zhuǎn)了個(gè)彎，使一些人困惑了，特別后面一個(gè)公式寫成一個(gè)二次型的過程并不是那末直觀，很多人往往在此卡住，而阻礙了全面的理解。我推薦大家去精讀 Saul 在
JMLR上的那篇LLE的長文。那篇文章無論在方法表達(dá)還是英文書寫，我認(rèn)為都是精品，值得好好玩味學(xué)習(xí)。
另外值得強(qiáng)調(diào)的是，對(duì)于每一點(diǎn)處擬合得到的系數(shù)歸一化的操作特別重要，如果沒有這一步，這個(gè)算法就沒有效果。但是在原始論文中，他們是為了保持?jǐn)?shù)據(jù)在平行移動(dòng)下embedding不變。 LLE的matlab代碼寫得簡潔明了，是一個(gè)樣板。
在此有必要提提Lawrence Saul這個(gè)人。在Isomap和LLE的作者們中，Saul算是唯一一個(gè)以流形學(xué)習(xí)（并不限于）為研究對(duì)象開創(chuàng)學(xué)派的人。Saul早年主要做參數(shù)模型有關(guān)的算法。自從LLE以后，坐陣UPen創(chuàng)造了一個(gè)個(gè)佳績。主要成就在于他的兩個(gè)出色學(xué)生，Kilian Weinberger和 Fei Sha，做的方法。拿了很多獎(jiǎng)，在此不多說，可以到他主頁上去看。Weinberger把學(xué)習(xí)核矩陣引入到流形學(xué)習(xí)中來。他的這個(gè)方法在流形學(xué)習(xí)中影響到不是很顯著，卻是在 convex optimization 中人人得知。Fei Sha不用多說了，machine learning中一個(gè)閃亮的新星，中國留學(xué)生之驕傲�，F(xiàn)在他們一個(gè)在Yahoo,一個(gè)在Jordan手下做PostDoc。
c) Laplacian Eigenmaps
要說哪一個(gè)方法被做的全面，那莫非LE莫屬。如果只說LE這個(gè)方法本身，是不新的，許多年前在做mesh相關(guān)的領(lǐng)域就開始這莫用。但是放在黎曼幾何的框架內(nèi)，給出完整的幾何分析的，應(yīng)該是Belkin和Niyogi（LE作者）的功勞。
LE的基本思想就是用一個(gè)無向有權(quán)圖來描述一個(gè)流形，然后通過用圖的嵌入（graph
embedding）來找低維表示。說白了，就是保持圖的局部鄰接關(guān)系的情況把這個(gè)圖從高維空間中重新畫在一個(gè)低維空間中（graph drawing）。
在至今為止的流行學(xué)習(xí)的典型方法中，LE是速度最快、效果相對(duì)來說不怎莫樣的。但是LE有一個(gè)其他方法沒有的特點(diǎn)，就是如果出現(xiàn)outlier情況下，它的魯棒性（robustness）特別好。 后來Belkin和Niyogi又分析了LE的收斂性。大家不要忽視這個(gè)問題，很重要。鼓勵(lì)有興趣數(shù)學(xué)功底不錯(cuò)的人好好看看這篇文章。
d) Hessian Eigenmaps
如果你對(duì)黎曼幾何不懂，基本上看不懂這個(gè)方法。又加作者表達(dá)的抽象，所以絕大多數(shù)人對(duì)這個(gè)方法了解不透徹。在此我就根據(jù)我自己的理解說說這個(gè)方法。
這個(gè)方法有兩個(gè)重點(diǎn)：（1）如果一個(gè)流形是局部等距（isometric）歐式空間中一個(gè)開子集的，那末它的Hessian矩陣具有d+1維的零空間。（2）在每一點(diǎn)處，Hessian系數(shù)的估計(jì)。
首先作者是通過考察局部Hessian的二次型來得出結(jié)論的，如果一個(gè)流形局部等距于歐式空間中的一個(gè)開子集，那末由這個(gè)流形patch 到開子集到的映射函數(shù)是一個(gè)線性函數(shù)，線性函數(shù)的二次混合導(dǎo)數(shù)為零，所以局部上由Hessian系數(shù)構(gòu)成的二次型也為零，這樣把每一點(diǎn)都考慮到，過渡到全局的Hessian矩陣就有d+1維的零空間，其中一維是常函數(shù)構(gòu)成的，也就是1向量。其它的d維子空間構(gòu)成等距坐標(biāo)。這就是理論基礎(chǔ)的大意，當(dāng)然作者在介紹的時(shí)候，為了保持理論嚴(yán)謹(jǐn)，作了一個(gè)由切坐標(biāo)到等距坐標(biāo)的過渡。
另外一個(gè)就是局部上Hessian系數(shù)的估計(jì)問題。我在此引用一段話：
If you approximate a function f(x) by a quadratic expansion
f(x) = f(0) + (grad f)^T x + x^T Hf x + rem
then the hessian is what you get for the quadratic component. So simply over a given neighborhood, develop the operator that approximates a function by its projection on 1, x_1,...,x_k, x_1^2,...,x_k^2, x_1*x_2,... ,x_{k-1}*x_{k}. Extract the component of the operator that delivers the projection on x_1^2,...,x_k^2, x_1*x_2,... ,x_{k-1}*x_{k}.
這段話是我在初學(xué)HE時(shí)候，寫信問Dave Donoho，他給我的回信。希望大家領(lǐng)會(huì)。如果你了解了上述基本含義，再去細(xì)看兩遍原始論文，也許會(huì)有更深的理解。由于HE牽扯到二階導(dǎo)數(shù)的估計(jì)，所以對(duì)噪聲很敏感。另外，HE的原始代碼中在計(jì)算局部切坐標(biāo)的時(shí)候，用的是奇異值分解(SVD)，所以如果想用他們的原始代碼跑一下例如圖像之類的真實(shí)數(shù)據(jù)，就特別的慢。其實(shí)把他們的代碼改一下就可以了，利用一般PCA的快速計(jì)算方法，計(jì)算小尺寸矩陣的特征向量即可。還有，在原始代碼中，他把Hessian系數(shù)歸一化了，這也就是為什莫他們叫這個(gè)方法為 Hessian LLE 的原因之一。
Dave Dohono是學(xué)術(shù)界公認(rèn)的大牛，在流形學(xué)習(xí)這一塊，是他帶著他的一個(gè)學(xué)生做的，Carrie Grimes�，F(xiàn)在這個(gè)女性研究員在Google做 project leader，學(xué)術(shù)界女生同學(xué)的楷模 : )
e) LTSA (Local tangent space alignment)
很榮幸，這個(gè)是國內(nèi)學(xué)者（浙江大學(xué)數(shù)學(xué)系的老師ZHANG Zhenyue）為第一作者做的一個(gè)在流行學(xué)習(xí)中最出色的方法。由于這個(gè)方法是由純數(shù)學(xué)做數(shù)值分析出身的老師所做，所以原始論文看起來公式一大堆，好像很難似的。其實(shí)這個(gè)方法非常直觀簡單。
象 Hessian Eigenmaps 一樣，流形的局部幾何表達(dá)先用切坐標(biāo)，也就是PCA的主子空間中的坐標(biāo)。那末對(duì)于流形一點(diǎn)處的切空間，它是線性子空間，所以可以和歐式空間中的一個(gè)開子集建立同構(gòu)關(guān)系，最簡單的就是線性變換。在微分流形中，就叫做切映射 (tangential map)，是個(gè)很自然很基礎(chǔ)的概念。把切坐標(biāo)求出來，建立出切映射，剩下的就是數(shù)值計(jì)算了。最終這個(gè)算法劃歸為一個(gè)很簡單的跌代加和形式。如果你已經(jīng)明白了MDS，那末你就很容易明白，這個(gè)算法本質(zhì)上就是MDS的從局部到整體的組合。
這里主要想重點(diǎn)強(qiáng)調(diào)一下，那個(gè)論文中使用的一個(gè)從局部幾何到整體性質(zhì)過渡的alignment技術(shù)。在spectral method（特征分解的）中，這個(gè)alignment方法特別有用。只要在數(shù)據(jù)的局部鄰域上你的方法可以寫成一個(gè)二次項(xiàng)的形式，就可以用。
其實(shí)LTSA最早的版本是在02年的DOCIS上。這個(gè)alignment方法在02年底Brand的 charting a manifold 中也出現(xiàn)，隱含在Hessian Eigenmaps中。在HE中，作者在從局部的Hessian矩陣過渡到全局的Hessian矩陣時(shí)，用了兩層加號(hào)，其中就隱含了這個(gè) alignment方法。后來國內(nèi)一個(gè)叫 ZHAO Deli 的學(xué)生用這個(gè)方法重新寫了LLE，發(fā)在Pattern Recognition上，一個(gè)短文。可以預(yù)見的是，這個(gè)方法還會(huì)被發(fā)揚(yáng)光大。
ZHA Hongyuan 后來專門作了一篇文章來分析 alignment matrix 的譜性質(zhì)，有興趣地可以找來看看。
f) MVU (Maximum variance unfolding)
這個(gè)方法剛發(fā)出來以后，名字叫做Semi-definite Embedding (SDE)。構(gòu)建一個(gè)局部的稀疏歐式距離矩陣以后，作者通過一定約束條件（主要是保持距離）來學(xué)習(xí)到一個(gè)核矩陣，對(duì)這個(gè)核矩陣做PCA就得到保持距離的 embedding，就這莫簡單。但是就是這個(gè)方法得了多少獎(jiǎng)，自己可以去找找看。個(gè)人觀點(diǎn)認(rèn)為，這個(gè)方法之所以被如此受人賞識(shí)，無論在vision還是在learning，除了給流形學(xué)習(xí)這一領(lǐng)域帶來了一個(gè)新的解決問題的工具之外，還有兩個(gè)重點(diǎn)，一是核方法（kernel），二是半正定規(guī)劃（semi-definite programming），這兩股風(fēng)無論在哪個(gè)方向（learning and Vision）上都吹得正猛。
g) S-Logmaps
這個(gè)方法不太被人所知，但是我認(rèn)為這個(gè)是流形學(xué)習(xí)發(fā)展中的一個(gè)典型的方法（其實(shí)其他還有很多人也這莫認(rèn)為）。就效果來說，這個(gè)方法不算好，說它是一個(gè)典型的方法，是因?yàn)檫@個(gè)方法應(yīng)用了黎曼幾何中一個(gè)很直觀的性質(zhì)。這個(gè)性質(zhì)和法坐標(biāo)(normal coordinate)、指數(shù)映射(exponential map)和距離函數(shù)(distance function)有關(guān)。
如果你了解黎曼幾何，你會(huì)知道，對(duì)于流形上的一條測地線，如果給定初始點(diǎn)和初始點(diǎn)處測地線的切方向，那莫這個(gè)測地線就可以被唯一確定。這是因?yàn)樵谶@些初始條件下，描述測地線的偏微分方程的解是唯一的。那末流形上的一條測地線就可以和其起點(diǎn)處的切平面上的點(diǎn)建立一個(gè)對(duì)應(yīng)關(guān)系。我們可以在這個(gè)切平面上找到一點(diǎn)，這個(gè)點(diǎn)的方向就是這個(gè)測地線在起點(diǎn)處的切方向，其長度等于這個(gè)測地線上的長。這樣的一個(gè)對(duì)應(yīng)關(guān)系在局部上是一一對(duì)應(yīng)的。那末這個(gè)在切平面上的對(duì)應(yīng)點(diǎn)在切平面中就有一個(gè)坐標(biāo)表示，這個(gè)表示就叫做測地線上對(duì)應(yīng)點(diǎn)的法坐標(biāo)表示（有的也叫指數(shù)坐標(biāo)）。那末反過來，我們可以把切平面上的點(diǎn)映射到流形上，這個(gè)映射過程就叫做指數(shù)映射（Logmap就倒過來）。如果流形上每一個(gè)點(diǎn)都可以這樣在同一個(gè)切平面上表示出來，那末我們就可以得到保持測地線長度的低維表示。如果這樣做得到，流形必須可以被單坐標(biāo)系統(tǒng)所覆蓋。
如果給定流形上的采樣點(diǎn)，如果要找到法坐標(biāo)，我們需要知道兩個(gè)東西，一是測地線距離，二是每個(gè)測地線在起點(diǎn)處的切方向。第一個(gè)東西好弄，利用Isomap中的方法直接就可以解決，關(guān)鍵是第二個(gè)。第二個(gè)作者利用了距離函數(shù)的梯度，這個(gè)梯度和那個(gè)切方向是一個(gè)等價(jià)的關(guān)系，一般的黎曼幾何書中都有敘述。作者利用一個(gè)局部切坐標(biāo)的二次泰勒展開來近似距離函數(shù)，而距離是知道的，就是測地線距離，局部切坐標(biāo)也知道，那末通過求一個(gè)簡單的最小二乘問題就可以估計(jì)出梯度方向。
如果明白這個(gè)方法的幾何原理，你再去看那個(gè)方法的結(jié)果，你就會(huì)明白為什莫在距離中心點(diǎn)比較遠(yuǎn)的點(diǎn)的embedding都可以清楚地看到在一條條線上，效果不太好。
最近這個(gè)思想被北大的一個(gè)年輕的老師 LIN Tong 發(fā)揚(yáng)光大，就是ECCV‘06上的那篇，還有即將刊登出的TPAMI上的 Riemannian Manifold Learning，實(shí)為國內(nèi)研究學(xué)者之榮幸。Lin的方法效果非常好，但是雖然取名叫Riemannian，沒有應(yīng)用到黎曼幾何本身的性質(zhì)，這樣使他的方法更容易理解。
Lin也是以一個(gè)切空間為基準(zhǔn)找法坐標(biāo)，這個(gè)出發(fā)點(diǎn)和思想和Brun（S-Logmaps）的是一樣的。但是Lin全是在局部上操作的，在得出切空間原點(diǎn)處局部鄰域的法坐標(biāo)以后，Lin采用逐步向外擴(kuò)展的方法找到其他點(diǎn)的法坐標(biāo)，在某一點(diǎn)處，保持此點(diǎn)到它鄰域點(diǎn)的歐式距離和夾角，然后轉(zhuǎn)化成一個(gè)最小二乘問題求出此點(diǎn)的法坐標(biāo)，這樣未知的利用已知的逐步向外擴(kuò)展。說白了就像縫網(wǎng)一樣，從幾個(gè)臨近的已知點(diǎn)開始，逐漸向外擴(kuò)散的縫。效果好是必然的。
淺談流形學(xué)習(xí)
bypluskid, on 2010-05-29, in Machine Learning76 comments
總覺得即使是“淺談”兩個(gè)字，還是讓這個(gè)標(biāo)
題有些過大了，更何況我自己也才剛剛接觸這么一個(gè)領(lǐng)域。不過懶得想其他標(biāo)題了，想起來要扯一下這個(gè)話題，也是因?yàn)楹团笥蚜钠鹞易约鹤罱谧龅姆较�。Manifold Learning 或者僅僅 Manifold 本身通常就聽起來頗有些深?yuàn)W的感覺，不過如果并不是想要進(jìn)行嚴(yán)格的理論推導(dǎo)的話，也可以從許多直觀的例子得到一些感性的認(rèn)識(shí)，正好我也就借這個(gè)機(jī)會(huì)來簡單地談一下這個(gè)話題吧，或者說至少是我到目前為止對(duì)這它的認(rèn)識(shí)。 這兩個(gè)詞，在談 Manifold 之前，不妨先說說 Learning ，也就是 Machine Learning 。而說道 Machine Learning 而不提一下 Artificial Intelligence 的話似乎又顯得有些不厚道。人說 AI 是一門最悲劇的學(xué)科，因?yàn)槊慨?dāng)它的一個(gè)子領(lǐng)域發(fā)展得像模像樣之后，就立馬自立門戶，從此和 AI “再無瓜葛”了，而 Machine Learning 大概要算是最新的一個(gè)典型吧。這就讓人有點(diǎn)奇怪，比如說數(shù)學(xué)，分門別類總算是夠多了吧？可以不管怎么分，大家兄弟姐妹也都還承認(rèn)自己是叫“數(shù)學(xué)”的。那 AI 呢？我覺得這里有很大一部分
是它自身定位的問題。
反正現(xiàn)在我是不太清楚 AI 是做什么的，不知道其他人到底清楚不清楚。Wikipedia 上
說 Artificial intelligence (AI) is the intelligence of machines and the branch of computer
science that aims to create it.
可是這相當(dāng)于一個(gè) tautology ，因?yàn)榈降资裁从质莟he intelligence of machines呢？一開始的時(shí)候，大牛們都野心勃勃，而且好像也是信心滿滿，就好像曾經(jīng)廣泛認(rèn)為“牛頓定理揭示了宇宙真理，科學(xué)剩下的事情只要按照公式來做計(jì)算就可以了”一樣，大家可能覺得，不出幾十年，人類就可以不用思考，交給 AI 來做了。不過我這里并不想再多說諸如什么是“思考”，什么是“智能”之類的以及隨之而來的“圖靈測試”之類的話題。我想說的是，到頭來，AI 到底是什么，這還是一個(gè)問題，或者說，AI 在一開始定了一個(gè)過高的目標(biāo)，幾十年后，發(fā)現(xiàn)情況并不像當(dāng)年那么樂觀，卻又有些下不了臺(tái)了。
這個(gè)時(shí)候，AI 的一些旁枝或者子領(lǐng)域果斷放下面子，丟掉了那個(gè)近乎玄幻的目標(biāo)，逐漸發(fā)展成為“正�！钡膶W(xué)科，所以也就不再好稱為 AI 了�；蛘哒f現(xiàn)在的 AI 有兩個(gè)意思，一個(gè)廣義的 AI ，包括了所有相關(guān)的以及派生的領(lǐng)域，另一個(gè)則是狹義的或者經(jīng)典的 AI ，專門指那些仍然在執(zhí)著地追求著真正的“智能”的部分，或者說得不好聽一點(diǎn)，就
是剩下的部分。
Machine Learning 作為離家出走的典型，雖然名字里帶了 Learning 一個(gè)詞，讓人乍一看覺得和 Intelligence 相比不過是換了個(gè)說法而已，然而事實(shí)上這里的 Learning 的意義要樸素得多。我們來看一看 Machine Learning 的典型的流程就知道了，其實(shí)有時(shí)候覺得和應(yīng)用數(shù)學(xué)或者更通俗的數(shù)學(xué)建模有些類似，通常我們會(huì)有需要分析或者處理的數(shù)據(jù)，根據(jù)一些經(jīng)驗(yàn)和一些假設(shè)，我們可以構(gòu)建一個(gè)模型，這個(gè)模型會(huì)有一些參數(shù)（即使是非參數(shù)化方法，也是可以類似地看待的），根據(jù)數(shù)據(jù)來求解模型參數(shù)的過程，就叫做 Parameter Estimation ，或者 Model Fitting ，但是搞機(jī)器學(xué)習(xí)的人，通常把它叫做 Learning （或者，換一個(gè)角度，叫 Training）——因?yàn)楦鶕?jù)數(shù)據(jù)歸納出一個(gè)有用的模型，這和我們?nèi)祟悺皩W(xué)習(xí)”的過程還是挺類似的吧。不過，如果拋開無聊的摳字眼游戲的話，我們可以看到，Machine Learning 已經(jīng)拋棄了“智能”的高帽子，它的目的就是要解決具
體的問題——而并不關(guān)心是否是通過一種“智能”的方式類解決的。
說到這里，其實(shí)我們構(gòu)造模型就類似于寫一個(gè)類，數(shù)據(jù)就是構(gòu)造函數(shù)的參數(shù)，Learning 就是構(gòu)造函數(shù)運(yùn)行的過程，成功構(gòu)造一個(gè)對(duì)象之后，我們就完成了學(xué)習(xí)。一些 Machine Learning 的問題到這一步就結(jié)束了，另一些情況還會(huì)使用得到的模型（對(duì)象）對(duì)后來的數(shù)據(jù)進(jìn)行一些處理，通常會(huì)是Inferencing。到這個(gè)時(shí)候，又有些像統(tǒng)計(jì)里的東西了，所謂“統(tǒng)計(jì)推斷”嘛。其實(shí)原本統(tǒng)計(jì)和機(jī)器學(xué)習(xí)研究的不少問題就是交叉在一起的，不過兩派人從不同的角度來看待同樣的問題。而且，也確實(shí)有 Statistical Learning 這么一個(gè)說法存在的，可以把他看成是 Machine Learning 的一個(gè)子領(lǐng)域（或者是一個(gè)分子或
者甚至就是 Machine Learning 本身）。
到這里，如果你還沒有因?yàn)椴粩嗟負(fù)缸盅鄱鵁┰甑脑挘?/p>
我已經(jīng)忍無可忍了。所以，我就假定你已經(jīng)了解了什么叫 Learning ，或者是已經(jīng)惡心到懶得去了解了。于是我們轉(zhuǎn)入下一個(gè)話題：流形，也就是 Manifold 。不知道你有沒有為我在本文開頭放上的那個(gè)地球的圖片感到困惑？這是因?yàn)榍蛎媸且粋�(gè)很典型的流
形的例子，而地球就是一個(gè)很典型的“球面”啦（姑且當(dāng)作球面好啦）。
有時(shí)候經(jīng)常會(huì)在 paper 里看到“嵌入在高維空間中的低維流形”，不過高維的數(shù)據(jù)對(duì)于我們這些可憐的低維生物來說總是很難以想像，所以最直觀的例子通常都會(huì)是嵌入在三維空間中的二維或者一維流行。比如說一塊布，可以把它看成一個(gè)二維平面，這是一個(gè)
二維的歐氏空間，現(xiàn)在我們（在三維）中把它扭一扭，它就變成了一個(gè)流形（當(dāng)然，不
扭的時(shí)候，它也是一個(gè)流形，歐氏空間是流形的一種特殊情況）。
所以，直觀上來講，一個(gè)流形好比是一個(gè) d 維的空間，在一個(gè) m 維的空間中 (m > d) 被扭曲之后的結(jié)果。需要注意的是，流形并不是一個(gè)“形狀”，而是一個(gè)“空間”，如果你覺得“扭曲的空間”難以想象，那么請(qǐng)?jiān)倩貞浿耙粔K布的例子。如果我沒弄錯(cuò)的話，廣義相對(duì)論似乎就是把我們的時(shí)空當(dāng)作一個(gè)四維流（空間三維加上時(shí)間一維）形來研究的，引力就是這個(gè)流形扭曲的結(jié)果。當(dāng)然，這些都是直觀上的概念，其實(shí)流形并不需要依靠嵌入在一個(gè)“外圍空間”而存在，稍微正式一點(diǎn)來說，一個(gè) d 維的流形就是一個(gè)在任意點(diǎn)出局部同胚于（簡單地說，就是正逆映射都是光滑的一一映射）歐氏空間。
實(shí)際上，正是這種局部與歐氏空間的同
胚給我們帶來了很多好處，這使得我們在日常生活中許許多多的幾何問題都可以使用簡單的歐氏幾何來解決，因?yàn)楹偷厍虻某叨缺绕饋�，我們的日常生活就算是一個(gè)很小的局部啦——我突然想起《七龍珠》里的那個(gè)界王住的那種私人小星球，走幾步就要繞一圈的感覺，看來界王不僅要體力好（那上面重力似乎是地球的十倍），而且腦力也要好，
初中學(xué)的必須是黎曼幾何了！
那么，除了地球這種簡單的例子，實(shí)際應(yīng)用中的數(shù)據(jù)，怎么知道它是不是一個(gè)流形呢？于是不妨又回歸直觀的感覺。再從球面說起，如果我們事先不知道球面的存在，那么球面上的點(diǎn)，其實(shí)就是三維歐氏空間上的點(diǎn)，可以用一個(gè)三元組來表示其坐標(biāo)。但是和空間中的普通點(diǎn)不一樣的是，它們允許出現(xiàn)的位置受到了一定的限制，具體到球面，可以
可以看一下它的參數(shù)方程：
可以看到，這些三維的坐標(biāo)實(shí)際上是由兩個(gè)變量和生成的，也可以說成是它的自由度是二，也正好對(duì)應(yīng)了它是一個(gè)二維的流形。有了這樣的感覺之后，再來看流形學(xué)習(xí)里經(jīng)
常用到的人臉的例子，就很自然了。下圖是Isomap論文里的一個(gè)結(jié)果：
這里的圖片來自同一張人臉（好吧，其實(shí)是人臉模型），每張圖片是 64×64 的灰度圖，如果把位圖按照列（或行）拼起來，就可以得到一個(gè) 4096 維的向量，這樣一來，每一張圖片就可以看成是 4096 維歐氏空間中的一個(gè)點(diǎn)。很顯然，并不是 4096 維空間中任意一個(gè)點(diǎn)都可以對(duì)應(yīng)于一張人臉圖片的，這就類似于球面的情形，我們可以假定所有可以是人臉的 4096 維向量實(shí)際上分布在一個(gè) d 維 (d < 4096) 的子空間中。而特定到Isomap的人臉這個(gè)例子，實(shí)際上我們知道所有的 698 張圖片是拍自同一個(gè)人臉（模型），不過是在不同的 pose 和光照下拍攝的，如果把 pose （上下和左右）當(dāng)作兩個(gè)自由度，而光照當(dāng)作一個(gè)自由度，那么這些圖片實(shí)際只有三個(gè)自由度，換句話說，存在一個(gè)類似于球面一樣的參數(shù)方程（當(dāng)然，解析式是沒法寫出來的），給定一組參數(shù)（也就是上下、左右的 pose 和光照這三個(gè)值），就可以生成出對(duì)應(yīng)的 4096 維的坐標(biāo)來。
換句話說，這是一個(gè)嵌入在 4096 維歐氏空間中的一個(gè) 3 維流形。
實(shí)際上，上面的那張圖就是Isomap將這個(gè)數(shù)據(jù)集從 4096 維映射到 3 維空間中，并顯示了其中 2 維的結(jié)果，圖中的小點(diǎn)就是每個(gè)人臉在這個(gè)二維空間中對(duì)應(yīng)的坐標(biāo)位置，其中一些標(biāo)紅圈的點(diǎn)被選出來，并在旁邊畫上了該點(diǎn)對(duì)應(yīng)的原始圖片，可以很直觀地看
出這兩個(gè)維度正好對(duì)應(yīng)了 pose 的兩個(gè)自由度平滑變化的結(jié)果。
就我目前所知，把流形引入到機(jī)器學(xué)習(xí)領(lǐng)域來主要有兩種用途：一是將原來在歐氏空間中適用的算法加以改造，使得它工作在流形上，直接或間接地對(duì)流形的結(jié)構(gòu)和性質(zhì)加以利用；二是直接分析流形的結(jié)構(gòu)，并試圖將其映射到一個(gè)歐氏空間中，再在得到的結(jié)果
上運(yùn)用以前適用于歐氏空間的算法來進(jìn)行學(xué)習(xí)。
這里Isomap正巧是一個(gè)非常典型的例子，因?yàn)樗鼘?shí)際上是通過“改造一種原本適用于歐
氏空間的算法”，達(dá)到了“將流形映射到一個(gè)歐氏空間”的目的。
Isomap所改造的這個(gè)方法叫做Multidimensional Scaling (MDS)，MDS 是一種降維方法，它的目的就是使得降維之后的點(diǎn)兩兩之間的距離盡量不變（也就是和在原是空間中對(duì)應(yīng)的兩個(gè)點(diǎn)之間的距離要差不多）。只是 MDS 是針對(duì)歐氏空間設(shè)計(jì)的，對(duì)于距離的計(jì)算也是使用歐氏距離來完成的。如果數(shù)據(jù)分布在一個(gè)流形上的話，歐氏距離就不適用了。 讓我們再回到地球——這個(gè)在三維空間中的二維流形，假設(shè)我們要在三維空間中計(jì)算北極點(diǎn)和南極點(diǎn)的距離，這很容易，就是兩點(diǎn)相連的線段的長度，可是，如果要在這個(gè)流形上算距離就不能這樣子算了，我們總不能從北極打個(gè)洞鉆到南極去吧？要沿著地球表面走才行，當(dāng)然，如果我隨便沿著什么路線走一遍，然后數(shù)出總共走了多少步作為距離，這是不成的，因?yàn)檫@樣一來如果我沿著不同的路線走，豈不是會(huì)得到不同的距離值？總而言之，我們現(xiàn)在需要一個(gè)新的定義在地球表面（流形）上的距離度量，理論上來說，任意滿足測度的 4 個(gè)條件的函數(shù)都可以被定義為距離，不過，為了和歐氏空間對(duì)應(yīng)起
來，這里選擇一個(gè)直線距離的推廣定義。
還記得初中學(xué)的“兩點(diǎn)之間，線段最短”嗎？現(xiàn)在，我們反過來說，把線段的概念推廣一下，變成“兩點(diǎn)之間最短的曲線是線段”，于是流形上的距離定義也就等同于歐氏空間了：流形上兩個(gè)點(diǎn)之間的距離就是連接兩個(gè)點(diǎn)的“線段”的長度。雖然只是置換了一個(gè)概念，但是現(xiàn)在兩者統(tǒng)一起來了，不過，在流形上的線段大概就不一定是“直”的了（于是直線也變成不一定是“直”的了），通常又稱作是“測地線”。對(duì)于球面這個(gè)簡單的流形來說，任意一條線段必定是在一個(gè)“大圓”上的，于是球面上的直線其實(shí)都是一些大圓，也造成了球面這個(gè)流形上沒有平行線等一系列尷尬的局面（任意兩條直線均相交），如果你看
過一些數(shù)學(xué)科普八卦類的書，應(yīng)該會(huì)回憶起不少東西啦！
回到Isomap，它主要做了一件事情，就是把 MDS 中原始空間中距離的計(jì)算從歐氏距離換為了流形上的測地距離。當(dāng)然，如果流形的結(jié)構(gòu)事先不知道的話，這個(gè)距離是沒法算的，于是Isomap通過將數(shù)據(jù)點(diǎn)連接起來構(gòu)成一個(gè)鄰接 Graph 來離散地近似原來的流形，而測地距離也相應(yīng)地通過 Graph 上的最短路徑來近似了。
【流形學(xué)習(xí)論文】相關(guān)文章：
集體交流形式的教學(xué)初探論文07-04
三圈環(huán)流形成原因09-25
大氣環(huán)流形成的原因及其意義08-24
秘魯漁場是哪兩個(gè)洋流形成的03-24
為了學(xué)習(xí)而學(xué)習(xí)議論文07-07
教師師德學(xué)習(xí)論文02-22