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

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

勇于開始，才能找到成功的路匯報提綱研究背景一理論基礎(chǔ)二典型算法分析三總結(jié)四勇于開始，才能找到成功的路3一、研究背景信息冗余維數(shù)災(zāi)難任務(wù)需求維數(shù)約簡勇于開始，才能找到成功的路維數(shù)約簡：假設(shè)個維數(shù)為

的高維數(shù)據(jù)點降維后得到維數(shù)為()的低維結(jié)果，若存在映射,使得則把

到

的過程稱為維數(shù)約簡。若為的線性函數(shù)，則稱為線性降維；否則，稱為非線性降維。為嵌入映射。線性維數(shù)約簡：PCA（PrincipalComponentAnalysis）：主分量分析(Jolliffe,2002;TurkandPentland,1991)

LDA（LinearDiscriminantAnalysis,）(Dudaetal.,2001)：線性判別分析線性維數(shù)約簡方法：優(yōu)點：1.對線性結(jié)構(gòu)分布的數(shù)據(jù)集有較好的降維效果；2.在壓縮、降噪以及數(shù)據(jù)可視化等方面非常有效的。3.計算簡單，易于理解缺點：對呈現(xiàn)出結(jié)構(gòu)非線性或?qū)傩詮?qiáng)相關(guān)性的數(shù)據(jù)集，無法發(fā)現(xiàn)復(fù)雜的非線性數(shù)據(jù)的內(nèi)在本質(zhì)結(jié)構(gòu)。1999，人工神經(jīng)網(wǎng)絡(luò)（ArtificialNeuralNetworks，ANN）的發(fā)展與興起；20世紀(jì)90年代中期，基于核的非線性方法的提出(Boseretal.,1992;CristianiniandShawe-Taylor,2000;Sch?lkopfandSmola,2002)。勇于開始，才能找到成功的路2000，Seung等，Science，《Themanifoldwaysofperception》，視覺感知的流形結(jié)構(gòu)假說。流形學(xué)習(xí)可能是人類認(rèn)知中一種自然的行為方式。流形是感知的基礎(chǔ)，人類的視覺記憶是以一種穩(wěn)定的流形形式存貯在大腦中,人類具有捕獲流形結(jié)構(gòu)的能力；勇于開始，才能找到成功的路2000，Science，《一種非線性維數(shù)約簡的全局幾何框架》，《局部線性嵌入的非線性維數(shù)約簡》等距特征映射算法（IsometricFeatureMapping，ISOMAP）(Tenenbaumetal.,2000),局部線性嵌入算法（LocallyLinearEmbedding，LLE）(RoweisandSaul,2000)。高維數(shù)據(jù)的學(xué)習(xí)實質(zhì)上可以理解為對嵌入在高維空間的低維流形的學(xué)習(xí)(RoweisandSaul,2000;Tenenbaumetal.,2000)。勇于開始，才能找到成功的路二、理論基礎(chǔ)流形流形學(xué)習(xí)勇于開始，才能找到成功的路121.流形流形是線性子空間的一種非線性推廣拓?fù)鋵W(xué)角度：局部區(qū)域線性，與低維歐式空間拓?fù)渫?1引自S.T.Roweisetal.2000#1Swiss-rollS-curveFishbow勇于開始，才能找到成功的路13流形的數(shù)學(xué)定義設(shè)是一個Hausdorff拓?fù)淇臻g，若對每一點都有的一個開鄰域和的一個開子集同胚,則稱為維拓?fù)淞餍?簡稱為維流形.1.流形#1引自M.H.Law,2004Mx1x2R2Rnzxx:coordinateforzUTheviewanglesofpedestrianpostureschangealongthecoordinatev,andthebodyconfigurationschangealongthecoordinateb.勇于開始，才能找到成功的路15一些基本數(shù)學(xué)概念拓?fù)洌琀ausdorff空間，坐標(biāo)卡，微分結(jié)構(gòu)光滑函數(shù)，光滑映射，切向量，切空間…參考文獻(xiàn)陳省身,陳維桓,微分幾何講義.北京大學(xué)出版社,1983MBerger,BGostiaux.DifferentialGeometry:Manifolds,CurvesandSurfaces,GTM115.Springer-Verlag,1974陳維桓,微分流形初步(第二版).高等教育出版社,20011.流形勇于開始，才能找到成功的路2.流形學(xué)習(xí)流形學(xué)習(xí)(ManifoldLearning),2000年科學(xué)雜志Science首次提出。用于從高維采樣數(shù)據(jù)恢復(fù)低維流形結(jié)構(gòu)，是一種非線性降維方法（另一種是核方法）。

勇于開始，才能找到成功的路172.流形學(xué)習(xí)的數(shù)學(xué)定義設(shè)是一個低維流形,是一個光滑嵌入,其中D>d

。數(shù)據(jù)集是隨機(jī)生成的,且經(jīng)過f映射為觀察空間的數(shù)據(jù)。流形學(xué)習(xí)就是在給定觀察樣本集的條件下重構(gòu)

f

和。勇于開始，才能找到成功的路18非線性降維高維數(shù)據(jù)空間data/observationspace低維嵌入空間embedding/coordinatespace保持一定幾何拓?fù)潢P(guān)系，如測地距離/鄰域線性重構(gòu)關(guān)系2.流形學(xué)習(xí)示例三、典型算法分析流形學(xué)習(xí)方法：全局特性保持方法局部特性保持方法全局特性保持方法基于低維流形的全局幾何特性，構(gòu)造所有數(shù)據(jù)點對之間的全局度量矩陣，然后運(yùn)算得到數(shù)據(jù)集的內(nèi)在低維表示。局部特性保持方法基于保持流形的局部幾何特性，即外圍觀測空間鄰域數(shù)據(jù)所具有的局部幾何特性在內(nèi)在低維空間得以保持,然后運(yùn)算以構(gòu)造全局唯一的低維坐標(biāo)。三、典型算法分析勇于開始，才能找到成功的路21三、典型算法分析---ISOMAP全局特性保持方法基本步驟思想核心：較近點對之間的測地距離用歐式距離代替較遠(yuǎn)點對之間的測地距離用最短路徑來逼近測地距離：測地線的長度（測地線:流形上連接兩個點的最短曲線）勇于開始，才能找到成功的路23三、典型算法分析---ISOMAP測地距離反映數(shù)據(jù)在流形上的真實距離差異歐式距離vs.測地距離最短路徑近似測地距離降維嵌入空間勇于開始，才能找到成功的路24算法流程1、構(gòu)造近鄰圖G計算每個樣本點與所有其他樣本點之間的歐式距離。如果樣本點和的歐式距離小于一個閾值，或者點是點的近鄰點，那么判定這兩點彼此相鄰，在圖G中用邊連接，邊的權(quán)重為；2、計算最短路徑對于相鄰樣本點和

，設(shè)置其初始最短路徑為，否則為。對分別設(shè)置為,為樣本點數(shù)，計算

,得到最短路徑距離矩陣勇于開始，才能找到成功的路25算法流程3、計算d維嵌入用MDS算法應(yīng)用到,通過極小化下列目標(biāo)函數(shù)來獲得全局低維坐標(biāo)Y

表示低維嵌入坐標(biāo)的歐式距離矩陣表示L2矩陣范數(shù)，矩陣操作算子是平方距離矩陣，是中心化矩陣設(shè)和分別是矩陣的第p個特征值和相應(yīng)的特征向量，當(dāng)?shù)途S嵌入坐標(biāo)Y取矩陣的前d個最大特征值對應(yīng)的特征向量時，即

，目標(biāo)函數(shù)達(dá)到全局最小。算法分析時間復(fù)雜度:計算DG矩陣為O(kn2logn)(k為近鄰數(shù),dijkstra算法)；應(yīng)用MDS的特征分解為O(n3)。優(yōu)點：

保持全局幾何特性；缺點：

樣本數(shù)量n較大時，算法的計算效率低；使用場合：適用于學(xué)習(xí)內(nèi)部平坦的低維流形；不適于學(xué)習(xí)有較大內(nèi)在曲率的流形。勇于開始，才能找到成功的路27三、典型算法分析---LLE局部特性保持方法---保局流形算法利用流形在局部可看作歐氏空間的觀點，建立局部模型，然后整合排列局部幾何模型，以構(gòu)造全局唯一的低維坐標(biāo)---分而治之。勇于開始，才能找到成功的路28LLE(Locallylinearembedding)前提假設(shè)采樣數(shù)據(jù)所在的低維流形在局部是線性的每個采樣點均可以利用其近鄰樣本進(jìn)行線性重構(gòu)表示學(xué)習(xí)目標(biāo)低維空間中保持每個鄰域中的重構(gòu)權(quán)值不變在嵌入映射為局部線性的條件下，最小化重構(gòu)誤差最終形式化為特征值分解問題三、典型算法分析---LLE勇于開始，才能找到成功的路29三、典型算法分析---LLELLE算法基本步驟勇于開始，才能找到成功的路30LLE算法流程1.計算每一個點的近鄰點,一般采用K近鄰或者鄰域;2.計算權(quán)值使得把用它的K個近鄰點線性表示的誤差最小,即通過最小化來求出;3.保持權(quán)值不變,求在低維空間的象,使得低維重構(gòu)誤差最小。勇于開始，才能找到成功的路31LLE算法的求解1.根據(jù)歐氏距離，計算每一個點的近鄰點；2.對于點和它的近鄰點的權(quán)值,3.令,低維嵌是M的最小的第2到第d＋1個特征向量。

勇于開始，才能找到成功的路33計算復(fù)雜度：

選擇鄰域為O(Dn2)，計算重構(gòu)權(quán)值矩陣O((D+k)k2n)，求解低維嵌入Y為O(dn2)。優(yōu)點算法可以學(xué)習(xí)任意維的局部線性的低維流形算法歸結(jié)為稀疏矩陣特征值計算，計算復(fù)雜度相對較小LLE算法的分析缺點算法所學(xué)習(xí)的流形只能是不閉合的算法要求樣本在流形上是稠密采樣的算法對樣本中的噪聲和鄰域參數(shù)比較敏感勇于開始，才能找到成功的路34LE(LaplacianEigenmap)2002年，Belkin和Niyogi基本思想：在高維空間中離得很近的點投影到低維空間中的象也應(yīng)該離得很近。求解方法：利用流形上Laplacian-Beltrami算子的特征函數(shù)三、典型算法分析---LE勇于開始，才能找到成功的路35流形Laplacian-Beltram算子:一般記作（delta）定義：設(shè)M是光滑的黎曼流形,f是M上的光滑函數(shù),（nabla算子）是f的梯度,則稱為M上的拉普拉斯算子,其中div是散度算子。函數(shù)

的梯度為：

梯度的負(fù)散度函數(shù)f

的拉普拉斯算子是笛卡兒坐標(biāo)系中的所有非混合二階偏導(dǎo)數(shù)：

二維空間

三維空間

根據(jù)譜圖理論，如果數(shù)據(jù)均勻采樣于高維空間中的低維流形，那么可以用圖的Laplacian矩陣去逼近流形上Laplacian-Beltrami算子，進(jìn)而可以用圖的Laplacian的特征向量去逼近流形上Laplacian-Beltrami算子的特征函數(shù)(BelkinandNiyogi,2003)。37LaplacianEigenmap算法流程1.構(gòu)建近鄰圖,(K近鄰或鄰域)。2.給每條邊賦予權(quán)值3.LE的目標(biāo)函數(shù)為極小化如下?lián)p失函數(shù)，即確保原來相鄰的樣本點投影后仍為近鄰4.對任何Y有，其中Y為Laplacian矩陣，D為對角矩陣，元素為權(quán)值矩陣的列和，即

,LE算法的優(yōu)化問題轉(zhuǎn)化為低維嵌入Y取Laplacian矩陣的最小d+1個特征值對應(yīng)的特征