11.非線性流形學(xué)習(xí)方法杭

1、非線性流形學(xué)習(xí)方法介紹Introduction to Nonlinear Manifold Learning Methods劉雨杭2016年11月28日為什么引入非線性的方法？線性降維方法的不足原始數(shù)據(jù)無法表示為特征的簡單線性組合比如：PCA無法表達(dá)Helix曲線流形1-D Helix曲線流形為什么引入非線性的方法？線性降維方法的不足真實數(shù)據(jù)中的有用信息不能由線性特征表示比如：如何獲取并表示多姿態(tài)人臉的姿態(tài)信息比如：如何獲取運動視頻序列中某個動作的對應(yīng)幀#1 引自J.B. Tenenbaum et al. 2000#2 引自Jenkins et. al, IROS 2002#1 #2目錄ISO

2、MAP算法LE算法3流形學(xué)習(xí)框架12LLE算法45總結(jié)與對比預(yù)備知識拓?fù)?，同?“拓?fù)洹边@個詞在希臘語中的意思是地貌。拓?fù)鋵W(xué)是研究幾何體連續(xù)形變中保持不變的性質(zhì) 而連續(xù)的變換（彎曲，延展，剪切）最后都能變成一樣的兩個物體，稱為同胚（Homeomorphism） “拓?fù)鋵W(xué)家就是不會區(qū)分甜甜圈和咖啡杯的人。” -John L. Kelley。從同胚角度上說，甜甜圈與有一只把手的杯子等價（都只有一個洞）。 拓?fù)鋵W(xué)上是“柔軟”的，傳統(tǒng)的基于歐式空間的幾何學(xué)是堅硬的。chart 把流體的任何一個微小的局部看作是歐幾里德空間，稱為一個chart預(yù)備知識廣義特征值 一個廣義特征值有如下形式：A=B， 其中A

3、和B為矩陣。其廣義特征值 可以通過求解方程(A-B)=0，得到det(A-B)=0（其中det即行列式）構(gòu)成。求得后帶入原方程A=B可求出拉普拉斯矩陣給定一個有n個頂點的圖G，它的拉普拉斯矩陣 定義為:L=D-A.其中D為圖的度矩陣，A為圖的鄰接矩陣.對于 1.若i = j,則為頂點i的度2.若i j，但i和j鄰接，則為-13.若i j，i和j不鄰接， 為0鄰接矩陣示例預(yù)備知識圖的拉普拉斯算子預(yù)備知識測地距離測地線: 流形上連接兩個點的最短曲線例如：球面上的測地線就是球面上的大圓弧測地距離：測地線的長度Figure from 流形學(xué)習(xí)框架什么是流形？流形是線性子空間的一種非線性推廣拓?fù)鋵W(xué)角度：

4、局部區(qū)域線性，與低維歐式空間拓?fù)渫呶⒎謳缀谓嵌龋河兄丿Bchart的光滑過渡黎曼流形就是以光滑的方式在每一點的切空間上指定了歐氏內(nèi)積的微分流形#1 引自S.T. Roweis et al. 2000#1Swiss-rollS-curveFishbow流形學(xué)習(xí)框架流形的數(shù)學(xué)定義設(shè) 是一個Hausdorff拓?fù)淇臻g，若對每一點 都有 的一個開鄰域 和 的一個開子集同胚, 則稱M為 d維拓?fù)淞餍? 簡稱為d 維流形.#1 引自M. H. Law, 2004#1Mx1x2RRnzxx: coordinate for zUd流形學(xué)習(xí)框架流形的性質(zhì)Manifold = Many + Fold, 很多曲面片

5、的疊加疊加但不是拼接，不自交歐氏空間屬于流形任何一個流形都可以嵌入到足夠高維度的歐氏空間中(Whitney嵌入定理)流形學(xué)習(xí)框架目的：降維，研究數(shù)據(jù)流形的幾何和拓?fù)涠x：從高維采樣數(shù)據(jù)恢復(fù)低維流形結(jié)構(gòu)時間：2000年Science首次提出動機(jī)：從認(rèn)知心理學(xué)的角度，心理學(xué)家認(rèn)為人的認(rèn)知過程是基于認(rèn)知流形和拓?fù)溥B續(xù)性的流形學(xué)習(xí)介紹流形學(xué)習(xí)框架流形學(xué)習(xí)數(shù)學(xué)定義流形學(xué)習(xí)框架流形學(xué)習(xí)示例非線性降維高維數(shù)據(jù)空間data / observation space低維嵌入空間embedding / coordinate space保持一定幾何拓?fù)潢P(guān)系，如測地距離/鄰域線性重構(gòu)關(guān)系流形學(xué)習(xí)框架真實數(shù)據(jù)是怎樣的？外

6、圍歐式空間的維度很高數(shù)據(jù)存在一定的低維內(nèi)在結(jié)構(gòu)我們假設(shè)數(shù)據(jù)是位于一個低維子流形上流形假設(shè)非線性流形學(xué)習(xí)方法 等距映射(Isomap).J.B. Tenenbaum, V. de Silva, and J. C. Langford. A global geometric framework for nonlinear dimensionality reduction. Science, vol. 290, pp. 2319-2323, 2000. 局部線性嵌入(LLE).S. T. Roweis and L. K. Saul. Nonlinear dimensionality reduction

7、 by locally linear embedding. Science, vol. 290, pp. 2323-2326, 2000. 拉普拉斯特征映射(Laplacian Eigenmap).M. Belkin, P. Niyogi, Laplacian Eigenmaps for Dimensionality Reduction and Data Representation. Neural Computation, Vol. 15, Issue 6, pp. 1373 1396, 2003 .幾種非線性流形學(xué)習(xí)算法非線性流形學(xué)習(xí)方法ISOMAP1 高維數(shù)據(jù)所在的低維流形與歐氏空間的一

8、個子集是整體等距的.2 與數(shù)據(jù)所在的流形等距的歐氏空間的子集是一個凸集.Isomap的前提假設(shè)等距映射(Isomap)的基本思想建立在多維尺度變換(MDS)的基礎(chǔ)上，力求保持?jǐn)?shù)據(jù)點的內(nèi)在幾何性質(zhì)，即保持兩點間的測地距離.非線性流形學(xué)習(xí)方法ISOMAPIsomap算法的核心估計兩點間的測地距離: 1 離得很近的點間的測地距離用歐氏距離代替. 2 離得較遠(yuǎn)的點間的測地距離用最短路徑來逼近.非線性流形學(xué)習(xí)方法ISOMAP測地距離估計非線性流形學(xué)習(xí)方法ISOMAPISOMAP算法流程1、選取每個樣本點最近的k個點，或以樣本點為中心半徑為 的圓內(nèi)的所有點。（參數(shù)k，或 ）2、通過最短路算法構(gòu)造一個N*N

9、的距離矩陣。3、通過Multi-dimensional Scaling算法根據(jù)距離矩陣進(jìn)行非線性降維。（參數(shù)d，降到d維）非線性流形學(xué)習(xí)方法ISOMAPISOMAP實驗結(jié)果Figures from ISOMAP paper非線性流形學(xué)習(xí)方法LE基本思想：在高維空間中離得很近的點投影到低維空間中的象也應(yīng)該離得很近. 通過使用兩點間的加權(quán)距離作為損失函數(shù)，可求得相應(yīng)的降維結(jié)果。待優(yōu)化的目標(biāo)函數(shù)： 快速對目標(biāo)函數(shù)進(jìn)行整理：非線性流形學(xué)習(xí)方法LE于是，我們的最小化問題可以等效為：這個目標(biāo)的求解就是一個廣義特征值分解問題限制條件保證優(yōu)化問題有解，并且保證映射后的數(shù)據(jù)點不會被“壓縮”到一個小于m維的子空間

10、中非線性流形學(xué)習(xí)方法LELE算法流程2中W也可取值：非線性流形學(xué)習(xí)方法LELaplacian Eigenmap實驗結(jié)果非線性流形學(xué)習(xí)方法LLELocally linear embedding（局部線性嵌入） 非線性流形學(xué)習(xí)方法LLE算法步驟：尋找每個樣本點的k個近鄰點；由每個樣本點的近鄰點計算出該樣本點的局部重建權(quán)值矩陣；（最小化權(quán)重誤差）由該樣本點的局部重建權(quán)值矩陣和其近鄰點計算出該樣本點的輸出值。（最小化隱射誤差） 具體的算法流程如下圖所示: 非線性流形學(xué)習(xí)方法LLE求解方法： 采用的是拉格朗日乘子法，求得W非線性流形學(xué)習(xí)方法LLE求解方法： 非線性流形學(xué)習(xí)方法LLE例.非線性流形學(xué)習(xí)方法LLELLE實驗結(jié)果總結(jié)與對比 LLE, Isomap, Laplacian Eigenmap 有效的原因1 它們都是非參數(shù)的方法，不需要對流形的很多的參數(shù)假設(shè).2 它們是非線性的方法，都基于流形的內(nèi)在幾何結(jié)構(gòu)，更能體現(xiàn)現(xiàn)實