（计算机软件与理论专业论文）流形学习的谱方法相关问题研究.pdf

摘要 摘要 在当今这个信息时代，可以方便地获得大量的数据。许多实际应用中，获得 的数据是高维的、庞大的、繁杂的、无序的，并且还在不断的增加，有价值的信 息淹没在大规模的海量高维数据集之中，需要发现数据的内在规律以及预测未来 发展趋势。流形学习就是假定这些观测数据位于或近似位于一个嵌入在高维欧氏 空间中的内在低维流形上，主要目标是发现高维观测数据集的内在低维流形结构 和嵌入映射关系。目前，流形学习已经成为机器学习、模式识别、数据挖掘以及 其它相关研究领域的研究热点。 本文通过分析流形学习的内涵与外延，立足于解决流形学习的谱方法中的重 要问题，在算法设计层面和图像流形应用层面上展开了一系列研究。首先对流形 学习的典型谱方法做了详细对比分析，然后针对流形的增殖学习、构造近邻关系 的合理度量、提高内在低维空间的可分性、基于集成的流形学习、局部保持的算 法和全局保持的算法两者优势融合等几方面进行了重点研究，提出了五个以谱方 法为基础的流形学习算法，并和相关研究成果做了理论上与实验上的比较，表明 了我们提出算法的有效性。 本文主要创新成果有以下几方面： ( 1 )定义了增殖流形学习的概念，这有利于指导符合人脑增殖学习机理的流形 学习算法的研究。以此为指导原则，提出了一种基于l l e 的动态增殖流形学习算 法( d k i l l e ) 。实验结果表明：d k i l l e 算法比l l e 的几个增量式算法在处理 新数据集时有更好的效果；d k i l l e 算法发现的整体低维结构更接近批处理的方 式获得的低维结构，使得新到来的数据子集所包含的低维结构知识被整合到原有 的低维结构中去；而l l e 的增量式算法处理新的观测数据时更依赖于原有数据的 低维坐标。 ( 2 ) 提出了一种基于测地线距离的广义高斯型拉普拉斯特征映射算法( g g l e ) 。 该算法将测地线距离和广义高斯函数融合到传统的拉普拉斯特征映射算法中，可 以调整近邻图结点间的相似度，通过选择超高斯、高斯或者次高斯函数来实现不 同程度的近邻局部特性的保持；而且当需要保持更多的近邻关系使得数据点邻域 增大时，采用测地线距离可以避免欧氏距离度量不合理的缺陷；实验结果表明在 用不同的广义高斯函数度量高维数据点间的相似度时，局部近邻结构保持的程度 是不同的，g g l e 获得的全局低维坐标也呈现出不同的聚类特性。 ( 3 )提出了一种基于g g l e 的集成判别算法( e g g l e ) ，该算法的主要优点是： 近邻参数露固定，邻接矩阵和测地线距离矩阵都只构造一次，只需要多次选择广 北京交通大学博士学位论文 义高斯型函数构造多个拉普拉斯矩阵，获取多个独立的低维空间坐标集合，独立 学习分类器，集成分类识别。时间复杂度上e g g l e 算法与e n s e m b l e i s o m a p 和 e n u l l e l d a 算法相比较通常更具有优越性。在半监督学习框架下做了l e 与 e g g l e 算法的对比实验，识别结果表明了e g g l e 算法的有效性。另外，本文也 提出了一种监督的集成流形学习算法( e g g l e l d a ) ，该算法将线性监督算法l d a 和e g g l e 相结合，加强集成流形学习在监督学习中的判别能力，使得e g g l e l d a 算法既考虑了数据的类别信息又考虑了几何分布特性。实验结果表明了 e g g l e l d a 算法和e n u l l e l d a 算法的集成识别性能的差异。 ( 4 )提出了一种全局拉普拉斯展开算法( g l u ) ，该算法综合了局部保持的拉普 拉斯特征映射算法( l e ) 和全局保持的最大化方差展开算法( m v u ) 的优点。主 要思想是使得局部近邻的点尽可能的接近，同时也要使得相互远离点尽可能远。 实现方法是构造局部尽可能近邻和全局展开的双目标函数，引入低维坐标的g r a m 内积矩阵，通过半定规划( s d p ) 的方法优化双目标函数，从而学习这样一个内积 矩阵，最后对这个内积矩阵进行特征分解求内在低维嵌入。在月亮形人造数据集、 真实的u s p s 手写体数字数据集和雕塑头像数据集上的可视化实验验证了g l u 算 法的有效性；并且比较了l e 、m v u 、u d p 和g l u 等4 种流形学习算法的低维可 分性和可视化效果，实验结果表明了g l u 算法的优越性。 关键词：流形学习；谱方法；邻接图；拉普拉斯；增殖；广义高斯函数：集成； 半定规划；展开 分类号：t p l 8 1 a b s t r a c t a bs t r a c t i nt h ec u r r e n ti n f o r m a t i o na g e ，al a r g eq u a n t i t yo fd a t ac a nb eo b t a i n e de a s i l y t h e o b t a i n e dd a t aa r e h i g h - d i m e n s i o n a l ，e n o r m o u s ，m u l t i f a r i o u s ，d i s o r d e r e d ，a n d c o n t i n u o u s l yi n c r e a s i n gi nm a n yp r a c t i c a la p p l i c a t i o n s t h ev a l u a b l ei n f o r m a t i o ni s s u b m e r g e d i n t ol a r g es c a l ed a t a s e t i ti sn e c e s s a r yt of i n dt h ei n t r i n s i cl a w so ft h ed a t a s e t a n dp r e d i c tt h ef u t u r e d e v e l o p m e n tt r e n d m a n i f o l dl e a r n i n ga s s u m e st h a tt h e s e o b s e r v e dd a t al i eo no rc l o s et oi n t r i n s i cl o w - d i m e n s i o n a lm a n i f o l d se m b e d d e di nt h e h i g h - d i m e n s i o n a le u c l i d e a ns p a c e t h em a i ng o a lo fm a n i f o l d l e a r n i n gi s t of i n d i n t r i n s i cl o w - d i m e n s i o n a lm a n i f o l ds t r u c t u r e so fh i g h - d i m e n s i o n a lo b s e r v e dd a t a s e ta n d t h ee m b e d d i n gm a p a tp r e s e n t ，m a n i f o l dl e a r n i n gh a sb e c o m eah o ti s s u ei nt h ef i e l d s o fm a c h i n el e a r n i n g ，p a t t e r nr e c o g n i t i o n ，d a t am i n i n ga n do t h e rr e l a t e dr e s e a r c h b ya n a l y z i n gt h ei n t e n s i o na n de x t e n s i o no fm a n i f o l dl e a r n i n g ，t h i sd i s s e r t a t i o ni s d e v o t e dt o s o l v i n gs e v e r a li m p o r t a n tp r o b l e m so fs p e c t r a lm e t h o d sf o rm a n i f o l d l e a r n i n g ，a n dc a r r i e so u tas e r i e so fr e s e a r c ho na l g o r i t h md e s i g na n di m a g em a n i f o l d a p p l i c a t i o n f i r s t l y , t r a d i t i o n a ls p e c t r a lm e t h o d sa r ea n a l y z e da n dc o n t r a s t e di nd e t a i l s e c o n d l y f i v ep r o b l e m sa r em a i n l yi n v e s t i g a t e d ，w h i c hi n c l u d ek n o w l e d g e i n c r e a s a b l e l e a r n i n go fm a n i f o l d ，c o n s t r u c t i n gar e a s o n a b l em e a s u r eo fn e i g h b o r h o o dr e l a t i o n ， e n h a n c i n gt h es e p a r a b i l i t yo ft h el o w - d i m e n s i o n a ls p a c e ，m a n i f o l dl e a r n i n gb a s e do n e n s e m b l e ，c o m b i n i n gt h ea d v a n t a g e so fl o c a lp r e s e r v i n ga l g o r i t h m sa n dg l o b a l p r e s e r v i n ga l g o r i t h m si nm a n i f o l d 1 e a r n i n g f i n a l l y , t h i sd i s s e r t a t i o np r o p o s e sl i v e m a n i f o l dl e a r n i n ga l g o r i t h m sb a s e do ns p e c t r a lm e t h o d o u rp r o p o s e da l g o r i t h m sa r e c o m p a r e dw i t ht h er e l a t e dr e s e a r c hi nt h e o r i e sa n de x p e r i m e n t s a n dt h er e s u l t ss h o w t h ee f f e c t i v e n e s so fo u rp r o p o s e da l g o r i t h m s t h em a i nc o n t r i b u t i o n so ft h i sd i s s e r t a t i o na r es u m m a r i z e da sf o l l o w s ： ( 1 ) t h ec o n c e p to fk n o w l e d g e i n c r e a s a b l em a n i f o l dl e a r n i n gi sd e f i n e d i ti s a d v a n t a g e o u st og u i d et h er e s e a r c ho fm a n i f o l dl e a r n i n ga l g o r i t h m sw h i c hf i tt o k n o w l e d g e - i n c r e a s a b l el e a r n i n gm e c h a n i s mi nh u m a nb r a i n a c c o r d i n gt ot h eg u i d i n g p r i n c i p l eo fk n o w l e d g e - i n c r e a s a b l em a n i f o l dl e a r n i n g ，w ep r o p o s ead y n a m i c a l l y k n o w l e d g e - i n c r e a s a b l em a n i f o l dl e a r n i n ga l g o r i t h mb a s e do nl o c a l l yl i n e a re m b e d d i n g ( d k i l l e ) e x p e r i m e n t a lr e s u l t ss h o wt h a td k i - l l ea l g o r i t h mh a sb e t t e rr e s u l mt h a n s e v e r a ll l e b a s e di n c r e m e n t a la l g o r i t h m si nd e a l i n g 、 ，i t ht h en e wd a t a s e t d k i l l ei s n e a r e rt ot h eo r i g i n a l ( b a t c h ) l l ef o rd i s c o v e r i n gl o w - d i m e n s i o n a ls t r u c t u r e ，a n dc a n v 北京交通大学博士学位论文 i n t e g r a t et h el o w d i m e n s i o n a ls t r u c t u r ek n o w l e d g eo ft h en e wd a t as u b s e ti n t ot h e p r e v i o u sl o w d i m e n s i o n a ls t r u c t u r e o nt h ec o n t r a r y , i n c r e m e n t a ll l ea l g o r i t h m s d e p e n dm o r eo nt h o s ep r e v i o u sl o w - d i m e n s i o n a lc o o r d i n a t e sf o rd e a l i n gw i t ht h en e w o b s e r v e dd a t a ( 2 ) ag e n e r a l i z e dg a u s s i a nl a p l a c i a ne i g e n m a pa l g o r i t h mb a s e do ng e o d e s i cd i s t a n c e ( g g l e ) i sp r o p o s e d ，w h i c hi n c o r p o r a t e sg e o d e s i cd i s t a n c ea n dg e n e r a l i z e dg a u s s i a n f u n c t i o ni n t ot h eo r i g i n a ll a p l a c i a ne i g e n m a pa l g o r i t h m g g l ea l g o r i t h mc a na d ju s t t h es i m i l a r i t i e sb e t w e e nn o d e so fn e i g h b o r h o o dg r a p h ，a n dc a np r e s e r v et h ed i f f e r e n t d e g r e e so fl o c a lp r o p e r t i e sb yu s i n gs u p e r - g a u s s i a nf u n c t i o n ，g a u s s i a nf u n c t i o no r s u b g a u s s i a nf u n c t i o n m o r e o v e r , g g l ec a na v o i dt h ed e f i c i e n c yo fe u c l i d e a nd i s t a n c e b yu s i n gg e o d e s i cd i s t a n c ew h e nn e i g h b o r h o o d so fd a t ap o i n t sa r ee n l a r g e df o r p r e s e r v i n gm o r en e i g h b o r h o o dr e l a t i o n s e x p e r i m e n t a lr e s u l t ss h o wt h a tt h eg l o b a l l o w - d i m e n s i o n a lc o o r d i n a t e so b t a i n e db yg g l eh a v ed i f f e r e n tc l u s t e r i n gp r o p e r t i e sa n d d i f f e r e n td e g r e e so fp r e s e r v i n gl o c a ln e i g h b o r h o o ds t r u c t u r e sw h e nd i f f e r e n tg e n e r a l i z e d g a u s s i a nf u n c t i o n sa r eu s e dt om e a s u r i n gt h es i m i l a r i t i e sb e t w e e nh i g h d i m e n s i o n a l d a t ap o i n t s ( 3 ) a n e n s e m b l e b a s e dd i s c r i m i n a n ta l g o r i t h mb a s e do ng g l e ( e g g l e ) i s p r o p o s e d t h em a i na d v a n t a g e so fe g g l ei n c l u d e ：t h ef i x e dn e i g h b o r h o o dp a r a m e t e r 露，o n l yo n e t i m ef o rc o n s t r u c t i n gn e i g h b o r h o o dg r a p ha n dg e o d e s i cd i s t a n c em a t r i x ，o n l yn e e d i n gt o c h o o s eg e n e r a l i z e dg a u s s i a nf u n c t i o n sm a n yt i m e sf o rc o n s t r u c t i n gm a n yl a p l a c i a n m a t r i x e s ， o b t a i n i n gm u l t i p l ei n d e p e n d e n t l o w - d i m e n s i o n a lc o o r d i n a t e s e t s ， i n d e p e n d e n t l yt r a i n i n gm u l t i p l ec l a s s i f i e r s ，a n dc o m b i n i n gc l a s s i f i c a t i o nr e s u l t so ft h e s e c o m p o n e n tc l a s s i f i e r st op r o d u c et h ef i n a li d e n t i f i c a t i o n e g g l ea l g o r i t h mg e n e r a l l y o u t p e r f o r m se n s e m b l e i s o m a pa l g o r i t h ma n de n - - u l l e l d aa l g o r i t h mo nt h et i m e c o m p l e x i t y u n d e rt h ef r a m e w o r kf o rs e m i s u p e r v i s e dl e a r n i n g ，t h ec o m p a r a t i v e e x p e r i m e n t so fe g g l e a n dl ea r ec o m p l e t e d e x p e r i m e n t a lr e s u l t ss h o wt h a te g g l e a l g o r i t h mi se f f e c t i v e i na d d i t i o n ，as u p e r v i s e dm a n i f o l dl e a r n i n ga l g o r i t h mb a s e do n e n s e m b l e ( e g g l e l d a ) i sp r o p o s e d i nt h i sd i s s e r t a t i o n f o r e n h a n c i n g t h e c l a s s i f i c a t i o na b i l i t yo fe n s e m b l e b a s e dm a n i f o l d l e a r n i n gi ns u p e r v i s e dl e a r n i n g ， e g g l ei sc o m b i n e d 诵t hl d a ，s ot h a te g g l e l d aa l g o r i t h mt a k e si n t oa c c o u n tt h e l a b e li n f o r m a t i o no fd a t aa sw e l la st h ec h a r a c t e r i z a t i o no ft h eg e o m e t r i cd i s t r i b u t i o n e x p e r i m e n t a l r e s u l t ss h o wt h ed i f f e r e n c eo ft h ee n s e m b l e - b a s e d r e c o g n i t i o n p e r f o r m a n c eb e t w e e ne g g l e - l d aa l g o r i t h ma n de n - u l l e l d aa l g o r i t h m ( 4 ) ag l o b a ll a p l a c i a nu n f o l d i n ga l g o r i t h m ( g l u ) i sp r o p o s e ds ot h a tl ea l g o r i t h m a b s t r a c t w i t hp r e s e r v i n gl o c a lp r o p e r t i e si s i n t e g r a t e di n t om v ua l g o r i t h mw i t hp r e s e r v i n g g l o b a lp r o p e r t i e s t h em a i ni d e ao fg l ua l g o r i t h mi st h a tn e a r b yp o i n t sa r ep u l l e da s n e a ra s p o s s i b l ew h i l ed i s t a n tp o i n t sa lep u l l e da sf a r a p a r t a s p o s s i b l e i t s i m p l e m e n t a t i o nm e t h o di st oc o n s t r u c tt h ed o u b l eo b j e c tf u n c t i o n sf o rr e m a i n i n ga sn e a r a sp o s s i b l ei n l o c a l i t ya n du n f o l d i n gi ng l o b a l i t y , t or e f o r m u l a t et h ed o u b l eo b j e c t f u n c t i o n si nt e r m so ft h eg r a mi n n e rp r o d u c tm a t r i xo fl o w d i m e n s i o n a lc o o r d i n a t e s t o o p t i m i z et h eo b j e c tf u n c t i o nf o rl e a r n i n gt h ei n n e rp r o d u c tm a t r i xb ys e m i - d e f i n i t e p r o g r a m m i n g ，a n dt oc o m p u t eai n t r i n s i c a l l yl o w d i m e n s i o n a le m b e d d i n gv i at h e e i g e n d e c o m p o s i t i o no ft h ei n n e rp r o d u c tm a t r i x v i s u a l i z a t i o ne x p e r i m e n t so ns y n t h e t i c ”t w om o o n s ”d a t a s e t ，u s p sh a n d w r i t t e nd i g i t sd a t a s e ta n dt h es c u l p t u r eh e a dp o r t r a i t d a t a s e td e m o n s t r a t et h ee f f e c t i v e n e s so fg l u a l g o r i t h m i na d d i t i o n ，t h ec l a s s i f i c a t i o n a b i l i t ya n dv i s u a l i z a t i o np e r f o r m a n c eo ff o u rm a n i f o l dl e a r n i n ga l g o r i t h m st h a ti n c l u d e l e ，m v u ，u d pa n dg l ua r ec o m p a r e d e x p e r i m e n t a lr e s u l t ss h o wt h es u p e r i o r i t yo f g l u a l g o r i t h m k e y w o r d s ：m a n i f o l dl e a r n i n g ；s p e c t r a lm e t h o d ；n e i g h b o r h o o dg r a p h ；l a p l a c i a n ； k n o w l e d g e i n c r e a s a b l e ；g e n e r a l i z e dg a u s s i a nf u n c t i o n ；e n s e m b l e ；s e m i d e f i n i t e p r o g r a m m i n g ；u n f o l d i n g c l a s s n o ：t p l8 i v i i 学位论文版权使用授权书 本学位论文作者完全了解北京交通大学有关保留、使用学位论文的规定。特 授权北京交通大学可以将学位论文的全部或部分内容编入有关数据库进行检索， 并采用影印、缩印或扫描等复制手段保存、汇编以供查阅和借阅。同意学校向国 家有关部门或机构送交论文的复印件和磁盘。 ( 保密的学位论文在解密后适用本授权说明) 学位论文 签字日期 导师签名： 弘吼， 签字日期：2 1 年月乙角 独创性声明 独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工作和取得的研 究成果，除了文中特别加以标注和致谢之处外，论文中不包含其他人已经发表或 撰写过的研究成果，也不包含为获得北京交通大学或其他教育机构的学位或证书 而使用过的材料。与我一同工作的同志对本研究所做的任何贡献均己在论文中作 了明确的说明并表示了谢意。 一虢啼钟期：y 歹年一虿月7 日 致谢 在此衷心感谢我的导师罗四维教授。自从我攻读博士学位以来，他对科学研 究的敏锐洞察力，引导我逐步深入的研究，本论文正是在他的精心指导下完成的。 他严谨的治学态度、宽广的学术视野、科学的工作方法和平易近人的高尚品格一 直是我学习的榜样。感谢罗老师给予了我无微不至的关心、鼓励、帮助；感谢罗 老师给予我在计算机领域深造的机会：感谢罗老师为我提供了良好的学习环境。 在实验室工作及撰写论文期间，感谢黄雅平老师、刘蕴辉老师、赵嘉莉老师、 田媚老师、邹琪老师、李清勇老师、尹辉老师、艾丽华老师、丁丁老师和黄华老 师等许多老师给予我无私帮助和指导。感谢在实验室一起工作过的博士同学们， 你们：赵连伟、廖灵芝、王娇、钟晶晶、李燕、杨树忠、高瞻、蔺源、王哲、林 杰、郑字、吕子昂、于欣妍、薄一航、白雪、孙巍、吴丽娜给予了我许多帮 助，和你们的讨论让我受益匪浅。 感谢加拿大多伦多大学的g e h i n t o n 教授、芬兰奥卢大学0 k o u r o p t e v a 博士、 雅虎的k q w e i b e r g e r 博士为我提供了许多研究资料。 感谢我的父母、妻子、兄长、儿子的理解和支持，使我能够在北京交通大学 专心完成我的学业，谨将此文献给你们。 l绪论 1 1 引言 1绪论 随着计算机与数字网络的普遍使用，人们获取信息的能力己今非昔比，不分 时间和地点，可以方便地获得大量的信息。随之出现了表示信息的数据集的快速 增长和快速更新、数据维数更高、非结构化性更突出等新特点。从大规模海量数 据集中发现和探索令人感兴趣的信息成为机器学习的主要目标之一。许多实际应 用中，如图形处理、计算机视觉、文本信息挖掘、计算生物学等，获得的数据是 高维的、庞大的、繁杂的、无序的，并且还在不断的增加，有价值的信息淹没在 大规模的海量高维数据集之中，迫切需要发现数据的内在规律以及预测未来发展 趋势。从流形的角度来考虑是一种潜在的解决办法。基于流形学习的研究方法能 够发现嵌入在高维数据集中的内在低维结构，因此流形学习可能是一条合理的研 究途径。 自2 0 0 0 年以来，流形学习的研究受到机器学习、模式识别、数据挖掘以及其 它领域研究人员的广泛关注。特别是2 0 0 0 年1 2 月在s c i e n c e 的同一期上发 表的三篇文章分别从神经科学和计算机科学的角度对流形学习问题进行了研究， 探讨了神经系统与嵌入在高维数据空间中低维认知概念之间的关系；s e u n g 提出感 知可能以流形方式存在，视觉记忆也可能是以稳态的流形( 或连续吸引子) 存储【i 】； t e n e n b a u m 和r o w e i s 分别从算法层面上给出了参数少、运算快、易求全局最优解 的经典算法i s o m a p 2 1 和l l e 【3 】。由此推动了流形学习成为当前机器学习、数据挖 掘研究的热点。在2 0 0 4 年i c m l 国际会议中首次将“流形学习”作为关键词，再 一次证明研究者们对流形学习的重视。近年来，流形学习的谱方法得到了迅猛的 发展，涌现出大批的流形学习的谱方法，典型的有等度规映射( i s o m a p ) 【2 】、局 部线性嵌入( l l e ) 1 3 j 、拉普拉斯特征映射( l e ) 【4 】、局部切空间排列算法( l t s a ) 1 5 j 、最大方差展开( m v u ) 1 6 】等，都是通过求矩阵的最大( 或最小) 特征谱对应的 特征向量捕获观测到的高维数据集的内在几何结构。流形学习的谱方法求解的优 化问题都是凸优化问题，且都能在多项式时间范围内求出最优解。然而，流形学 习的这些谱方法仍有一些问题有待解决，如依赖于从已知数据集构造的矩阵的谱 分解，对新观测到的高维数据集求其低维结构是困难的；如何构造合理邻接权； 近邻参数的选择直接关系到内在低维结构的有效恢复；部分算法需要求最小特征 谱，大稀疏矩阵特征谱过小使得数值计算不稳定。在理论上和应用上都值得研究 北京交通大学博士学位论文 者关注流形学习的谱方法。 1 2 流形学习的概念及其诠释 1 2 1流形的几个基本概念 流形是欧氏空间的推广，是微分几何和拓扑代数的研究对象，流形上每一点 都存在一个邻域和欧氏空间的一个开集同胚，因此流形上每点处都存在一个邻域 可以用局部坐标系来刻画。直观来看，可把流形看成是一块块“欧氏空间”粘起 来的结果，而欧氏空间是流形的特例，即，欧氏空间是一个平凡流形。流形的确 切数学定义涉及以下几个概念： 定义1 1 如果在非空集合肘上引入一个子集簇r ，子集簇r 满足下面三个条件， 则称集合m 就是一个拓扑空间( t o p o l o g i c a ls p a c e ) 。 ( 1 ) r 中任意多个元素的并仍然属于r 。 ( 2 ) f 中任意多个元素的交仍然属于r 。 ( 3 ) 空集矽和集合m 属于r 。 定义1 2 设集合m 是一个拓扑空间，如果对m 中任意两个不同的点z ，y ，都存在 点x 的邻域u 和点y 的邻域i 使得u n y 三，则称集合m 是h a u s d o f f 空间。 定义1 3 设两个拓扑空间x 和l ，如果存在映射厂：x 专y 是一一映射，并且厂及 其逆映射厂- 1 都是连续的，则称x 和，是同胚( h o m e o m o r p h i s m ) 。 定义1 4设集合m 是一个h a u s d o 腔间，如果v x m 都存在一个邻域u ( x ) 与d 维欧氏空间r d 的某个子集同胚，则m 是一个d 维流形( m a n i f o l d ) 。 微分几何中研究的通常是连续可微的流形，而实际问题中是通过离散逼近连 续的方法得到连续可微流形的性质。对给定的高维观测数据集，数据变量可以用 少量几个影响因素来表示，这种在现象几何学上表现为数据点散布在低维光滑流 形上，或者是在低维光滑流形附近。而要有效揭示数据内在的几何结构，需要根 据有限的离散观测样本数据学习和发现嵌入在高维空间中的低维光滑流形，这也 就是流形学习的主要目标。 1 2 2 流形学习的定义 在通常情况下，用于数据分析的线性降维技术和非线线降维技术都被认为是 流形学习的范畴。根据“流形”这一微分几何中的概念，流形学习的研究最早可 以追溯到1 9 8 4 年斯坦福大学的h a s t i e 提出通过数据集的“中间”结构即一维主曲 2 1绪论 线和二维主曲面等主流形概念【7 1 。然而首次提出“流形学习”( m a n i f o l dl e a r n i n g ) 这一术语是在1 9 9 5 年由b r e g l e r 和o m o h u n d r o 发表关于可视语音识别的学术论文中 8 9 1 。确切给出了“流形学习”的数学描述是在2 0 0 2 年s i l v a & t e n e n b a u m 发表在，n i p s ” 国际会议上的“非线性维数约减的全局与局部方法”一文中【1 0 l ，将概念“流形学习” 定义如下： 定义1 5 流形学习的数学定义如下： 设y 是包含在欧氏空间r d 中的d 维定义域，且设从d 维欧氏空间r j 到d 维欧氏空 间r d 存在一个光滑嵌入映射为： f ：ycr d _ r d ，d d 若给定由未知嵌入映射生成的观测数据集 x t = f ( y ，) ) c 7 r d ，则流形学习的目标 是从观测数据集( x ， 重构嵌入映射厂和对应的低维坐标 y ， 。 上述流形学习的定义可知，流形学习是一类无监督统计学习问题，只知道高 维观测数据集x = “，一，无) ，隐含假定观测数据集x 位于或近似位于一个嵌入 在高维欧氏空间尺d 中的内在低维流形m 上，流形学习的定义中又常把观测数据假 定为x ，= f ( y ，) + g ，i - l ，聆，其中t 表示随机噪声干扰。流形学习通常需要解决 三个问题： ( 1 )内在维数d 的估计： 计算嵌入在高维观测空间中的低维流形的内在维数。内在维数是指描 述数据集中所有数据所需要的独立参数的最小数目。大多数流形学习算法都 要求显示设定流形的内在维数，如图1 1 中的基于神经网络的流形学习方法、 基于互信息的流形学习方法、谱方法中基于局部保持的流形学习方法等都要事 先指定内在维数；谱方法中全局保持的流形学习常常采用特征谱变化的拐点 ( 或者对应方差损失形成的拐点) 来估计内在维数，其中线性谱方法p c a 和 m d s 通常会高估内在维数。实际上，目前已有一些独立于流形学习的内在维 数估计方法，如最近邻域法【i l 】、分形维【1 2 j 、p a c k i n g 数【1 3 1 、测地线最小生成树 【1 4 】等。 ( 2 ) 计算低维坐标y = m ，奶，以) ； 这是绝大多数流形学习算法必须解决的基本问题，需要求出已知观测数 据集彳的对应低维坐标，另外，也要能够给出新的观测数据点的低维表示。 ( 3 ) 重构嵌入映射厂及其逆映射厂- ； 构建从高维空间r d 到低维空间的映射关系厂1 ：r d r d ，能够求出 高维观测数据的低维坐标，这是流形学习算法的基本目标，在高维观测数 据的可视化、特征抽取、基于低维坐标的分类识别等应用方面都是必要的。 嵌入映射厂能够从低维坐标重建观测数据，在数据融合如图像插值、语音 北京交通大学博士学位论文 恢复与识别等方面，当数据集在高维观测空间具有较大曲率时基于流形学 习的这种插值方法优势明显。流形学习算法中许多非线性方法在高维观测 空间和内在低维空间之间建立的映射是隐式的非线性映射，特别是流形学 习的非线性谱方法中在高维观测空间和内在低维空间之间建立的就是隐式 的非线性映射，而且这样的隐式映射只定义在训练数据上，对于新来观测 数据点不能快速明确的映射到低维空间中。线性谱方法如主成分分析( p c a ) 、 多维尺度分析( m d s ) 、局部保持投影( l p p ) 、近邻保持嵌入( n p e ) 、线性 的局部切空间排列( l l t s a ) 等都能在高维观测空间和内在低维空间之间 建立显式的线性变换，缺陷是这些线性方法只能够发现高维观测数据集中的 全局线性结构，而对于数据集中的非线性几何结构无能为力，详细分析比较见 第二章。 1 3 流形学习算法的分类 图1 1 流形学习的分类( 非线性降维技术) 流形学习通常是指一类无监督学习问题，它的主要目标是发现嵌入在高维数 4 l绪论 据空间中观测数据的低维光滑流形。它是一个具有基础性和前瞻性的研究方向， 由于有着广阔的应用前景。近年来流形学习已经成为机器学习、模式识别、数据 挖掘等领域的研究热点之一，形成大量的研究方法。广义流形学习方法包括线性 方法和非线性方法，其线性方法主要指线性降维技术，如主成分分析( p c a ) 、多 维尺度分析( m d s ) 、因子分析( f a ) 、独立分量分析( i c a ) 、典型相关分析( c c a ) 等典型算法，在高维观测数据集具有线性结构时，这些算法具有好的效果；这里 的非线性方法主要是指非线性降维技术( 即通常所指的流形学习) ，主要目的是发 现隐含在高维数据集中的低维非线性结构，已经提出的算法很多，图卜l 按数据处 理的方式、高维数据几何结构的分析方法、局部几何的表示以及目标函数的定义 等进行了分类。 1 4 流形学习的谱方法研究进展 广义流形学习的谱方法包含线性的p c a 、m d s 等传统的线性投影技术和非线 性的i s o m a p 、l l e 、l e 、l t s a 、m v u 等新型流形学习算法( 即基于谱图的流 形学习方法) ，都是通过求矩阵的最大( 或最小) 特征谱对应的特征向量捕获高维 数据集的内在几何结构。流形学习的谱方法求解的优化问题都是凸优化问题，且 都能在多项式时间范围内求出最优解。计算机科学中，谱方法探索高维数据集的 内在流形结构的研究可以追溯到计算机视觉和图像识别的研究。早在1 9 9 5 年，哥 伦比亚大学的n a y a r 等人利用主成分分析( p c a ) ，在对机器人的研究中就发现图 像具有内在维数这