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

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

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

LLE（locallylinearembedding）3）保持權值不變，在低維空間d（d<<D）中對原數(shù)據(jù)點重構。設低維空間的數(shù)據(jù)點為Yi，可以通過求最小的代價函數(shù)

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

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

由Rayleittz-Riz定理，低維嵌入是M的最小的第2到第d＋1個特征向量.去掉最小特征值0對應的特征向量。LLE算法的優(yōu)點LLE算法可以學習任意維數(shù)的低維流形.LLE算法中的待定參數(shù)很少,K和d.LLE算法中每個點的近鄰權值在平移,旋轉,伸縮變換下是保持不變的.LLE算法有解析的整體最優(yōu)解,不需迭代.LLE算法歸結為稀疏矩陣特征值計算,計算復雜度相對較小,容易執(zhí)行.LLE算法的缺點LLE算法要求所學習的流形只能是不閉合的且在局部是線性的.LLE算法要求樣本在流形上是稠密采樣的.LLE算法中的參數(shù)K,d有過多的選擇.LLE算法對樣本中的噪音很敏感.對于新樣本的映射需要重新計算。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ù)約簡方法.MDS的基本思想:約簡后低維空間中任意兩點間的距離應該與它們在原始空間中的距離相同.MDS的求解:通過適當定義準則函數(shù)來體現(xiàn)在低維空間中對高維距離的重建誤差,對準則函數(shù)用梯度下降法求解,對于某些特殊的距離可以推導出解析解法.ISOMAP建立在多維尺度變換(MDS)的基礎上，力求保持數(shù)據(jù)點的內在幾何性質，即保持兩點間的測地距離.等距映射(Isomap)的基本思想ISOMAP1高維數(shù)據(jù)所在的低維流形與歐氏空間的一個子集是整體等距的.2與數(shù)據(jù)所在的流形等距的歐氏空間的子集是一個凸集.Isomap的前提假設估計兩點間的測地距離:

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

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

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

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

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

最小特征值對應的特征向量。(由Rayleittz-Riz定理)

LaplacianEigenmap算法的特點

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

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

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

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

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

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

為流形學習提供更為堅實和易于接受的認知基礎.

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

當采樣數(shù)據(jù)很稀疏時,怎樣進行有效的學習.

將統(tǒng)計學習理論引入流形學習對其泛化性能進行研究.流形學習問題探討2流形學習問題探討3

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

將其作為一種監(jiān)督的學習方法用于模式識別,雖然有研究者涉足,但是目前在這方面的工作還很有限.幾種線性流行學方法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)局部保持投影目標函數(shù)：

其中是一個權重矩陣，定義如下：通過簡單的推算得到：

局部保持投影

這里