my流形学习简介.ppt

流 形 学 习 简 介 许馨 2004.9 设 是一个低维流形， 是一个光滑嵌入, 其中 Dd . 数据集 是随机生成的，且经过 f 映射为观 察空间的数据 流形学习就是在给定观察样本 集 的条件下重构 f 和 . V. de Silva and J. B. Tenenbaum. Global versus local methods in nonlinear dimensionality reduction . Neural Information Processing Systems 15 (NIPS2002), pp. 705- 712, 2003. 流形学习的定义 几种流形学习算法 局部线性嵌入(LLE). S. T. Roweis and L. K. Saul. Nonlinear dimensionality reduction by locally linear embedding. Science, vol. 290, pp. 2323-2326, 2000. 等距映射(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. 拉普拉斯特征映射(Laplacian Eigenmap). M. Belkin, P. Niyogi, Laplacian Eigenmaps for Dimensionality Reduction and Data Representation. Neural Computation, Vol. 15, Issue 6, pp. 1373 1396, 2003 . 基于流形学习的方法LLE（locally linear embedding）* 1.LLE算法的主要思想：对于一组具有嵌套流形的数据集，在嵌套空间与内 在低维空间局部邻域间的点的关系应该不变。 即在嵌套空间每个采样点可以用它的近邻点线性表示，在低维空间中保持每 个邻域中的权值不变，重构原数据点, 使重构误差最小. 2.算法步骤： 1）设D维空间中有N个数据属于同一流形，记做：Xixi1,xi2,.,xiD，i=1 N。假设有足够的数据点，并且认为空间中的每一个数据点可以用它的K 个近邻线性表示。求近邻点，一般采用K近邻或者 邻域. 2）计算权值Wij，代价函数为： ，（1） 并且权值要满足两个约束条件： 每一个数据点Xi都只能由它的邻近点来 表示，若Xj不是近邻点，则Wij=0； 权值矩阵的每一行的和为1，即： 。 这样，求最优权值就是对于公式（1）在两个约束条件下求解最小二乘问题 。权值体现了数据间内在的几何关系。 ， 基于流形学习的方法LLE（locally linear embedding）* 3）保持权值不变，在低维空间d（dd会提高算法的鲁 棒性； 2 K不能过大，对于高曲率的流形，K过大会导致不能正确 表示其局部几何关系。 3 K过小会导致流形不连续。 文献*估计K的方法是： Dx是输入空间X的欧氏距离矩阵，Dy是得到嵌入的低维流 形Y的欧氏距离矩阵， 是他们之间的相关系数。 (实验得到的K值并不理想！) * Olga Kouropteva,Oleg Okun and Matti Pietikainen. Selection of the optimal parameter value for the locally linear embedding algorithm 非线性降维近邻点K的选取 LLE算法的例子(2)-正常星系非线性降维求红移 基于光谱数据的K选取的方法： 同种类型的光谱按照红移的大小，在一维空间中 曲线呈单调的（因为一维流形是连续光滑的），所以 只要判定这种单调性就可以确定K的大小。如果K过大 或者过小，其分布就不是单调的，或是有奇异点的。 单调数列定义：若x10.01有130条；用加权距离得到的红移误差 0.01也有130条。 实验结果 实验结果 实验结果 多维尺度变换 (MDS) MDS 是一种非监督的维数约简方法. MDS的基本思想: 约简后低维空间中任意两点间的 距离应该与它们在原始空间中的距离相同. MDS的求解: 通过适当定义准则函数来体现在低维 空间中对高维距离的重建误差, 对准则函数用梯度下 降法求解,对于某些特殊的距离可以推导出解析解法. 基于流形学习的方法ISOMAP 建立在多维尺度变换(MDS)的基础上，力求保持数据 点的内在几何性质，即保持两点间的测地距离. 等距映射(Isomap)的基本思想 基于流形学习的方法ISOMAP Isomap的前提假设 1 高维数据所在的低维流形与欧氏空间的一个子集是整 体等距的. 2 与数据所在的流形等距的欧氏空间的子集是一个凸集 . 基于流形学习的方法ISOMAP 估计两点间的测地距离: 1 离得很近的点间的测地距离用欧氏距离代替. 2 离得较远的点间的测地距离用最短路径来逼 近. Isomap算法的核心 基于流形学习的方法ISOMAP 测地距离估计 基于流形学习的方法ISOMAP Isomap算法 1 计算每个点的近邻点 (用K近邻或 邻域). 2 在样本集上定义一个赋权无向图 如果 和 互为近邻点，则 边的权值为 3 计算图中两点间的最短距离，记所得的距离矩阵为 . 4 用MDS求低维嵌入流形 , ? 代价函数： 令 低维嵌入是 的第2小到第 d1小的特征值所对应的特征向量. 推导？ 基于流形学习的方法ISOMAP 图距离逼近测地距离 M. Bernstein, V. Silva, J.C. Langford, J.B. Tenenbaum 证明了如下的渐进收敛定理. 假设采样点是依据密度函数 随机抽取的, 则 渐进收敛定理 给定 则对充分大的 , 不 等式 至少以概率 成立. 基于流形学习的方法ISOMAP Isomap 算法的例子(1) 基于流形学习的方法ISOMAP Isomap 算法的例子(2) 基于流形学习的方法ISOMAP Isomap算法的特点 Isomap是非线性的, 适用于学习内部平坦的低维流 形, 不适于学习有较大内在曲率的流形 . Isomap算法中有两个待定参数K, d . Isomap算法计算图上两点间的最短距离, 执行起来 比较慢 . R 基于流形学习的方法ISOMAP 拉普拉斯特征映射(Laplacian Eigenmap) 基本思想：在高维空间中离得很近的点投影到低维空间 中的象也应该离得很近. 通过使用两点间的加权距离作 为损失函数，可求得相应的降维结果。 待优化的目标函数： s.t. （矩阵D提供了对图的顶点的一种自然测度，Dii越大， 说明这个顶点越重要。） 求解方法：求解图拉普拉斯算子的广义特征值问题. 基于流形学习的方法 Laplacian Eigenmap Laplacian Eigenmap 算法 1 从样本点构建一个近邻图, 图的顶点为样本点，离得 很近两点用边相连 (K近邻或 邻域）. 2 给每条边赋予权值 如果第 个点和第 j 个点不相连， 权值为0，否则 (a) ; (b) 3 计算图拉普拉斯算子的广义特征向量，求得低维嵌入. 优化问题可化简为： 令D为对角矩阵 L是近邻图上的 拉普拉斯算子，求解y转为求广义特征值问题 最小特征值对应的特征向量。(由Rayleittz-Riz定理) （*） 基于流形学习的方法 Laplacian Eigenmap 拉普拉斯算子 设 M 是光滑的黎曼流形, f 是 M 上的光滑函数, 是 f 的梯度, 则称线性映射 为 M 上的拉普拉斯算子, 其中div是散度算子. 基于流形学习的方法 Laplacian Eigenmap 其中 T 是对角矩阵,对角线的元素为 , 则称 L 为图 G 上的拉普拉斯算子. 图上的拉普拉斯算子 设 G 是一个图, v 是它的顶点, 是 v 的自由度, w(u,v) 是连接顶点u,v 的边的权值,令 基于流形学习的方法 Laplacian Eigenmap Laplacian Eigenmap算法的例子 (1) 基于流形学习的方法 Laplacian Eigenmap Laplacian Eigenmap算法的特点 算法是局部的非线性方法. 算法与谱图理论有很紧密的联系. 算法中有两个参数 k,d. 算法通过求解稀疏矩阵的特征值问题解析地求出整体 最优解. 算法使原空间中离得很近的点在低维空间也离得很近 , 可以用于聚类. 基于流形学习的方法 Laplacian Eigenmap LLE, Isomap, Laplacian Eigenmap 有效的原因 1 它们都是非参数的方法，不需要对流形的很多的参 数假设. 2 它们是非线性的方法，都基于流形的内在几何结构 ，更能体现现实中数据的本质. 3 它们的求解简单，都转化为求解特征值问题，而不 需要用迭代算法. 流形学习问题探讨1 1 对嵌入映射或者低维流形作出某种特定的假设, 或者以 保持高维数据的某种性质不变为目标. 2 将问题转化为求解优化问题. 3 提供有效的算法. 为流形学习提供更为坚实和易于接受