2014.7.3流形学习算法研究

1、流形学习流形学习算法算法研究研究勇于开始，才能找到成功的路汇报提纲汇报提纲研究背景研究背景一 理论基础理论基础二典型算法分析典型算法分析三总结总结四勇于开始，才能找到成功的路3一、研究背景一、研究背景 信息冗余信息冗余 维数灾难维数灾难 任务需求任务需求维数约简维数约简勇于开始，才能找到成功的路维数约简：维数约简： 假设假设 个维数为个维数为 的高维数据点的高维数据点降降 维维 后后 得得 到到 维维 数数 为为 ( )的的 低低 维维 结结 果果12 ,.D nnXx xxRdD12n,.Rd nYy yy，若存在映射 ,使得( )iiyf x则把则把 到到 的过程称为维数约简。的过程称为维

2、数约简。XYnDdf 若若 为为 的线性函数的线性函数，则则 称为线性降维称为线性降维；否则，否则，称为非线性降维。称为非线性降维。fxf1:fYX为为嵌入映射嵌入映射。线性维数约简：线性维数约简：PCA（Principal Component Analysis）：主分量分）：主分量分析析(Jolliffe, 2002; Turk and Pentland, 1991) LDA（Linear Discriminant Analysis, ）(Duda et al., 2001)：线性判别分析：线性判别分析线性维数约简方法：线性维数约简方法：优点：优点：1.对线性结构分布的数据集有较好的降维效果

3、；对线性结构分布的数据集有较好的降维效果；2.在压缩、降噪以及数据可视化等方面非常有效的。在压缩、降噪以及数据可视化等方面非常有效的。3.计算简单，易于理解计算简单，易于理解缺点：缺点： 对呈现出结构非线性或属性强相关性的数据集，对呈现出结构非线性或属性强相关性的数据集，无法发现复杂的非线性数据的内在本质结构。无法发现复杂的非线性数据的内在本质结构。1999，人工神经网络（，人工神经网络（Artificial Neural Networks，ANN）的发展与兴起；）的发展与兴起；20 世纪世纪 90 年代中期，基于核的非线性方法的提年代中期，基于核的非线性方法的提出出 (Boser et al

4、., 1992; Cristianini and Shawe-Taylor, 2000; Schlkopf and Smola, 2002)。勇于开始，才能找到成功的路 2000，Seung 等，等， Science，The manifold ways of perception，视觉感知的流形结构假说视觉感知的流形结构假说。 流形学习可能是人类认知中一种自然的行为方式。流形学习可能是人类认知中一种自然的行为方式。 流形是感知的基础，人类的视觉记忆是以一种稳定的流流形是感知的基础，人类的视觉记忆是以一种稳定的流形形式存贮在大脑中形形式存贮在大脑中,人类具有捕获流形结构的能力；人类具有捕获流形结

5、构的能力；勇于开始，才能找到成功的路2000，Science，一种非线性维数约简的全局几何框架一种非线性维数约简的全局几何框架，局部线性嵌入的非线性维数约简局部线性嵌入的非线性维数约简等距特征映射算法（等距特征映射算法（Isometric Feature Mapping ，ISOMAP）(Tenenbaum et al., 2000),局部线性嵌入算法局部线性嵌入算法（Locally Linear Embedding，LLE）(Roweis and Saul, 2000)。 高维数据的学习实质上可以理解为对嵌入在高维空间的低高维数据的学习实质上可以理解为对嵌入在高维空间的低维流形的学习维流形的

6、学习(Roweis and Saul, 2000; Tenenbaum et al., 2000)。勇于开始，才能找到成功的路二、理论基础二、理论基础v流形流形v流形学习流形学习勇于开始，才能找到成功的路121.1.流形流形 流形是线性子空间的一种非线性推广流形是线性子空间的一种非线性推广 拓扑学角度：局部区域线性，与低维欧式空间拓扑拓扑学角度：局部区域线性，与低维欧式空间拓扑同胚同胚#1 引自S.T. Roweis et al. 2000#1Swiss-rollS-curveFishbow勇于开始，才能找到成功的路13v流形的数学定义流形的数学定义 设设 是一个是一个Hausdorff拓扑空

7、间，若对每一点拓扑空间，若对每一点 都有都有 的一个开邻域的一个开邻域 和和 的一个开子集同胚的一个开子集同胚, 则称则称 为为 维拓扑流形维拓扑流形, 简称为简称为 维流形维流形.1.1.流形流形MpMpUddMd#1 引自M. H. Law, 2004Mx1x2R2Rnzxx: coordinate for zUThe view angles of pedestrian postures change along the coordinate v, and the body configurations change along the coordinate b.勇于开始，才能找到成功的路

8、15v 一些基本数学概念一些基本数学概念 拓扑，拓扑，Hausdorff 空间，坐标卡，微分结构空间，坐标卡，微分结构 光滑函数，光滑映射，切向量，切空间光滑函数，光滑映射，切向量，切空间 v 参考文献参考文献 陈省身陈省身, 陈维桓陈维桓, 微分几何讲义微分几何讲义. 北京大学出版社北京大学出版社, 1983 M Berger, B Gostiaux. Differential Geometry: Manifolds, Curves and Surfaces, GTM115. Springer-Verlag, 1974 陈维桓陈维桓, 微分流形初步微分流形初步(第二版第二版). 高等教育出版

9、社高等教育出版社, 20011.1.流形流形勇于开始，才能找到成功的路2.2.流形学习流形学习 流形学习流形学习(Manifold Learning), 2000年科学杂志年科学杂志Science首次提出。用于从高维采样数据恢复低维首次提出。用于从高维采样数据恢复低维流形结构，流形结构，是一种非线性降维方法是一种非线性降维方法（另一种是核（另一种是核方法）。方法）。 勇于开始，才能找到成功的路172.2.流形学习的数学定义流形学习的数学定义 设设 是一个低维流形是一个低维流形, , 是一是一个光滑嵌入个光滑嵌入, ,其中其中 DdDd 。数据集。数据集 是随机生成是随机生成的的, , 且经过且

10、经过f f 映射为观察空间的数据映射为观察空间的数据 。流形学习就是在给定观察样本集流形学习就是在给定观察样本集 的条件下重的条件下重构构 f f 和和 。dRY DRYf:iy).(iiyfx ixiy勇于开始，才能找到成功的路18非线性降维高维数据空间data / observation space低维嵌入空间embedding / coordinate space保持一定几何拓扑关系，如测地距离/邻域线性重构关系2.2.流形学习示例流形学习示例三、典型算法分析流形学习方法：流形学习方法：全局特性保持方法全局特性保持方法局部特性保持方法局部特性保持方法 全局特性保持方法基于低维流形的全局特

11、性保持方法基于低维流形的全局几何特性全局几何特性，构造，构造所有数据所有数据点对点对之间的全局度量矩阵，然后运算得到数据集的内在低维表示。之间的全局度量矩阵，然后运算得到数据集的内在低维表示。 局部特性保持方法基于保持局部特性保持方法基于保持流形的局部几何特性流形的局部几何特性，即外围观测空，即外围观测空间邻域数据所具有的局部几何特性在内在低维空间得以保持间邻域数据所具有的局部几何特性在内在低维空间得以保持, , 然后运然后运算以构造全局唯一的低维坐标。算以构造全局唯一的低维坐标。三、典型算法分析勇于开始，才能找到成功的路21三、典型算法分析-ISOMAP 全局特性保持方法基本步骤 思想核心：

12、思想核心： 较较近近点对之间的测地距离用点对之间的测地距离用欧式距离欧式距离代替代替 较较远远点对之间的测地距离用点对之间的测地距离用最短路径最短路径来逼近来逼近测地距离：测地线的长度（测地线测地距离：测地线的长度（测地线: 流形上连接两个点的最短曲线）流形上连接两个点的最短曲线）勇于开始，才能找到成功的路23三、典型算法分析-ISOMAP 测地距离反映数据在流形上的真实距离差异测地距离反映数据在流形上的真实距离差异欧式距离 vs.测地距离最短路径近似测地距离降维嵌入空间勇于开始，才能找到成功的路24算法流程1 1、构造近邻图、构造近邻图G G 计算每个样本点与计算每个样本点与所有其他所有其他

13、样本点之间的欧式距离。如果样本点样本点之间的欧式距离。如果样本点 和和 的欧式距离的欧式距离 小于一个阈值小于一个阈值 ，或者点，或者点 是点是点 的的 近邻点，那么判近邻点，那么判定这两点彼此相邻，定这两点彼此相邻，在图在图G 中用边连接，边的权重为中用边连接，边的权重为 ；2 2、计算最短路径、计算最短路径 对于相邻样本点对于相邻样本点 和和 ，设置其初始最短路径为，设置其初始最短路径为 ，否则，否则为为 。对。对 分别设置为分别设置为 , 为样本点数，计算为样本点数，计算 ,得到最短路径距离矩阵得到最短路径距离矩阵ixjxXd (i, j)ixjxkXd (i, j)ixjxGXd (i

14、, j)= d (i, j)l1,2.nnGGGGd (i, j)= mind (i, j),d (i,l)+d (l, j)GD勇于开始，才能找到成功的路25算法流程3 3、 计算计算d d维嵌入维嵌入用用MDSMDS算法应用到算法应用到 , ,通过极小化下列目标函数来获得全局低维坐标通过极小化下列目标函数来获得全局低维坐标Y Y 表示低维嵌入坐标的欧式距离矩阵表示低维嵌入坐标的欧式距离矩阵 表示表示L L2 2矩阵范数，矩阵操作算子矩阵范数，矩阵操作算子 是平方距离矩阵是平方距离矩阵 ， 是中心化矩阵是中心化矩阵设设 和和 分别是矩阵分别是矩阵 的第的第p p个特征值和相应的特征向量，当低

15、维个特征值和相应的特征向量，当低维嵌入坐标嵌入坐标Y Y取矩阵取矩阵 的前的前d d个最大特征值对应的特征向量时，即个最大特征值对应的特征向量时，即 ，目标函数达到全局最小。，目标函数达到全局最小。GDGY2E=(D )- (D ) LYDYijd (i, j)= y - y22ijLijAA/ 2G(D )HSH S2ijijS = DijijH =-1/ nHppvG(D )G(D )T1n1y ,.y 1,.,ddYvv算法分析 时间复杂度时间复杂度: 计算计算DG矩阵为矩阵为O(kn2logn)(k为近邻数为近邻数,dijkstra算法算法)；应用；应用MDS的特征的特征分解为分解为O

16、(n3)。 优点：优点： 保持全局几何特性；保持全局几何特性； 缺点：缺点： 样本数量样本数量n 较大时，算法的计算效率低；较大时，算法的计算效率低； 使用场合：使用场合： 适用于学习内部平坦的低维流形；适用于学习内部平坦的低维流形；不适于学习有较大内在曲率的流形。不适于学习有较大内在曲率的流形。勇于开始，才能找到成功的路27三、典型算法分析-LLE局部特性保持方法局部特性保持方法-保局流形算法保局流形算法利用流形在局部可看作欧氏空间的观点，建立利用流形在局部可看作欧氏空间的观点，建立局部模型，然后整合排列局部几何模型，以构造局部模型，然后整合排列局部几何模型，以构造全局唯一的低维坐标全局唯一

17、的低维坐标-分而治之。分而治之。勇于开始，才能找到成功的路28vLLE (Locally linear embedding) 前提假设前提假设 采样数据所在的低维流形在局部是线性的采样数据所在的低维流形在局部是线性的 每个采样点均可以利用其近邻样本进行线性重构表示每个采样点均可以利用其近邻样本进行线性重构表示 学习目标学习目标 低维空间中保持每个邻域中的重构权值不变低维空间中保持每个邻域中的重构权值不变 在嵌入映射为局部线性的条件下，最小化重构误差在嵌入映射为局部线性的条件下，最小化重构误差 最终形式化为特征值分解问题最终形式化为特征值分解问题三、典型算法分析-LLE勇于开始，才能找到成功的路

18、29三、典型算法分析-LLELLE 算法基本步骤算法基本步骤勇于开始，才能找到成功的路30LLELLE算法流程算法流程 1.1.计算每一个点计算每一个点 的近邻点的近邻点, , 一般采用一般采用K K 近邻或者近邻或者 邻域邻域; ;2.2.计算权值计算权值 使得把使得把 用它的用它的K K个近邻点线性表示的误差最小个近邻点线性表示的误差最小, , 即通过最小化即通过最小化 来求出来求出 ; ;3.3.保持权值保持权值 不变不变, , 求求 在低维空间的象在低维空间的象 , , 使使得低维重构误差最小。得低维重构误差最小。，ijWiYijWjijiXWX ijWiXiXiX勇于开始，才能找到成

19、功的路31LLELLE算法的求解算法的求解1.1.根据欧氏距离，计算每一个点根据欧氏距离，计算每一个点 的近邻点；的近邻点；2.2.对于点对于点 和它的近邻点的权值和它的近邻点的权值 , , 3.3.令令 , , 低维嵌低维嵌是是M M的最小的的最小的第第2 2到第到第d d1 1个特征向量。个特征向量。 iXiXijW.X, ,XX 11的近邻点为）（）（其中，iljlijiijklmilmkijkijGGGW)()(TWIWIM勇于开始，才能找到成功的路33计算复杂度：计算复杂度： 选择邻域为选择邻域为O ( Dn2 )，计算重构权值矩阵，计算重构权值矩阵O ( D + k ) k2 n)

20、，求解低维嵌入求解低维嵌入Y 为为O ( dn2 )。优点优点算法可以学习任意维的局部线性的低维流形算法可以学习任意维的局部线性的低维流形算法归结为稀疏矩阵特征值计算，计算复杂度相对较小算法归结为稀疏矩阵特征值计算，计算复杂度相对较小LLELLE算法的分析算法的分析缺点缺点算法所学习的流形只能是不闭合的算法所学习的流形只能是不闭合的算法要求样本在流形上是稠密采样的算法要求样本在流形上是稠密采样的算法对样本中的噪声和邻域参数比较敏感算法对样本中的噪声和邻域参数比较敏感勇于开始，才能找到成功的路34vLE (Laplacian Eigenmap) 2002年，年，Belkin 和和Niyogi 基

21、本思想：在高维空间中离得很近的点投影到低基本思想：在高维空间中离得很近的点投影到低维空间中的象也应该离得很近。维空间中的象也应该离得很近。 求解方法：利用流形上求解方法：利用流形上Laplacian-Beltrami算子算子的特征函数的特征函数三、典型算法分析-LE勇于开始，才能找到成功的路35流形流形Laplacian-Beltram算子算子:一般记作一般记作 （delta）定义：定义：设设 M M 是光滑的黎曼流形是光滑的黎曼流形, ,f是是 M M 上的光滑函数上的光滑函数, , （nabla算子）是）是f的梯度的梯度, , 则称则称 为为 M M 上的拉普拉斯算子上的拉普拉斯算子, ,

22、 其中其中divdiv是散度算子。是散度算子。 f:div()ff 函数函数 的梯度为：的梯度为： 梯度的负散度函数梯度的负散度函数f 的拉普拉斯算子是笛卡儿坐标系中的所有的拉普拉斯算子是笛卡儿坐标系中的所有非混合非混合二阶偏导数：二阶偏导数： 二维空间二维空间 三维空间三维空间 根据谱图理论，如果数据均匀采样于高维空间中的低维流形，那么可以用图的根据谱图理论，如果数据均匀采样于高维空间中的低维流形，那么可以用图的Laplacian矩阵去逼近流形上矩阵去逼近流形上Laplacian-Beltrami算子，进而可以用图的算子，进而可以用图的Laplacian的特征向量去逼近流形上的特征向量去逼近流形上Laplacian-Beltrami算子的特征函数算子的特征函数(Belkin and Niyogi, 2003)。 勇于开始，才能找到成功的路37Laplacian Eigenmap 算法流程算法流程1.1.构