流形学习专题介绍

1流形学习专题介绍王瑞平人脸识别课题组中国科学院计算技术研究所2010/05/06@VMRGroupBookReading提纲研究背景基本知识介绍经典方法概览总结讨论3提纲研究背景基本知识介绍经典方法概览总结讨论4从降维问题说起降维的动机原始观察空间中的样本具有极大的信息冗余样本的高维数引发分类器设计的“维数灾难”数据可视化、特征提取、分类与聚类等任务需求6464ImagespaceFaceslieonalow-DmanifoldintheimagespaceManifoldfaceslieon3featuresneededLeft-RightPoseUp-DownPoseLightingDirection5从降维问题说起降维的动机增加特征数增加信息量提高准确性增加训练分类器的难度维数灾难解决办法：选取尽可能多的,可能有用的特征,然后根据需要进行特征/维数约简.6从降维问题说起降维的动机特征选择特征约简特征提取依据某一标准选择性质最突出的特征实验数据分析，数据可视化（通常为2维或3维）等也需要维数约简经已有特征的某种变换获取约简特征7降维方法概述线性降维通过特征的线性组合来降维本质上是把数据投影到低维线性子空间线性方法相对比较简单且容易计算代表方法主成分分析(PCA)线性判别分析(LDA)多维尺度变换(MDS)8线性降维方法主成分分析(PCA)[Jolliffe,1986]降维目的：寻找能够保持采样数据方差的最佳投影子空间求解方法：对样本的散度矩阵进行特征值分解,所求子空间为经过样本均值,以最大特征值所对应的特征向量为方向的子空间Principalcomponent9线性降维方法主成分分析(PCA)[Jolliffe,1986]PCA对于椭球状分布的样本集有很好的效果,学习所得的主方向就是椭球的主轴方向.PCA是一种非监督的算法,能找到很好地代表所有样本的方向,但这个方向对于分类未必是最有利的10线性降维方法线性判别分析(LDA)[Fukunaga,1991]降维目的：寻找最能把两类样本分开的投影直线，使投影后两类样本的均值之差与投影样本的总类散度的比值最大求解方法：经过推导把原问题转化为关于样本集总类内散度矩阵和总类间散度矩阵的广义特征值问题Bestprojectiondirectionforclassification11降维方法概述线性降维主成分分析(PCA)[Jolliffe,1986]线性判别分析(LDA)[Fukunaga,1991]PCALDA12降维方法概述线性降维主成分分析(PCA)[Jolliffe,1986]线性判别分析(LDA)[Fukunaga,1991]多维尺度变换(MDS)[Cox,1994]xixjdijMappingzizjgij原始空间，可能非欧式低维欧式空间13线性降维方法的不足原始数据无法表示为特征的简单线性组合比如：PCA无法表达Helix曲线流形1-DHelix曲线流形-1-0.500.51-1-0.500.510510152014线性降维方法的不足真实数据中的有用信息不能由线性特征表示比如：如何获取并表示多姿态人脸的姿态信息比如：如何获取运动视频序列中某个动作的对应帧#1引自J.B.Tenenbaumetal.2000#2引自Jenkinset.al,IROS2002#2#115降维方法概述线性降维传统非线性降维核主成分分析(KPCA)[Scholkopf,1998]主曲线(PrincipalCurves)[Hastie,1989][Tibshirani,1992]自组织映射(SOM)[Kohonen,1995]产生式拓扑映射(GTM)[Bishop,1998]…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]…17提纲研究背景基本知识介绍经典方法概览总结讨论18流形学习框架什么是流形？流形是线性子空间的一种非线性推广拓扑学角度：局部区域线性，与低维欧式空间拓扑同胚微分几何角度：有重叠chart的光滑过渡黎曼流形就是以光滑的方式在每一点的切空间上指定了欧氏内积的微分流形#1引自S.T.Roweisetal.2000#1Swiss-rollS-curveFishbow19流形的数学定义设是一个Hausdorff拓扑空间，若对每一点都有的一个开邻域和的一个开子集同胚,则称为维拓扑流形,简称为维流形.流形学习框架MpMpUddMd#1引自M.H.Law,2004#1Mx1x2R2Rnzxx:coordinateforzU20一些基本数学概念拓扑，Hausdorff空间，坐标卡，微分结构光滑函数，光滑映射，切向量，切空间…参考文献陈省身,陈维桓,微分几何讲义.北京大学出版社,1983MBerger,BGostiaux.DifferentialGeometry:Manifolds,CurvesandSurfaces,GTM115.Springer-Verlag,1974陈维桓,微分流形初步(第二版).高等教育出版社,2001流形学习框架21流形学习的目的流形学习是一种非线性的维数约简方法高维观察数据的变化模式本质是由少数几个隐含变量所决定的如：人脸采样由光线亮度、人与相机的距离、人的头部姿势、人的面部表情等因素决定从认知心理学的角度，心理学家认为人的认知过程是基于认知流形和拓扑连续性的流形学习框架#1引自Linetal.PAMI2008#122流形学习的数学定义设是一个低维流形,是一个光滑嵌入,其中Dd.数据集是随机生成的,且经过f映射为观察空间的数据流形学习就是在给定观察样本集的条件下重构f和.V.deSilvaandJ.B.Tenenbaum.Globalversuslocalmethodsinnonlineardimensionalityreduction.NeuralInformationProcessingSystems15(NIPS'2002),pp.705-712,2003.dRYDRYf:}{iy)}.({iiyfx}{ix}{iy23非线性降维高维数据空间data/observationspace低维嵌入空间embedding/coordinatespace保持一定几何拓扑关系，如测地距离/邻域线性重构关系流形学习示例24提纲研究背景基本知识介绍经典方法概览总结讨论25经典流形学习方法一览方法简称所保持的几何属性全局/局部关系计算复杂度ISOMAP点对测地距离全局非常高LLE局部线性重构关系局部低LE局部邻域相似度局部低HLLE局部等距性局部高LTSA局部坐标表示全局+局部低MVU局部距离全局+局部非常高Logmap测地距离与方向局部非常低DiffusionMapsdiffusion距离全局中等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.重点介绍的几个方法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.重点介绍的几个方法29代表性算法-1ISOMAP(Isometricfeaturemapping)保持全局测地距离测地距离反映数据在流形上的真实距离差异等距映射基于线性算法MDS，采用“测地距离”作为数据差异度量#1引自J.B.Tenenbaumetal.2000#1欧式距离vs.测地距离最短路径近似测地距离降维嵌入空间30多维尺度变换(MDS)MDS是一种非监督的维数约简方法.MDS的基本思想:约简后低维空间中任意两点间的距离应该与它们在原高维空间中的距离相同.MDS的求解:通过适当定义准则函数来体现在低维空间中对高维距离的重建误差,对准则函数用梯度下降法求解,对于某些特殊的距离可以推导出解析解法.31jiijijijjiijefdJ2)(1,)(22jiijjiijijeedJ2jiijijijffdJMDS的准则函数32MDS的示意图33MDS的失效34测地线:流形上连接两个点的最短曲线例如：球面上的测地线就是球面上的大圆弧测地距离：测地线的长度ABFigurefrom测地距离35ISOMAP算法流程1计算每个点的近邻点(用K近邻或邻域).2在样本集上定义一个赋权无向图如果和互为近邻点,则边的权值为3计算图中两点间的最短距离,记所得的距离矩阵为.4用MDS求低维嵌入坐标,令低维嵌入是的第1大到第d大的特征值所对应的特征向量.).,(jidX)},({jidDGGjXiX,2/)()/1()()()(2HSHDNHHDSSijijijij，，)(D36M.Bernstein,V.Silva,J.C.Langford,J.B.Tenenbaum证明了如下的渐进收敛定理.假设采样点是随机均匀抽取的,则渐进收敛定理给定则只要样本集充分大且适当选择K,不等式至少以概率成立.,0,,21211distancegeodesicdistancegraph11图距离逼