流形学习算法研究.pptx

《流形学习算法研究.pptx》由会员分享，可在线阅读，更多相关《流形学习算法研究.pptx（39页珍藏版）》请在得力文库 - 分享文档赚钱的网站上搜索。

1、勇于开始，才能找到成功的路汇报提纲汇报提纲研究背景研究背景一 理论基础理论基础二典型算法分析典型算法分析三总结总结四第1页/共39页勇于开始，才能找到成功的路2一、研究背景一、研究背景信息冗余维数灾难任务需求维数约简第2页/共39页勇于开始，才能找到成功的路维数约简：假设个维数为的高维数据点降维后得到维数为()的低维结果，若存在映射,使得则把则把到到的过程称为维数约简。的过程称为维数约简。若若为为的线性函数的线性函数，则则称为线性降维称为线性降维；否则，否则，称为非线性降维。称为非线性降维。为嵌入映射。第3页/共39页线性维数约简：PCA（PrincipalComponentAnalysis）

2、：主分量分析(Jolliffe,2002;TurkandPentland,1991)LDA（LinearDiscriminantAnalysis,）(Dudaetal.,2001)：线性判别分析第4页/共39页线性维数约简方法：优点：1.对线性结构分布的数据集有较好的降维效果；2.在压缩、降噪以及数据可视化等方面非常有效的。3.计算简单，易于理解缺点：对呈现出结构非线性或属性强相关性的数据集，无法发现复杂的非线性数据的内在本质结构。第5页/共39页1999，人工神经网络（ArtificialNeuralNetworks，ANN）的发展与兴起；20世纪90年代中期，基于核的非线性方法的提出(Bo

3、seretal.,1992;CristianiniandShawe-Taylor,2000;SchlkopfandSmola,2002)。第6页/共39页勇于开始，才能找到成功的路2000，Seung等，Science，The manifold ways of perception，视觉感知的流形结构假说。流形学习可能是人类认知中一种自然的行为方式。流形是感知的基础，人类的视觉记忆是以一种稳定的流形形式存贮在大脑中,人类具有捕获流形结构的能力；第7页/共39页第8页/共39页勇于开始，才能找到成功的路2000，Science，一种非线性维数约简的全局几何框架，局部线性嵌入的非线性维数约简等距特

4、征映射算法（IsometricFeatureMapping，ISOMAP）(Tenenbaumetal.,2000),局部线性嵌入算法（LocallyLinearEmbedding，LLE）(RoweisandSaul,2000)。高维数据的学习实质上可以理解为对嵌入在高维空间的低维流形的学习(RoweisandSaul,2000;Tenenbaumetal.,2000)。第9页/共39页勇于开始，才能找到成功的路二、理论基础二、理论基础流形流形学习第10页/共39页勇于开始，才能找到成功的路111.1.流形流形流形是线性子空间的一种非线性推广拓扑学角度：局部区域线性，与低维欧式空间拓扑同胚#

5、1引自S.T.Roweisetal.2000#1Swiss-rollS-curveFishbow第11页/共39页勇于开始，才能找到成功的路12流形的数学定义设 是一个Hausdorff拓扑空间，若对每一点 都有 的一个开邻域 和 的一个开子集同胚,则称 为 维拓扑流形,简称为 维流形.1.1.流形流形#1引自M.H.Law,2004Mx1x2R2Rnzxx:coordinate for zU第12页/共39页Theviewanglesofpedestrianpostureschangealongthecoordinatev,andthebodyconfigurationschangealon

6、gthecoordinateb.第13页/共39页勇于开始，才能找到成功的路14一些基本数学概念拓扑，Hausdorff 空间，坐标卡，微分结构光滑函数，光滑映射，切向量，切空间参考文献陈省身,陈维桓,微分几何讲义.北京大学出版社,1983M Berger,B Gostiaux.Differential Geometry:Manifolds,Curves and Surfaces,GTM115.Springer-Verlag,1974陈维桓,微分流形初步(第二版).高等教育出版社,20011.1.流形流形第14页/共39页勇于开始，才能找到成功的路2.2.流形学习流形学习 流形学习(Manif

7、old Learning),2000年科学杂志Science首次提出。用于从高维采样数据恢复低维流形结构，是一种非线性降维方法（另一种是核方法）。第15页/共39页勇于开始，才能找到成功的路162.2.流形学习的数学定义流形学习的数学定义 设设 是一个低维流形是一个低维流形,是一个是一个光滑嵌入光滑嵌入,其中其中 DdDd 。数据集。数据集 是随机生成的是随机生成的,且经过且经过f f 映射为观察空间的数据映射为观察空间的数据 。流形。流形学习就是在给定观察样本集学习就是在给定观察样本集 的条件下重构的条件下重构 f f 和和 。第16页/共39页勇于开始，才能找到成功的路17非线性降维高维数

8、据空间data/observation space低维嵌入空间embedding/coordinate space保持一定几何拓扑关系，如测地距离/邻域线性重构关系2.2.流形学习示例流形学习示例第17页/共39页三、典型算法分析流形学习方法：全局特性保持方法局部特性保持方法 全局特性保持方法基于低维流形的全局几何特性，构造所有数据点对之间的全局度量矩阵，然后运算得到数据集的内在低维表示。局部特性保持方法基于保持流形的局部几何特性，即外围观测空间邻域数据所具有的局部几何特性在内在低维空间得以保持,然后运算以构造全局唯一的低维坐标。第18页/共39页三、典型算法分析第19页/共39页勇于开始，才

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

10、如果样本点 和和 的的欧式距离欧式距离 小于一个阈值小于一个阈值 ，或者点，或者点 是点是点 的的 近邻点，那么判定这近邻点，那么判定这两点彼此相邻，两点彼此相邻，在图在图G中用边连接，边的权重为中用边连接，边的权重为；2 2、计算最短路径、计算最短路径对于相邻样本点对于相邻样本点和和，设置其初始最短路径为，设置其初始最短路径为，否则为，否则为。对。对分别设置为分别设置为,为样本点数，计算为样本点数，计算,得到最短路径距离矩阵得到最短路径距离矩阵第23页/共39页勇于开始，才能找到成功的路24算法流程3 3、计算计算d d维嵌入维嵌入用用MDSMDS算法应用到算法应用到 ,通过极小化下列目标函

11、数来获得全局低维坐标通过极小化下列目标函数来获得全局低维坐标Y Y 表示低维嵌入坐标的欧式距离矩阵表示低维嵌入坐标的欧式距离矩阵 表示表示L L2 2矩阵范数，矩阵操作算子矩阵范数，矩阵操作算子 是平方距离矩阵是平方距离矩阵 ，是中心化矩阵是中心化矩阵设设 和和 分别是矩阵分别是矩阵 的第的第p p个特征值和相应的特征向量，当低维个特征值和相应的特征向量，当低维嵌入坐标嵌入坐标Y Y取矩阵取矩阵 的前的前d d个最大特征值对应的特征向量时，即个最大特征值对应的特征向量时，即 ，目标函数达到全局最小。，目标函数达到全局最小。第24页/共39页算法分析 时间复杂度:计算DG矩阵为O(kn2logn

12、)(k为近邻数,dijkstra算法)；应用MDS的特征分解为O(n3)。优点：保持全局几何特性；缺点：样本数量n 较大时，算法的计算效率低；使用场合：适用于学习内部平坦的低维流形；不适于学习有较大内在曲率的流形。第25页/共39页勇于开始，才能找到成功的路26三、典型算法分析-LLE局部特性保持方法-保局流形算法利用流形在局部可看作欧氏空间的观点，建立局部模型，然后整合排列局部几何模型，以构造全局唯一的低维坐标-分而治之。第26页/共39页勇于开始，才能找到成功的路27LLE(Locally linear embedding)前提假设采样数据所在的低维流形在局部是线性的每个采样点均可以利用其

13、近邻样本进行线性重构表示学习目标低维空间中保持每个邻域中的重构权值不变在嵌入映射为局部线性的条件下，最小化重构误差最终形式化为特征值分解问题三、典型算法分析-LLE第27页/共39页勇于开始，才能找到成功的路28三、典型算法分析-LLELLE算法基本步骤第28页/共39页勇于开始，才能找到成功的路29LLELLE算法流程算法流程 1.1.计算每一个点计算每一个点 的近邻点的近邻点,一般采用一般采用K K 近邻或者近邻或者 邻域邻域;2.2.计算权值计算权值 使得把使得把 用它的用它的K K个近邻点线性表示的误差最小个近邻点线性表示的误差最小,即通过最小化即通过最小化 来求出来求出 ;3.3.保

14、持权值保持权值 不变不变,求求 在低维空间的象在低维空间的象 ,使使得低维重构误差最小。得低维重构误差最小。第29页/共39页勇于开始，才能找到成功的路30LLELLE算法的求解算法的求解1.1.根据欧氏距离，计算每一个点根据欧氏距离，计算每一个点 的近邻点；的近邻点；2.2.对于点对于点 和它的近邻点的权值和它的近邻点的权值 ,3.3.令令 ,低维嵌低维嵌是是M M的最小的的最小的第第2 2到第到第d d1 1个特征向量。个特征向量。第30页/共39页第31页/共39页勇于开始，才能找到成功的路32计算复杂度：选择邻域为O(Dn2)，计算重构权值矩阵O(D+k)k2 n)，求解低维嵌入Y 为

15、O(dn2)。优点算法可以学习任意维的局部线性的低维流形算法归结为稀疏矩阵特征值计算，计算复杂度相对较小LLELLE算法的分析算法的分析缺点算法所学习的流形只能是不闭合的算法要求样本在流形上是稠密采样的算法对样本中的噪声和邻域参数比较敏感第32页/共39页勇于开始，才能找到成功的路33LE(Laplacian Eigenmap)2002年，Belkin 和Niyogi基本思想：在高维空间中离得很近的点投影到低维空间中的象也应该离得很近。求解方法：利用流形上Laplacian-Beltrami算子的特征函数三、典型算法分析-LE第33页/共39页勇于开始，才能找到成功的路34流形流形Laplac

16、ian-Beltram算子算子:一般记作一般记作（delta）定义：定义：设设 M M 是光滑的黎曼流形是光滑的黎曼流形,f是是 M M 上的光滑函数上的光滑函数,（nabla算子）是）是f的梯度的梯度,则称则称 为为 M M 上的拉普拉斯算子上的拉普拉斯算子,其中其中divdiv是散度算子。是散度算子。函数的梯度为：梯度的负散度函数梯度的负散度函数第34页/共39页f的拉普拉斯算子是笛卡儿坐标系中的所有非混合二阶偏导数：二维空间三维空间根据谱图理论，如果数据均匀采样于高维空间中的低维流形，那么可以用图的Laplacian矩阵去逼近流形上Laplacian-Beltrami算子，进而可以用图的

17、Laplacian的特征向量去逼近流形上Laplacian-Beltrami算子的特征函数(BelkinandNiyogi,2003)。第35页/共39页勇于开始，才能找到成功的路36Laplacian Eigenmap 算法流程算法流程1.1.构建近邻图构建近邻图,(K,(K近邻或近邻或 邻域邻域)。2.2.给每条边赋予权值给每条边赋予权值 3.LE3.LE的目标函数为极小化如下损失函数，即确保原来相邻的目标函数为极小化如下损失函数，即确保原来相邻的样本点投影后仍为近邻的样本点投影后仍为近邻4.4.对任何对任何Y Y有有 ，其中，其中Y Y为为LaplacianLaplacian矩阵，矩阵，

18、D D为对角矩阵，元素为权值矩阵的列和，即为对角矩阵，元素为权值矩阵的列和，即 ,LE,LE算法的优化问题转化为算法的优化问题转化为低维嵌入低维嵌入Y Y取取LaplacianLaplacian矩阵的最小矩阵的最小d+1d+1个特征值对应的特个特征值对应的特征向量，即征向量，即边i和边j相连边i和边j不相连第36页/共39页勇于开始，才能找到成功的路37代表性算法代表性算法-3LE(Laplacian Eigenmap)优点算法是局部非线性方法，与谱图理论有很紧密的联系.算法通过求解稀疏矩阵的特征值问题解析地求出整体最优解，效率非常高算法使原空间中离得很近的点在低维空间也离得很近,可以用于聚类缺点同样对算法参数和数据采样密度较敏感不能有效保持流形的全局几何结构第37页/共39页总结总结研究背景理论基础典型算法第38页/共39页勇于开始，才能找到成功的路感谢您的观看！第39页/共39页