模式識(shí)別課件 流形學(xué)習(xí)

流形學(xué)習(xí)流行學(xué)習(xí)NonlinearMethodsIsomap，laplacianeigenmap(LE)locallinearembedding(LLE)LinearMethodsIsometricProjection，LPP，NPE，

UDP,2DLPP,tensorLPP,tensorNPE假定：數(shù)據(jù)的內(nèi)在特征都嵌入在低維非線性流形面上幾種非線性流形學(xué)習(xí)算法

局部線性嵌入(LLE).S.T.RoweisandL.K.Saul.Nonlineardimensionalityreductionbylocallylinearembedding.Science,vol.290,pp.2323--2326,2000.

等距映射(Isomap).J.B.Tenenbaum,V.deSilva,andJ.C.Langford.Aglobalgeometricframeworkfornonlineardimensionalityreduction.Science,vol.290,pp.2319--2323,2000.

拉普拉斯特征映射(LaplacianEigenmap).M.Belkin,P.Niyogi,LaplacianEigenmapsforDimensionalityReductionandDataRepresentation.NeuralComputation,

Vol.15,Issue6,pp.1373–1396,2003.

LLE（locallylinearembedding）LLE算法的主要思想：對(duì)于一組具有嵌套流形的數(shù)據(jù)集，在嵌套空間與內(nèi)在低維空間局部鄰域間的點(diǎn)的關(guān)系應(yīng)該保持不變。即在嵌套空間每個(gè)采樣點(diǎn)可以用它的近鄰點(diǎn)線性表示，在低維空間中保持每個(gè)鄰域中的權(quán)值不變，重構(gòu)原數(shù)據(jù)點(diǎn),使重構(gòu)誤差最小.LLE算法示意圖LLE（locallylinearembeddingLLE（locallylinearembedding）2.算法步驟：1）設(shè)D維空間中有N個(gè)數(shù)據(jù)屬于同一流形，記做：Xi＝〔xi1,xi2,...,xiD〕，i=1～N。假設(shè)有足夠的數(shù)據(jù)點(diǎn)，并且認(rèn)為空間中的每一個(gè)數(shù)據(jù)點(diǎn)可以用它的K個(gè)近鄰線性表示。求近鄰點(diǎn)，一般采用K近鄰或者鄰域.2）計(jì)算權(quán)值Wij，代價(jià)函數(shù)為：，（1）并且權(quán)值要滿足兩個(gè)約束條件：<1>每一個(gè)數(shù)據(jù)點(diǎn)Xi都只能由它的鄰近點(diǎn)來(lái)表示，若Xj不是近鄰點(diǎn)，則Wij=0；<2>權(quán)值矩陣的每一行的和為1，即：。這樣，求最優(yōu)權(quán)值就是對(duì)于公式（1）在兩個(gè)約束條件下求解最小二乘問(wèn)題。權(quán)值體現(xiàn)了數(shù)據(jù)間內(nèi)在的幾何關(guān)系。

LLE（locallylinearembedding）3）保持權(quán)值不變，在低維空間d（d<<D）中對(duì)原數(shù)據(jù)點(diǎn)重構(gòu)。設(shè)低維空間的數(shù)據(jù)點(diǎn)為Yi，可以通過(guò)求最小的代價(jià)函數(shù)

最優(yōu)解需要滿足下面的約束條件：

條件1消除了Y向量平移不變的影響；條件2避免產(chǎn)生退化解。LLE

由Rayleittz-Riz定理，低維嵌入是M的最小的第2到第d＋1個(gè)特征向量.去掉最小特征值0對(duì)應(yīng)的特征向量。LLE算法的優(yōu)點(diǎn)LLE算法可以學(xué)習(xí)任意維數(shù)的低維流形.LLE算法中的待定參數(shù)很少,K和d.LLE算法中每個(gè)點(diǎn)的近鄰權(quán)值在平移,旋轉(zhuǎn),伸縮變換下是保持不變的.LLE算法有解析的整體最優(yōu)解,不需迭代.LLE算法歸結(jié)為稀疏矩陣特征值計(jì)算,計(jì)算復(fù)雜度相對(duì)較小,容易執(zhí)行.LLE算法的缺點(diǎn)LLE算法要求所學(xué)習(xí)的流形只能是不閉合的且在局部是線性的.LLE算法要求樣本在流形上是稠密采樣的.LLE算法中的參數(shù)K,d有過(guò)多的選擇.LLE算法對(duì)樣本中的噪音很敏感.對(duì)于新樣本的映射需要重新計(jì)算。RReferencesS.T.RoweisandL.K.Saul.Nonlineardimensionalityreductionbylocallylinearembedding.Science,vol.290,pp.2323--2326,2000.OlgaKouropteva,OlegOkunandMattiPietikainen.Selectionoftheoptimalparametervalueforthelocallylinearembeddingalgorithm,PatternRecognitionLetetrs,2006,968-979-------多維尺度變換(MDS)MDS是一種非監(jiān)督的維數(shù)約簡(jiǎn)方法.MDS的基本思想:約簡(jiǎn)后低維空間中任意兩點(diǎn)間的距離應(yīng)該與它們?cè)谠伎臻g中的距離相同.MDS的求解:通過(guò)適當(dāng)定義準(zhǔn)則函數(shù)來(lái)體現(xiàn)在低維空間中對(duì)高維距離的重建誤差,對(duì)準(zhǔn)則函數(shù)用梯度下降法求解,對(duì)于某些特殊的距離可以推導(dǎo)出解析解法.ISOMAP建立在多維尺度變換(MDS)的基礎(chǔ)上，力求保持?jǐn)?shù)據(jù)點(diǎn)的內(nèi)在幾何性質(zhì)，即保持兩點(diǎn)間的測(cè)地距離.等距映射(Isomap)的基本思想ISOMAP1高維數(shù)據(jù)所在的低維流形與歐氏空間的一個(gè)子集是整體等距的.2與數(shù)據(jù)所在的流形等距的歐氏空間的子集是一個(gè)凸集.Isomap的前提假設(shè)估計(jì)兩點(diǎn)間的測(cè)地距離:

1離得很近的點(diǎn)間的測(cè)地距離用歐氏距離代替.2離得較遠(yuǎn)的點(diǎn)間的測(cè)地距離用最短路徑來(lái)逼近.Isomap算法的核心ISOMAP測(cè)地距離估計(jì)ISOMAPIsomap算法1計(jì)算每個(gè)點(diǎn)的近鄰點(diǎn)(用K近鄰或鄰域).2在樣本集上定義一個(gè)賦權(quán)無(wú)向圖如果和互為近鄰點(diǎn)，則邊的權(quán)值為3計(jì)算圖中兩點(diǎn)間的最短距離，記所得的距離矩陣為4用MDS求低維嵌入流形,???代價(jià)函數(shù)：令低維嵌入是

的第2小到第d＋1小的特征值所對(duì)應(yīng)的特征向量.（推導(dǎo)）Isomap算法的特點(diǎn)Isomap是非線性的,適用于學(xué)習(xí)內(nèi)部平坦的低維流形,不適于學(xué)習(xí)有較大內(nèi)在曲率的流形.Isomap算法中有兩個(gè)待定參數(shù)K,d.Isomap算法計(jì)算圖上兩點(diǎn)間的最短距離,執(zhí)行起來(lái)比較慢.RISOMAP拉普拉斯特征映射(LaplacianEigenmap)

基本思想：在高維空間中離得很近的點(diǎn)投影到低維空間中的象也應(yīng)該離得很近.通過(guò)使用兩點(diǎn)間的加權(quán)距離作為損失函數(shù)，可求得相應(yīng)的降維結(jié)果。待優(yōu)化的目標(biāo)函數(shù)：

s.t.（矩陣D提供了對(duì)圖的頂點(diǎn)的一種自然測(cè)度，Dii越大，說(shuō)明這個(gè)頂點(diǎn)越重要。）求解方法：求解圖拉普拉斯算子的廣義特征值問(wèn)題.示意圖LaplacianEigenmap算法1從樣本點(diǎn)構(gòu)建一個(gè)近鄰圖,圖的頂點(diǎn)為樣本點(diǎn)，離得很近兩點(diǎn)用邊相連(K近鄰或鄰域）.2給每條邊賦予權(quán)值如果第

個(gè)點(diǎn)和第j個(gè)點(diǎn)不相連，權(quán)值為0，否則(a);(b)LaplacianEigenmap算法3計(jì)算圖拉普拉斯算子的廣義特征向量，求得低維嵌入.優(yōu)化問(wèn)題可化簡(jiǎn)為：令D為對(duì)角矩陣L是近鄰圖上的拉普拉斯算子，求解y轉(zhuǎn)為求廣義特征值問(wèn)題

最小特征值對(duì)應(yīng)的特征向量。(由Rayleittz-Riz定理)

LaplacianEigenmap算法的特點(diǎn)

算法是局部的非線性方法.

算法與譜圖理論有很緊密的聯(lián)系.

算法中有兩個(gè)參數(shù)k,d.

算法通過(guò)求解稀疏矩陣的特征值問(wèn)題解析地求出整體最優(yōu)解.

算法使原空間中離得很近的點(diǎn)在低維空間也離得很近,可以用于聚類.

LLE,Isomap,LaplacianEigenmap有效的原因1它們都是非參數(shù)的方法，不需要對(duì)流形的很多的參數(shù)假設(shè).2它們是非線性的方法，都基于流形的內(nèi)在幾何結(jié)構(gòu)，更能體現(xiàn)現(xiàn)實(shí)中數(shù)據(jù)的本質(zhì).3它們的求解簡(jiǎn)單，都轉(zhuǎn)化為求解特征值問(wèn)題，而不需要用迭代算法.流形學(xué)習(xí)問(wèn)題探討11對(duì)嵌入映射或者低維流形作出某種特定的假設(shè),或者以保持高維數(shù)據(jù)的某種性質(zhì)不變?yōu)槟繕?biāo).2將問(wèn)題轉(zhuǎn)化為求解優(yōu)化問(wèn)題.3提供有效的算法.

為流形學(xué)習(xí)提供更為堅(jiān)實(shí)和易于接受的認(rèn)知基礎(chǔ).

如何確定低維目標(biāo)空間的維數(shù).

當(dāng)采樣數(shù)據(jù)很稀疏時(shí),怎樣進(jìn)行有效的學(xué)習(xí).

將統(tǒng)計(jì)學(xué)習(xí)理論引入流形學(xué)習(xí)對(duì)其泛化性能進(jìn)行研究.流形學(xué)習(xí)問(wèn)題探討2流形學(xué)習(xí)問(wèn)題探討3

流形學(xué)習(xí)作為一種非線性降維或數(shù)據(jù)可視化的方法已經(jīng)在圖像處理如人臉圖像,手寫(xiě)數(shù)字圖像,語(yǔ)言處理方面取得了較好的效果.

將其作為一種監(jiān)督的學(xué)習(xí)方法用于模式識(shí)別,雖然有研究者涉足,但是目前在這方面的工作還很有限.幾種線性流行學(xué)方法LPPX.He,S.Yan,Y.Hu,P.Niyogi,andH.Zhang.FaceRecognitionUsingLaplacianfaces.IEEETrans.PAMI,27(3):328-340,2005.NPEX.He,D.Cai,S.Yan,andH.Zhang.NeighborhoodPreservingEmbedding.ProceedingoftheTenthIEEEInternationalConferenceonComputerVision,2005IsomatricProjectionD.Cai,X.He,andJ.Han.IsometricProjection.AssociationfortheAdvancementofArtificialIntelligence,2007局部保持投影

LocalityPreservingProjection(LPP)局部保持投影目標(biāo)函數(shù)：

其中是一個(gè)權(quán)重矩陣，定義如下：通過(guò)簡(jiǎn)單的推算得到：

局部保持投影

這里