流形学习简介

流形学习简介许馨2004.9设是一个低维流形，是一个光滑嵌入,其中Dd.数据集是随机生成的，且经过f映射为观察空间的数据流形学习就是在给定观察样本集的条件下重构f和.V.deSilvaandJ.B.Tenenbaum.Globalversuslocalmethodsinnonlineardimensionalityreduction.NeuralInformationProcessingSystems15(NIPS'2002),pp.705-712,2003.dRYDRYf:}{iy)}.({iiyfx}{ix}{iy流形学习的定义几种流形学习算法•局部线性嵌入(LLE).S.T.RoweisandL.K.Saul.Nonlineardimensionalityreductionbylocallylinearembedding.Science,vol.290,pp.2323--2326,2000.•等距映射(Isomap).J.B.Tenenbaum,V.deSilva,andJ.C.Langford.Aglobalgeometricframeworkfornonlineardimensionalityreduction.Science,vol.290,pp.2319--2323,2000.•拉普拉斯特征映射(LaplacianEigenmap).M.Belkin,P.Niyogi,LaplacianEigenmapsforDimensionalityReductionandDataRepresentation.NeuralComputation,Vol.15,Issue6,pp.1373–1396,2003.基于流形学习的方法－LLE（locallylinearembedding）*1.LLE算法的主要思想：对于一组具有嵌套流形的数据集，在嵌套空间与内在低维空间局部邻域间的点的关系应该不变。即在嵌套空间每个采样点可以用它的近邻点线性表示，在低维空间中保持每个邻域中的权值不变，重构原数据点,使重构误差最小.2.算法步骤：1）设D维空间中有N个数据属于同一流形，记做：Xi＝〔xi1,xi2,...,xiD〕，i=1～N。假设有足够的数据点，并且认为空间中的每一个数据点可以用它的K个近邻线性表示。求近邻点，一般采用K近邻或者邻域.2）计算权值Wij，代价函数为：，（1）并且权值要满足两个约束条件：1每一个数据点Xi都只能由它的邻近点来表示，若Xj不是近邻点，则Wij=0；2权值矩阵的每一行的和为1，即：。这样，求最优权值就是对于公式（1）在两个约束条件下求解最小二乘问题。权值体现了数据间内在的几何关系。，2()iijjjiWXWX1ijjW基于流形学习的方法－LLE（locallylinearembedding）*3）保持权值不变，在低维空间d（dD）中对原数据点重构。设低维空间的数据点为Yi，可以通过求最小的代价函数（2）来得到。公式（2）的最优解需要满足下面的约束条件：1）；2）条件1消除了Y向量平移不变的影响；条件2避免产生退化解。??由Rayleittz-Riz定理，低维嵌入是M的最小的第2到第d＋1个特征向量.去掉最小特征值0对应的特征向量。0iiY1TiiNiYYI2,,()()iijjijijjiijYYWYMYYT()()MIWIW.ijijijjikikjkMLLE算法示意图基于流形学习的方法－LLE（locallylinearembedding）*LLE算法的优点•LLE算法可以学习任意维数的低维流形.•LLE算法中的待定参数很少,K和d.•LLE算法中每个点的近邻权值在平移,旋转,伸缩变换下是保持不变的.•LLE算法有解析的整体最优解,不需迭代.•LLE算法归结为稀疏矩阵特征值计算,计算复杂度相对较小,容易执行.基于流形学习的方法－LLE（locallylinearembedding）*LLE算法的缺点•LLE算法要求所学习的流形只能是不闭合的且在局部是线性的.•LLE算法要求样本在流形上是稠密采样的.•LLE算法中的参数K,d有过多的选择.•LLE算法对样本中的噪音很敏感.•对于新样本的映射需要重新计算。R基于流形学习的方法－LLE（locallylinearembedding）*LLE算法的例子(1)基于流形学习的方法－LLE（locallylinearembedding）*K选取的原则：1近邻点K的值要大于流形的维数d；Kd会提高算法的鲁棒性；2K不能过大，对于高曲率的流形，K过大会导致不能正确表示其局部几何关系。3K过小会导致流形不连续。文献*估计K的方法是：Dx是输入空间X的欧氏距离矩阵，Dy是得到嵌入的低维流形Y的欧氏距离矩阵，是他们之间的相关系数。(实验得到的K值并不理想！！)*‘OlgaKouropteva,OlegOkunandMattiPietikainen.Selectionoftheoptimalparametervalueforthelocallylinearembeddingalgorithm’非线性降维－近邻点K的选取2argmin(1)xyDDkkLLE算法的例子(2)---正常星系非线性降维求红移基于光谱数据的K选取的方法：同种类型的光谱按照红移的大小，在一维空间中曲线呈单调的（因为一维流形是连续光滑的），所以只要判定这种单调性就可以确定K的大小。如果K过大或者过小，其分布就不是单调的，或是有奇异点的。单调数列定义：若x1=x2=…=xn=…,则把{xn}称为递增数列；不等号反向，可定义递减数列。程序实现：利用数值一阶差分实现。优点：判定简单，实用性较强。（同样的方法也适用于活动星系中近邻点的确定。）非线性降维－近邻点K的选取LLE算法的例子(2)---正常星系非线性降维求红移非线性降维－近邻点K的选取例如：正常星系（501条光谱）特征提取后，做非线性降维时，不同k值下的一维流形。非线性降维－近邻点K的选取利用LLE将高维空间的正常星系的数据降到一维空间，记为Yi（i=1,2,..501），数据点排列近似为一条直线，直线上的点按照红移从小到大的顺序进行排列。如图所示，可以认为：Y=k0z+b，推出：z=(Y-b)/k0.（参数k0,b可由图中的点估计得出。）理论上分析，理想情况下（样本集均匀分布时），当红移范围超出模板0.5上限时，仍可以根据直线公式计算出红移值。实际操作中，由于实测数据分布不均匀，只对实测数据用流形学习来分析，会造成流形不连续，而模板样本的均匀分布实际上保证了流形的连续性。低维空间中求红移值－方法1：直线拟合LLE算法的例子(2)---正常星系非线性降维求红移不足：但是此时近邻点近邻点的选择范围变小了，选择限制为k＝4是最好的。某种程度上这是个经验值。利用LLE将高维空间的正常星系的数据降到2维空间，仍可以保持数据间的几何关系。在2维空间中我们看到的是一条曲线，曲线上的点按照红移从大到小的顺序进行排列。设在低维空间中，任意一个测试点Y，与训练集Tj(j=1,2,…,M)属于同一个流形，则：j=1,2…M.k=1,2,…,j-1,j+1,…,M.Tj的红移值记为Zj，Tk的红移值记为Zk，Y的红移值Zy可由下面的公式求出：低维空间中求红移值－方法2：加权距离1minjVYT2minkVYT121212yjkVVZZZVVVVLLE算法的例子(2)---正常星系非线性降维求红移训练样本来自Kinney[8]在其文章中构造的星系的模板，选取其中的静止模板Ellipticals,s0,sa,sb做主分量分析，取方差贡献最大的第一个主分量做为正常星系模板，它代表了正常星系的四个模板中的最主要的特点。给定红移的范围为0－0.5，红移模拟的步长为0.001，对模板进行红移模拟，得到各个红移值下的模拟光谱共计501条。待测红移样本来自于SDSS数据库中0266－0270天区的正常星系的观测数据共2373个。其中，用直线拟合得到的红移误差0.01有130条；用加权距离得到的红移误差0.01也有130条。实验结果实验结果实验结果多维尺度变换(MDS)•MDS是一种非监督的维数约简方法.•MDS的基本思想:约简后低维空间中任意两点间的距离应该与它们在原始空间中的距离相同.•MDS的求解:通过适当定义准则函数来体现在低维空间中对高维距离的重建误差,对准则函数用梯度下降法求解,对于某些特殊的距离可以推导出解析解法.基于流形学习的方法－ISOMAP建立在多维尺度变换(MDS)的基础上，力求保持数据点的内在几何性质，即保持两点间的测地距离.等距映射(Isomap)的基本思想基于流形学习的方法－ISOMAPIsomap的前提假设1高维数据所在的低维流形与欧氏空间的一个子集是整体等距的.2与数据所在的流形等距的欧氏空间的子集是一个凸集.基于流形学习的方法－ISOMAP估计两点间的测地距离:1离得很近的点间的测地距离用欧氏距离代替.2离得较远的点间的测地距离用最短路径来逼近.Isomap算法的核心基于流形学习的方法－ISOMAP测地距离估计基于流形学习的方法－ISOMAPIsomap算法1计算每个点的近邻点(用K近邻或邻域).2在样本集上定义一个赋权无向图如果和互为近邻点，则边的权值为3计算图中两点间的最短距离，记所得的距离矩阵为.4用MDS求低维嵌入流形,???代价函数：令低维嵌入是的第2小到第d＋1小的特征值所对应的特征向量.推导？？).,(jidX)},({jidDGGjXiX,2/)()/1()()()(2HSHDNHHDSSijijijij，，)(D基于流形学习的方法－ISOMAP2()()GYLEDD,YYijDdijyy图距离逼近测地距离M.Bernstein,V.Silva,J.C.Langford,J.B.Tenenbaum证明了如下的渐进收敛定理.假设采样点是依据密度函数随机抽取的,则渐进收敛定理给定则对充分大的,不等式至少以概率成立.,0,,21211distancegeodesicdistancegraph11基于流形学习的方法－ISOMAPIsomap算法的例子(1)基于流形学习的方法－ISOMAPIsomap算法的例子(2)基于流形学习的方法－ISOMAPIsomap算法的特点•Isomap是非线性的,适用于学习内部平坦的低维流形,不适于学习有较大内在曲率的流形.•Isomap算法中有两个待定参数K,d.•Isomap算法计算图上两点间的最短距离,执行起来比较慢.R基于流形学习的方法－ISOMAP拉普拉斯特征映射(LaplacianEigenmap)基本思想：在高维空间中离得很近的点投影到低维空间中的象也应该离得很近.通过使用两点间的加权距离作为损失函数，可求得相应的降维结果。待优化的目标函数：s.t.（矩阵D提供了对图的顶点的一种自然测度，Dii越大，说明这个顶点越重要。）求解方法：求解图拉普拉斯算子的广义特征值问题.2minijijijyyW,TiiijjYDYIDW基于流形学习的方法－LaplacianEigenmapLaplacianEigenmap算法1从样本点构建一个近邻图,图的顶点为样本点，离得很近两点用边相连(K近邻或邻域）.2给每条边赋予权值如果第个点和第j个点不相连，权值为0，否则(a);(b)3计算图拉普拉斯算子的广义特征向量，求得低维嵌入.优化问题可化简为：令D为对角矩阵L是近邻图上的拉普拉斯算子，求解y转为求广义特征值问题最小特征值对应的特征向量。(由Rayleittz-Riz定理)i1ijW.,2为热核参数teWtXXijji,,WDLWDjjiii.LyDymin..TyTargtrYLYstYDYI（*）基于流形学习的方法－LaplacianEigenmap拉普拉斯算子设M是光滑的