流形学习专题介绍课件

1流形学习专题介绍王瑞平人脸识别课题组中国科学院计算技术研究所2010/05/06@VMRGroupBookReading/project/faceId/paperreading/vlpr/1流形学习专题介绍王瑞平2010/05/06@VMRG2提纲研究背景基本知识介绍经典方法概览总结讨论2提纲研究背景3提纲研究背景基本知识介绍经典方法概览总结讨论3提纲研究背景4从降维问题说起降维的动机原始观察空间中的样本具有极大的信息冗余样本的高维数引发分类器设计的“维数灾难”数据可视化、特征提取、分类与聚类等任务需求4从降维问题说起降维的动机5从降维问题说起降维的动机增加特征数增加信息量提高准确性增加训练分类器的难度维数灾难解决办法：选取尽可能多的,可能有用的特征,然后根据需要进行特征/维数约简.5从降维问题说起降维的动机增加特征数增加信息量提高准确性增加6从降维问题说起降维的动机特征选择特征约简特征提取依据某一标准选择性质最突出的特征实验数据分析，数据可视化（通常为2维或3维）等也需要维数约简经已有特征的某种变换获取约简特征6从降维问题说起降维的动机特征选择特征约简特征提取依据某一标7降维方法概述线性降维通过特征的线性组合来降维本质上是把数据投影到低维线性子空间线性方法相对比较简单且容易计算代表方法主成分分析(PCA)线性判别分析(LDA)多维尺度变换(MDS)7降维方法概述线性降维8线性降维方法主成分分析(PCA)[Jolliffe,1986]降维目的：寻找能够保持采样数据方差的最佳投影子空间求解方法：对样本的散度矩阵进行特征值分解,所求子空间为经过样本均值,以最大特征值所对应的特征向量为方向的子空间Principalcomponent8线性降维方法主成分分析(PCA)[Jolliffe,19线性降维方法主成分分析(PCA)[Jolliffe,1986]PCA对于椭球状分布的样本集有很好的效果,学习所得的主方向就是椭球的主轴方向.PCA是一种非监督的算法,能找到很好地代表所有样本的方向,但这个方向对于分类未必是最有利的9线性降维方法主成分分析(PCA)[Jolliffe,110线性降维方法线性判别分析(LDA)[Fukunaga,1991]降维目的：寻找最能把两类样本分开的投影直线，使投影后两类样本的均值之差与投影样本的总类散度的比值最大求解方法：经过推导把原问题转化为关于样本集总类内散度矩阵和总类间散度矩阵的广义特征值问题Bestprojectiondirectionforclassification10线性降维方法线性判别分析(LDA)[Fukunaga,11降维方法概述线性降维主成分分析(PCA)[Jolliffe,1986]线性判别分析(LDA)[Fukunaga,1991]PCALDA11降维方法概述线性降维PCALDA12降维方法概述线性降维主成分分析(PCA)[Jolliffe,1986]线性判别分析(LDA)[Fukunaga,1991]多维尺度变换(MDS)[Cox,1994]xixjdijMappingzizjgij原始空间，可能非欧式低维欧式空间12降维方法概述线性降维xixjdijMappingzizj13线性降维方法的不足原始数据无法表示为特征的简单线性组合比如：PCA无法表达Helix曲线流形1-DHelix曲线流形13线性降维方法的不足原始数据无法表示为特征的简单线性组合114线性降维方法的不足真实数据中的有用信息不能由线性特征表示比如：如何获取并表示多姿态人脸的姿态信息比如：如何获取运动视频序列中某个动作的对应帧#1引自J.B.Tenenbaumetal.2000#2引自Jenkinset.al,IROS2002#2#114线性降维方法的不足真实数据中的有用信息不能由线性特征表示15降维方法概述线性降维传统非线性降维核主成分分析(KPCA)[Scholkopf,1998]主曲线(PrincipalCurves)[Hastie,1989][Tibshirani,1992]自组织映射(SOM)[Kohonen,1995]产生式拓扑映射(GTM)[Bishop,1998]…15降维方法概述线性降维16降维方法概述基于流形学习的非线性降维保距特征映射(ISOMAP)[Tenenbaum,2000]局部线性嵌入(LLE)[Roweis,2000]拉普拉斯特征映射(LE,LaplacianEigenmap)[Belkin,2001]HessianLLE(HLLE)[Donoho,2003]局部切空间对齐(LTSA,LocalTangentSpaceAlignment)[Zhang,2004]最大方差展开(MVU/SDE,MaximumVarianceUnfolding)[Weinberger,2004]局部保持映射(LocalityPreservingProjections)[He,2003]…16降维方法概述基于流形学习的非线性降维17提纲研究背景基本知识介绍经典方法概览总结讨论17提纲研究背景18流形学习框架什么是流形？流形是线性子空间的一种非线性推广拓扑学角度：局部区域线性，与低维欧式空间拓扑同胚微分几何角度：有重叠chart的光滑过渡黎曼流形就是以光滑的方式在每一点的切空间上指定了欧氏内积的微分流形#1引自S.T.Roweisetal.2000#1Swiss-rollS-curveFishbow18流形学习框架什么是流形？#1引自S.T.Roweis19流形的数学定义设是一个Hausdorff拓扑空间，若对每一点都有的一个开邻域和的一个开子集同胚,则称为维拓扑流形,简称为维流形.流形学习框架#1引自M.H.Law,2004#1Mx1x2R2Rnzxx:coordinateforzU19流形的数学定义流形学习框架#1引自M.H.Law,20一些基本数学概念拓扑，Hausdorff空间，坐标卡，微分结构光滑函数，光滑映射，切向量，切空间…参考文献陈省身,陈维桓,微分几何讲义.北京大学出版社,1983MBerger,BGostiaux.DifferentialGeometry:Manifolds,CurvesandSurfaces,GTM115.Springer-Verlag,1974陈维桓,微分流形初步(第二版).高等教育出版社,2001流形学习框架20一些基本数学概念流形学习框架21流形学习的目的流形学习是一种非线性的维数约简方法高维观察数据的变化模式本质是由少数几个隐含变量所决定的如：人脸采样由光线亮度、人与相机的距离、人的头部姿势、人的面部表情等因素决定从认知心理学的角度，心理学家认为人的认知过程是基于认知流形和拓扑连续性的流形学习框架#1引自Linetal.PAMI2008#121流形学习的目的流形学习框架#1引自Linetal.22流形学习的数学定义设

是一个低维流形,是一个光滑嵌入,其中D>d.数据集是随机生成的,且经过f映射为观察空间的数据流形学习就是在给定观察样本集的条件下重构

f

和.V.deSilvaandJ.B.Tenenbaum.Globalversuslocalmethodsinnonlineardimensionalityreduction.NeuralInformationProcessingSystems15(NIPS'2002),pp.705-712,2003.22流形学习的数学定义设是一个23非线性降维高维数据空间data/observationspace低维嵌入空间embedding/coordinatespace保持一定几何拓扑关系，如测地距离/邻域线性重构关系流形学习示例23非线性降维高维数据空间低维嵌入空间保持一定几何拓扑关系，24提纲研究背景基本知识介绍经典方法概览总结讨论24提纲研究背景25经典流形学习方法一览方法简称所保持的几何属性全局/局部关系计算复杂度ISOMAP点对测地距离全局非常高LLE局部线性重构关系局部低LE局部邻域相似度局部低HLLE局部等距性局部高LTSA局部坐标表示全局+局部低MVU局部距离全局+局部非常高Logmap测地距离与方向局部非常低DiffusionMapsdiffusion距离全局中等25经典流形学习方法一览方法简称所保持的几何属性全局/局部关26经典方法分类结构图26经典方法分类结构图27等距映射(ISOMAP)J.B.Tenenbaum,V.deSilva,andJ.C.Langford.Aglobalgeometricframeworkfornonlineardimensionalityreduction.Science,vol.290,pp.2319--2323,2000.局部线性嵌入(LLE)S.T.RoweisandL.K.Saul.Nonlineardimensionalityreductionbylocallylinearembedding.Science,vol.290,pp.2323--2326,2000.拉普拉斯特征映射(LaplacianEigenmap)M.Belkin,P.Niyogi,LaplacianEigenmapsforDimensionalityReductionandDataRepresentation.NeuralComputation,

Vol.15,Issue6,pp.1373–1396,

2003.

重点介绍的几个方法27等距映射(ISOMAP)重点介绍的几个方法28等距映射(ISOMAP)J.B.Tenenbaum,V.deSilva,andJ.C.Langford.Aglobalgeometricframeworkfornonlineardimensionalityreduction.Science,vol.290,pp.2319--2323,2000.局部线性嵌入(LLE)S.T.RoweisandL.K.Saul.Nonlineardimensionalityreductionbylocallylinearembedding.Science,vol.290,pp.2323--2326,2000.拉普拉斯特征映射(LaplacianEigenmap)M.Belkin,P.Niyogi,LaplacianEigenmapsforDimensionalityReductionandDataRepresentation.NeuralComputation,

Vol.15,Issue6,pp.1373–1396,

2003.

重点介绍的几个方法28等距映射(ISOMAP)重点介绍的几个方法29代表性算法-1ISOMAP(Isometricfeaturemapping)保持全局测地距离测地距离反映数据在流形上的真实距离差异等距映射基于线性算法MDS，采用“测地距离”作为数据差异度量#1引自J.B.Tenenbaumetal.2000#1欧式距离vs.测地距离最短路径近似测地距离降维嵌入空间29代表性算法-1ISOMAP(Isometricfea30多维尺度变换(MDS)MDS是一种非监督的维数约简方法.MDS的基本思想:约简后低维空间中任意两点间的距离应该与它们在原高维空间中的距离相同.MDS的求解:通过适当定义准则函数来体现在低维空间中对高维距离的重建误差,对准则函数用梯度下降法求解,对于某些特殊的距离可以推导出解析解法.30多维尺度变换(MDS)MDS是一种非监督的维数约简31MDS的准则函数31MDS的准则函数32MDS的示意图32MDS的示意图33MDS的失效33MDS的失效34测地线:流形上连接两个点的最短曲线例如：球面上的测地线就是球面上的大圆弧测地距离：测地线的长度ABFigurefrom/GreatCircle.html测地距离34测地线:流形上连接两个点的最短曲线ABFiguref35ISOMAP算法流程1计算每个点的近邻点(用K近邻或邻域).2在样本集上定义一个赋权无向图如果和互为近邻点,则边的权值为3计算图中两点间的最短距离,记所得的距离矩阵为

.4用MDS求低维嵌入坐标,

令低维嵌入是

的第1大到第d大的特征值所对应的特征向量.35ISOMAP算法流程1计算每个点的近邻点(用K近邻或36M.Bernstein,V.Silva,J.C.Langford,J.B.Tenenbaum证明了如下的渐进收敛定理.假设采样点是随机均匀抽取的,则

渐进收敛定理给定

则只要样本集充分大且适当选择K,不等式

至少以概率成立.图距离逼近测地距离36M.Bernstein,V.Silva,J.C.37ISOMAP实验结果FiguresfromISOMAPpaper37ISOMAP实验结果FiguresfromISOMA38Figurefrom/handfig.htmlISOMAP实验结果38Figurefromhttp://isomap.st39FiguresfromISOMAPpaperISOMAP实验结果39FiguresfromISOMAPpaperISO40InterpolationonStraightLinesintheProjectedCo-ordinatesFiguresfromISOMAPpaper40InterpolationonStraightLi41代表性算法-1ISOMAP(Isometricfeaturemapping)前提假设数据所在的低维流形与欧式空间的一个子集整体等距该欧式空间的子集是一个凸集思想核心较近点对之间的测地距离用欧式距离代替较远点对之间的测地距离用最短路径来逼近算法特点适用于学习内部平坦的低维流形不适于学习有较大内在曲率的流形计算点对间的最短路径比较耗时41代表性算法-1ISOMAP(Isometricfea42ISOMAP-summaryInheritsfeaturesofMDSandPCA:guaranteedasymptoticconvergencetotruestructurePolynomialruntimeNon-iterativeAbilitytodiscovermanifoldsofarbitrarydimensionalityPerformwellwhendataisfromasinglewellsampledclusterFewfreeparametersGoodtheoreticalbaseforitsmetricspreservingproperties42ISOMAP-summaryInheritsfea43ProblemswithISOMAPEmbeddingsarebiasedtopreservetheseparationoffarawaypoints,whichcanleadtodistortionoflocalgeometryFailstonicelyprojectdataspreadamongmultipleclustersWell-conditionedalgorithmbutcomputationallyexpensiveforlargedatasets43ProblemswithISOMAPEmbeddin44ImprovementstoISOMAPConformalIsomap–capableoflearningthestructureofcertaincurvedmanifoldsLandmarkIsomap–approximateslargeglobalcomputationsbyamuchsmallersetofcalculationReconstructdistancesusingk/2closestobjects,aswellask/2farthestobjects44ImprovementstoISOMAPConfor45等距映射(ISOMAP)J.B.Tenenbaum,V.deSilva,andJ.C.Langford.Aglobalgeometricframeworkfornonlineardimensionalityreduction.Science,vol.290,pp.2319--2323,2000.局部线性嵌入(LLE)S.T.RoweisandL.K.Saul.Nonlineardimensionalityreductionbylocallylinearembedding.Science,vol.290,pp.2323--2326,2000.拉普拉斯特征映射(LaplacianEigenmap)M.Belkin,P.Niyogi,LaplacianEigenmapsforDimensionalityReductionandDataRepresentation.NeuralComputation,

Vol.15,Issue6,pp.1373–1396,

2003.

重点介绍的几个方法45等距映射(ISOMAP)重点介绍的几个方法46代表性算法-2LLE(Locallylinearembedding)显式利用“局部线性”的假设保持局部邻域几何结构–重构权重权重对样本集的几何变换具有不变性46代表性算法-2LLE(Locallylineare47代表性算法-2LLE(Locallylinearembedding)前提假设采样数据所在的低维流形在局部是线性的每个采样点均可以利用其近邻样本进行线性重构表示学习目标低维空间中保持每个邻域中的重构权值不变在嵌入映射为局部线性的条件下，最小化重构误差最终形式化为特征值分解问题47代表性算法-2LLE(Locallylineare48LLE算法示意图48LLE算法示意图49LLE算法流程

1计算每一个点的近邻点,一般采用K近邻或者邻域.2计算权值使得把用它的K个近邻点线性表示的误差最小,即通过最小化来求出.3保持权值不变,求在低维空间的象,使得低维重构误差最小.49LLE算法流程1计算每一个点的近邻点,50LLE算法的求解1计算每一个点的近邻点.2对于点和它的近邻点的权值,3令,低维嵌入是M的最小的第2到第d＋1个特征向量.

50LLE算法的求解1计算每一个点的近邻点.51LLE实验结果51LLE实验结果52LLE实验结果52LLE实验结果53LLE实验结果邻域参数的影响53LLE实验结果邻域参数的影响54FigurefromLLEpaperLLE实验结果54FigurefromLLE实验结果55LLE实验结果55LLE实验结果56代表性算法-2LLE(Locallylinearembedding)优点算法可以学习任意维的局部线性的低维流形算法归结为稀疏矩阵特征值计算，计算复杂度相对较小缺点算法所学习的流形只能是不闭合的算法要求样本在流形上是稠密采样的算法对样本中的噪声和邻域参数比较敏感56代表性算法-2LLE(Locallylineare57NumericalIssuesCovariancematrixusedtocomputeWcanbeill-conditioned,regularizationneedstobeusedSmalleigenvaluesaresubjecttonumericalprecisionerrorsandtogettingmixedBut,sparsematricesusedinthisalgorithmmakeitmuchfasterthenIsomap57NumericalIssuesCovariancem58等距映射(ISOMAP)J.B.Tenenbaum,V.deSilva,andJ.C.Langford.Aglobalgeometricframeworkfornonlineardimensionalityreduction.Science,vol.290,pp.2319--2323,2000.局部线性嵌入(LLE)S.T.RoweisandL.K.Saul.Nonlineardimensionalityreductionbylocallylinearembedding.Science,vol.290,pp.2323--2326,2000.拉普拉斯特征映射(LaplacianEigenmap)M.Belkin,P.Niyogi,LaplacianEigenmapsforDimensionalityReductionandDataRepresentation.NeuralComputation,

Vol.15,Issue6,pp.1373–1396,

2003.

重点介绍的几个方法58等距映射(ISOMAP)重点介绍的几个方法59代表性算法-3LE(LaplacianEigenmap)基本思想：在高维空间中离得很近的点投影到低维空间中的象也应该离得很近.求解方法：求解图拉普拉斯算子的广义特征值问题.59代表性算法-3LE(LaplacianEigenma60拉普拉斯算子设M是光滑的黎曼流形,f是M上的光滑函数,是f的梯度,则称线性映射为M上的拉普拉斯算子,其中div是散度算子.60拉普拉斯算子设M是光滑的黎曼流形,f是M上61图上的拉普拉斯算子设G是一个图,v是它的顶点,是v的自由度,w(u,v)是连接顶点u,v的边的权值,令

其中T

是对角矩阵,对角线的元素为

,则称L

为图G上的拉普拉斯算子.61图上的拉普拉斯算子设G是一个图,v是它的顶点,62LaplacianEigenmap算法流程1从样本点构建一个近邻图,图的顶点为样本点,离得很近两点用边相连(K近邻或邻域).2给每条边赋予权值如果第

个点和第j个点不相连，权值为0，否则;3计算图拉普拉斯算子的广义特征向量,求得低维嵌入.令D为对角矩阵L是近邻图上的拉普拉斯算子,求解广义特征值问题.62LaplacianEigenmap算法流程1从样本63LaplacianEigenmap实验结果(1)63LaplacianEigenmap实验结果(1)64300mostfrequentwordsoftheBrowncorpusrepresentedinthespectraldomainLaplacianEigenmap实验结果(2)64300mostfrequentwordsoft65LaplacianEigenmap实验结果(2)Thefirstisexclusivelyinfinitivesofverbs,thesecondcontainsprepositionsandthethirdmostlymodalandauxiliaryverbs.Weseethatsyntacticstructureiswell-preserved.

65LaplacianEigenmap实验结果(2)The66代表性算法-3LE(LaplacianEigenmap)优点算法是局部非线性方法，与谱图理论有很紧密的联系.算法通过求解稀疏矩阵的特征值问题解析地求出整体最优解，效率非常高算法使原空间中离得很近的