基于谱图理论的流形学习算法

计算机研究与发展 JournalofComputerResearchandDevelopment ISSN1000—1239／CN11—1777／TP 43(7)：1173～1179，2006 基于谱图理论的流形学习算法 罗四维 赵连伟 (北京交通大学计算机与信息技术学院北京 100044) (swluo@center．njtu．edu．cn) ManifoldLearningAlgorithmsBasedonSpectralGraphTheory LuoSiweiandZhao“anwei (Sc^00￡q厂Gompt‘抛randf规如r僦￡io托仡^nozogy，Be巧ingJ洳￡o札gU心i曰Prsi￡3，，嘲i扎g100044) AbstractIntheproblemofmanifoldlearning，oneseekstofinda smoothlow-dimensionalmanifold embeddedinthehigh—dimensionalvectorspace，basedonasetofsamplepoints．Spectralgraphtheory studiestheeigenvectorsandeigenvaluesofmat“cesassociatedwithgraphsandhasbeenwidelyusedinthe manifoldlearningalgo“thmrecently．Inthispaper，therelationshipbetweenthemanifoldandthemanifold learningisintroducedfirst，andthensometypicalmanifoldlearningalgorithmsbasedonspectralgraph theoryarestudied．FinaUy，somedirectionsforfurtherresearcharesuggested． Keywordsmanifoldlearning；spectralgraphtheory；localtangentspace；randomwalk；eigenmaps 摘要流形学习的主要目标是发现嵌入在高维数据空间的低维光滑流形．近年来基于谱图理论的学 习算法受到研究者的广泛关注．介绍了流形与流形学习的关系，着重研究了几种有代 表 关于同志近三年现实表现材料材料类招标技术评分表图表与交易pdf视力表打印pdf用图表说话 pdf 性的基于谱图 理论的流形学习算法，并对算法进行了比较分析，最后进行 总结 初级经济法重点总结下载党员个人总结TXt高中句型全总结.doc高中句型全总结.doc理论力学知识点总结pdf 和对进一步的研究做了展望． 关键词流形学习；谱图理论；局部切空间；随机游走；特征映射 中图法分类号TPl8 1 引 言 近年来，神经科学的研究取得很多重大发展． 越来越多的研究表明，视感知系统响应具有的某种 不变性与连续变化信号本身蕴涵的不变性非常一致． 研究还发现整个神经细胞群的触发率可以由少量变 量组成的函数描述，如眼的角度和头的方向，这表明 神经元的群体活动性是由外界刺激的内在低维结构 所控制．Seung等人认为感知可能以流形方式存 在uJ，视觉记忆也可能是以稳态的流形存储，而在 理解人脑中感知如何从神经网络动力学产生，流形 可能是至关重要的． 能够从相对少量的数据中学习到有效的知识是 人类智能的一个重要特性，理解人类的感知过程无 疑是科学界最令人关注的问题之一．流形是微分几 何中的一个基本概念．20世纪微分几何得到高速发 展，几何和拓扑的研究 方法 快递客服问题件处理详细方法山木方法pdf计算方法pdf华与华方法下载八字理论方法下载 也逐渐形成和完善，同时 也愈加广泛应用在其他学科中，神经科学中用流形 方法研究人类感知就是典型的一个应用．微分几何 学为研究感知流形的形成及其性质提供了坚实的数 学理论基础，几何和拓扑的研究方法为研究感知流 形提供了新的思路． 如果把外界的感知表示为高维空间上的点集， 而这些感知输入可能会有较强的相关性，可能会在 一个低维流形上，或在低维流形的附近。人能够从 收稿日期：2005—0519；修回日期：2006—0222 基金项目：国家自然科学基金项目(60373029)；国家教育部博士学科点基金项目(20050004001)；北京市重点学科共建基金项目(Ⅺ(100040415) 万方数据 计算机研究与发展2006，43(7) 外界的刺激感知到这些固有的低维流形，研究和模 拟人的这种感知能力，即从有限样本数据中学习到 潜在流形的问题，成为众多计算机科学家的研究 目标． 2流形与流形学习 微分几何中首先对M上每一点的无穷小邻域 定义与Euclid空间某个开集的微分同胚，加上这些 邻域的连接信息组成微分结构，M连同这个微分结 构称为流形．严格的流形定义参见文献[2]．简单的 说一个流形就是一个拓扑空间，它在局部上是欧氏 的．若在保留流形拓扑或连接特性的条件下把M 表示在某种空间中，这样的表示称为嵌入．从流形 的定义可以看出，流形最基本的一个性质就是可以 在局部上建立与Euclid空间的微分同胚，并借以研 究流形的全局性质．虽然在许多情形下传统的实数 或复数空间是最重要的情形，但是在微分几何中只 可以看做是局部的情形． 几何上研究的通常是连续可微的流形，而实际 问题中，对象通常给定的是高维观测数据集，数据变 量可以用少量几个影响因素来表示，这种现象在几 何学上表现为样本点散布在低维流形上，或者是在 低维流形附近．而要有效揭示数据潜在的几何结 构，需要根据有限的离散样本数据学习和发现嵌入 在高维空间中的低维光滑流形，这就是流形学习的 主要目标． 流形学习问题的数学描述：给定高维观测数据 集x={工】，x2，⋯，工N}，其中工i∈RD，为独立同分 布的随机样本，散布在光滑的d维流形M[RD上， 即M为嵌入在D维欧氏空间中d维流形，定义嵌 入映射厂：McRD—R4，这里d《D．流形学习是在 没有任何关于M和d的先验知识的条件下，根据 有限的观测数据集x发现未知嵌入映射．厂(·)，且找 到与高维观测数据一一对应的低维嵌入l，={y】， j，2，⋯，J，N}，yi∈Rd． 流形学习算法的主要思想：①由局部到整体的 思想．根据流形的定义，流形在局部上可以看做是 欧氏的，研究中通常首先在局部建立坐标卡，然后用 对每个局部的坐标卡进行整合，进而得到全局低维 嵌入．②由离散逼近连续的思想．对于给定的离散样 本，要得到连续可微流形的性质，必须通过逼近方法． 本文主要对基于谱图理论的流形学习算法进行研究． 3基于谱图理论的流形学习 谱方法是数学领域里一种经典的分析和代数方 法，在高维数据的低维表示和聚类问题¨’4j中有着 广泛的应用．算法首先根据给定的样本数据集定义 一个描述成对数据点相似度的关系矩阵，并计算此 矩阵的特征值和特征向量；然后选择合适的特征向 量，投影得到数据的低维嵌入．如果相似度矩阵定 义在一个给定的图上，比如为图上的邻接矩阵、 Laplacian矩阵等，则称为谱图方法．谱图理论¨J通 过研究根据图定义的矩阵的谱，进一步研究图中包 含的信息，并通过几何、分析和代数的技术在离散空 间和连续空间之间建立了联系． 一个图G=(V，E)包含有两个集合：v为顶点 集合，E为边的集合．对于取样自d维流形上的样 本数据集x，首先在数据点和图G的顶点之间建立 一一对应，并定义成对数据点的相似度为图中的边， 这样就根据数据点建立了一个与之对应的图．图和 流形有很多相近的性质，最重要的一点就是都可以 嵌入到Euclid空间，所以很多研究人员都使用图的 方法逼近流形，并利用图的理论求解低维嵌入．对 于流形来说，一个与之对应的图就是一个拓扑对象， 其拓扑性质通过边的权值表现．如果数据集足够 大，噪声较小，合理定义图中边的权值可以充分逼近 嵌入流形． 谱图理论在流形学习中有着广泛的应用，本文 根据成对数据点之间相似度的定义方法把基于谱图 理论的方法分为两类：一是基于全局的方法，即计算 每一个数据点与所有其他数据点的关系，即建立全 连接图．二是基于局部的方法，即考虑每一个数据 点与它邻域内的点的关系，如忌近邻或e邻域方法 定义图中的边． 3．1基于全局的方法 3．1．1 PCA，KernelPCA和主曲线 处理高维数据的经典方法是采用线性方法进行 降维，线性组合容易计算，且能够进行解析分析．主 成分分析(PCA)在全局最小重构误差的意义下把高 维观察数据投影到低维主子空间上，而数据点协方 差矩阵最大几个特征值所对应的特征向量生成的子 空间正好满足这个条件．PcA是一种理论完善且在 算法上可行的线性降维方法，也是最为经典方法之 一，但是其有效性建立在假设数据嵌入在全局线性 或近似线性的低维子流形上． 万方数据 罗四维等：基于谱图理论的流形学习算法 1175 KernelPCAMl是PCA的非线性推广，主要思想 是把输人数据x经由一个非线性映射垂(工)映射到 特征空间F，然后在特征空间F执行线性PCA． KernelPCA对于特征空间中特征值和向量在特征 空间上投影的计算都不要求映射西(x)有显式的形 式，而只需要计算映射的点积，实际中点积可以由核 函数计算．KernelPCA的非线性是通过核变换把输 入空间变换到Hilbert特征空间来实现的，所以可以 说PCA是在输入空间上的计算，KernelPCA则是 在特征空间上的计算．Hastie和Stuetzle【7J提出的主 曲线在统计学上定义为满足自相合特性的曲线，是 第一主成分的非线性推广．有关主曲线算法大多不 是基于谱的方法，本文不做详细论述，更详细的论述 参见文献[8，9]． 3．1．2MDS和Isomap PCA、主曲线(面)等都是把高维空间的数据点 映射到一个低维流形空间中，而在一些应用中可能 没有可以利用的数据点坐标，只有这些数据点的某 种相似度关系．多维尺度分析(MDs)¨钊就是根据 数据间的相似度(可以为距离)组成关系矩阵，并利 用求解关系矩阵的谱，寻找数据在低维空间中的投 影，借此尽可能地保留每对观测之间的相似性关系． MDS保留的是直线距离，所以只能发现线性结 构，Tenenbaum等提出的Isomap算法111，12J首先计 算流形上的测地线距离，然后应用MDs算法，发现 嵌入在高维空间的低维流形，这样Isomap就通过数 据间的测地线距离，保留了数据固有的非线性几何 结构．其主要思想是通过在输入空间与参数空间建 立等距映射，保持测地线距离不变，以进一步研究流 形上的全局几何结构．Donoho等人u3J用人工合成 的数据用Isomap算法进行测试实验，实验结果表明 Isomap能够准确地发现图像流形潜在的参数空间， 并在自然图像的实验中得到较好的结果．标准 ISomap算法共有3步： Stepl．构建邻接图，距离定义为Euclid距离 d。(i，j)，邻接关系定义为￡球或志最近邻． Step2．通过计算图G上两点间的最短路径 dG(i，J)估计流形M上测地线距离dM(i，J)，得到 的矩阵D(；={dG(i，j)}为图G上任意两点间的最 短路径距离． Step3．应用MDS算法，构建d维Euclid空间 l，上的嵌入． 文献[14]提出通过在输入空间与参数空间之间 建立共形映射的方法——C—Isomap，保留各个局部 之间的连接信息．C—ISomap与Isomap主要区别在 于在局部邻域上采用的距离为一种平均距离． 3．2基于局部的方法 3．2．1局部线性嵌入(LLE) LLE[15，16]认为流形上每一个局部邻域内的任 意一点都可以描述为邻域内其他点的线性表示，各 个邻域之间的连接信息也可以通过相互重叠的部分 得以描述，而这个线性关系在映射时保持不变，这样 即可以把输人数据映射到统一的一个全局低维坐标 系统，并保留邻接特性．通过利用线性重构的局部 对称性质，LLE能够学习非线性流形的全局结构， 比如从人脸和文本图像中学习到有意义的特性、人 脸姿态和文本语义关联等．另外LLE算法还具有旋 转、尺度和平移不变性，最优化过程也不包含局部极 小，算法中的可变参数较少．LLE算法的具体 步骤 新产品开发流程的步骤课题研究的五个步骤成本核算步骤微型课题研究步骤数控铣床操作步骤 如下： Stepl．使用忌近邻方法为每一个数据点xi分 配近邻； Step2．计算根据xi近邻线性重构工i的权值 wi，使得min￡(w)=∑lxi一∑wi马I2； l J Step3．通过求稀疏对称矩阵Mi，=、瓯i—wi，一 wji+∑眠i岷的最小特征值，最小化西(y)= ^ ∑l咒一∑w鹕I2，计算由w巧最优重构的低维 2 J 嵌入向量咒． 清华大学张长水等人¨7J在LLE的基础上提出 一个从低维嵌入空间向高维空间的映射方法，并在 多姿态人脸图像的重构实验中得到验证． 3．2．2局部切空间整合算法(LTSA) 对于非线性流形来说，全局的非线性结构来自 于局部线性分析和局部线性信息的全局整合，根据 这个思想浙江大学张振跃等人提出局部切空间整合 算法(LTSA)[18，19。．算法假定待定的参数表示函数 厂为正则的，则．厂在点f的切空间r可以由厂在f 的Jacobi矩阵J，(f)的d个列向量张成．由于函数 未知，并不能显式地计算Jacobi矩阵，但是可以利用 厂(f)在某个邻域点集来逼近其切空间，由厂(亏)一 厂(f)向T7的正交投影的局部坐标口(f)逼近其真 实局部坐标9，再利用仿射变换L，将局部坐标D整 合到厂的全局坐标f．对于给定的高维数据集x， LTSA算法基本步骤如下： Stepl．局部近邻选取．对于样本点xi，选取包 含鼍本身在内的愚个近邻； 万方数据 1176 计算机研究与发展2006，43(7) Step2．局部线性拟合．计算点xi处d维切空 间的正交基Qi和每一个x甜在切空间上的正交投 影：o；=Qj’(x“一ji)，这里牙i为忌个近邻的均值． Step3．局部坐标整合．根据咒个局部投影Di= [oj，⋯，吠]，整合得到全局坐标{％}冬1．对于所有 的Li∈R4“4和T=[f1，⋯，f。]，fi=[fil，⋯，f浊]， 通过最小化全局重构误差得到全局坐标： ∑№JK=∑№(J一知T)一L；Di忆 。。Z 上述最小化问题能够等价地转化为一个求特征 值的简单问题． 浙江大学王靖等人提出一种自适应的局部切空 间整合算法(AdaptiveLTSA)[20|，算法能够自适应 地选择近邻的个数，局部空间整合时考虑了流形曲 率和数据集取样密度的变化对算法的影响，所以能 够更好地拟合局部几何结构． 在VQPCA和LTSA算法的基础上，中国科学 院自动化研究所杨剑、王珏等人提出一种改进的局 部切空间排列算法(PLTSA)幢1|．算法利用x一均值 算法把样本空间划分成一些相互有重叠的块，通过 把样本点投影到它所在块的局部切空间上得到局部 低维坐标，对局部低维坐标施加变换，求出整体低维 坐标．PLTSA解决了LTSA中大规模矩阵的特征 值分解问题，且能够有效处理新样本． Brand提出的建立流形坐标卡算法(chartinga manifold)怛2J的基本思想也是使用局部坐标卡覆盖 流形．它把流形学习看做是密度估计问题，首先根 据样本估计流形固有维数，然后用软划分的方法把 样本数据集分解为局部线性低维近邻，建立局部坐 标卡，最后根据仿射变换的方法，连接坐标卡为一个 统一的坐标系统，进而得到样本和坐标空间之间的 映射和逆映射． 3．2．3Laplacian特征映射 Belkin和Niyogi提出的Laplacian特征映射算 法[23'24]是为找到一个在平均意义上保留数据点局 部特性的映射，即最小化问题：L(，)=寺∑(工一厶 i，J ．^)2W¨其中L表示LaplacianBeltrami算子．L 是半正定的，这样问题可转化为求L的特征函数问 题．而根据谱图理论，如果数据均匀取样自高维空 间中的低维流形，流形上Laplace—Beltrami算子可以 由图的Laplacian逼近，而图的Laplacian最前面的 几个特征向量就是流形上Laplace—Beltrami算子特 征函数的离散逼近125|，这也是算法的成功之处．算 法具体步骤如下： Stepl．使用最近邻或e邻域的方法构建邻接图； Step2．使用热核(heatkemel)方法定义权值； Step3．特征映射．假设图G为连接图(否则对 每一个连接部分)，计算方程L拿=AD考的特征值和 特征向量，以及zi在低维空间的映射，这里D越= ∑w_，L=D—w为Laplacian矩阵． J Belkin等还成功地把图的Laplacian作为正则 化项，应用于半监督学习问题，提出流形正则化算 法[26，27]，其有效性在声音、文本分类的实验中得到 验证． 3．2．4Hessian特征映射 Donoho和Grimes认为ISomap要求参数空间 的概率测度有凸支撑，进行全局等距映射这个条件 过于严格，而局部等距更合理，从而提出一种HessiaJl 特征映射算法[28|．Hessian特征映射和Laplacian特 征映射的理论框架非常相似，只是使用Hessian算 子代替了Laplacian算子．映射，：M—R，厂∈C2的 Hessian算子使用局部坐标的方法定义为 j 3 (H尹(m))锄2豢静(x)I删， r Il lI 1 H(厂)=I。，IlH罗“(m)惦dm． 这里dm代表M上的概率测度．如果流形M 和Rd开的连接子集存在局部等距映射，则H(．厂)的 d+1维零空间包含常数函数和d维函数空间，并 证明了对于H(厂)一个适当的基，都可以恢复其参 数空间．Hessian特征映射要解N个忌×忌的特征值 问题，这一点又同LLE算法非常相似，但是Hessian 方法要求估计局部邻域内的二阶导，而这对于高维 数据样本来说是非常困难的． 3．2．5扩散映射(diffusionmap) 很多的学习算法的目标函数都归结于最小化一 个低维表示的二次函数，这个问题很自然地转化为 求关系矩阵的特征向量问题．如果关系矩阵的每一 行的和都为1，那么元素巧就可以看做随机意义上 从i到j的一步转移概率．受此启发，Coifman等人 首先使用高斯核函数定义图中任意两点的边，然后 利用归一化方法构建图上的扩散过程．扩散过程的 转移矩阵构成算子的核，对应于一次转移概率 口(xi，zi)，口‘优)(xi，xi)表示从xi到xf随机游走优 步的转移概率．而对核进行特征分解可得到映射到 低维空间的特征向量，Coifman等人称之为扩散映 射[29，3o|．Coifman等人还在图上随机游走理论的基 万方数据 罗四维等：基于谱图理论的流形学习算法 础上定义了任意两点的距离函数，称为扩散距离．扩 散距离考虑了连接两点所有路径经过边的贡献，所以 比测地线距离的鲁棒性更强．算法具体步骤如下： Stepl．对于给定的样本数据集x，使用GuaSSiall 核定义成对数据点之间的相似度矩阵； Step2．利用加权的图Laplacian归一化方法，构 建扩散核口(xi，xi)； Step3．扩散核的谱分解。．首先定义扩散算子 Ⅳ(鼍)=∑n(薯，弓)厂(弓)，根据M凼过程的谱 J 图理论，可以得到谱分解，口(毛，弓)=∑A，九(墨) 5≥0 声。(薯)，其中1=Ao≥A1≥⋯≥0，那么通过映射 西(x)即可得到高维数据集的低维嵌入． 文献[31]表明合理选择归一化的高斯核可以逼 近Laplace—Beltrami算子，而不必考虑数据点的分布 密度，这个构造把由Laplace—Beltrami算子表示的几 何结构和数据集的统计特性分离开来，这一点在密 度无意义和数据点不是均匀取样的情况下尤其重要． Szummer等人还把随机游走理论的方法应用于半监 督学习算法[32，33|，取得较好的结果． 4 算法分析 流形学习算法的目标为了发现嵌入在高维数据 空间中的低维流形结构，并给出一个有效的低维表 示．基于全局的方法的主要优点在于能够对数据的 全局结构给予更可信的表示，而且保留全局度量在 理论上也更容易理解．基于局部的方法的优点在 于：一是计算复杂度较低，通常是对一个稀疏矩阵进 行特征分解；二是能够发现曲率较大的流形的潜在 几何结构，应用范围更广． 发现线性空间低维结构的方法在理论上较为完 善，所以对于线性的结构，PCA和MDS有很完善的 解释，并且都能够取得较好的效果．而对于非线性 流形结构来说，则要复杂很多．利用不同的性质，给 予不同的约束，就可以得到不同的算法，每一种算法 都是在保留某一方面特性的条件下得到高维数据的 低维表示．比如ISomap保留的是其测地线距离， Laplacian特征映射则利用流形上函数的Laplacian 算子等．同样各种算法也各有优缺点，LLE得到的 整体坐标通常有一定的拉伸与压缩的形变；Isomap， LTSA以及Hessian特征映射仅有较小的形变，但是 实验中发现Hessian特征映射对于样本个数和近邻 参数敏感，选取不当可能导致失败，这是因为算法要 利用样本估计每个点处的二阶微分，在局部要有充 分的样本；Isomap要求样本集为凸集，否则也将产 生一定的形变．Laplacian特征映射和扩散映射来源 于图的分割方法，在映射时有聚类效果，所以比较适 于聚类． 虽然这些学习算法的动机和推导过程不同，然 而其共同的地方在于首先得到一个关系矩阵，然后 利用谱分解的方法，最终把流形投影到低维空间，并 希望这个低维空间能够表示流形固有的几何结构． 这些算法之间的区别在于构造的关系矩阵不同，文 献[34]把不同关系矩阵看做是不同的核矩阵，然后 用核方法对这些学习算法进行解释．然而除了PCA 之外，几乎所有的基于谱图理论的学习算法中只能 直接得到训练样本的低维嵌入，而不能直接处理新 的样本．Bengio等人给出一个统一的框架，得到 MDS，IsOmap，LLE以及Laplacian特征映射等算法 的扩展135|．这个框架下关系矩阵被看做一个独立于 数据的核，根据这个核学习其特征函数，这样使得其 能够在不必重新计算特征向量的条件下直接得到新 样本的低维嵌入． 5总结与展望 流形学习是一个具有基础性和前瞻性的研究方 向，研究流形学习的主要意义在于寻找海量高维数 据集中蕴涵的整体几何和拓扑规律，而这种规律本 质上不依赖于实际观测的维数．对流形学习问题的 研究有着非常重要的实际意义，比如生物信息、经济 数据、网页搜索、气象预测等领域都有着广泛的应用． 除了本文介绍的基于谱图理论的算法外，还有很多的 方法应用于流形学习，如神经网络方法旧6'37J等，详细 论述参见文献[38]中由张军平和王珏撰写的流形学 习专题．另外流形固有维数的估计也是一个关键的 问题，在这方面研究也取得了很多的成果139~41|． 本文总结了文献中出现的基于谱图理论的流形 学习算法，对这些算法进行了综述和分析，并指出这 些算法都是通过把局部看做Euclid空间，然后研究 局部邻域的连接信息．算法的目的都是为了能够发 现非线性流形，为了更好地描述数据的固有几何结 构．尽管基于谱图理论的流形学习算法在过去的几 年中已经取得了丰硕的成果，但是仍有许多亟需研 究和解决的问题，尤其在下述几个方面： (1)流形学习算法的理论基础研究涉及微分几 何、图论、概率、随机过程等多个数学分支，比较复杂， 万方数据 1178 计算机研究与发展2006，43(7) 而要研究鲁棒性更强、应用范围更广的算法又必须 有充分的理论支持．目前关于学习问题的数学基础 研究已经取得一定的成果H2~4引． (2)基于谱图理论的算法都涉及求特征值和特 征向量的问题，不利于进行大规模的计算和扩展，所 以需要在此基础上研究大规模学习问题的高效和可 扩展的学习算法． (3)目前大部分学习算法都是基于局部的，而 基于局部算法一个很大缺陷就在于受噪声影响较 大，所以需要研究减小局部方法对于噪声和离群值 的影响，提高学习算法鲁棒性及泛化能力． (4)虽然基于谱图理论的算法已经在图像流 形H5。、对象识别146J等有了一定的应用，但若要更成 熟更广泛地应用于实际问题，仍需要进一步的研究． 1 2 4 5 6 7 8 9 10 致谢 感谢审稿专家提出的宝贵意见与建议． 参 考 文 献 H． SebastianSeung，DanielD． Lee．Themanif01dwaysof perception[J]．science，2000，290(12)：2268～2269 ChenXingshen，ChenWeihuan．LectureNotesinDi“erentiable Manifold[M]．Be妇ing：PekinguniverSityPress，1983(in Chinese) (陈省身，陈维桓．微分几何讲义[M]．北京：北京大学出版 社，1983) AndrewY．Ng，MichaelI．Jordan，YairWeiss．0nspectral clustering：Analysisandanakorithm[G]．In：AdvancesinNIPs 14．Camb“dge，MA：MITPress，2001．849～856 J． Shawe—Taylor，N． Cristianini，J． Kandola．Onthe concentrationofspectralpmperties[G]．In：AdvancesinNIPs 14．Cambridge，MA：MITPress，2001．511～517 F． R． K． Chung．SpectralGraphTheory[M]．Fresno： AmericanMathematicalSociety．1997 B．Sch01kopf，A．snlola，K—R．Muller．Nonlinearcomponent analysisas a kemeleigenvalueproblem[J]． Neural Computacation，1998，10(5)：1299～1319 T．Hastie，w． StuetzIe．PrincipaIcurves[J]．JournaIofthe AmericanStatisticalAsSociation，1989，84(406)：502～516 zhangJunping，wangJue．Anoverviewofprincipalcurves[J]． ChineseJoumalofC。mputers，2003，26(2)：126～146(in Chinese) (张军平，王珏．主曲线研究综述[J]．计算机学报，2003，26 (2)：129～146) ZhangJunping．Manifoldlearningandits applications： [Ph．D．dissertation][D]．Be巧ing：InstituteofAutomation， ChineseAcademyofSciences，2003(inChinese) (张军平．流形学习及应用：[博士论文][D]．北京：中国科学 院自动化研究所，2003) T．Cox，M． cox．MultidimensionalScaling【MJ． London： 11 20 21 23 24 25 26 27 Chapman&Hall，1994 J．B．Tenenbaum，V．deSilva，J．C． Langford．Aglobal geometricframe、Ⅳorkfornonlineardimensionalityreduction[J]． Science，2000，290(12)：2319～2323 M．Balasubr锄anian，E．L．Schwartz．Theisomapalgorithmand topologicalstability[J]．science，2002，295(5552)：7 D．Donoho，C．Grimes．WhendoesISOMAPrecoverthenatural parameterizationof familiesof articulatedimages?[R]． DepartmentofStatistics，StanfordUniversity，Tech．Rep．： 2002．27．2002 V．DeSilva，J．B．Tenenbaum．Globalversuslocalmethodsin nonlineardimensionalityreduction[G]．In： AdvancesinNIPs 15．Cambridge，MA：MITPress，2002．705～712 S．T．Roweis，L．K．Saul．Nonlineardimensionalityanalysisby locallylinear锄bedding[J]．science，2000，290(12)：2323～ 2326 L． K．SauI，S． T． Roweis．Thinkglobally，fit locally： Unsupervisedleamingoflowdimensionalmanifolds[J]．Joumal 0fMachineLeamingResearch，2003，4(6)：119～155 ZhangChangshui，WangJun， ZhaoNanyuan，P￡ 口Z． Reconstructionandanalysisofmulti—posefaceimagesbasedon nonlineardimensionalityreduction[J]．PatternRecognition， 2004，37(1)：325～336 ZhangZhenyue，ZhaHongyuan．Principalmanifoldsandnonlinear dimensionalityreductionviatangentspacealignment[J]．SIAM JournalofScientificComputing，2004，26(1)：313～338 ZhangZhenyue，ZhaHongyuan．Linearlow—rankapproximations andnonlineardimensiDnalityreductjon[J]．SciencejnChinaSeries A，Mathematics，2005，35(3)：273～285(inChinese) (张振跃，查宏远．线性低秩逼近与非线性降维[J]．中国科学 A辑：数学，2005，35(3)：273～285) WangJing，ZhngZhenyue，ZhaHongyuan．Adaptivemanifold leaming[G]．In：AdvancesinNIPS17．Cambridge，MA：MIT Press．2004 YaJlgJian，LiFuxin，WangJue．Abetterscaledlocaltangent spacealignmentakorithm[J]．Journalofsoftware，2005，16 (9)：1584～1590(inChinese) (杨剑，李伏欣，王珏．一种改进的局部切空间排列算法[J]． 软件学报，2005，16(9)：1584～1590) M．Brand．chartingamanifold[G]．In：AdvancesinNIPs15． Cambridge，MA：MITPress，2002．961～968 M． Belkin，P． Niyogi．Laplacianeigenmapsandspectral techniquesforembeddingandclustering[G]．In：Advancesin NIPS14．Carrlbridge，MA：MITPress，2001．585～591 M．Belkin，P． Niypgi．Laplacianeigenmapsfordimensionality reductionanddatarepresentation[J]．Neural(沁mputation， 2003，15(6)：1373～1396 M．Belkin，P． Niyogi．Towarda theoreticalfoundationfor Laplaciambasedmanifoldmethods【G]．In：Proc．18thAnnual Conf．LeamingTheory，LNCS3559．Berlin：Springer-Verlag， 2005．486～500 M．Belkin，P． Niyogi．Usingmanifoldstructureforpanially 1abeledclaSsification[G]．In：AdvancesinNIPs15．Cambridge， MA：MITPress．2002．929～936 M．Belkin，P．Niyogi，V．Sindhwani．Manifoldregularization：A 万方数据 罗四维等：基于谱图理论的流形学习算法 1179 32 33 34 35 36 37 38 39 geometricframeworkforlearningfromexamples[R]．Department ofComputerScience，UniversityofChicago，Tech．Rep．：TR一 2004．06．2004 D．Donoho，C．Grimes．HeSsianEigenmaps：Newlocallylinear embeddjngtechnjqueSforhigh．dimensionaldata[J]．Proceedings oftheNationalAcademyofSciences，2003，100(10)：5591～ 5596 R．R．Coifman，S． Lafon，A．B． Lee，以nZ．Geometric diffusionsasat00lforharHlonicanalysisandstructuredefinitionof data．PartI： Diffusionmaps[J]．ProceedingsoftheNational AcademyofSciences，2005，102(21)：7426～7431 R．R．Coifman，S． Lafon，A． B． Lee，甜口￡． Geometric diffusjonsasat00lforha珊onicanalysjsandstructuredefinitionof data．PartII： Multiscalemethods[J]．Proceedingsofthe NationalAcademyofSciences，2005，102(21)：7432～7437 B．Nadler，S．Lafon，R．R．C0jfman，甜甜．Diffusionmaps， spectralclusteringandeigenfunctionsofFokker-Planckoperators [G]．In：AdvancesinNIPS17．Cambridge，MA：MITPresS， 2004 M．Szummer，T．Jaakkola．PartiallylabeledclaSSificationwith Markovrandomwalks[G]．In： AdvancesinNIPS14． C姗bridge，MA：MITPress，2001．945～952 ZhouDengyong，sch6lkopfBemhard．LeamingfromlabeIedand unIabeleddatausingrandomwalks[G]．In：Proc．26thDAGM SymposiumPatternRecognition，LNCS3175．BerIin：Sp血【ger— Verlag，2004．237～244 HamJihun，DanielD．Lee，SebastianMika，以“．Akernelview ofthedimensionalityreductionofmanifolds[C]．ICML2004， Banff，Alberta，Canada，2004 Y．Bengio，J．Paiement，P．Vincent．0ut-of—sampleextensions f。rLLE，Isomap，MDs，Eigenrnapsandspectralclustering[G]． In：AdvancesinNIPS16．Cambridge，MA：MITPress，2003 T． Kohonen．self一0rganizingMaps[M]．Berlin：Springer— Verlag，1995 ChristopherM． Bishop，MarkusSvensen，ChristopherK． I． williams．GTM：Thegenerativetopographicmapping[J]．NeuraI Computation，1998，10(1)：215～234 ZhouZhihua，CaoCungen．Neuralnetworkanditsapplications [G]．Be巧ing：Tsinghuaunivers“yPress，2004(inchinese) (周志华，曹存根．神经网络及其应用[G]．北京：清华大学出 版社，2004) FrancescoCamastra．Datadimensionalityestimationmethods：A survey[J]．PattemRecognition，2003，36(12)：2945～2954 42 43 45 M． Hein，Y． Audibert．IntrinSicdimensionalityestimationof submani“dsinRd[c]．IcML2005，Bonn，Germany，2005 ElizavetaLevina，PeterJ．Bickel．Maximumlikelihc，0destimation of intrinsicdimension[G]． In： Advancesin NIPs17． cambrjdge，MA：MITPress，2004 T．Poggio，S．Smale．Themathematicsofleaming：Dealingwith data[J]．Not．AmericanMathematicsS0ciety，2003，50(5)： 537～544 T．Poggio，R，Rifkin，S．Mukheljee，甜n￡．Generalconditions forpredictivityin1ea玎lingtheory[J]．Nature，2004，428(3)： 419～422 Carlo’romasi．Leamingtheory：Pastperfb珊anceandfuture resultS[J]，Natufe，2004，428(3)：378 K． Weinberger，L． Saul．Unsupervisedleamingof image manif01dsbysemidefiniteprogr啪ming[C]．In：Proc．CVPR 2004(2)．LosAl砌jtos：IEEEC0mputerSocietyPress，2004， 988～995 A． E19ammal，C． S． Lee．Inferring3Dbodyposefrom silhouettesusingactivitymanifoldlearning[c]．In：Pmc．cVPR 2004(2)．LosAl咖itos：IEEEC0mputerSocietyPress，2004． 681～688 LuOSiwei．bornin1943．Pro{essorandPh． D．supervisOrofBe巧ingJiaotongUniversity． Hismainresearchinterestsincludeartificial neuralnetwork，parallelcomputing， statisticaIIearningtheory，andmanifbId 1earning． 罗四维，1943年生，教授，博士生导师，主要研究方向为人工 神经网络、并行计算、统计学习理论、流形学习． ZhaoLianwej，bornin 19’76．Ph． D． candidateincomputingsciencefmmBe巧ing JiaotongUniversity．Hismainresearch interestsincludemanifoldleaming，statistical learningtheory，andartificialneural net、^，ork． 赵连伟，1976年生，博士研究生，主要研究方向为流形学习、 统计学习理论、人工神经网络． ResearchBackground 0neofthemaindifficultiesinmachineleamingishowtocopewiththeseeminglyhigh—dimensionalobservationdatasets． However，theSeobservationsoftenhaveonlyafewdegreesoffreedom．Basedontheassumptionthatthedatalieonorclosetoalow— dimensionalmanifold，therehasbeenconsiderableintereStindevelopingefficientalgorithmforreconstructinglow—dimensionaI manif01dembeddedinthehigh—dimensionalspace．SpectralgraphtheOrystudiestheeigenvectorsandeigenvaluesofmatrices associatedwithgraphsandhasbeenwidelyusedinthemanifoldleaminga190rithmrecently．Inthispaper，wereviewS0metypicaI manifoldleamingalgorithmsbasedonspectralgraphtheOry．0urworkissupportedbytheNationalNaturalScienceFoundationsof ChinaundergrantNo．60373029，theNationalResearchFoundationfortheDoctoralProgramofHigherEducationofChinaunder grantNo．20050004001andCo—ConstructionProjectofKeySubjectofBe幻ing． 万方数据 基于谱图理论的流形学习算法 作者： 罗四维， 赵连伟， Luo Siwei， Zhao Lianwei 作者单位： 北京交通大学,计算机与信息技术学院,北京,100044 刊名： 计算机研究与发展 英文刊名： JOURNAL OF COMPUTER RESEARCH AND DEVELOPMENT 年，卷(期)： 2006,43(7) 被引用次数： 47次 参考文献(46条) 1.H.Sebastian Seung;Daniel D.Lee The manifold ways of perception 2000(12) 2.陈省身;陈维桓 微分几何讲义 1983 3.Andrew Y.Ng;Michael I.Jordan;Yair Weiss On spectral clustering:Analysis and an algorithm 2001 4.J.Shawe-Taylor;N.Cristianini;J.Kandola On the concentration of spectral properties 2001 5.F.R.K.Chung Spectral Graph Theory 1997 6.B.Scholkopf;A.Smola;K-R.Muller Nonlinear component analysis as a kernel eigenvalue problem[外文期 刊] 1998(05) 7.T.Hastie;W.Stuetzle Principal curves[外文期刊] 1989(406) 8.张军平;王珏 主曲线研究综述[期刊论文]-计算机学报 2003(02) 9.张军平 流形学习及应用 2003 10.T.Cox;M.Cox Multidimensional Scaling 1994 11.J.B.Tenenbaum;V.de Silva;J.C.Langford A global geometric framework for nonlinear dimensionality reduction[外文期刊] 2000(12) 12.M.Balasubramanian;E.L.Schwartz The isomap algorithm and topological stability 2002(5552) 13.D.Donoho;C.Grimes When does ISOMAP recover the natural parameterization of families of articulated images 2002 14.V.De Silva;J.B.Tenenbaum Global versus local methods in nonlinear dimensionality reduction 2002 15.S.T.Roweis;L.K.Saul Nonlinear dimensionality analysis by locally linear embedding[外文期刊] 2000(12) 16.L.K.Saul;S.T.Roweis Think globally,fit locally:Unsupervised learning of low dimensional manifolds 2003(06) 17.Zhang Changshui;Wang Jun;Zhao Nanyuan Reconstruction and analysis of multi-pose face images based on nonlinear dimensionality reduction[外文期刊] 2004(01) 18.Zhang Zhenyu