《机器学习：流形学习》由会员分享，可在线阅读，更多相关《机器学习：流形学习（47页珍藏版）》请在金锄头文库上搜索。
1、流形学习流形学习流形学习的基本概念尽可能应用少的数学概念来解释。所谓流形流形（manifold）就是一般的几何对象的总称。流形流形包括各种维数的曲线曲面等。和一般的降维分析一样，流形学习流形学习把一组在高维空间中的数据在低维空间中重新表示。和以往方法不同的是，在流形学习流形学习中有一个假设，就是所处理的数据采样于一个潜在的流形流形上，或是说对于这组数据存在一个潜在的流形流形。ISOMAP LLE 降维重要的一步，也是观察数据特性的手段降维特征选择:依据某一标准选择性质最突出的特征特征变换:经已有特征的某种变换获取约简特征数据可视化和数据挖掘分析也需要降维通常降到2维或3维流形降维来观测数据的内
2、在形状LinearMethod:(PCA)PCA的目的：寻找能够表示采样数据的最好的投影子的目的：寻找能够表示采样数据的最好的投影子空间空间.PCA的求解：对样本的协方差矩阵进行特征值分解的求解：对样本的协方差矩阵进行特征值分解, 所求子空间为过样本均值所求子空间为过样本均值, 以最大特征值所对应的特征以最大特征值所对应的特征向量为方向的子空间向量为方向的子空间.PrincipalcomponentLinearMethod:(LDA)LDA的思想的思想: 寻找最能把两类样本分开的投影方向寻找最能把两类样本分开的投影方向.LDA的目标的目标: 使投影后两类样本的均值之差与投影样使投影后两类样本的
3、均值之差与投影样本的总类散布的比值最大本的总类散布的比值最大 . Multiple discriminant analysis (MDA) 把 LDA 扩展到多类分类器的最佳投影方向线性方法的不足数据特征并不具备简单性例如: PCA 不能发现螺旋型数据，适合高斯分布KPCA或许能解决主曲线问题，但曲面，立体？Example64X64 Input Images form4096-dimensional vectorsIntrinsically, three dimensions is enough for presentations Two pose parameters and lightin
4、g angle何谓流形?能够展开成低维形状的几何结构一根麻绳的例子从 1D 曲线和 2D 曲面产生比较繁琐的数学定义ManifoldNon-manifold流形学习从大量的数据中发现流形和应用流形的过程从大量的数据中发现流形和应用流形的过程 流形学习是一种非线性的维数约简方法流形学习是一种非线性的维数约简方法.流形是线性子空间的一种非线性推广流形是线性子空间的一种非线性推广. 流形是一个局部可坐标化的拓扑空间流形是一个局部可坐标化的拓扑空间.特征的低维可视特征的低维可视局部坐标化Mx1x2R2Rnzxx:coordinateforzy1 许多高维采样数据都是由少数几个隐含变量所决定许多高维采样
5、数据都是由少数几个隐含变量所决定的的, 如人脸采样由光线亮度如人脸采样由光线亮度, 人离相机的距离人离相机的距离, 人的头人的头部姿势部姿势, 人的脸部肌肉等因素决定人的脸部肌肉等因素决定.2 从认知心理学的角度从认知心理学的角度, 心理学家认为人的认知过程心理学家认为人的认知过程是基于认知流形和拓扑连续性的是基于认知流形和拓扑连续性的.R流形学习的可行性流形学习的可行性 局部线性嵌入局部线性嵌入(LLE).S. T. Roweis and L. K. Saul. Nonlinear dimensionality reduction by locally linear embedding. S
6、cience, 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. 拉普拉斯特征映射(LaplacianEigenmap).M. Belkin, P. Niyogi, Laplacian Eigenmaps for Dimensionali
7、ty Reduction and Data Representation. Neural Computation, Vol. 15, Issue 6, pp.13731396, 2003 .几种流形学习方法几种流形学习方法 Tenenbaum根本不是做与数据处理有关算法的人，他是做计算认知科根本不是做与数据处理有关算法的人，他是做计算认知科 学（学（computational cognition science）的。在做这个方法的时候，他还）的。在做这个方法的时候，他还在在stanford，2年就去了年就去了MIT开创一派，成了开创一派，成了CoCoSci 的掌门人，他的的掌门人，他的组成长十
8、分迅速。但是有趣的组成长十分迅速。但是有趣的 ,在在Isomap之后，他包括他在之后，他包括他在MIT带的学带的学生就从来再也没有做过类似的工作。生就从来再也没有做过类似的工作。他在今年参加他在今年参加 UCLA Alan Yuille 组织的一个组织的一个summer school上说，我们上说，我们经常忘了做研究的原始出发点是什么。他做经常忘了做研究的原始出发点是什么。他做Isomap就是为了找一个好就是为了找一个好的的visual perception的方法，他还坚持了他的方向和信仰，的方法，他还坚持了他的方向和信仰，computational cognition，他没有随波逐流。，他没
9、有随波逐流。而由他引导起来的而由他引导起来的 manifold learning 却快速的发展成了一个新的方向。却快速的发展成了一个新的方向。 J.B. Tenenbaum1.建立在多维尺度变换建立在多维尺度变换(MDS)的基础的基础上上, 力求保持数据力求保持数据2.前提假设：点的内在几何性质前提假设：点的内在几何性质, 即即保持两点间的测地距离保持两点间的测地距离.3.估计两点间的测地距离估计两点间的测地距离: 1 离得很近的点间的测地距离用离得很近的点间的测地距离用欧氏距离代替欧氏距离代替. 2 离得较远的点间的测地距离用离得较远的点间的测地距离用最短路径来逼近最短路径来逼近.epsho
10、rt-circuit edgeacbfdghIsomap的基本思想的基本思想中国科学院自动化研究所多维尺度变换(MDS)MDS是一种非监督的维数约简方法.MDS的基本思想:约简后低维空间中任意两点间的距离应该与它们在原高维空间中的距离相同.MDS的求解:通过适当定义准则函数来体现在低维空间中对高维距离的重建误差,对准则函数用梯度下降法求解,对于某些特殊的距离可以推导出解析解法.中国科学院自动化研究所MDS的准则函数Linear Approach- classical MDSMDS:MultidimensionalscalingBorgandGroenen,1997MDStakesamatrix
11、ofpairwisedistancesandgivesamappingtoRd.Itfindsanembeddingthatpreservestheinterpointdistances,equivalenttoPCAwhenthosedistanceareEuclidean.LowdimensionaldataforvisualizationLinear Approach- classical MDSExample:Linear Approach- classical MDSLinear Approach- classical MDSLinear Approach- classical MD
12、SLinear Approach- classical MDSSo far, we focus on classical MDS, assuming D is the squared distance matrix.Metric scalingHow to deal with more general dissimilarity measuresNon-metric scaling Solutions:(1)Addalargeconstanttoitsdiagonal.(2)Finditsnearestpositivesemi-definitematrixbysettingallnegativ
13、eeigenvaluestozero.Nonlinear Dimensionality Reduction Many data sets contain essential nonlinear structures that invisible to PCA and MDSResorts to some nonlinear dimensionality reduction approaches.Kernel methodsDepend on the kernelsMost kernels are not data dependentNonlinear Approaches- IsomapCon
14、structing neighbourhood graph GFor each pair of points in G, Computing shortest path distances - geodesic distances.Use Classical MDS with geodesic distances. Euclidean distance Geodesic distanceJosh.Tenenbaum,VindeSilva,Johnlangford2000Sample points with Swiss RollAltogether there are 20,000 points
15、 in the “Swiss roll” data set. We sample 1000 out of 20,000.Construct neighborhood graph GK- nearest neighborhood (K=7)DG is 1000 by 1000 (Euclidean) distance matrix of two neighbors (figure A)Compute all-points shortest path in GNow DG is 1000 by 1000 geodesic distance matrix of two arbitrary point
16、s along the manifold (figure B)Findad-dimensionalEuclideanspaceY(Figurec)topreservethepariwisediatances.Use MDS to embed graph in RdThe Isomap algorithmNonlinearGloballyoptimalStillproducesgloballyoptimallow-dimensionalEuclideanrepresentationeventhoughinputspaceishighlyfolded,twisted,orcurved.Guaran
17、teeasymptoticallytorecoverthetruedimensionality.Isomap: AdvantagesMaynotbestable,dependentontopologyofdataGuaranteedasymptoticallytorecovergeometricstructureofnonlinearmanifoldsAsNincreases,pairwisedistancesprovidebetterapproximationstogeodesics,butcostmorecomputationIfNissmall,geodesicdistanceswill
18、beveryinaccurate.Isomap: DisadvantagesApplicationsIsomap and Nonparametric Models of Image DeformationLLE and Isomap Analysis of Spectra and Colour ImagesImage Spaces and Video Trajectories: Using Isomap to Explore Video SequencesMining the structural knowledge of high-dimensional medical data using
19、 isomap IsomapWebpage:http:/isomap.stanford.edu/Example64X64 Input Images form4096-dimensional vectorsIntrinsically, three dimensions is enough for presentations Two pose parameters and lighting angleExamplesInterpolations between distant points in the low-dimensional coordinate space.SummaryIsomap
20、handles non-linear manifoldIsomap keeps the advantages of PCA and MDSNon-iterative procedurePolynomial procedureGuaranteed convergenceIsomap represents the global structure of a data set within a single coordinate system.前提假设：采样数据所在的低维流形在局部是线性的前提假设：采样数据所在的低维流形在局部是线性的,即每个采样点可以用它的近邻点线性表示即每个采样点可以用它的近邻点
21、线性表示.学习目标：在低维空间中保持每个邻域中的权值不变学习目标：在低维空间中保持每个邻域中的权值不变, 即假设嵌入映射在局部是线性的条件下即假设嵌入映射在局部是线性的条件下, 最小化重构误最小化重构误差差.局部线性嵌入局部线性嵌入(LLE)LLELocallyLinearEmbeddings模型:Locally Linear Embeddings算法:基于矩阵特征值求解的优化技术LLE模型拓扑学流形样本（特征）在高维空间具有低维流形嵌入LLE策略（1）假设即策略假设即策略采样数据所在的低维流形在采样数据所在的低维流形在局部是线性的局部是线性的,即每个采样即每个采样点可以用它的近邻点线性表点可
22、以用它的近邻点线性表示示.在低维空间中保持每个邻域在低维空间中保持每个邻域中的权值不变。中的权值不变。LLE策略（2）:最小化重构误差最小化重构误差.1 计算每一个点计算每一个点 的近邻点的近邻点, 一般采用一般采用K 近邻或者近邻或者 邻域邻域.2 计算权值计算权值 使得把使得把 用它的用它的K个近邻点线性表示个近邻点线性表示的误差最小的误差最小, 即通过最小化即通过最小化 来求出来求出 .3 保持权值保持权值 不变不变, 求求 在低维空间的象在低维空间的象 , 使使得低维重构误差最小得低维重构误差最小.LLE算法1 计算每一个点计算每一个点 的近邻点的近邻点.2 对于点对于点 和它的近邻点
23、的权值和它的近邻点的权值 , 3 令令 , 低维嵌入低维嵌入是是 M 的最小的第的最小的第 2到第到第 d1 个特征向量个特征向量. 它们都是非参数的方法它们都是非参数的方法, 不需要对流形的很多的参数假设不需要对流形的很多的参数假设.它们是非线性的方法它们是非线性的方法, 都基于流形的内在几何结构都基于流形的内在几何结构, 更能体现更能体现现实中数据的本质现实中数据的本质.它们的求解简单它们的求解简单, 都转化为求解特征值问题都转化为求解特征值问题, 而不需要用迭代而不需要用迭代算法算法.比较Applications(1)Applications(4)Manifold for Recogni
24、tion对嵌入映射或者低维流形作出某种特定的假设对嵌入映射或者低维流形作出某种特定的假设, 或者以或者以保持高维数据的某种性质不变为目标保持高维数据的某种性质不变为目标.流形是将空间进行变换以观察特征流形是将空间进行变换以观察特征将问题转化为求解优化问题将问题转化为求解优化问题.Discussion(1) 流形学习作为一种非线性降维或数据可视化的方法流形学习作为一种非线性降维或数据可视化的方法已经在图像处理如人脸图像已经在图像处理如人脸图像,手写数字图像手写数字图像, 语言处理语言处理方面得了利用方面得了利用. 将其作为一种监督的学习方法用于模式识别将其作为一种监督的学习方法用于模式识别, 虽然虽然有研究者涉足有研究者涉足, 但是目前在这方面的工作还很有限但是目前在这方面的工作还很有限.Discussion(2)发现一个问题或者掌握工具解决一个好的问题，是成功的捷径！数学最重要的工具！勤奋比数学还重要！Luck is what happens when preparation meets opportunityTheEndThank YouThank You！
