流形學(xué)習(xí) (manifold learning)
流形學(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é)概念來(lái)解釋這個(gè)東西。所謂流形（manifold）就是一般的幾何對(duì)象的總稱。比如人，有中國(guó)人、美國(guó)人等等；流形就包括各種維數(shù)的曲線曲面等。和一般的降維分析一樣，流形學(xué)習(xí)把一組在高維空間中的數(shù)據(jù)在低維空間中重新表示。和以往方法不同的是，在流形學(xué)習(xí)中有一個(gè)假設(shè)，就是所處理的數(shù)據(jù)采樣于一個(gè)潛在的流形上，或是說(shuō)對(duì)于這組數(shù)據(jù)存在一個(gè)潛在的流形。對(duì)于不同的方法，對(duì)于流形性質(zhì)的要求各不相同，這也就產(chǎn)生了在流形假設(shè)下的各種不同性質(zhì)的假設(shè)，比如在Laplacian Eigenmaps中要假設(shè)這個(gè)流形是緊致黎曼流形等。對(duì)于描述流形上的點(diǎn)，我們要用坐標(biāo)，而流形上本身是沒(méi)有坐標(biāo)的，所以為了表示流形上的點(diǎn)，必須把流形放入外圍空間（ambient space）中，那末流形上的點(diǎn)就可以用外圍空間的坐標(biāo)來(lái)表示。比如R^3中的球面是個(gè)2維的曲面，因?yàn)榍蛎嫔现挥袃蓚€(gè)自由度，但是球面上的點(diǎn)一般是用外圍R^3空間中的坐標(biāo)表示的，所以我們看到的R^3中球面上的點(diǎn)有3個(gè)數(shù)來(lái)表示的。當(dāng)然球面還有柱坐標(biāo)球坐標(biāo)等表示。對(duì)于R^3中的球面來(lái)說(shuō)，那末流形學(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è)過(guò)程也叫參數(shù)化（parameterization）。直觀上來(lái)說(shuō)，就是把這個(gè)球面盡量好的展開(kāi)在通過(guò)原點(diǎn)的平面上。在PAMI中，這樣的低維表示也叫內(nèi)蘊(yùn)特征（intrinsic feature）。一般外圍空間的維數(shù)也叫觀察維數(shù)，其表示也叫自然坐標(biāo)（外圍空間是歐式空間）表示,在統(tǒng)計(jì)中一般叫observation。
了解了流形學(xué)習(xí)的這個(gè)基礎(chǔ)，那末流形學(xué)習(xí)中的一些是非也就很自然了，這個(gè)下面穿插來(lái)說(shuō)。由此，如果你想學(xué)好流形學(xué)習(xí)里的方法，你至少要了解一些微分流形和黎曼幾何的基本知識(shí)。
2. 代表方法
a) Isomap。
Josh Tenenbaum的Isomap開(kāi)創(chuàng)了一個(gè)數(shù)據(jù)處理的新戰(zhàn)場(chǎng)。在沒(méi)有具體說(shuō)Isomap之前，有必要先說(shuō)說(shuō)MDS（Multidimensional Scaling）這個(gè)方法。我們國(guó)內(nèi)的很多人知道PCA，卻很多人不知道MDS。PCA和MDS是相互對(duì)偶的兩個(gè)方法。MDS就是理論上保持歐式距離的一個(gè)經(jīng)典方法，MDS最早主要用于做數(shù)據(jù)的可視化。由于MDS得到的低維表示中心在原點(diǎn)，所以又可以說(shuō)保持內(nèi)積。也就是說(shuō)，用低維空間中的內(nèi)積近似高維空間中的距離。經(jīng)典的MDS方法，高維空間中的距離一般用歐式距離。
Isomap就是借窩生蛋。他的理論框架就是MDS，但是放在流形的理論框架內(nèi)，原始的距離換成了流形上的測(cè)地線（geodesic）距離。其它一模一樣。所謂的測(cè)地線，就是流形上加速度為零的曲線，等同于歐式空間中的直線。我們經(jīng)常聽(tīng)到說(shuō)測(cè)地線是流形上兩點(diǎn)之間距離最短的線。其實(shí)這末說(shuō)是不嚴(yán)謹(jǐn)?shù)?。流形上兩點(diǎn)之間距離最短的線是測(cè)地線，但是反過(guò)來(lái)不一定對(duì)。另外，如果任意兩個(gè)點(diǎn)之間都存在一個(gè)測(cè)地線，那末這個(gè)流形必須是連通的鄰域都是凸的。Isomap就是把任意兩點(diǎn)的測(cè)地線距離（準(zhǔn)確地說(shuō)是最短距離）作為流形的幾何描述，用MDS理論框架理論上保持這個(gè)點(diǎn)與點(diǎn)之間的最短距離。在Isomap中，測(cè)地線距離就是用兩點(diǎn)之間圖上的最短距離來(lái)近似的，這方面的算法是一般計(jì)算機(jī)系中用的圖論中的經(jīng)典算法。
如果你曾細(xì)致地看過(guò)Isomap主頁(yè)上的matlab代碼，你就會(huì)發(fā)現(xiàn)那個(gè)代碼的實(shí)現(xiàn)復(fù)雜度遠(yuǎn)超與實(shí)際論文中敘述的算法。在那個(gè)代碼中，除了論文中寫(xiě)出的算法外，還包括了 outlier detection和embedding scaling。這兩樣?xùn)|西，保證了運(yùn)行他們的程序得到了結(jié)果一般來(lái)說(shuō)相對(duì)比較理想。但是，這在他們的算法中并沒(méi)有敘述。如果你直接按照他論文中的方法來(lái)實(shí)現(xiàn)，你可以體會(huì)一下這個(gè)結(jié)果和他們結(jié)果的差距。從此我們也可以看出，那幾個(gè)作者做學(xué)問(wèn)的嚴(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開(kāi)創(chuàng)一派，成了CoCoSci 的掌門人，他的組成長(zhǎng)十分迅速。但是有趣的是，在Isomap之后，他包括他在MIT帶的學(xué)生就從來(lái)再也沒(méi)有做過(guò)類似的工作。其原因我今年夏天有所耳聞。他在今年參加 UCLA Alan Yuille 組織的一個(gè)summer school上說(shuō)，（不是原文，是大意）我們經(jīng)常忘了做研究的原始出發(fā)點(diǎn)是什莫。他做Isomap就是為了找一個(gè)好的visual perception的方法，他還堅(jiān)持了他的方向和信仰，computational cognition，他沒(méi)有隨波逐流。而由他引導(dǎo)起來(lái)的 manifold learning 卻快速的發(fā)展成了一個(gè)新的方向。
這是一個(gè)值得我們好好思考的問(wèn)題。我們做一個(gè)東西，選擇一個(gè)研究方向究竟是為了什么。你考慮過(guò)嗎？
b) LLE (Locally linear Embedding)
LLE在作者寫(xiě)出的表達(dá)式看,是個(gè)具有十分對(duì)稱美的方法. 這種看上去的對(duì)稱對(duì)于啟發(fā)人很重要。LLE的思想就是，一個(gè)流形在很小的局部鄰域上可以近似看成歐式的，就是局部線性的。那末，在小的局部鄰域上，一個(gè)點(diǎn)就可以用它周圍的點(diǎn)在最小二乘意義下最優(yōu)的線性表示。LLE把這個(gè)線性擬合的系數(shù)當(dāng)成這個(gè)流形局部幾何性質(zhì)的刻畫(huà)。那末一個(gè)好的低維表示，就應(yīng)該也具有同樣的局部幾何，所以利用同樣的線性表示的表達(dá)式，最終寫(xiě)成一個(gè)二次型的形式，十分自然優(yōu)美。
注意在LLE出現(xiàn)的兩個(gè)加和優(yōu)化的線性表達(dá)，第一個(gè)是求每一點(diǎn)的線性表示系數(shù)的。雖然原始公式中是寫(xiě)在一起的，但是求解時(shí)，是對(duì)每一個(gè)點(diǎn)分別來(lái)求得。第二個(gè)表示式，是已知所有點(diǎn)的線性表示系數(shù)，來(lái)求低維表示（或嵌入embedding）的，他是一個(gè)整體求解的過(guò)程。這兩個(gè)表達(dá)式的轉(zhuǎn)化正好中間轉(zhuǎn)了個(gè)彎，使一些人困惑了，特別后面一個(gè)公式寫(xiě)成一個(gè)二次型的過(guò)程并不是那末直觀，很多人往往在此卡住，而阻礙了全面的理解。我推薦大家去精讀 Saul 在JMLR上的那篇LLE的長(zhǎng)文。那篇文章無(wú)論在方法表達(dá)還是英文書(shū)寫(xiě)，我認(rèn)為都是精品，值得好好玩味學(xué)習(xí)。
另外值得強(qiáng)調(diào)的是，對(duì)于每一點(diǎn)處擬合得到的系數(shù)歸一化的操作特別重要，如果沒(méi)有這一步，這個(gè)算法就沒(méi)有效果。但是在原始論文中，他們是為了保持?jǐn)?shù)據(jù)在平行移動(dòng)下embedding不變。
LLE的matlab代碼寫(xiě)得簡(jiǎn)潔明了，是一個(gè)樣板。
在此有必要提提Lawrence Saul這個(gè)人。在Isomap和LLE的作者們中，Saul算是唯一一個(gè)以流形學(xué)習(xí)（并不限于）為研究對(duì)象開(kāi)創(chuàng)學(xué)派的人。Saul早年主要做參數(shù)模型有關(guān)的算法。自從LLE以后，坐陣UPen創(chuàng)造了一個(gè)個(gè)佳績(jī)。主要成就在于他的兩個(gè)出色學(xué)生，Kilian Weinberger和 Fei Sha，做的方法。拿了很多獎(jiǎng)，在此不多說(shuō)，可以到他主頁(yè)上去看。Weinberger把學(xué)習(xí)核矩陣引入到流形學(xué)習(xí)中來(lái)。他的這個(gè)方法在流形學(xué)習(xí)中影響到不是很顯著，卻是在 convex optimization 中人人得知。Fei Sha不用多說(shuō)了，machine learning中一個(gè)閃亮的新星，中國(guó)留學(xué)生之驕傲。現(xiàn)在他們一個(gè)在Yahoo,一個(gè)在Jordan手下做PostDoc。
c) Laplacian Eigenmaps
要說(shuō)哪一個(gè)方法被做的全面，那莫非LE莫屬。如果只說(shuō)LE這個(gè)方法本身，是不新的，許多年前在做mesh相關(guān)的領(lǐng)域就開(kāi)始這莫用。但是放在黎曼幾何的框架內(nèi)，給出完整的幾何分析的，應(yīng)該是Belkin和Niyogi（LE作者）的功勞。
LE的基本思想就是用一個(gè)無(wú)向有權(quán)圖來(lái)描述一個(gè)流形，然后通過(guò)用圖的嵌入（graph embedding）來(lái)找低維表示。說(shuō)白了，就是保持圖的局部鄰接關(guān)系的情況把這個(gè)圖從高維空間中重新畫(huà)在一個(gè)低維空間中（graph drawing）。
在至今為止的流行學(xué)習(xí)的典型方法中，LE是速度最快、效果相對(duì)來(lái)說(shuō)不怎莫樣的。但是LE有一個(gè)其他方法沒(méi)有的特點(diǎn)，就是如果出現(xiàn)outlier情況下，它的魯棒性（robustness）特別好。
后來(lái)Belkin和Niyogi又分析了LE的收斂性。大家不要忽視這個(gè)問(wèn)題，很重要。鼓勵(lì)有興趣數(shù)學(xué)功底不錯(cuò)的人好好看看這篇文章。
d) Hessian Eigenmaps
如果你對(duì)黎曼幾何不懂，基本上看不懂這個(gè)方法。又加作者表達(dá)的抽象，所以絕大多數(shù)人對(duì)這個(gè)方法了解不透徹。在此我就根據(jù)我自己的理解說(shuō)說(shuō)這個(gè)方法。
這個(gè)方法有兩個(gè)重點(diǎn)：（1）如果一個(gè)流形是局部等距（isometric）歐式空間中一個(gè)開(kāi)子集的，那末它的Hessian矩陣具有d+1維的零空間。（2）在每一點(diǎn)處，Hessian系數(shù)的估計(jì)。
首先作者是通過(guò)考察局部Hessian的二次型來(lái)得出結(jié)論的，如果一個(gè)流形局部等距于歐式空間中的一個(gè)開(kāi)子集，那末由這個(gè)流形patch到開(kāi)子集到的映射函數(shù)是一個(gè)線性函數(shù)，線性函數(shù)的二次混合導(dǎo)數(shù)為零，所以局部上由Hessian系數(shù)構(gòu)成的二次型也為零，這樣把每一點(diǎn)都考慮到，過(guò)渡到全局的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)的過(guò)渡。
另外一個(gè)就是局部上Hessian系數(shù)的估計(jì)問(wèn)題。我在此引用一段話：
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}.
dave
這段話是dodo在初學(xué)HE時(shí)候，寫(xiě)信問(wèn)Dave Donoho，他給dodo的回信。希望大家領(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è)是國(guó)內(nèi)學(xué)者（浙江大學(xué)數(shù)學(xué)系的老師ZHANG Zhenyue）為第一作者做的一個(gè)在流行學(xué)習(xí)中最出色的方法。由于這個(gè)方法是由純數(shù)學(xué)做數(shù)值分析出身的老師所做，所以原始論文看起來(lái)公式一大堆，好像很難似的。其實(shí)這個(gè)方法非常直觀簡(jiǎn)單。
象 Hessian Eigenmaps 一樣，流形的局部幾何表達(dá)先用切坐標(biāo)，也就是PCA的主子空間中的坐標(biāo)。那末對(duì)于流形一點(diǎn)處的切空間，它是線性子空間，所以可以和歐式空間中的一個(gè)開(kāi)子集建立同構(gòu)關(guān)系，最簡(jiǎn)單的就是線性變換。在微分流形中，就叫做切映射 (tangential map)，是個(gè)很自然很基礎(chǔ)的概念。把切坐標(biāo)求出來(lái)，建立出切映射，剩下的就是數(shù)值計(jì)算了。最終這個(gè)算法劃歸為一個(gè)很簡(jiǎn)單的跌代加和形式。如果你已經(jīng)明白了MDS，那末你就很容易明白，這個(gè)算法本質(zhì)上就是MDS的從局部到整體的組合。
這里主要想重點(diǎn)強(qiáng)調(diào)一下，那個(gè)論文中使用的一個(gè)從局部幾何到整體性質(zhì)過(guò)渡的alignment技術(shù)。在spectral method（特征分解的）中，這個(gè)alignment方法特別有用。只要在數(shù)據(jù)的局部鄰域上你的方法可以寫(xiě)成一個(gè)二次項(xiàng)的形式，就可以用。
其實(shí)LTSA最早的版本是在02年的DOCIS上。這個(gè)alignment方法在02年底Brand的 charting a manifold 中也出現(xiàn)，隱含在Hessian Eigenmaps中。在HE中，作者在從局部的Hessian矩陣過(guò)渡到全局的Hessian矩陣時(shí)，用了兩層加號(hào)，其中就隱含了這個(gè)alignment方法。后來(lái)國(guó)內(nèi)一個(gè)叫 ZHAO Deli 的學(xué)生用這個(gè)方法重新寫(xiě)了LLE，發(fā)在Pattern Recognition上，一個(gè)短文?？梢灶A(yù)見(jiàn)的是，這個(gè)方法還會(huì)被發(fā)揚(yáng)光大。
ZHA Hongyuan 后來(lái)專門作了一篇文章來(lái)分析 alignment matrix 的譜性質(zhì)，有興趣地可以找來(lái)看看。
f) MVU (Maximum variance unfolding)
這個(gè)方法剛發(fā)出來(lái)以后，名字叫做Semi-definite Embedding (SDE)。構(gòu)建一個(gè)局部的稀疏歐式距離矩陣以后，作者通過(guò)一定約束條件（主要是保持距離）來(lái)學(xué)習(xí)到一個(gè)核矩陣，對(duì)這個(gè)核矩陣做PCA就得到保持距離的embedding，就這莫簡(jiǎn)單。但是就是這個(gè)方法得了多少獎(jiǎng)，自己可以去找找看。個(gè)人觀點(diǎn)認(rèn)為，這個(gè)方法之所以被如此受人賞識(shí)，無(wú)論在vision還是在learning，除了給流形學(xué)習(xí)這一領(lǐng)域帶來(lái)了一個(gè)新的解決問(wèn)題的工具之外，還有兩個(gè)重點(diǎn)，一是核方法（kernel），二是半正定規(guī)劃（semi-definite programming），這兩股風(fēng)無(wú)論在哪個(gè)方向（learning and Vision）上都吹得正猛。
g) S-Logmaps
這個(gè)方法不太被人所知，但是我認(rèn)為這個(gè)是流形學(xué)習(xí)發(fā)展中的一個(gè)典型的方法（其實(shí)其他還有很多人也這莫認(rèn)為）。就效果來(lái)說(shuō)，這個(gè)方法不算好，說(shuō)它是一個(gè)典型的方法，是因?yàn)檫@個(gè)方法應(yīng)用了黎曼幾何中一個(gè)很直觀的性質(zhì)。這個(gè)性質(zhì)和法坐標(biāo)(normal coordinate)、指數(shù)映射(exponential map)和距離函數(shù)(distance function)有關(guān)。
如果你了解黎曼幾何，你會(huì)知道，對(duì)于流形上的一條測(cè)地線，如果給定初始點(diǎn)和初始點(diǎn)處測(cè)地線的切方向，那莫這個(gè)測(cè)地線就可以被唯一確定。這是因?yàn)樵谶@些初始條件下，描述測(cè)地線的偏微分方程的解是唯一的。那末流形上的一條測(cè)地線就可以和其起點(diǎn)處的切平面上的點(diǎn)建立一個(gè)對(duì)應(yīng)關(guān)系。我們可以在這個(gè)切平面上找到一點(diǎn)，這個(gè)點(diǎn)的方向就是這個(gè)測(cè)地線在起點(diǎn)處的切方向，其長(zhǎng)度等于這個(gè)測(cè)地線上的長(zhǎng)。這樣的一個(gè)對(duì)應(yīng)關(guān)系在局部上是一一對(duì)應(yīng)的。那末這個(gè)在切平面上的對(duì)應(yīng)點(diǎn)在切平面中就有一個(gè)坐標(biāo)表示，這個(gè)表示就叫做測(cè)地線上對(duì)應(yīng)點(diǎn)的法坐標(biāo)表示（有的也叫指數(shù)坐標(biāo)）。那末反過(guò)來(lái)，我們可以把切平面上的點(diǎn)映射到流形上，這個(gè)映射過(guò)程就叫做指數(shù)映射（Logmap就倒過(guò)來(lái)）。如果流形上每一個(gè)點(diǎn)都可以這樣在同一個(gè)切平面上表示出來(lái)，那末我們就可以得到保持測(cè)地線長(zhǎng)度的低維表示。如果這樣做得到，流形必須可以被單坐標(biāo)系統(tǒng)所覆蓋。
如果給定流形上的采樣點(diǎn)，如果要找到法坐標(biāo)，我們需要知道兩個(gè)東西，一是測(cè)地線距離，二是每個(gè)測(cè)地線在起點(diǎn)處的切方向。第一個(gè)東西好弄，利用Isomap中的方法直接就可以解決，關(guān)鍵是第二個(gè)。第二個(gè)作者利用了距離函數(shù)的梯度，這個(gè)梯度和那個(gè)切方向是一個(gè)等價(jià)的關(guān)系，一般的黎曼幾何書(shū)中都有敘述。作者利用一個(gè)局部切坐標(biāo)的二次泰勒展開(kāi)來(lái)近似距離函數(shù)，而距離是知道的，就是測(cè)地線距離，局部切坐標(biāo)也知道，那末通過(guò)求一個(gè)簡(jiǎn)單的最小二乘問(wèn)題就可以估計(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í)為國(guó)內(nèi)研究學(xué)者之榮幸。Lin的方法效果非常好，但是雖然取名叫Riemannian，沒(méi)有應(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è)最小二乘問(wèn)題求出此點(diǎn)的法坐標(biāo)，這樣未知的利用已知的逐步向外擴(kuò)展。說(shuō)白了就像縫網(wǎng)一樣，從幾個(gè)臨近的已知點(diǎn)開(kāi)始，逐漸向外擴(kuò)散的縫。效果好是必然的。
有人做了個(gè)好事情，做了個(gè)系統(tǒng)，把幾個(gè)方法的matlab代碼放在了一起 http://www.math.umn.edu/~wittman/mani/以上提到方法論文，都可以用文中給出的關(guān)鍵詞借助google.com找到。
3. 基本問(wèn)題和個(gè)人觀點(diǎn)
流形學(xué)習(xí)現(xiàn)在還基本處于理論探討階段，在實(shí)際中難以施展拳腳，不過(guò)在圖形學(xué)中除外。我就說(shuō)說(shuō)幾個(gè)基本的問(wèn)題。
a. 譜方法對(duì)噪聲十分敏感。希望大家自己做做實(shí)驗(yàn)體會(huì)一下，流形學(xué)習(xí)中譜方法的脆弱。
b. 采樣問(wèn)題對(duì)結(jié)果的影響。
c. 收斂性
d. 一個(gè)最尷尬的事情莫過(guò)于，如果用來(lái)做識(shí)別，流形學(xué)習(xí)線性化的方法比原來(lái)非線性的方法效果要好得多，如果用原始方法做識(shí)別，那個(gè)效果叫一個(gè)差。也正因?yàn)榇?，使很多人?duì)流形學(xué)習(xí)產(chǎn)生了懷疑。原因方方面面 : )
e. 把偏微分幾何方法引入到流形學(xué)習(xí)中來(lái)是一個(gè)很有希望的方向。這樣的工作在最近一年已經(jīng)有出現(xiàn)的跡象。
看一些問(wèn)到人臉識(shí)別有關(guān)的問(wèn)題。由于此文結(jié)尾寫(xiě)得有點(diǎn)草，我這里再補(bǔ)充一下。
dodo
1）人臉識(shí)別的識(shí)別效果首先取決于 visual feature，圖片中表示的模式和一般的向量模式還是有很大差別的。visual feature的好壞，決定了你所用的向量到底能不能代表這個(gè)圖像中的模式和這個(gè)模式與其他模式的正確關(guān)系，如果能，那再談降維識(shí)別的事情。
結(jié)構(gòu)能保持，效果就好；不能保持，就很難說(shuō)。
2）現(xiàn)在流形學(xué)習(xí)中的極大多數(shù)方法不收斂。正因?yàn)檫@樣，在原始樣本集中，如果增添少部分點(diǎn)，或是減少少部分點(diǎn)，或是擾動(dòng)少部分點(diǎn)，都會(huì)對(duì)最后的nonlinear embedding產(chǎn)生影響。也就是說(shuō)，極不穩(wěn)定。
到現(xiàn)在為止，就 Laplacian Eigenmaps 有收斂性的證明。但是，這個(gè)被證明的結(jié)果的前提條件是啥，這個(gè)很重要。如果是均勻采樣，那么基本對(duì)實(shí)際用處不大，理論上有引導(dǎo)作用。
3）采樣的問(wèn)題，包括采樣密度和采樣方式，都對(duì)最后結(jié)果有顯著影響。而實(shí)際數(shù)據(jù)都是非常復(fù)雜的。
4）最后降到多少維的問(wèn)題。這個(gè)對(duì)于流行學(xué)習(xí)來(lái)說(shuō)，也是一個(gè)正在爭(zhēng)論探討的問(wèn)題。
5）多流形的問(wèn)題。現(xiàn)在的流形學(xué)習(xí)算法能處理的流形情況非常的弱，前提建設(shè)的條件非常的強(qiáng)，比如單坐標(biāo)系統(tǒng)覆蓋，與歐式空間的開(kāi)子集等距等等。對(duì)于具有不同維數(shù)的多流形混合的問(wèn)題，還沒(méi)有人能解。而
這恰恰是模式識(shí)別中一個(gè)合理的情況?。ň哂胁煌S數(shù)的多流形混合的問(wèn)題）
而4）5）后兩者是緊緊聯(lián)系在一起。
這幾點(diǎn)也是流形學(xué)習(xí)能發(fā)揮其威力必須克服的問(wèn)題。實(shí)際的情況并不是像一些人說(shuō)的“流形學(xué)習(xí)已經(jīng)做爛了”，問(wèn)題在于
1）沒(méi)有找到真正的問(wèn)題在哪，
2）知道問(wèn)題在哪兒，解決不了。
這就是流形學(xué)習(xí)目前的狀況，如果你能用恰當(dāng)?shù)睦碚?，而不是技巧和?shí)驗(yàn)，解決了2）、5）其中一個(gè)問(wèn)題，你就會(huì)是流形學(xué)習(xí)進(jìn)入下一個(gè)黃金時(shí)期的功臣。
而現(xiàn)在的情況是，引導(dǎo)和開(kāi)創(chuàng)流形學(xué)習(xí)進(jìn)入第一個(gè)黃金時(shí)期和為這個(gè)黃金時(shí)期推波助瀾的那第一撥人，大都不再為此而努力了。現(xiàn)在就M. Belkin還在第一線為2）問(wèn)題而奮斗。
另外一個(gè)可喜的局面是，那些專職搞數(shù)值和幾何的數(shù)學(xué)人開(kāi)始涉足此領(lǐng)域，這必將帶動(dòng)流形學(xué)習(xí)這個(gè)方向深入發(fā)展，這也是這個(gè)方向發(fā)展的一個(gè)必然。