11.非线性流形学习方法杭

1、非线性流形学习方法介绍Introduction to Nonlinear Manifold Learning Methods刘雨杭2016年11月28日为什么引入非线性的方法？线性降维方法的不足原始数据无法表示为特征的简单线性组合比如：PCA无法表达Helix曲线流形1-D Helix曲线流形为什么引入非线性的方法？线性降维方法的不足真实数据中的有用信息不能由线性特征表示比如：如何获取并表示多姿态人脸的姿态信息比如：如何获取运动视频序列中某个动作的对应帧#1 引自J.B. Tenenbaum et al. 2000#2 引自Jenkins et. al, IROS 2002#1 #2目录ISO

2、MAP算法LE算法3流形学习框架12LLE算法45总结与对比预备知识拓扑，同胚 “拓扑”这个词在希腊语中的意思是地貌。拓扑学是研究几何体连续形变中保持不变的性质 而连续的变换（弯曲，延展，剪切）最后都能变成一样的两个物体，称为同胚（Homeomorphism） “拓扑学家就是不会区分甜甜圈和咖啡杯的人。” -John L. Kelley。从同胚角度上说，甜甜圈与有一只把手的杯子等价（都只有一个洞）。 拓扑学上是“柔软”的，传统的基于欧式空间的几何学是坚硬的。chart 把流体的任何一个微小的局部看作是欧几里德空间，称为一个chart预备知识广义特征值 一个广义特征值有如下形式：A=B， 其中A

3、和B为矩阵。其广义特征值 可以通过求解方程(A-B)=0，得到det(A-B)=0（其中det即行列式）构成。求得后带入原方程A=B可求出拉普拉斯矩阵给定一个有n个顶点的图G，它的拉普拉斯矩阵 定义为:L=D-A.其中D为图的度矩阵，A为图的邻接矩阵.对于 1.若i = j,则为顶点i的度2.若i j，但i和j邻接，则为-13.若i j，i和j不邻接， 为0邻接矩阵示例预备知识图的拉普拉斯算子预备知识测地距离测地线: 流形上连接两个点的最短曲线例如：球面上的测地线就是球面上的大圆弧测地距离：测地线的长度Figure from 流形学习框架什么是流形？流形是线性子空间的一种非线性推广拓扑学角度：

4、局部区域线性，与低维欧式空间拓扑同胚微分几何角度：有重叠chart的光滑过渡黎曼流形就是以光滑的方式在每一点的切空间上指定了欧氏内积的微分流形#1 引自S.T. Roweis et al. 2000#1Swiss-rollS-curveFishbow流形学习框架流形的数学定义设 是一个Hausdorff拓扑空间，若对每一点 都有 的一个开邻域 和 的一个开子集同胚, 则称M为 d维拓扑流形, 简称为d 维流形.#1 引自M. H. Law, 2004#1Mx1x2RRnzxx: coordinate for zUd流形学习框架流形的性质Manifold = Many + Fold, 很多曲面片

5、的叠加叠加但不是拼接，不自交欧氏空间属于流形任何一个流形都可以嵌入到足够高维度的欧氏空间中(Whitney嵌入定理)流形学习框架目的：降维，研究数据流形的几何和拓扑定义：从高维采样数据恢复低维流形结构时间：2000年Science首次提出动机：从认知心理学的角度，心理学家认为人的认知过程是基于认知流形和拓扑连续性的流形学习介绍流形学习框架流形学习数学定义流形学习框架流形学习示例非线性降维高维数据空间data / observation space低维嵌入空间embedding / coordinate space保持一定几何拓扑关系，如测地距离/邻域线性重构关系流形学习框架真实数据是怎样的？外

6、围欧式空间的维度很高数据存在一定的低维内在结构我们假设数据是位于一个低维子流形上流形假设非线性流形学习方法 等距映射(Isomap).J.B. Tenenbaum, V. de Silva, and J. C. Langford. A global geometric framework for nonlinear dimensionality reduction. Science, vol. 290, pp. 2319-2323, 2000. 局部线性嵌入(LLE).S. T. Roweis and L. K. Saul. Nonlinear dimensionality reduction

7、 by locally linear embedding. Science, vol. 290, pp. 2323-2326, 2000. 拉普拉斯特征映射(Laplacian Eigenmap).M. Belkin, P. Niyogi, Laplacian Eigenmaps for Dimensionality Reduction and Data Representation. Neural Computation, Vol. 15, Issue 6, pp. 1373 1396, 2003 .几种非线性流形学习算法非线性流形学习方法ISOMAP1 高维数据所在的低维流形与欧氏空间的一

8、个子集是整体等距的.2 与数据所在的流形等距的欧氏空间的子集是一个凸集.Isomap的前提假设等距映射(Isomap)的基本思想建立在多维尺度变换(MDS)的基础上，力求保持数据点的内在几何性质，即保持两点间的测地距离.非线性流形学习方法ISOMAPIsomap算法的核心估计两点间的测地距离: 1 离得很近的点间的测地距离用欧氏距离代替. 2 离得较远的点间的测地距离用最短路径来逼近.非线性流形学习方法ISOMAP测地距离估计非线性流形学习方法ISOMAPISOMAP算法流程1、选取每个样本点最近的k个点，或以样本点为中心半径为 的圆内的所有点。（参数k，或 ）2、通过最短路算法构造一个N*N

9、的距离矩阵。3、通过Multi-dimensional Scaling算法根据距离矩阵进行非线性降维。（参数d，降到d维）非线性流形学习方法ISOMAPISOMAP实验结果Figures from ISOMAP paper非线性流形学习方法LE基本思想：在高维空间中离得很近的点投影到低维空间中的象也应该离得很近. 通过使用两点间的加权距离作为损失函数，可求得相应的降维结果。待优化的目标函数： 快速对目标函数进行整理：非线性流形学习方法LE于是，我们的最小化问题可以等效为：这个目标的求解就是一个广义特征值分解问题限制条件保证优化问题有解，并且保证映射后的数据点不会被“压缩”到一个小于m维的子空间

10、中非线性流形学习方法LELE算法流程2中W也可取值：非线性流形学习方法LELaplacian Eigenmap实验结果非线性流形学习方法LLELocally linear embedding（局部线性嵌入） 非线性流形学习方法LLE算法步骤：寻找每个样本点的k个近邻点；由每个样本点的近邻点计算出该样本点的局部重建权值矩阵；（最小化权重误差）由该样本点的局部重建权值矩阵和其近邻点计算出该样本点的输出值。（最小化隐射误差） 具体的算法流程如下图所示: 非线性流形学习方法LLE求解方法： 采用的是拉格朗日乘子法，求得W非线性流形学习方法LLE求解方法： 非线性流形学习方法LLE例.非线性流形学习方法LLELLE实验结果总结与对比 LLE, Isomap, Laplacian Eigenmap 有效的原因1 它们都是非参数的方法，不需要对流形的很多的参数假设.2 它们是非线性的方法，都基于流形的内在几何结构，更能体现现实