《计算机视觉课程-流形学习》由会员分享，可在线阅读，更多相关《计算机视觉课程-流形学习（59页珍藏版）》请在金锄头文库上搜索。
1、什么是流形？Manifold Learning定义仁如果一个N维的拓扑空间M内的任 意一点都存在一个邻域um使得该邻域是 N维欧氏空间的同胚，则这个拓扑空间M被 称为流形。R2流形学习的数学基础参考文献:-陈省身，陈维桓,微分几何讲义北京大学出版 社，1983-陈维桓，微分流形初步（第二版）高等教育出版社，2001什么是流形学习?定义2：令丫是包含在欧氏空间疋的d维域,YRN为光滑嵌入，其中/Vd。数据点uY是随机生成的，经f映射形成观察空 间的数据W*(y)u疋。一般称丫为隐空间,为隐数据。流形学习的目标是要从观察数中重构用I”流形是线性子空间的一种非线性推广.流形是一个局部可坐标化的拓扑空
2、间.什么是流形学习?OO什么是流形学习?OO流形学习的可行性1许多高维采样数据都是由少数儿个隐含变量所决定的， 如人脸采样由光线亮度，人离相机的距离，人的头部姿势， 人的脸部肌肉等因素决定.2从认知心理学的角度，心理学家认为人的认知过程是基于 认知流形和拓扑连续性的.算法简介 Sciences 2000年：Tenenbaum等人：IsomapRoweis和Saul： LLE NIPS, 2001 年：M.Belkin和P.Niyogi: Laplacian Eigenmaps NIPS &ICCV2003：Xiaofei He等人：LPP PAMI 2007：Graph Embedding a
3、nd Extensions： A General Framework for DimensionLLE S.T.Roweis and L.K.SaulNonlinear dimensionality reduction by locally linear embeddingScience 2000LLE主要思想：LLE (Locally Linear Embedding)算法强调在样本集结 构不满足全局线性结构时，样本空间与内在低维子空间之间在局部 意义下的结构可以用线性空间近似。LLELLE叙LLEoLLE邻接图Step 3oLLE权值计算:学习目标：在低维空间中保持每个邻域中的权值不变，即
4、假设嵌 入映射在局部是线性的条件下，最小化重构误差。细）=工-力的F流程图:Step 1:构建邻域。对于原始空间任一给定样本点，用K近邻法 得到它的一组邻域点。Step 2：计算权值。在第二步用权值“如描述原始空间任一点与 其邻域的关系。权值【是使得样本点坨用它的相邻点叼重构误 差最小的解：23Step 3：嵌入。最后的嵌入通过最小化误差来保留尽可能多的原 空间几何性质：这里W是第二步计算的权值，乩和的是样本点在嵌入空间的投影LLEMW卿fflSelect neighborsooMmp ff embedded cooreLm驚 e$0应用应用人脸图像在2D流形空间的投影应用嘴唇图像在2D流形空
5、间的投影LLE算法的优点LLE算法可以学习任意维数的低维流形. LLE算法中的待定参数很少，K和d LLE算法中每个点的近邻权值在平移，旋转，伸缩变换下是保持不变的. LLE算法有解析的整体最优解，不需迭代.LLE算法归结为稀疏矩阵特征值计算,计算复 杂度相对较小，容易执行.LLE算法的缺点LLE算法要求所学习的流形只能是不闭合的且在 局部是线性的.LLE算法要求样本在流形上是稠密采样的.LLE算法中的参数K,d有过多的选择.LLE算法对样本中的噪音很敏感.Isomap （等距映射） J.B.Tenenbaum, V.D.Silva and K.C.LangfordA global geome
6、tric framework for nonlinear dimensionality reductionScience 2000多维尺度变换(MDS)MDS是一种非监督的维数约简方法.MDS的基本思想:约简后低维空间中任意两点间的 距离应该与它们在原始空间中的距离相同.MDS的求解:通过适当定义准则函数来体现在低维 空间中对高维距离的重建误差,对准则函数用梯度下 降法求解，对于某些特殊的距离可以推导出解析解法.MDS的示意图2 10 12 3 -III-2-101 2grrnwfi 屛MDS的失效Isomap主要思想：建立在多维尺度变换(MDS)的基础上，力求保 持数据点的内在几何性质，即保
7、持两点间的 测地距离，不是欧式距离。 Isomap = MDS +测地距离IsomapXRIsomap流程图:Step 1:在样本集上构建近邻图G。如果样本/和/之间距离小于某个 阈值，或者他们为k近邻，则连接/和/Step 2：计算样本两两之间测地距离(用Dijkstra算法)，建立测 地距离矩阵Dg = deg巧)Step 3：利用MDS算法构造内在d维子空间，最小化下式E=t(Dg)-t(Dy)矩阵变换算子厂(巧=-HSH/2将距离转换成MDS所需内积形式, 其中S是平方距离矩阵S“ =。爲是集中矩阵HXixj=几宀一 1/N上式的最小值可以通过求矩阵丁(Dg)的d个最大特征值对应的 特
8、征向量来实现应用 Swiss Roll在2D流形空间的投影3维数据集2维投影应用人脸图像在2D流形空间的投影横坐标反映了光照变化，纵坐标反映姿态变化应用手写数字（2）在2D流形空间的投影横坐标反映底部坏型变化，纵坐标反映顶上穹型变化Bottom loop articulaten| CO 匸co d 应用手势在2D流形空间的投影横坐标反映手腕旋转变化，纵坐标反映手指的伸展变化UOSUZX sj 鱼iLWrist rotationIsomap算法的特点Isomap是非线性的，适用于学习内部平坦的低维流 形,不适于学习有较大内在曲率的流形.Isomap算法中有两个待定参数K, d .Laplacia
9、n Eigenmap M.Belkin and P.NiyogiLaplacian eigenmaps and spectral techniques for embedding and clusteringNIPS 2001Laplacian Eigenmap主要思想：在高釜空间中离得很近的点投影到低维空间中的象也 应该离得很近.主要思想的数学表达：令样本集:X =（九皿）投影后样本:y =（如他）LE的冃标是最小化冃标函数：nZ恢-的j=l这里权值反映样本之间的关系，一般用热核表示：”11%-勺 |2% = e -也可以简单定义成1 （节点i和j相邻）或0 （不相邻）为了使最小化问题解唯一
10、，必须加上尺度归一的限制条件，冃标函数变为:arg min yryyTDy=l这里L=D-W被称为Laplacian矩阵禺=%咋是对角矩阵可以转化成广义特征值问题求解：Lv = XD1/ 1/Laplacian Eigenmap 算法的特点算法是局部的非线性方法.算法与谱图理论有很紧密的联系.算法中有两个参数k,d.算法通过求解稀疏矩阵的特征值问题解析地求出整体最 优解.算法使原空间中离得很近的点在低维空间也离得很近,可 以用于聚类.没有给出显式的投影映射，即，对于新样本(out-of- sample) 无法直接得到其在低维子流形上的投影LPP何晓飞等人在Laplacian Eigenmap的
11、基础上，提出了局 部保留投影(Locality Preserving Projection)算法，得到 了一个显式的投影映射。 “Learning a locality preserving subspace for visual recognitiorT, ICCV, 2003Locality preserving projections”，Advances in Neural Information Processing Systems, 2003LPP LPP与LE样，都可以归纳为相同目标函数最小化问 题：minXII 另一儿W(V)F 1但不同的是，LPP没有在流形上展开上式，而是通过
12、一 个原空间到流形上的映射P转换成原空间上的问题vT = PTXLPP可以得到如下推导:1 1弓刀恢-场=PTXi - PTxj2Wij=PtX(D - W)XTP =ptxlxtp加上尺度归一限制：YtDY = 1今PtXDXtP = 1最小化问题转化成如下广义特征值求解问题:XLXtP = XX D XTP应用人脸图像在2D流形空间的投影横坐标反映了旋转变化，纵坐标反映表情变化小结方法结构保留范 围显式映射近邻矩阵Isomap全局无稠密LLE局部无稀疏LE局部无稀疏LPP局部有稀疏LLE, Isomap, Laplacian Eigenmap 有效的原因1它们都是非参数的方法，不需要对流形的很多的参 数假设.2它们是非线性的方法，都基于流形的内在几何结构, 更能体现现实中数据的本质.3它们的求解简单，都转化为求解特征值问题，而不 需要用迭代算法.目前流形学习研究的一般模式1对嵌
