计算机视觉课程-流形学习

ManifoldLearning什么是流形？•定义1：如果一个N维的拓扑空间M内的任意一点都存在一个邻域使得该邻域是N维欧氏空间的同胚，则这个拓扑空间M被称为流形。MUMx1x2R2Rn流形学习的数学基础•参考文献:–陈省身,陈维桓,微分几何讲义.北京大学出版社,1983–陈维桓,微分流形初步(第二版).高等教育出版社,2001什么是流形学习？•定义2：令Y是包含在欧氏空间的d维域，为光滑嵌入，其中Nd。数据点是随机生成的，经f映射形成观察空间的数据。一般称Y为隐空间，为隐数据。流形学习的目标是要从观察数据中重构f和dRNRYf:Yyi}{NiiRyfx)}({}{iyix}{iy流形是线性子空间的一种非线性推广.流形是一个局部可坐标化的拓扑空间.什么是流形学习？流形学习的可行性•1许多高维采样数据都是由少数几个隐含变量所决定的，如人脸采样由光线亮度,人离相机的距离,人的头部姿势,人的脸部肌肉等因素决定.•2从认知心理学的角度,心理学家认为人的认知过程是基于认知流形和拓扑连续性的.算法简介•Sciences2000年:Tenenbaum等人:IsomapRoweis和Saul：LLE•NIPS,2001年：M.Belkin和P.Niyogi:LaplacianEigenmaps•NIPS&ICCV2003：XiaofeiHe等人:LPP•PAMI2007：GraphEmbeddingandExtensions：AGeneralFrameworkforDimensionLLE•S.T.RoweisandL.K.SaulNonlineardimensionalityreductionbylocallylinearembeddingScience2000LLE主要思想：LLE（LocallyLinearEmbedding）算法强调在样本集结构不满足全局线性结构时，样本空间与内在低维子空间之间在局部意义下的结构可以用线性空间近似。jijixWxLLE邻接图LLE权值计算：学习目标：在低维空间中保持每个邻域中的权值不变，即假设嵌入映射在局部是线性的条件下,最小化重构误差。LLE•流程图：Step1：构建邻域。对于原始空间任一给定样本点，用K近邻法得到它的一组邻域点。Step2：计算权值。在第二步用权值描述原始空间任一点与其邻域的关系。权值是使得样本点用它的相邻点重构误差最小的解：Step3：嵌入。最后的嵌入通过最小化误差来保留尽可能多的原空间几何性质：这里W是第二步计算的权值，和是样本点在嵌入空间的投影LLE算法示意图应用应用人脸图像在2D流形空间的投影应用嘴唇图像在2D流形空间的投影LLE算法的优点•LLE算法可以学习任意维数的低维流形.•LLE算法中的待定参数很少,K和d.•LLE算法中每个点的近邻权值在平移,旋转,伸缩变换下是保持不变的.•LLE算法有解析的整体最优解,不需迭代.•LLE算法归结为稀疏矩阵特征值计算,计算复杂度相对较小,容易执行.LLE算法的缺点•LLE算法要求所学习的流形只能是不闭合的且在局部是线性的.•LLE算法要求样本在流形上是稠密采样的.•LLE算法中的参数K,d有过多的选择.•LLE算法对样本中的噪音很敏感.RIsomap（等距映射）•J.B.Tenenbaum,V.D.SilvaandK.C.LangfordAglobalgeometricframeworkfornonlineardimensionalityreductionScience2000多维尺度变换(MDS)•MDS是一种非监督的维数约简方法.•MDS的基本思想:约简后低维空间中任意两点间的距离应该与它们在原始空间中的距离相同.•MDS的求解:通过适当定义准则函数来体现在低维空间中对高维距离的重建误差,对准则函数用梯度下降法求解,对于某些特殊的距离可以推导出解析解法.MDS的示意图MDS的失效Isomap•主要思想：建立在多维尺度变换(MDS)的基础上，力求保持数据点的内在几何性质，即保持两点间的测地距离，不是欧式距离。•Isomap=MDS+测地距离IsomapIsomap流程图：Step1：在样本集上构建近邻图G。如果样本i和j之间距离小于某个阈值,或者他们为k-近邻，则连接i和jStep2：计算样本两两之间测地距离（用Dijkstra算法），建立测地距离矩阵Step3：利用MDS算法构造内在d维子空间，最小化下式矩阵变换算子将距离转换成MDS所需内积形式，其中S是平方距离矩阵，H是集中矩阵上式的最小值可以通过求矩阵的d个最大特征值对应的特征向量来实现应用SwissRoll在2D流形空间的投影3维数据集2维投影应用人脸图像在2D流形空间的投影横坐标反映了光照变化，纵坐标反映姿态变化应用手写数字（2）在2D流形空间的投影横坐标反映底部环型变化，纵坐标反映顶上穹型变化应用手势在2D流形空间的投影横坐标反映手腕旋转变化，纵坐标反映手指的伸展变化Isomap算法的特点•Isomap是非线性的,适用于学习内部平坦的低维流形,不适于学习有较大内在曲率的流形.•Isomap算法中有两个待定参数K,d.RLaplacianEigenmap•M.BelkinandP.NiyogiLaplacianeigenmapsandspectraltechniquesforembeddingandclusteringNIPS2001LaplacianEigenmap主要思想：在高维空间中离得很近的点投影到低维空间中的象也应该离得很近.LaplacianEigenmap•主要思想的数学表达：令样本集：投影后样本：LE的目标是最小化目标函数：LaplacianEigenmap这里权值反映样本之间的关系，一般用热核表示：也可以简单定义成1（节点i和j相邻）或0（不相邻）为了使最小化问题解唯一，必须加上尺度归一的限制条件，目标函数变为:这里L=D-W被称为Laplacian矩阵是对角矩阵可以转化成广义特征值问题求解：LaplacianEigenmap算法的特点•算法是局部的非线性方法.•算法与谱图理论有很紧密的联系.•算法中有两个参数k,d.•算法通过求解稀疏矩阵的特征值问题解析地求出整体最优解.•算法使原空间中离得很近的点在低维空间也离得很近,可以用于聚类.•没有给出显式的投影映射，即，对于新样本（out-of-sample）无法直接得到其在低维子流形上的投影RLPP•何晓飞等人,在LaplacianEigenmap的基础上，提出了局部保留投影（LocalityPreservingProjection）算法，得到了一个显式的投影映射。•“Learningalocalitypreservingsubspaceforvisualrecognition”,ICCV,2003•“Localitypreservingprojections”,AdvancesinNeuralInformationProcessingSystems,2003LPPnjijiPjiWyy1,2),(||||minLPP与LE一样，都可以归纳为相同目标函数最小化问题：但不同的是，LPP没有在流形上展开上式，而是通过一个原空间到流形上的映射P转换成原空间上的问题LPP可以得到如下推导：加上尺度归一限制：最小化问题转化成如下广义特征值求解问题：应用人脸图像在2D流形空间的投影横坐标反映了旋转变化，纵坐标反映表情变化小结方法结构保留范围显式映射近邻矩阵Isomap全局无稠密LLE局部无稀疏LE局部无稀疏LPP局部有稀疏LLE,Isomap,LaplacianEigenmap有效的原因1它们都是非参数的方法，不需要对流形的很多的参数假设.2它们是非线性的方法，都基于流形的内在几何结构，更能体现现实中数据的本质.3它们的求解简单，都转化为求解特征值问题，而不需要用迭代算法.目前流形学习研究的一般模式1对嵌入映射或者低维流形作出某种特定的假设,或者以保持高维数据的某种性质不变为目标.2将问题转化为求解优化问题.3提供有效的算法.•如何确定低维目标空间的维数?•当采样数据很稀疏时,怎样进行有效的学习?•将统计学习理论引入流形学习对其泛化性能进行研究。流形学习中存在的问题