模式识别课件 流形学习

流形学习流行学习NonlinearMethodsIsomap，laplacianeigenmap(LE)locallinearembedding(LLE)LinearMethodsIsometricProjection，LPP，NPE，

UDP,2DLPP,tensorLPP,tensorNPE假定：数据的内在特征都嵌入在低维非线性流形面上几种非线性流形学习算法

局部线性嵌入(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）LLE算法的主要思想：对于一组具有嵌套流形的数据集，在嵌套空间与内在低维空间局部邻域间的点的关系应该保持不变。即在嵌套空间每个采样点可以用它的近邻点线性表示，在低维空间中保持每个邻域中的权值不变，重构原数据点,使重构误差最小.LLE算法示意图LLE（locallylinearembeddingLLE（locallylinearembedding）2.算法步骤：1）设D维空间中有N个数据属于同一流形，记做：Xi＝〔xi1,xi2,...,xiD〕，i=1～N。假设有足够的数据点，并且认为空间中的每一个数据点可以用它的K个近邻线性表示。求近邻点，一般采用K近邻或者邻域.2）计算权值Wij，代价函数为：，（1）并且权值要满足两个约束条件：<1>每一个数据点Xi都只能由它的邻近点来表示，若Xj不是近邻点，则Wij=0；<2>权值矩阵的每一行的和为1，即：。这样，求最优权值就是对于公式（1）在两个约束条件下求解最小二乘问题。权值体现了数据间内在的几何关系。

LLE（locallylinearembedding）3）保持权值不变，在低维空间d（d<<D）中对原数据点重构。设低维空间的数据点为Yi，可以通过求最小的代价函数

最优解需要满足下面的约束条件：

条件1消除了Y向量平移不变的影响；条件2避免产生退化解。LLE

由Rayleittz-Riz定理，低维嵌入是M的最小的第2到第d＋1个特征向量.去掉最小特征值0对应的特征向量。LLE算法的优点LLE算法可以学习任意维数的低维流形.LLE算法中的待定参数很少,K和d.LLE算法中每个点的近邻权值在平移,旋转,伸缩变换下是保持不变的.LLE算法有解析的整体最优解,不需迭代.LLE算法归结为稀疏矩阵特征值计算,计算复杂度相对较小,容易执行.LLE算法的缺点LLE算法要求所学习的流形只能是不闭合的且在局部是线性的.LLE算法要求样本在流形上是稠密采样的.LLE算法中的参数K,d有过多的选择.LLE算法对样本中的噪音很敏感.对于新样本的映射需要重新计算。RReferencesS.T.RoweisandL.K.Saul.Nonlineardimensionalityreductionbylocallylinearembedding.Science,vol.290,pp.2323--2326,2000.OlgaKouropteva,OlegOkunandMattiPietikainen.Selectionoftheoptimalparametervalueforthelocallylinearembeddingalgorithm,PatternRecognitionLetetrs,2006,968-979-------多维尺度变换(MDS)MDS是一种非监督的维数约简方法.MDS的基本思想:约简后低维空间中任意两点间的距离应该与它们在原始空间中的距离相同.MDS的求解:通过适当定义准则函数来体现在低维空间中对高维距离的重建误差,对准则函数用梯度下降法求解,对于某些特殊的距离可以推导出解析解法.ISOMAP建立在多维尺度变换(MDS)的基础上，力求保持数据点的内在几何性质，即保持两点间的测地距离.等距映射(Isomap)的基本思想ISOMAP1高维数据所在的低维流形与欧氏空间的一个子集是整体等距的.2与数据所在的流形等距的欧氏空间的子集是一个凸集.Isomap的前提假设估计两点间的测地距离:

1离得很近的点间的测地距离用欧氏距离代替.2离得较远的点间的测地距离用最短路径来逼近.Isomap算法的核心ISOMAP测地距离估计ISOMAPIsomap算法1计算每个点的近邻点(用K近邻或邻域).2在样本集上定义一个赋权无向图如果和互为近邻点，则边的权值为3计算图中两点间的最短距离，记所得的距离矩阵为4用MDS求低维嵌入流形,???代价函数：令低维嵌入是

的第2小到第d＋1小的特征值所对应的特征向量.（推导）Isomap算法的特点Isomap是非线性的,适用于学习内部平坦的低维流形,不适于学习有较大内在曲率的流形.Isomap算法中有两个待定参数K,d.Isomap算法计算图上两点间的最短距离,执行起来比较慢.RISOMAP拉普拉斯特征映射(LaplacianEigenmap)

基本思想：在高维空间中离得很近的点投影到低维空间中的象也应该离得很近.通过使用两点间的加权距离作为损失函数，可求得相应的降维结果。待优化的目标函数：

s.t.（矩阵D提供了对图的顶点的一种自然测度，Dii越大，说明这个顶点越重要。）求解方法：求解图拉普拉斯算子的广义特征值问题.示意图LaplacianEigenmap算法1从样本点构建一个近邻图,图的顶点为样本点，离得很近两点用边相连(K近邻或邻域）.2给每条边赋予权值如果第

个点和第j个点不相连，权值为0，否则(a);(b)LaplacianEigenmap算法3计算图拉普拉斯算子的广义特征向量，求得低维嵌入.优化问题可化简为：令D为对角矩阵L是近邻图上的拉普拉斯算子，求解y转为求广义特征值问题

最小特征值对应的特征向量。(由Rayleittz-Riz定理)

LaplacianEigenmap算法的特点

算法是局部的非线性方法.

算法与谱图理论有很紧密的联系.

算法中有两个参数k,d.

算法通过求解稀疏矩阵的特征值问题解析地求出整体最优解.

算法使原空间中离得很近的点在低维空间也离得很近,可以用于聚类.

LLE,Isomap,LaplacianEigenmap有效的原因1它们都是非参数的方法，不需要对流形的很多的参数假设.2它们是非线性的方法，都基于流形的内在几何结构，更能体现现实中数据的本质.3它们的求解简单，都转化为求解特征值问题，而不需要用迭代算法.流形学习问题探讨11对嵌入映射或者低维流形作出某种特定的假设,或者以保持高维数据的某种性质不变为目标.2将问题转化为求解优化问题.3提供有效的算法.

为流形学习提供更为坚实和易于接受的认知基础.

如何确定低维目标空间的维数.

当采样数据很稀疏时,怎样进行有效的学习.

将统计学习理论引入流形学习对其泛化性能进行研究.流形学习问题探讨2流形学习问题探讨3

流形学习作为一种非线性降维或数据可视化的方法已经在图像处理如人脸图像,手写数字图像,语言处理方面取得了较好的效果.

将其作为一种监督的学习方法用于模式识别,虽然有研究者涉足,但是目前在这方面的工作还很有限.几种线性流行学方法LPPX.He,S.Yan,Y.Hu,P.Niyogi,andH.Zhang.FaceRecognitionUsingLaplacianfaces.IEEETrans.PAMI,27(3):328-340,2005.NPEX.He,D.Cai,S.Yan,andH.Zhang.NeighborhoodPreservingEmbedding.ProceedingoftheTenthIEEEInternationalConferenceonComputerVision,2005IsomatricProjectionD.Cai,X.He,andJ.Han.IsometricProjection.AssociationfortheAdvancementofArtificialIntelligence,2007局部保持投影

LocalityPreservingProjection(LPP)局部保持投影目标函数：

其中是一个权重矩阵，定义如下：通过简单的推算得到：

局部保持投影

这里