流行学习简介.ppt

1、流 形 学 习 简 介,许馨 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.,流形学习的定义,几种流形学习算法,局部

2、线性嵌入(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. 2

3、319-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算法的主要思想：对于一组具有嵌套流形的数据集，在嵌套空间与内在低维空间局部邻域间的点的关系应该不变。 即在

4、嵌套空间每个采样点可以用它的近邻点线性表示，在低维空间中保持每个邻域中的权值不变，重构原数据点, 使重构误差最小. 2.算法步骤： 1）设D维空间中有N个数据属于同一流形，记做：Xixi1,xi2,.,xiD，i=1N。假设有足够的数据点，并且认为空间中的每一个数据点可以用它的K个近邻线性表示。求近邻点，一般采用K近邻或者 邻域. 2）计算权值Wij，代价函数为： ，（1） 并且权值要满足两个约束条件： 每一个数据点Xi都只能由它的邻近点来表示，若Xj不是近邻点，则Wij=0； 权值矩阵的每一行的和为1，即： 。 这样，求最优权值就是对于公式（1）在两个约束条件下求解最小二乘问题。权值体现了数

5、据间内在的几何关系。 ，,基于流形学习的方法LLE（locally linear embedding）*,3）保持权值不变，在低维空间d（dD）中对原数据点重构。设低维空间的数据点为Yi，可以通过求最小的代价函数 （2）来得到。 公式（2）的最优解需要满足下面的约束条件： 1） ； 2） 条件1消除了Y向量平移不变的影响；条件2避免产生退化解。? 由Rayleittz-Riz定理，低维嵌入是 M 的最小的第 2到第 d1 个特征向量. 去掉最小特征值0对应的特征向量。,LLE算法示意图,基于流形学习的方法LLE（locally linear embedding）*,LLE算法的优点,LLE算法

6、可以学习任意维数的低维流形. LLE算法中的待定参数很少, K 和 d. LLE算法中每个点的近邻权值在平移, 旋转,伸缩变换下是保持不变的. LLE算法有解析的整体最优解,不需迭代. LLE算法归结为稀疏矩阵特征值计算, 计算复杂度相对较小, 容易执行.,基于流形学习的方法LLE（locally linear embedding）*,LLE算法的缺点,LLE算法要求所学习的流形只能是不闭合的且在局部是线性的. LLE算法要求样本在流形上是稠密采样的. LLE算法中的参数 K, d 有过多的选择. LLE算法对样本中的噪音很敏感. 对于新样本的映射需要重新计算。,R,基于流形学习的方法LLE（

7、locally linear embedding）*,LLE算法的例子(1),基于流形学习的方法LLE（locally linear embedding）*,K选取的原则： 1 近邻点K的值要大于流形的维数d；Kd会提高算法的鲁棒性； 2 K不能过大，对于高曲率的流形，K过大会导致不能正确表示其局部几何关系。 3 K过小会导致流形不连续。 文献*估计K的方法是： Dx是输入空间X的欧氏距离矩阵，Dy是得到嵌入的低维流形Y的欧氏距离矩阵， 是他们之间的相关系数。 (实验得到的K值并不理想！) * Olga Kouropteva,Oleg Okun and Matti Pietikainen. S

8、election of the optimal parameter value for the locally linear embedding algorithm,非线性降维近邻点K的选取,LLE算法的例子(2)-正常星系非线性降维求红移,基于光谱数据的K选取的方法： 同种类型的光谱按照红移的大小，在一维空间中曲线呈单调的（因为一维流形是连续光滑的），所以只要判定这种单调性就可以确定K的大小。如果K过大或者过小，其分布就不是单调的，或是有奇异点的。 单调数列定义：若x1=x2=xn=,则把xn称为递增数列；不等号反向，可定义递减数列。 程序实现：利用数值一阶差分实现。 优点：判定简单，实用性

9、较强。 （同样的方法也适用于活动星系中近邻点的确定。）,非线性降维近邻点K的选取,LLE算法的例子(2)-正常星系非线性降维求红移,非线性降维近邻点K的选取,例如：正常星系（501条光谱）特征提取后，做非线性降维时，不同k值下的一维流形。,非线性降维近邻点K的选取,利用LLE将高维空间的正常星系的数据降到一维空间，记为Yi（i=1,2,.501），数据点排列近似为一条直线，直线上的点按照红移从小到大的顺序进行排列。 如图所示，可以认为：Y=k0z+b， 推出：z=(Y-b)/k0.（参数k0,b可由图中的点估计得出。） 理论上分析，理想情况下（样本集均匀分布时），当红移范围超出模板0.5上限时

10、，仍可以根据直线公式计算出红移值。实际操作中，由于实测数据分布不均匀，只对实测数据用流形学习来分析，会造成流形不连续，而模板样本的均匀分布实际上保证了流形的连续性。,低维空间中求红移值方法1：直线拟合,LLE算法的例子(2)-正常星系非线性降维求红移,不足：但是此时近邻点近邻点的选择范围变小了，选择限制为k4是最好的。某种程度上这是个经验值。,利用LLE将高维空间的正常星系的数据降到2维空间，仍可以保持数据间的几何关系。在2维空间中我们看到的是一条曲线，曲线上的点按照红移从大到小的顺序进行排列。设在低维空间中，任意一个测试点Y，与训练集Tj (j=1,2,M)属于同一个流形，则： j=1,2M

11、. k=1,2,j-1,j+1,M. Tj 的红移值记为Zj，Tk的红移值记为Zk，Y的红移值Zy可由下面的公式求出：,低维空间中求红移值方法2：加权距离,LLE算法的例子(2)-正常星系非线性降维求红移,训练样本来自Kinney8在其文章中构造的星系的模板，选取其中的静止模板Ellipticals,s0,sa,sb做主分量分析，取方差贡献最大的第一个主分量做为正常星系模板，它代表了正常星系的四个模板中的最主要的特点。 给定红移的范围为00.5，红移模拟的步长为0.001，对模板进行红移模拟，得到各个红移值下的模拟光谱共计501条。待测红移样本来自于SDSS 数据库中02660270天区的正常

12、星系的观测数据共2373个。 其中，用直线拟合得到的红移误差0.01有130条；用加权距离得到的红移误差0.01也有130条。,实验结果,实验结果,实验结果,多维尺度变换 (MDS),MDS 是一种非监督的维数约简方法. MDS的基本思想: 约简后低维空间中任意两点间的 距离应该与它们在原始空间中的距离相同. MDS的求解: 通过适当定义准则函数来体现在低维 空间中对高维距离的重建误差, 对准则函数用梯度下 降法求解,对于某些特殊的距离可以推导出解析解法.,基于流形学习的方法ISOMAP,建立在多维尺度变换(MDS)的基础上，力求保持数据 点的内在几何性质，即保持两点间的测地距离.,等距映射(

13、Isomap)的基本思想,基于流形学习的方法ISOMAP,Isomap的前提假设,1 高维数据所在的低维流形与欧氏空间的一个子集是整体等距的. 2 与数据所在的流形等距的欧氏空间的子集是一个凸集.,基于流形学习的方法ISOMAP,估计两点间的测地距离: 1 离得很近的点间的测地距离用欧氏距离代替. 2 离得较远的点间的测地距离用最短路径来逼近.,Isomap算法的核心,基于流形学习的方法ISOMAP,测地距离估计,基于流形学习的方法ISOMAP,Isomap算法,1 计算每个点的近邻点 (用K近邻或 邻域). 2 在样本集上定义一个赋权无向图 如果 和 互为近邻点，则边的权值为 3 计算图中两

14、点间的最短距离，记所得的距离矩阵为 . 4 用MDS求低维嵌入流形 , ? 代价函数： 令 低维嵌入是 的第2小到第 d1小的特征值所对应的特征向量. 推导？,基于流形学习的方法ISOMAP,图距离逼近测地距离,M. Bernstein, V. Silva, J.C. Langford, J.B. Tenenbaum 证明了如下的渐进收敛定理. 假设采样点是依据密度函数 随机抽取的, 则 渐进收敛定理 给定 则对充分大的 , 不 等式 至少以概率 成立.,基于流形学习的方法ISOMAP,Isomap 算法的例子(1),基于流形学习的方法ISOMAP,Isomap 算法的例子(2),基于流形学习

15、的方法ISOMAP,Isomap算法的特点,Isomap是非线性的, 适用于学习内部平坦的低维流形, 不适于学习有较大内在曲率的流形 . Isomap算法中有两个待定参数K, d . Isomap算法计算图上两点间的最短距离, 执行起来比较慢 .,R,基于流形学习的方法ISOMAP,拉普拉斯特征映射(Laplacian Eigenmap),基本思想：在高维空间中离得很近的点投影到低维空间 中的象也应该离得很近. 通过使用两点间的加权距离作为损失函数，可求得相应的降维结果。 待优化的目标函数： s.t. （矩阵D提供了对图的顶点的一种自然测度，Dii越大，说明这个顶点越重要。） 求解方法：求解图

16、拉普拉斯算子的广义特征值问题.,基于流形学习的方法 Laplacian Eigenmap,Laplacian Eigenmap 算法,1 从样本点构建一个近邻图, 图的顶点为样本点，离得 很近两点用边相连 (K近邻或 邻域）. 2 给每条边赋予权值 如果第 个点和第 j 个点不相连， 权值为0，否则 (a) ; (b) 3 计算图拉普拉斯算子的广义特征向量，求得低维嵌入. 优化问题可化简为： 令D为对角矩阵 L是近邻图上的 拉普拉斯算子，求解y转为求广义特征值问题 最小特征值对应的特征向量。(由Rayleittz-Riz定理),（*）,基于流形学习的方法 Laplacian Eigenmap,

17、拉普拉斯算子,设 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,Lapla

18、cian Eigenmap算法的特点,算法是局部的非线性方法. 算法与谱图理论有很紧密的联系. 算法中有两个参数 k,d. 算法通过求解稀疏矩阵的特征值问题解析地求出整体最优解. 算法使原空间中离得很近的点在低维空间也离得很近, 可以用于聚类.,基于流形学习的方法 Laplacian Eigenmap,LLE, Isomap, Laplacian Eigenmap 有效的原因,1 它们都是非参数的方法，不需要对流形的很多的参数假设. 2 它们是非线性的方法，都基于流形的内在几何结构，更能体现现实中数据的本质. 3 它们的求解简单，都转化为求解特征值问题，而不需要用迭代算法.,流形学习问题探讨1,1 对嵌入映