2014.7.3流形學(xué)習(xí)算法研究

1、流形學(xué)習(xí)流形學(xué)習(xí)算法算法研究研究勇于開始，才能找到成功的路匯報提綱匯報提綱研究背景研究背景一 理論基礎(chǔ)理論基礎(chǔ)二典型算法分析典型算法分析三總結(jié)總結(jié)四勇于開始，才能找到成功的路3一、研究背景一、研究背景 信息冗余信息冗余 維數(shù)災(zāi)難維數(shù)災(zāi)難 任務(wù)需求任務(wù)需求維數(shù)約簡維數(shù)約簡勇于開始，才能找到成功的路維數(shù)約簡：維數(shù)約簡： 假設(shè)假設(shè) 個維數(shù)為個維數(shù)為 的高維數(shù)據(jù)點(diǎn)的高維數(shù)據(jù)點(diǎn)降降 維維 后后 得得 到到 維維 數(shù)數(shù) 為為 ( )的的 低低 維維 結(jié)結(jié) 果果12 ,.D nnXx xxRdD12n,.Rd nYy yy，若存在映射 ,使得( )iiyf x則把則把 到到 的過程稱為維數(shù)約簡。的過程稱為維

2、數(shù)約簡。XYnDdf 若若 為為 的線性函數(shù)的線性函數(shù)，則則 稱為線性降維稱為線性降維；否則，否則，稱為非線性降維。稱為非線性降維。fxf1:fYX為為嵌入映射嵌入映射。線性維數(shù)約簡：線性維數(shù)約簡：PCA（Principal Component Analysis）：主分量分）：主分量分析析(Jolliffe, 2002; Turk and Pentland, 1991) LDA（Linear Discriminant Analysis, ）(Duda et al., 2001)：線性判別分析：線性判別分析線性維數(shù)約簡方法：線性維數(shù)約簡方法：優(yōu)點(diǎn)：優(yōu)點(diǎn)：1.對線性結(jié)構(gòu)分布的數(shù)據(jù)集有較好的降維效果

3、；對線性結(jié)構(gòu)分布的數(shù)據(jù)集有較好的降維效果；2.在壓縮、降噪以及數(shù)據(jù)可視化等方面非常有效的。在壓縮、降噪以及數(shù)據(jù)可視化等方面非常有效的。3.計算簡單，易于理解計算簡單，易于理解缺點(diǎn)：缺點(diǎn)： 對呈現(xiàn)出結(jié)構(gòu)非線性或?qū)傩詮?qiáng)相關(guān)性的數(shù)據(jù)集，對呈現(xiàn)出結(jié)構(gòu)非線性或?qū)傩詮?qiáng)相關(guān)性的數(shù)據(jù)集，無法發(fā)現(xiàn)復(fù)雜的非線性數(shù)據(jù)的內(nèi)在本質(zhì)結(jié)構(gòu)。無法發(fā)現(xiàn)復(fù)雜的非線性數(shù)據(jù)的內(nèi)在本質(zhì)結(jié)構(gòu)。1999，人工神經(jīng)網(wǎng)絡(luò)（，人工神經(jīng)網(wǎng)絡(luò)（Artificial Neural Networks，ANN）的發(fā)展與興起；）的發(fā)展與興起；20 世紀(jì)世紀(jì) 90 年代中期，基于核的非線性方法的提年代中期，基于核的非線性方法的提出出 (Boser et al

4、., 1992; Cristianini and Shawe-Taylor, 2000; Schlkopf and Smola, 2002)。勇于開始，才能找到成功的路 2000，Seung 等，等， Science，The manifold ways of perception，視覺感知的流形結(jié)構(gòu)假說視覺感知的流形結(jié)構(gòu)假說。 流形學(xué)習(xí)可能是人類認(rèn)知中一種自然的行為方式。流形學(xué)習(xí)可能是人類認(rèn)知中一種自然的行為方式。 流形是感知的基礎(chǔ)，人類的視覺記憶是以一種穩(wěn)定的流流形是感知的基礎(chǔ)，人類的視覺記憶是以一種穩(wěn)定的流形形式存貯在大腦中形形式存貯在大腦中,人類具有捕獲流形結(jié)構(gòu)的能力；人類具有捕獲流形結(jié)

5、構(gòu)的能力；勇于開始，才能找到成功的路2000，Science，一種非線性維數(shù)約簡的全局幾何框架一種非線性維數(shù)約簡的全局幾何框架，局部線性嵌入的非線性維數(shù)約簡局部線性嵌入的非線性維數(shù)約簡等距特征映射算法（等距特征映射算法（Isometric Feature Mapping ，ISOMAP）(Tenenbaum et al., 2000),局部線性嵌入算法局部線性嵌入算法（Locally Linear Embedding，LLE）(Roweis and Saul, 2000)。 高維數(shù)據(jù)的學(xué)習(xí)實(shí)質(zhì)上可以理解為對嵌入在高維空間的低高維數(shù)據(jù)的學(xué)習(xí)實(shí)質(zhì)上可以理解為對嵌入在高維空間的低維流形的學(xué)習(xí)維流形的

6、學(xué)習(xí)(Roweis and Saul, 2000; Tenenbaum et al., 2000)。勇于開始，才能找到成功的路二、理論基礎(chǔ)二、理論基礎(chǔ)v流形流形v流形學(xué)習(xí)流形學(xué)習(xí)勇于開始，才能找到成功的路121.1.流形流形 流形是線性子空間的一種非線性推廣流形是線性子空間的一種非線性推廣 拓?fù)鋵W(xué)角度：局部區(qū)域線性，與低維歐式空間拓?fù)渫負(fù)鋵W(xué)角度：局部區(qū)域線性，與低維歐式空間拓?fù)渫咄?1 引自S.T. Roweis et al. 2000#1Swiss-rollS-curveFishbow勇于開始，才能找到成功的路13v流形的數(shù)學(xué)定義流形的數(shù)學(xué)定義 設(shè)設(shè) 是一個是一個Hausdorff拓?fù)淇?/p>

7、間，若對每一點(diǎn)拓?fù)淇臻g，若對每一點(diǎn) 都有都有 的一個開鄰域的一個開鄰域 和和 的一個開子集同胚的一個開子集同胚, 則稱則稱 為為 維拓?fù)淞餍尉S拓?fù)淞餍? 簡稱為簡稱為 維流形維流形.1.1.流形流形MpMpUddMd#1 引自M. H. Law, 2004Mx1x2R2Rnzxx: coordinate for zUThe view angles of pedestrian postures change along the coordinate v, and the body configurations change along the coordinate b.勇于開始，才能找到成功的路

8、15v 一些基本數(shù)學(xué)概念一些基本數(shù)學(xué)概念 拓?fù)洌負(fù)洌琀ausdorff 空間，坐標(biāo)卡，微分結(jié)構(gòu)空間，坐標(biāo)卡，微分結(jié)構(gòu) 光滑函數(shù)，光滑映射，切向量，切空間光滑函數(shù)，光滑映射，切向量，切空間 v 參考文獻(xiàn)參考文獻(xiàn) 陳省身陳省身, 陳維桓陳維桓, 微分幾何講義微分幾何講義. 北京大學(xué)出版社北京大學(xué)出版社, 1983 M Berger, B Gostiaux. Differential Geometry: Manifolds, Curves and Surfaces, GTM115. Springer-Verlag, 1974 陳維桓陳維桓, 微分流形初步微分流形初步(第二版第二版). 高等教育出版

9、社高等教育出版社, 20011.1.流形流形勇于開始，才能找到成功的路2.2.流形學(xué)習(xí)流形學(xué)習(xí) 流形學(xué)習(xí)流形學(xué)習(xí)(Manifold Learning), 2000年科學(xué)雜志年科學(xué)雜志Science首次提出。用于從高維采樣數(shù)據(jù)恢復(fù)低維首次提出。用于從高維采樣數(shù)據(jù)恢復(fù)低維流形結(jié)構(gòu)，流形結(jié)構(gòu)，是一種非線性降維方法是一種非線性降維方法（另一種是核（另一種是核方法）。方法）。 勇于開始，才能找到成功的路172.2.流形學(xué)習(xí)的數(shù)學(xué)定義流形學(xué)習(xí)的數(shù)學(xué)定義 設(shè)設(shè) 是一個低維流形是一個低維流形, , 是一是一個光滑嵌入個光滑嵌入, ,其中其中 DdDd 。數(shù)據(jù)集。數(shù)據(jù)集 是隨機(jī)生成是隨機(jī)生成的的, , 且經(jīng)過且

10、經(jīng)過f f 映射為觀察空間的數(shù)據(jù)映射為觀察空間的數(shù)據(jù) 。流形學(xué)習(xí)就是在給定觀察樣本集流形學(xué)習(xí)就是在給定觀察樣本集 的條件下重的條件下重構(gòu)構(gòu) f f 和和 。dRY DRYf:iy).(iiyfx ixiy勇于開始，才能找到成功的路18非線性降維高維數(shù)據(jù)空間data / observation space低維嵌入空間embedding / coordinate space保持一定幾何拓?fù)潢P(guān)系，如測地距離/鄰域線性重構(gòu)關(guān)系2.2.流形學(xué)習(xí)示例流形學(xué)習(xí)示例三、典型算法分析流形學(xué)習(xí)方法：流形學(xué)習(xí)方法：全局特性保持方法全局特性保持方法局部特性保持方法局部特性保持方法 全局特性保持方法基于低維流形的全局特

11、性保持方法基于低維流形的全局幾何特性全局幾何特性，構(gòu)造，構(gòu)造所有數(shù)據(jù)所有數(shù)據(jù)點(diǎn)對點(diǎn)對之間的全局度量矩陣，然后運(yùn)算得到數(shù)據(jù)集的內(nèi)在低維表示。之間的全局度量矩陣，然后運(yùn)算得到數(shù)據(jù)集的內(nèi)在低維表示。 局部特性保持方法基于保持局部特性保持方法基于保持流形的局部幾何特性流形的局部幾何特性，即外圍觀測空，即外圍觀測空間鄰域數(shù)據(jù)所具有的局部幾何特性在內(nèi)在低維空間得以保持間鄰域數(shù)據(jù)所具有的局部幾何特性在內(nèi)在低維空間得以保持, , 然后運(yùn)然后運(yùn)算以構(gòu)造全局唯一的低維坐標(biāo)。算以構(gòu)造全局唯一的低維坐標(biāo)。三、典型算法分析勇于開始，才能找到成功的路21三、典型算法分析-ISOMAP 全局特性保持方法基本步驟 思想核心：

12、思想核心： 較較近近點(diǎn)對之間的測地距離用點(diǎn)對之間的測地距離用歐式距離歐式距離代替代替 較較遠(yuǎn)遠(yuǎn)點(diǎn)對之間的測地距離用點(diǎn)對之間的測地距離用最短路徑最短路徑來逼近來逼近測地距離：測地線的長度（測地線測地距離：測地線的長度（測地線: 流形上連接兩個點(diǎn)的最短曲線）流形上連接兩個點(diǎn)的最短曲線）勇于開始，才能找到成功的路23三、典型算法分析-ISOMAP 測地距離反映數(shù)據(jù)在流形上的真實(shí)距離差異測地距離反映數(shù)據(jù)在流形上的真實(shí)距離差異歐式距離 vs.測地距離最短路徑近似測地距離降維嵌入空間勇于開始，才能找到成功的路24算法流程1 1、構(gòu)造近鄰圖、構(gòu)造近鄰圖G G 計算每個樣本點(diǎn)與計算每個樣本點(diǎn)與所有其他所有其他

13、樣本點(diǎn)之間的歐式距離。如果樣本點(diǎn)樣本點(diǎn)之間的歐式距離。如果樣本點(diǎn) 和和 的歐式距離的歐式距離 小于一個閾值小于一個閾值 ，或者點(diǎn)，或者點(diǎn) 是點(diǎn)是點(diǎn) 的的 近鄰點(diǎn)，那么判近鄰點(diǎn)，那么判定這兩點(diǎn)彼此相鄰，定這兩點(diǎn)彼此相鄰，在圖在圖G 中用邊連接，邊的權(quán)重為中用邊連接，邊的權(quán)重為 ；2 2、計算最短路徑、計算最短路徑 對于相鄰樣本點(diǎn)對于相鄰樣本點(diǎn) 和和 ，設(shè)置其初始最短路徑為，設(shè)置其初始最短路徑為 ，否則，否則為為 。對。對 分別設(shè)置為分別設(shè)置為 , 為樣本點(diǎn)數(shù)，計算為樣本點(diǎn)數(shù)，計算 ,得到最短路徑距離矩陣得到最短路徑距離矩陣ixjxXd (i, j)ixjxkXd (i, j)ixjxGXd (i

14、, j)= d (i, j)l1,2.nnGGGGd (i, j)= mind (i, j),d (i,l)+d (l, j)GD勇于開始，才能找到成功的路25算法流程3 3、 計算計算d d維嵌入維嵌入用用MDSMDS算法應(yīng)用到算法應(yīng)用到 , ,通過極小化下列目標(biāo)函數(shù)來獲得全局低維坐標(biāo)通過極小化下列目標(biāo)函數(shù)來獲得全局低維坐標(biāo)Y Y 表示低維嵌入坐標(biāo)的歐式距離矩陣表示低維嵌入坐標(biāo)的歐式距離矩陣 表示表示L L2 2矩陣范數(shù)，矩陣操作算子矩陣范數(shù)，矩陣操作算子 是平方距離矩陣是平方距離矩陣 ， 是中心化矩陣是中心化矩陣設(shè)設(shè) 和和 分別是矩陣分別是矩陣 的第的第p p個特征值和相應(yīng)的特征向量，當(dāng)?shù)?/p>

15、維個特征值和相應(yīng)的特征向量，當(dāng)?shù)途S嵌入坐標(biāo)嵌入坐標(biāo)Y Y取矩陣取矩陣 的前的前d d個最大特征值對應(yīng)的特征向量時，即個最大特征值對應(yīng)的特征向量時，即 ，目標(biāo)函數(shù)達(dá)到全局最小。，目標(biāo)函數(shù)達(dá)到全局最小。GDGY2E=(D )- (D ) LYDYijd (i, j)= y - y22ijLijAA/ 2G(D )HSH S2ijijS = DijijH =-1/ nHppvG(D )G(D )T1n1y ,.y 1,.,ddYvv算法分析 時間復(fù)雜度時間復(fù)雜度: 計算計算DG矩陣為矩陣為O(kn2logn)(k為近鄰數(shù)為近鄰數(shù),dijkstra算法算法)；應(yīng)用；應(yīng)用MDS的特征的特征分解為分解為O

16、(n3)。 優(yōu)點(diǎn)：優(yōu)點(diǎn)： 保持全局幾何特性；保持全局幾何特性； 缺點(diǎn)：缺點(diǎn)： 樣本數(shù)量樣本數(shù)量n 較大時，算法的計算效率低；較大時，算法的計算效率低； 使用場合：使用場合： 適用于學(xué)習(xí)內(nèi)部平坦的低維流形；適用于學(xué)習(xí)內(nèi)部平坦的低維流形；不適于學(xué)習(xí)有較大內(nèi)在曲率的流形。不適于學(xué)習(xí)有較大內(nèi)在曲率的流形。勇于開始，才能找到成功的路27三、典型算法分析-LLE局部特性保持方法局部特性保持方法-保局流形算法保局流形算法利用流形在局部可看作歐氏空間的觀點(diǎn)，建立利用流形在局部可看作歐氏空間的觀點(diǎn)，建立局部模型，然后整合排列局部幾何模型，以構(gòu)造局部模型，然后整合排列局部幾何模型，以構(gòu)造全局唯一的低維坐標(biāo)全局唯一

17、的低維坐標(biāo)-分而治之。分而治之。勇于開始，才能找到成功的路28vLLE (Locally linear embedding) 前提假設(shè)前提假設(shè) 采樣數(shù)據(jù)所在的低維流形在局部是線性的采樣數(shù)據(jù)所在的低維流形在局部是線性的 每個采樣點(diǎn)均可以利用其近鄰樣本進(jìn)行線性重構(gòu)表示每個采樣點(diǎn)均可以利用其近鄰樣本進(jìn)行線性重構(gòu)表示 學(xué)習(xí)目標(biāo)學(xué)習(xí)目標(biāo) 低維空間中保持每個鄰域中的重構(gòu)權(quán)值不變低維空間中保持每個鄰域中的重構(gòu)權(quán)值不變 在嵌入映射為局部線性的條件下，最小化重構(gòu)誤差在嵌入映射為局部線性的條件下，最小化重構(gòu)誤差 最終形式化為特征值分解問題最終形式化為特征值分解問題三、典型算法分析-LLE勇于開始，才能找到成功的路

18、29三、典型算法分析-LLELLE 算法基本步驟算法基本步驟勇于開始，才能找到成功的路30LLELLE算法流程算法流程 1.1.計算每一個點(diǎn)計算每一個點(diǎn) 的近鄰點(diǎn)的近鄰點(diǎn), , 一般采用一般采用K K 近鄰或者近鄰或者 鄰域鄰域; ;2.2.計算權(quán)值計算權(quán)值 使得把使得把 用它的用它的K K個近鄰點(diǎn)線性表示的誤差最小個近鄰點(diǎn)線性表示的誤差最小, , 即通過最小化即通過最小化 來求出來求出 ; ;3.3.保持權(quán)值保持權(quán)值 不變不變, , 求求 在低維空間的象在低維空間的象 , , 使使得低維重構(gòu)誤差最小。得低維重構(gòu)誤差最小。，ijWiYijWjijiXWX ijWiXiXiX勇于開始，才能找到成

19、功的路31LLELLE算法的求解算法的求解1.1.根據(jù)歐氏距離，計算每一個點(diǎn)根據(jù)歐氏距離，計算每一個點(diǎn) 的近鄰點(diǎn)；的近鄰點(diǎn)；2.2.對于點(diǎn)對于點(diǎn) 和它的近鄰點(diǎn)的權(quán)值和它的近鄰點(diǎn)的權(quán)值 , , 3.3.令令 , , 低維嵌低維嵌是是M M的最小的的最小的第第2 2到第到第d d1 1個特征向量。個特征向量。 iXiXijW.X, ,XX 11的近鄰點(diǎn)為）（）（其中，iljlijiijklmilmkijkijGGGW)()(TWIWIM勇于開始，才能找到成功的路33計算復(fù)雜度：計算復(fù)雜度： 選擇鄰域?yàn)檫x擇鄰域?yàn)镺 ( Dn2 )，計算重構(gòu)權(quán)值矩陣，計算重構(gòu)權(quán)值矩陣O ( D + k ) k2 n)

20、，求解低維嵌入求解低維嵌入Y 為為O ( dn2 )。優(yōu)點(diǎn)優(yōu)點(diǎn)算法可以學(xué)習(xí)任意維的局部線性的低維流形算法可以學(xué)習(xí)任意維的局部線性的低維流形算法歸結(jié)為稀疏矩陣特征值計算，計算復(fù)雜度相對較小算法歸結(jié)為稀疏矩陣特征值計算，計算復(fù)雜度相對較小LLELLE算法的分析算法的分析缺點(diǎn)缺點(diǎn)算法所學(xué)習(xí)的流形只能是不閉合的算法所學(xué)習(xí)的流形只能是不閉合的算法要求樣本在流形上是稠密采樣的算法要求樣本在流形上是稠密采樣的算法對樣本中的噪聲和鄰域參數(shù)比較敏感算法對樣本中的噪聲和鄰域參數(shù)比較敏感勇于開始，才能找到成功的路34vLE (Laplacian Eigenmap) 2002年，年，Belkin 和和Niyogi 基

21、本思想：在高維空間中離得很近的點(diǎn)投影到低基本思想：在高維空間中離得很近的點(diǎn)投影到低維空間中的象也應(yīng)該離得很近。維空間中的象也應(yīng)該離得很近。 求解方法：利用流形上求解方法：利用流形上Laplacian-Beltrami算子算子的特征函數(shù)的特征函數(shù)三、典型算法分析-LE勇于開始，才能找到成功的路35流形流形Laplacian-Beltram算子算子:一般記作一般記作 （delta）定義：定義：設(shè)設(shè) M M 是光滑的黎曼流形是光滑的黎曼流形, ,f是是 M M 上的光滑函數(shù)上的光滑函數(shù), , （nabla算子）是）是f的梯度的梯度, , 則稱則稱 為為 M M 上的拉普拉斯算子上的拉普拉斯算子, ,

22、 其中其中divdiv是散度算子。是散度算子。 f:div()ff 函數(shù)函數(shù) 的梯度為：的梯度為： 梯度的負(fù)散度函數(shù)梯度的負(fù)散度函數(shù)f 的拉普拉斯算子是笛卡兒坐標(biāo)系中的所有的拉普拉斯算子是笛卡兒坐標(biāo)系中的所有非混合非混合二階偏導(dǎo)數(shù)：二階偏導(dǎo)數(shù)： 二維空間二維空間 三維空間三維空間 根據(jù)譜圖理論，如果數(shù)據(jù)均勻采樣于高維空間中的低維流形，那么可以用圖的根據(jù)譜圖理論，如果數(shù)據(jù)均勻采樣于高維空間中的低維流形，那么可以用圖的Laplacian矩陣去逼近流形上矩陣去逼近流形上Laplacian-Beltrami算子，進(jìn)而可以用圖的算子，進(jìn)而可以用圖的Laplacian的特征向量去逼近流形上的特征向量去逼近流形上Laplacian-Beltrami算子的特征函數(shù)算子的特征函數(shù)(Belkin and Niyogi, 2003)。 勇于開始，才能找到成功的路37Laplacian Eigenmap 算法流程算法流程1.1.構(gòu)