2014.7.3流形学习算法研究

流形学习算法研究勇于开始，才能找到成功的路汇报提纲研究背景一理论基础二典型算法分析三总结四勇于开始，才能找到成功的路3一、研究背景信息冗余维数灾难任务需求6464维数约简勇于开始，才能找到成功的路维数约简：假设个维数为的高维数据点降维后得到维数为()的低维结果12[,,...]DnnXxxxRdD12n[,,...]RdnYyyy，若存在映射,使得()iiyfx则把到的过程称为维数约简。XYnDdf若为的线性函数，则称为线性降维；否则，称为非线性降维。fxf1:fYX为嵌入映射。线性维数约简：PCA（PrincipalComponentAnalysis）：主分量分析(Jolliffe,2002;TurkandPentland,1991)LDA（LinearDiscriminantAnalysis,）(Dudaetal.,2001)：线性判别分析线性维数约简方法：优点：1.对线性结构分布的数据集有较好的降维效果；2.在压缩、降噪以及数据可视化等方面非常有效的。3.计算简单，易于理解缺点：对呈现出结构非线性或属性强相关性的数据集，无法发现复杂的非线性数据的内在本质结构。1999，人工神经网络（ArtificialNeuralNetworks，ANN）的发展与兴起；20世纪90年代中期，基于核的非线性方法的提出(Boseretal.,1992;CristianiniandShawe-Taylor,2000;SchölkopfandSmola,2002)。勇于开始，才能找到成功的路2000，Seung等，Science，《Themanifoldwaysofperception》，视觉感知的流形结构假说。流形学习可能是人类认知中一种自然的行为方式。流形是感知的基础，人类的视觉记忆是以一种稳定的流形形式存贮在大脑中,人类具有捕获流形结构的能力；勇于开始，才能找到成功的路2000，Science，《一种非线性维数约简的全局几何框架》，《局部线性嵌入的非线性维数约简》等距特征映射算法（IsometricFeatureMapping，ISOMAP）(Tenenbaumetal.,2000),局部线性嵌入算法（LocallyLinearEmbedding，LLE）(RoweisandSaul,2000)。高维数据的学习实质上可以理解为对嵌入在高维空间的低维流形的学习(RoweisandSaul,2000;Tenenbaumetal.,2000)。勇于开始，才能找到成功的路二、理论基础流形流形学习勇于开始，才能找到成功的路121.流形流形是线性子空间的一种非线性推广拓扑学角度：局部区域线性，与低维欧式空间拓扑同胚#1引自S.T.Roweisetal.2000#1Swiss-rollS-curveFishbow勇于开始，才能找到成功的路13流形的数学定义设是一个Hausdorff拓扑空间，若对每一点都有的一个开邻域和的一个开子集同胚,则称为维拓扑流形,简称为维流形.1.流形MpMpUddMd#1引自M.H.Law,2004Mx1x2R2Rnzxx:coordinateforzUTheviewanglesofpedestrianpostureschangealongthecoordinatev,andthebodyconfigurationschangealongthecoordinateb.勇于开始，才能找到成功的路15一些基本数学概念拓扑，Hausdorff空间，坐标卡，微分结构光滑函数，光滑映射，切向量，切空间…参考文献陈省身,陈维桓,微分几何讲义.北京大学出版社,1983MBerger,BGostiaux.DifferentialGeometry:Manifolds,CurvesandSurfaces,GTM115.Springer-Verlag,1974陈维桓,微分流形初步(第二版).高等教育出版社,20011.流形勇于开始，才能找到成功的路2.流形学习流形学习(ManifoldLearning),2000年科学杂志Science首次提出。用于从高维采样数据恢复低维流形结构，是一种非线性降维方法（另一种是核方法）。勇于开始，才能找到成功的路172.流形学习的数学定义设是一个低维流形,是一个光滑嵌入,其中Dd。数据集是随机生成的,且经过f映射为观察空间的数据。流形学习就是在给定观察样本集的条件下重构f和。dRYDRYf:}{iy)}.({iiyfx}{ix}{iy勇于开始，才能找到成功的路18非线性降维高维数据空间data/observationspace低维嵌入空间embedding/coordinatespace保持一定几何拓扑关系，如测地距离/邻域线性重构关系2.流形学习示例三、典型算法分析流形学习方法：全局特性保持方法局部特性保持方法全局特性保持方法基于低维流形的全局几何特性，构造所有数据点对之间的全局度量矩阵，然后运算得到数据集的内在低维表示。局部特性保持方法基于保持流形的局部几何特性，即外围观测空间邻域数据所具有的局部几何特性在内在低维空间得以保持,然后运算以构造全局唯一的低维坐标。三、典型算法分析勇于开始，才能找到成功的路21三、典型算法分析---ISOMAP全局特性保持方法基本步骤思想核心：较近点对之间的测地距离用欧式距离代替较远点对之间的测地距离用最短路径来逼近测地距离：测地线的长度（测地线:流形上连接两个点的最短曲线）勇于开始，才能找到成功的路23三、典型算法分析---ISOMAP•测地距离反映数据在流形上的真实距离差异欧式距离vs.测地距离最短路径近似测地距离降维嵌入空间勇于开始，才能找到成功的路24算法流程1、构造近邻图G计算每个样本点与所有其他样本点之间的欧式距离。如果样本点和的欧式距离小于一个阈值，或者点是点的近邻点，那么判定这两点彼此相邻，在图G中用边连接，边的权重为；2、计算最短路径对于相邻样本点和，设置其初始最短路径为，否则为。对分别设置为,为样本点数，计算,得到最短路径距离矩阵ixjxXd(i,j)ixjxkXd(i,j)ixjxGXd(i,j)=d(i,j)l1,2...nnGGGGd(i,j)=min{d(i,j),d(i,l)+d(l,j)}GD勇于开始，才能找到成功的路25算法流程3、计算d维嵌入用MDS算法应用到,通过极小化下列目标函数来获得全局低维坐标Y表示低维嵌入坐标的欧式距离矩阵表示L2矩阵范数，矩阵操作算子是平方距离矩阵，是中心化矩阵设和分别是矩阵的第p个特征值和相应的特征向量，当低维嵌入坐标Y取矩阵的前d个最大特征值对应的特征向量时，即，目标函数达到全局最小。GDGY2E=(D)-(D)LYD{}Yijd(i,j)=y-y22ijLijAA/2G(D)HSHS{}2ijijS=DijijH=-1/nHppvG(D)G(D)T1n1[y,...y][1,...,]ddYvv算法分析时间复杂度:计算DG矩阵为O(kn2logn)(k为近邻数,dijkstra算法)；应用MDS的特征分解为O(n3)。优点：保持全局几何特性；缺点：样本数量n较大时，算法的计算效率低；使用场合：适用于学习内部平坦的低维流形；不适于学习有较大内在曲率的流形。勇于开始，才能找到成功的路27三、典型算法分析---LLE局部特性保持方法---保局流形算法利用流形在局部可看作欧氏空间的观点，建立局部模型，然后整合排列局部几何模型，以构造全局唯一的低维坐标---分而治之。勇于开始，才能找到成功的路28LLE(Locallylinearembedding)前提假设•采样数据所在的低维流形在局部是线性的•每个采样点均可以利用其近邻样本进行线性重构表示学习目标•低维空间中保持每个邻域中的重构权值不变•在嵌入映射为局部线性的条件下，最小化重构误差•最终形式化为特征值分解问题三、典型算法分析---LLE勇于开始，才能找到成功的路29三、典型算法分析---LLELLE算法基本步骤勇于开始，才能找到成功的路30LLE算法流程1.计算每一个点的近邻点,一般采用K近邻或者邻域;2.计算权值使得把用它的K个近邻点线性表示的误差最小,即通过最小化来求出;3.保持权值不变,求在低维空间的象,使得低维重构误差最小。，ijWiYijWjijiXWXijWiXiXiX勇于开始，才能找到成功的路31LLE算法的求解1.根据欧氏距离，计算每一个点的近邻点；2.对于点和它的近邻点的权值,3.令,低维嵌是M的最小的第2到第d＋1个特征向量。iXiXijW.X,,XX11的近邻点为）（）＝（其中，iljlijiijklmilmkijkijGGGW)()(TWIWIM勇于开始，才能找到成功的路33计算复杂度：选择邻域为O(Dn2)，计算重构权值矩阵O((D+k)k2n)，求解低维嵌入Y为O(dn2)。优点算法可以学习任意维的局部线性的低维流形算法归结为稀疏矩阵特征值计算，计算复杂度相对较小LLE算法的分析缺点算法所学习的流形只能是不闭合的算法要求样本在流形上是稠密采样的算法对样本中的噪声和邻域参数比较敏感勇于开始，才能找到成功的路34LE(LaplacianEigenmap)2002年，Belkin和Niyogi基本思想：在高维空间中离得很近的点投影到低维空间中的象也应该离得很近。求解方法：利用流形上Laplacian-Beltrami算子的特征函数三、典型算法分析---LE勇于开始，才能找到成功的路35流形Laplacian-Beltram算子:一般记作（delta）定义：设M是光滑的黎曼流形,f是M上的光滑函数,（nabla算子）是f的梯度,则称为M上的拉普拉斯算子,其中div是散度算子。f:div()ff函数的梯度为：梯度的负散度函数f的拉普拉斯算子是笛卡儿坐标系中的所有非混合二阶偏导数：二维空间三维空间根据谱图理论，如果数据均匀采样于高维空间中的低维流形，那么可以用图的Laplacian矩阵去逼近流形上Laplacian-Beltrami算子，进而可以用图的Laplacian的特征向量去逼近流形上Laplacian-Beltrami算子的特征函数(BelkinandNiyogi,2003)。勇于开始，才能找到成功的路37LaplacianEigenmap算法流程1.构建近邻图,(K近邻或邻域)。2.给每条边赋予权值3.LE的目标函数为极小化如下损失函数，即确保原来相邻的样本点投影后仍为近邻4.对任何Y有，其中Y为Laplacian矩阵，D为对角矩阵，元素为权值矩阵的列和，即,LE算法的优化问题转化为低维嵌入Y取Laplacian矩阵的最小d+1个特征值对应的特征向量，即10ijijWW边i和边j相连边i和边j不相连2ijijijminyyW21()2TijijijyyWtrYLY=iiijjDWTargmintr(YLY)[]2d+1Y=v,...,v勇于开始，才能找到成功的路38代表性算法-3LE(LaplacianEigenmap)优点•算法是局部非线性方法，与谱图理论有很紧密的联系.•算法通过求解稀疏矩阵的特征值问题解析地求出整体最优解，效率非常高•算法使原空间中离得很近的点在低维空间也离得很近,可以用于聚类缺点•同样对算法参数和数据采样密度较敏感•不能有效保持流形的全局几何结构总结研究背景理论基础典型算法