流形學(xué)習(xí)專題介紹

1、1 提綱 l研究背景 l基本知識(shí)介紹 l經(jīng)典方法概覽 l總結(jié)討論 2 提綱 l研究背景 l基本知識(shí)介紹 l經(jīng)典方法概覽 l總結(jié)討論 3 從降維問題說起 l降維的動(dòng)機(jī) 原始觀察空間中的樣本具有極大的信息冗余 樣本的高維數(shù)引發(fā)分類器設(shè)計(jì)的“維數(shù)災(zāi)難” 數(shù)據(jù)可視化、特征提取、分類與聚類等任務(wù)需求 4 從降維問題說起 l降維的動(dòng)機(jī) 增加特 征數(shù) 增加信 息量 提高準(zhǔn) 確性 增加訓(xùn)練分 類器的難度 維數(shù)災(zāi)難 解決辦法：選取盡可能多的解決辦法：選取盡可能多的, , 可能有用的特征可能有用的特征, , 然后根據(jù)需要進(jìn)然后根據(jù)需要進(jìn) 行特征行特征/ /維數(shù)約簡(jiǎn)維數(shù)約簡(jiǎn). . 5 從降維問題說起 l降維的動(dòng)機(jī)

2、特征選擇 特征約簡(jiǎn) 特征提取 依據(jù)某一標(biāo)準(zhǔn)選擇 性質(zhì)最突出的特征 實(shí)驗(yàn)數(shù)據(jù)分析，數(shù)據(jù)可視化（通常為2維或3 維）等也需要維數(shù)約簡(jiǎn) 經(jīng)已有特征的某種 變換獲取約簡(jiǎn)特征 6 降維方法概述 l 線性降維 通過特征的線性組合來降維 本質(zhì)上是把數(shù)據(jù)投影到低維線性子空間 線性方法相對(duì)比較簡(jiǎn)單且容易計(jì)算 代表方法 l主成分分析(PCA) l線性判別分析(LDA) l多維尺度變換(MDS) 7 線性降維方法 l 主成分分析(PCA) Jolliffe, 1986 降維目的：尋找能夠保持采樣數(shù)據(jù)方差的最佳投影子空間 求解方法：對(duì)樣本的散度矩陣進(jìn)行特征值分解, 所求子空 間為經(jīng)過樣本均值, 以最大特征值所對(duì)應(yīng)的特

3、征向量為方 向的子空間 Principal component 8 線性降維方法 l 主成分分析(PCA) Jolliffe, 1986 PCA對(duì)于橢球狀分布的樣本集有很好的效果, 學(xué)習(xí)所得的 主方向就是橢球的主軸方向. PCA 是一種非監(jiān)督的算法, 能找到很好地代表所有樣本的 方向, 但這個(gè)方向?qū)τ诜诸愇幢厥亲钣欣?9 線性降維方法 l 線性判別分析(LDA) Fukunaga, 1991 降維目的：尋找最能把兩類樣本分開的投影直線，使投影 后兩類樣本的均值之差與投影樣本的總類散度的比值最大 求解方法：經(jīng)過推導(dǎo)把原問題轉(zhuǎn)化為關(guān)于樣本集總類內(nèi)散 度矩陣和總類間散度矩陣的廣義特征值問題 Bes

4、t projection direction for classification 10 降維方法概述 l 線性降維 主成分分析 (PCA) Jolliffe, 1986 線性判別分析 (LDA) Fukunaga, 1991 PCA LDA 11 降維方法概述 l 線性降維 主成分分析 (PCA) Jolliffe, 1986 線性判別分析 (LDA) Fukunaga, 1991 多維尺度變換 (MDS) Cox, 1994 xi xj dij Mapping zi zj gij 原始空間， 可能非歐式 低維歐式空間 12 線性降維方法的不足 l原始數(shù)據(jù)無法表示為特征的簡(jiǎn)單線性組合 比如：

5、PCA無法表達(dá)Helix曲線流形 1-D Helix曲線流形 -1 -0.5 0 0.5 1 -1 -0.5 0 0.5 1 0 5 10 15 20 13 線性降維方法的不足 l真實(shí)數(shù)據(jù)中的有用信息不能由線性特征表示 比如：如何獲取并表示多姿態(tài)人臉的姿態(tài)信息 比如：如何獲取運(yùn)動(dòng)視頻序列中某個(gè)動(dòng)作的對(duì)應(yīng)幀 #1 引自J.B. Tenenbaum et al. 2000 #2 引自Jenkins et. al, IROS 2002 #2 #1 14 降維方法概述 l 線性降維 l 傳統(tǒng)非線性降維 核主成分分析 (KPCA) Scholkopf, 1998 主曲線 (Principal Curve

6、s) Hastie, 1989 Tibshirani, 1992 自組織映射 (SOM) Kohonen, 1995 產(chǎn)生式拓?fù)溆成?(GTM) Bishop, 1998 15 降維方法概述 l 基于流形學(xué)習(xí)的非線性降維 保距特征映射 (ISOMAP) Tenenbaum, 2000 局部線性嵌入 (LLE) Roweis, 2000 拉普拉斯特征映射 (LE, Laplacian Eigenmap) Belkin, 2001 Hessian LLE (HLLE) Donoho, 2003 局部切空間對(duì)齊 (LTSA, Local Tangent Space Alignment) Zhang,

7、 2004 最大方差展開 (MVU/SDE, Maximum Variance Unfolding) Weinberger, 2004 局部保持映射 (Locality Preserving Projections) He, 2003 16 提綱 l研究背景 l基本知識(shí)介紹 l經(jīng)典方法概覽 l總結(jié)討論 17 流形學(xué)習(xí)框架 l 什么是流形？ 流形是線性子空間的一種非線性推廣 拓?fù)鋵W(xué)角度：局部區(qū)域線性，與低維歐式空間拓?fù)渫?微分幾何角度：有重疊chart的光滑過渡 黎曼流形就是以光滑的方式在每一點(diǎn)的切空間上指定了 歐氏內(nèi)積的微分流形 #1 引自S.T. Roweis et al. 2000 #1

8、 Swiss-rollS-curveFishbow 18 l流形的數(shù)學(xué)定義 設(shè) 是一個(gè)Hausdorff拓?fù)淇臻g，若對(duì)每一點(diǎn) 都有 的一個(gè)開鄰域 和 的一個(gè)開子集同胚, 則稱 為 維拓?fù)淞餍? 簡(jiǎn)稱為 維流形. 流形學(xué)習(xí)框架 M pM p U d dMd #1 引自M. H. Law, 2004 #1M x1 x2 R2 Rn z x x: coordinate for z U 19 l 一些基本數(shù)學(xué)概念 拓?fù)洌琀ausdorff 空間，坐標(biāo)卡，微分結(jié)構(gòu) 光滑函數(shù)，光滑映射，切向量，切空間 l 參考文獻(xiàn) 陳省身, 陳維桓, 微分幾何講義. 北京大學(xué)出版社, 1983 M Berger, B G

9、ostiaux. Differential Geometry: Manifolds, Curves and Surfaces, GTM115. Springer-Verlag, 1974 陳維桓, 微分流形初步(第二版). 高等教育出版社, 2001 流形學(xué)習(xí)框架 20 l流形學(xué)習(xí)的目的 流形學(xué)習(xí)是一種非線性的維數(shù)約簡(jiǎn)方法 高維觀察數(shù)據(jù)的變化模式本質(zhì)是由少數(shù)幾個(gè)隱含 變量所決定的 l如：人臉采樣由光線亮度、人與相機(jī)的距離、人的頭部 姿勢(shì)、人的面部表情等因素決定 從認(rèn)知心理學(xué)的角度，心理學(xué)家認(rèn)為人的認(rèn)知過 程是基于認(rèn)知流形和拓?fù)溥B續(xù)性的 流形學(xué)習(xí)框架 #1 引自Lin et al. PAMI 2

10、008 #1 21 流形學(xué)習(xí)的數(shù)學(xué)定義 設(shè)設(shè) 是一個(gè)低維流形是一個(gè)低維流形, 是一個(gè)光滑嵌入是一個(gè)光滑嵌入, 其中其中 Dd . 數(shù)據(jù)集數(shù)據(jù)集 是隨機(jī)生成的是隨機(jī)生成的, 且經(jīng)過且經(jīng)過 f 映射為觀映射為觀 察空間的數(shù)據(jù)察空間的數(shù)據(jù) 流形學(xué)習(xí)就是在給定觀察樣本流形學(xué)習(xí)就是在給定觀察樣本 集集 的條件下重構(gòu)的條件下重構(gòu) f 和和 . V. de Silva and J. B. Tenenbaum. Global versus local methods in nonlinear dimensionality reduction . Neural Information Processing Sy

11、stems 15 (NIPS2002), pp. 705- 712, 2003. d RY D RYf: i y ).( ii yfx i x i y 22 非線性降維 高維數(shù)據(jù)空間 data / observation space 低維嵌入空間 embedding / coordinate space 保持一定幾何拓?fù)?關(guān)系，如測(cè)地距離/ 鄰域線性重構(gòu)關(guān)系 流形學(xué)習(xí)示例 23 提綱 l研究背景 l基本知識(shí)介紹 l經(jīng)典方法概覽 l總結(jié)討論 24 經(jīng)典流形學(xué)習(xí)方法一覽 方法簡(jiǎn)稱所保持的幾何屬性全局/局部關(guān)系計(jì)算復(fù)雜度 ISOMAP點(diǎn)對(duì)測(cè)地距離全局非常高 LLE局部線性重構(gòu)關(guān)系局部低 LE局部鄰域

12、相似度局部低 HLLE局部等距性局部高 LTSA局部坐標(biāo)表示全局+局部低 MVU局部距離全局+局部非常高 Logmap 測(cè)地距離與方向 局部非常低 Diffusion Mapsdiffusion距離全局中等 25 經(jīng)典方法分類結(jié)構(gòu)圖 26 等距映射(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. 局部線性嵌入(LL

13、E) S. T. Roweis and L. K. Saul. Nonlinear dimensionality reduction 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, p

14、p. 1373 1396, 2003 . 重點(diǎn)介紹的幾個(gè)方法 27 等距映射(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 by locally linear e

15、mbedding. 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 . 重點(diǎn)介紹的幾個(gè)方法 28 代表性算法-1 lISOMAP (Isometric feature mapping) 保持全局測(cè)地距離

16、 l測(cè)地距離反映數(shù)據(jù)在流形上的真實(shí)距離差異 等距映射 l基于線性算法MDS，采用“測(cè)地距離”作為數(shù)據(jù)差異度 量 #1 引自J.B. Tenenbaum et al. 2000 #1 歐式距離 vs. 測(cè)地距離 最短路徑近 似測(cè)地距離 降維嵌入空間 29 多維尺度變換多維尺度變換 (MDS) MDS 是一種非監(jiān)督的維數(shù)約簡(jiǎn)方法是一種非監(jiān)督的維數(shù)約簡(jiǎn)方法. MDS的基本思想的基本思想: 約簡(jiǎn)后低維空間中任意兩點(diǎn)間的距離約簡(jiǎn)后低維空間中任意兩點(diǎn)間的距離 應(yīng)該與它們?cè)谠呔S空間中的應(yīng)該與它們?cè)谠呔S空間中的距離相同距離相同. MDS的求解的求解: 通過適當(dāng)定義準(zhǔn)則函數(shù)來體現(xiàn)在低維空間通過適當(dāng)定義準(zhǔn)則函

17、數(shù)來體現(xiàn)在低維空間 中對(duì)高維距離的重建誤差中對(duì)高維距離的重建誤差, 對(duì)準(zhǔn)則函數(shù)用梯度下降法求解對(duì)準(zhǔn)則函數(shù)用梯度下降法求解, 對(duì)于某些特殊的距離可以推導(dǎo)出解析解法對(duì)于某些特殊的距離可以推導(dǎo)出解析解法. 30 ji ij ijij ji ij ef d J 2 )( 1 , )( 2 2 ji ij ji ijij ee d J 2 ji ij ijij ff d J MDS的準(zhǔn)則函數(shù)的準(zhǔn)則函數(shù) 31 MDS的示意圖的示意圖 32 MDS的失效的失效 33 l測(cè)地線: 流形上連接兩個(gè)點(diǎn)的最短曲線 例如：球面上的測(cè)地線就是球面上的大圓弧 l測(cè)地距離：測(cè)地線的長(zhǎng)度 AB Figure from htt

18、p:/mathworld.wolfra 測(cè)地距離測(cè)地距離 34 ISOMAP算法流程算法流程 1 計(jì)算每個(gè)點(diǎn)的近鄰點(diǎn)計(jì)算每個(gè)點(diǎn)的近鄰點(diǎn) (用用K近鄰或近鄰或 鄰域鄰域). 2 在樣本集上定義一個(gè)賦權(quán)無向圖在樣本集上定義一個(gè)賦權(quán)無向圖 如果如果 和和 互為互為 近鄰點(diǎn)近鄰點(diǎn), 則邊的權(quán)值為則邊的權(quán)值為 3 計(jì)算圖中兩點(diǎn)間的最短距離計(jì)算圖中兩點(diǎn)間的最短距離, 記所得的距離矩陣為記所得的距離矩陣為 . 4 用用MDS求低維嵌入坐標(biāo)求低維嵌入坐標(biāo) , 令令 低維嵌入是低維嵌入是 的第的第1大到第大到第 d大的特征值所對(duì)應(yīng)的大的特征值所對(duì)應(yīng)的 特征向量特征向量. ).,(jidX ), (jidD GG

19、 j X i X , 2/)()/1()()()( 2 HSHDNHHDSS ijijijij ， )(D 35 M. Bernstein, V. Silva, J.C. Langford, J.B. Tenenbaum 證明了如下的漸進(jìn)收斂定理證明了如下的漸進(jìn)收斂定理. 假設(shè)采樣點(diǎn)是隨機(jī)均勻抽取的假設(shè)采樣點(diǎn)是隨機(jī)均勻抽取的, 則則 漸進(jìn)收斂定理漸進(jìn)收斂定理 給定給定 則只要樣本集充分大則只要樣本集充分大 且適當(dāng)選擇且適當(dāng)選擇K , 不等式不等式 至少以概率至少以概率 成立成立. , 0, 21 21 1 distance geodesic distance graph 1 1 圖距離逼近測(cè)地

20、距離圖距離逼近測(cè)地距離 36 ISOMAP實(shí)驗(yàn)結(jié)果 Figures from ISOMAP paper 37 Figure from http:/isomap.stanford. edu/handfig.html ISOMAP實(shí)驗(yàn)結(jié)果 38 Figures from ISOMAP paper ISOMAP實(shí)驗(yàn)結(jié)果 39 Interpolation on Straight Lines in the Projected Co-ordinates Figures from ISOMAP paper 40 代表性算法-1 lISOMAP (Isometric feature mapping) 前提假設(shè)

21、 l數(shù)據(jù)所在的低維流形與歐式空間的一個(gè)子集整體等距 l該歐式空間的子集是一個(gè)凸集 思想核心 l較近點(diǎn)對(duì)之間的測(cè)地距離用歐式距離代替 l較遠(yuǎn)點(diǎn)對(duì)之間的測(cè)地距離用最短路徑來逼近 算法特點(diǎn) l適用于學(xué)習(xí)內(nèi)部平坦的低維流形 l不適于學(xué)習(xí)有較大內(nèi)在曲率的流形 l計(jì)算點(diǎn)對(duì)間的最短路徑比較耗時(shí) 41 ISOMAP - summary l Inherits features of MDS and PCA: guaranteed asymptotic convergence to true structure Polynomial runtime Non-iterative Ability to discove

22、r manifolds of arbitrary dimensionality l Perform well when data is from a single well sampled cluster l Few free parameters l Good theoretical base for its metrics preserving properties 42 Problems with ISOMAP lEmbeddings are biased to preserve the separation of faraway points, which can lead to di

23、stortion of local geometry lFails to nicely project data spread among multiple clusters lWell-conditioned algorithm but computationally expensive for large datasets 43 Improvements to ISOMAP lConformal Isomap capable of learning the structure of certain curved manifolds lLandmark Isomap approximates

24、 large global computations by a much smaller set of calculation lReconstruct distances using k/2 closest objects, as well as k/2 farthest objects 44 等距映射(ISOMAP) J.B. Tenenbaum, V. de Silva, and J. C. Langford. A global geometric framework for nonlinear dimensionality reduction. Science, vol. 290, p

25、p. 2319-2323, 2000. 局部線性嵌入(LLE) S. T. Roweis and L. K. Saul. Nonlinear dimensionality reduction 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 Com

26、putation, Vol. 15, Issue 6, pp. 1373 1396, 2003 . 重點(diǎn)介紹的幾個(gè)方法 45 代表性算法-2 lLLE (Locally linear embedding) 顯式利用“局部線性”的假設(shè) 保持局部鄰域幾何結(jié)構(gòu) 重構(gòu)權(quán)重 權(quán)重對(duì)樣本集的幾何變換具有不變性 46 代表性算法-2 lLLE (Locally linear embedding) 前提假設(shè) l采樣數(shù)據(jù)所在的低維流形在局部是線性的 l每個(gè)采樣點(diǎn)均可以利用其近鄰樣本進(jìn)行線性重構(gòu)表示 學(xué)習(xí)目標(biāo) l低維空間中保持每個(gè)鄰域中的重構(gòu)權(quán)值不變 l在嵌入映射為局部線性的條件下，最小化重構(gòu)誤差 l最終形式化為

27、特征值分解問題 47 LLE算法示意圖算法示意圖 48 LLE算法流程算法流程 1 計(jì)算每一個(gè)點(diǎn)計(jì)算每一個(gè)點(diǎn) 的近鄰點(diǎn)的近鄰點(diǎn), 一般采用一般采用K 近鄰或者近鄰或者 鄰域鄰域. 2 計(jì)算權(quán)值計(jì)算權(quán)值 使得把使得把 用它的用它的K個(gè)近鄰點(diǎn)線性表示個(gè)近鄰點(diǎn)線性表示 的誤差最小的誤差最小, 即通過最小化即通過最小化 來求出來求出 . 3 保持權(quán)值保持權(quán)值 不變不變, 求求 在低維空間的象在低維空間的象 , 使 使 得低維重構(gòu)誤差最小得低維重構(gòu)誤差最小. ， ij W i Y ij W jiji XWX ij W i X i X i X 49 LLE算法的求解算法的求解 1 計(jì)算每一個(gè)點(diǎn)計(jì)算每一個(gè)點(diǎn)

28、 的近鄰點(diǎn)的近鄰點(diǎn). 2 對(duì)于點(diǎn)對(duì)于點(diǎn) 和它的近鄰點(diǎn)的權(quán)值和它的近鄰點(diǎn)的權(quán)值 , 3 令令 , 低維嵌入 低維嵌入 是是 M 的最小的第的最小的第 2到第到第 d1 個(gè)特征向量個(gè)特征向量. i X i X ij W .X, ,XX 1 1 的近鄰點(diǎn)為）（）（其中， iljliji i jk lm i lm k i jk ij G G G W ，)( ij WW)()( T WIWIM 50 LLE實(shí)驗(yàn)結(jié)果 51 LLE實(shí)驗(yàn)結(jié)果 52 LLE實(shí)驗(yàn)結(jié)果 鄰域參數(shù)的影響 53 Figure from LLE paper LLE實(shí)驗(yàn)結(jié)果 54 LLE實(shí)驗(yàn)結(jié)果 55 代表性算法-2 lLLE (Loca

29、lly linear embedding) 優(yōu)點(diǎn) l算法可以學(xué)習(xí)任意維的局部線性的低維流形 l算法歸結(jié)為稀疏矩陣特征值計(jì)算，計(jì)算復(fù)雜度相對(duì)較小 缺點(diǎn) l算法所學(xué)習(xí)的流形只能是不閉合的 l算法要求樣本在流形上是稠密采樣的 l算法對(duì)樣本中的噪聲和鄰域參數(shù)比較敏感 56 Numerical Issues lCovariance matrix used to compute W can be ill-conditioned, regularization needs to be used lSmall eigen values are subject to numerical precision er

30、rors and to getting mixed lBut, sparse matrices used in this algorithm make it much faster then Isomap 57 等距映射(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. Rowei

31、s and L. K. Saul. Nonlinear dimensionality reduction 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,

32、2003 . 重點(diǎn)介紹的幾個(gè)方法 58 代表性算法-3 lLE (Laplacian Eigenmap) 基本思想：在高維空間中離得很近的點(diǎn)投影到低 維空間中的象也應(yīng)該離得很近. 求解方法：求解圖拉普拉斯算子的廣義特征值問 題. 59 拉普拉斯算子拉普拉斯算子 設(shè)設(shè) M 是光滑的黎曼流形是光滑的黎曼流形, f 是是 M 上的光滑函數(shù)上的光滑函數(shù), 是是 f 的梯度的梯度, 則稱線性映射則稱線性映射 為為 M 上的拉普拉斯算子上的拉普拉斯算子, 其中 其中div是散度算子是散度算子. f : )div( ),()(ffMCMC 60 圖上的拉普拉斯算子圖上的拉普拉斯算子 設(shè)設(shè) G 是一個(gè)圖是一個(gè)

33、圖, v 是它的頂點(diǎn)是它的頂點(diǎn), 是是 v 的自由度的自由度, w(u,v) 是連接頂點(diǎn)是連接頂點(diǎn)u,v 的邊的權(quán)值的邊的權(quán)值,令令 v d 0 )( ),(d ),( 其它 是連接的u,vu,v-w vuvuw vul v , 2 1 2 1 lTTL 其中其中 T 是對(duì)角矩陣是對(duì)角矩陣,對(duì)角線的元素為對(duì)角線的元素為 , 則稱則稱 L 為圖為圖 G 上的拉普拉斯算子上的拉普拉斯算子. vu u vuw ),( 61 Laplacian Eigenmap 算法流程算法流程 1 從樣本點(diǎn)構(gòu)建一個(gè)近鄰圖從樣本點(diǎn)構(gòu)建一個(gè)近鄰圖, 圖的頂點(diǎn)為樣本點(diǎn)圖的頂點(diǎn)為樣本點(diǎn), 離得離得 很近兩點(diǎn)用邊相連很近兩點(diǎn)

34、用邊相連 (K近鄰或近鄰或 鄰域鄰域). 2 給每條邊賦予權(quán)值給每條邊賦予權(quán)值 如果第如果第 個(gè)點(diǎn)和第個(gè)點(diǎn)和第 j 個(gè)點(diǎn)不相連，個(gè)點(diǎn)不相連， 權(quán)值為權(quán)值為0，否則，否則 ; 3 計(jì)算圖拉普拉斯算子的廣義特征向量計(jì)算圖拉普拉斯算子的廣義特征向量, 求得低維嵌入求得低維嵌入. 令令D為對(duì)角矩陣為對(duì)角矩陣 L是近鄰圖上的是近鄰圖上的 拉普拉斯算子拉普拉斯算子, 求解廣義特征值問題求解廣義特征值問題 . i 1 ij W , ,WDLWD j jiii DfLf 62 Laplacian Eigenmap實(shí)驗(yàn)結(jié)果實(shí)驗(yàn)結(jié)果(1) 63 300 most frequent words of the Bro

35、wn corpus represented in the spectral domain Laplacian Eigenmap實(shí)驗(yàn)結(jié)果實(shí)驗(yàn)結(jié)果(2) 64 Laplacian Eigenmap實(shí)驗(yàn)結(jié)果實(shí)驗(yàn)結(jié)果(2) The first is exclusively infinitives of verbs, the second contains prepositions and the third mostly modal and auxiliary verbs. We see that syntactic structure is well-preserved. 65 代表性算法-3 lL

36、E (Laplacian Eigenmap) 優(yōu)點(diǎn) l算法是局部非線性方法，與譜圖理論有很緊密的聯(lián)系. l算法通過求解稀疏矩陣的特征值問題解析地求出整體 最優(yōu)解，效率非常高 l算法使原空間中離得很近的點(diǎn)在低維空間也離得很近, 可以用于聚類 缺點(diǎn) l同樣對(duì)算法參數(shù)和數(shù)據(jù)采樣密度較敏感 l不能有效保持流形的全局幾何結(jié)構(gòu) 66 提綱 l研究背景 l基本知識(shí)介紹 l經(jīng)典方法概覽 l總結(jié)討論 67 經(jīng)典方法小結(jié) l 優(yōu)點(diǎn) 非參數(shù)：不需要對(duì)流形的很多參數(shù)作假設(shè) 非線性：基于流形內(nèi)在幾何結(jié)構(gòu)，體現(xiàn)現(xiàn)實(shí)數(shù)據(jù)的本質(zhì) 求解簡(jiǎn)單：轉(zhuǎn)化為求解優(yōu)化問題，通常采用特征值分解， 而不需要采用迭代算法 l 缺點(diǎn) 對(duì)觀察數(shù)據(jù)存

37、在流形結(jié)構(gòu)的假設(shè) 需要調(diào)節(jié)較多的算法參數(shù)，如k-NN的鄰域參數(shù)k 對(duì)數(shù)據(jù)采樣稠密性、均勻性以及噪聲數(shù)據(jù)的敏感性 68 研究難點(diǎn)與未來方向 l 如何進(jìn)行統(tǒng)一有效的定量化評(píng)估 真實(shí)數(shù)據(jù) vs. 人工數(shù)據(jù) 理論分析依據(jù) 評(píng)估指標(biāo)：一致性，收斂率，穩(wěn)定性，復(fù)雜度 l 如何求解測(cè)試數(shù)據(jù)的out-of-sample問題 線性近似 回歸方法 l 如何確定低維目標(biāo)空間的維數(shù) l如何進(jìn)行監(jiān)督式推廣應(yīng)用于分類問題 69 參考文獻(xiàn) l Roweis, S. T. and L. K. Saul (2000). Nonlinear dimensionality reduction by locally linear embedding Science 290(5500): 2323-2326. l Tenenbaum, J. B., V. de Silva, et al. (2000). A global geometric framework for nonlinear dimensionality reduction Science 290(5500): 2319-2323. l Vlachos, M., C. Domeniconi, et al. (2002). No