（信号与信息处理专业论文）流形学习及其在模式识别中的应用.pdf

北京邮电大学博士学位论文摘要 流形学习及其在模式识别中的应用 摘要 随着信息技术的飞速发展，数据的采集工作变得越来越容易。然 而数据的海量性、高维性和分布的非线性特性却使人们感到越来越难 以对其进行驾驭和处理。一方面我们可以获取的数据量变得越来越 大；而另一方面，我们却难以找到所需的信息。在此背景下，流形学 习应运而生，并为越来越多的研究者所关注。而其目标是解决高维数 据分析中数据分布非线性所带来的难题，探索高维非线性数据集中的 真实分布几何。 本论文面向模式识别来研究流形学习，其目的在于促进流形学习 在模式识别中的成功应用。论文的主要工作大体上可以分为三个部 分：构造非线性等距映射关系( 即微分同胚) ，探讨数据集的内蕴几 何( 包括内蕴维数、非线性特性、内蕴几何模型) ，计算审美的初步 探索。具体来讲，本文的主要创新性工作包括： l 、提出具有显式等距映射的i s o m a p 算法。针对原i s o m a p 算 法缺少从高维空间到低维空间显式映射关系的不足，基于迭代优化设 计出e i s o m a p 算法，并给出其监督版本s e i s o m a p 算法。由于显 式等距映射的存在，e i s o m a p 和s e i s o m a p 可以用于基于测地线 距离的非线性特征抽取。 2 、提出采用“分两步走 的方式来解决i s o m a p 算法中非线性 等距映射的构造问题。在学习参数化的测地线距离函数和构造距离保 持映射的基础上，实现了i s o m a p 算法中从高维空间到低维空间的 非线性等距映射的显式构造，可以用于基于测地线距离的非线性特征 提取。 3 、展开对非负局部线性重构系数的实验研究，探讨它在内蕴维 数估计和在发掘数据集内精细类别子结构方面的可能应用。实验表 明：在噪声较小、内蕴维数较低的情况下，显著非负局部线性重构系 数的数目和分布可以指示出数据集的内蕴维数；非负局部线性重构系 北京邮电大学博士学位论文摘要 数的分布能够指示出数据集内的精细类别子结构，可以用于对邻域关 系图的剪枝，以提高基于测地线距离的半监督分类的识别精度。 4 、针对某些存在多个类别的数据集，提出主纤维丛( p r i n c i p a l f i b e rb u n d l e ：p f b ) 模型假设。在主纤维丛假设下，提出基于双重邻 域关系图的“丛流形学习 ( b u n d l em a n i f o l dl e a r n i n g ：b m l ) 算法， 用来发现数据集中潜在的精细子结构。在基准数据库上的实验表明： b m l 算法能够发现多类别数据集中的精细子结构，而现有的其他流 形学习算法都不能。 5 、提出计算审美的研究任务，结合h c l 2 0 0 0 数据库完成美观度 标注数据集，利用数据可视化技术给出对美观度标注结果的初步分 析，为计算审美研究的深入开展提供依据。 关键词：流形学习维数约减测地线距离维数估计主纤维丛计算 审美 北京邮电大学博士学位论文 卫订a n 7 0 l dl e ar n 叮ga n di t s a p p l i c a t l 0 n s i np 越门匝r nr e c o g n i t i o n a b s t r a c t w i t ht h ef a n t a s t i cd e v e l o p m e n to fi n f o r m a t i o nt e c h n o l o g y , d a t a c o l l e c t i o nh a sb e c o m ei n c r e a s i n g l ye a s y h o w e v e r , t h el a 砖a m o u n t so f d a t ar e s o u r c e sh a v ep u z z l e dp e o p l e ，d u et ot h e i rh u g eq u a n t i t y , h i g h d i m e n s i o n a l i t ya n dn o n l i n e a r i t y a l t h o u g ht h ed a t ar e s o u r c ei ss u f f i c i e n t ， w ea r ec o n f r o n t i n gw i t ht h ee m b a r r a s s m e n tt h a tt h en e e d e di n f o r m a t i o n c a n n o tb ed i s c o v e r e d a n dt h e n ，an e wr e s e a r c hd i r e c t i o no fh i g h d i m e n s i o n a ld a t aa n a l y s i s ，c a l l e d ，m a n i f o l dl e a r n i n g , e m e r g e da st h e t i m e sr e q u i r e ，a n da t t r a c t sas u r g eo fr e s e a r c hi n t e r e s t s t h eg o a lo f m a n i f o l dl e a r n i n gi st os o l v et h ed i f f i c u l t i e sc a u s e df r o mt h en o n l i n e a r i t y o fd a t ad i s t r i b u t i o ni nh i g hd i m e n s i o n a ld a t a s e t ，a n dt oe x p l o r et h e f a i t h f u li n t r i n s i cg e o m e t r yh i d i n gi nh i g hd i m e n s i o n a ld a t a s e t i nt h i sd i s s e r t a t i o n ，w ee x p a n dm a n i f o l dl e a r n i n gt o w a r d st op a r e r n r e c o g n i t i o na n dt h em o t i v a t i o ni st of a c i l i t a t ei t sa p p l i c a t i o n si np a t t e r n r e c o g n i t i o n t h ew o r ko ft h i sd i s s e r t a t i o nc o n s i s t so ft h r e ep a r t s ：( 1 ) c o n s t r u c t i n gn o n l i n e a ri s o m e t r i cm a p p i n g ( i e d i f f e o m o r p h i s m ) ；( 2 ) i n v e s t i g a t i n g t h ei n t r i n s i c g e o m e t r y ( i e i n t r i n s i cd i m e n s i o n a l i t y , n o n l i n e a r i t ya n dg e o m e t r i c a lm o d e l ) o fh i g hd i m e n s i o n a ld a t a s e t ；a n d ( 3 ) a t t e m p t i n gt o w a r d sc o m p u t a t i o n a la e s t h e t i c s s p e c i f i c a l l ys p e a k i n g ，t h e f o l l o w i n gi n n o v a t i v ew o r k sa r ea c h i e v e di nt h i st h e s i s ： 1 p r o p o s e da ne i s o m a pa l g o r i t h m ，w h i c ha i m sa tr e m e d y i n gt h e d e f i c i e n c yo fl a c ko fa ne x p l i c i tn o n l i n e a ri s o m e t r i cm a p p i n gi nt h e i i i 北京邮电大学博士学位论文 a b s t r a c t o r i g i n a li s o m a pa l g o r i t h m b a s e do ni t e r a t i v em a j o r i z a t i o np r o c e d u r e ，a v e r s i o no fi s o m a pa l g o r i t h mw i t he x p l i c i tn o n l i n e a ri s o m e t r i cm a p p i n g ( e - i s o m a p ) i sp r e s e n t e da n di t ss u p e r v i s e dv e r s i o n ( s e i s o m a p ) i s a l s og i v e n o w n i n gt ot h ee x i s t e n c eo fe x p l i c i ti s o m e t r i cm a p p i n g ， e i s o m a pa n ds e i s o m a pa l g o r i t h m sc a l lb e u s e df o rn o n l i n e a r f e a t u r ee x t r a c t i o nb a s e do ng e o d e s i cd i s t a n c e 2 p r o p o s e da t w o - s t e p a p p r o a c hf o rc o n s t r u c t i n gt h en o n l i n e a r i s o m e t r i cm a p p i n go fi s o m a p b a s e do nl e a r n i n go fp a r a m e t e r i z e d g e o d e s i c d i s t a n c ef u n c t i o na n dc o n s t r u c t i n go fd i s t a n c e - p r e s e r v i n g m a p p i n g ( i e t r i a n g u l a t i o n ) ，t h en o n l i n e a ri s o m e t r i cm a p p i n gw h i c hi s f r o mh i g hd i r m e n s i o n a le u c l i d e a ns p a c ei n t ol o wd i m e n s i o n a le u c l i d e a n s p a c ei sc o n s t r u c t e di na ne x p l i c i tw a ya n daf r a m e w o r kf o rf e a t u r e e x t r a c t i o nw j t bi s o ma pi sa l s of o r m u l a t e d 3 i n v e s t i g a t e d t h eb e h a v i o ro f n o n n e g a t i v e 1 0 c a ll i n e a r r e c o n s t r u c t i o nc o e 衢c i e n t sa n dd i s c u s s e dt h e i rp o s s i b l ea p p l i c a t i o n sf o r e s t i m a t i n g t h ei n t r i n s i c d i m e n s i o n a l i t ya n dd i s c o v e r i n gt h es u b t l e s t r u c t u r eh i d i n gi nh i g hd i m e n s i o n a ld a t a s e t s e x p e r i m e n t a lr e s u l t sh a v e s h o w nt h a t ：( 1 ) t h en u m b e ro ft h ed o m i n a n tn o n n e g a t i v el o c a l l i n e a r r e c o n s t r u c t i o nc o e 硒c i e n t si n d i c a t e st h ei n t r i n s i c d i m e n s i o n a l i t yo f d a t a s e tp r o v i d e dt h en o i s yl e v e li sl o wa n dt h ei n t r i n s i cd i m e n s i o ni s s m a l l ；( 2 ) t h en o n n e g a t i v el o c a ll i n e a rr e c o n s t r u c t i o nc o e f f i c i e n t sc a n d i s c o v e rt h es u b t l ei n t r i n s i cs t r u c t u r eh i d i n gi nd a t a s e ta n dh e n c ec a nb e u s e df o rc o n d u c t i n gt h ep r u n i n go p e r a t i o nt oi m p r o v et h ea c c u r a c yo f g e o d e s i cd i s t a n c eb a s e ds e m i s u p e r v i s e dc l a s s i f i c a t i o n 4 p u tf o r w a r dap r i n c i p a lf i b e rb u n d l e ( p f b ) m o d e la s s u m p t i o nt o f o r m u l a t et h ei n t r i n s i cg e o m e t r yo fc e r t a i nd a t a s e t ，w h i c hc o n s i s t so f s a m p l e sf r o mm u l t i p l ec l a s s e s u n d e rp f ba s s u m p t i o n ，w ep r e s e n t e da n a i v eb u n d l em a n i f o l dl e a r n i n g ( b m l ) a l g o r i t h m ，w h i c hu t i l i z e st h e d o u b l en e i g h b o r h o o dg r a p h s ，t od i s c o v e rt h es u b t l es t r u c t u r eh i d i n gi n d a t a s e tw h i c hl i e so nb u n d l em a n i f o l d 5 b r o u g h tf o r w a r dan o v e lr e s e a r c ht a s k ，t e r m e da sc o m p u t a t i o n a l a e s t h e t i c s ，w h i c hj u d g e st h eh a n d s o m e n e s s o fc h i n e s eh a n d w r i t i n g c h a r a c t e rb yc o m p u t e ra u t o m a t i c a l l y p r i m a r yd a t a s e t sh c l 2 0 0 0 一c a i v 北京邮电大学博士学位论文a b s t ra c t t o w a r d st oc o m p u t a t i o n a la e s t h e t i c sa r ep r e p a r e da n ds o m ee x p l o r a t o r y e x p e r i m e n t so nh c l 2 0 0 0 一c ad a t a s e ta r eg i v e n k e yw o r d s ：m a n i f o l d l e a r n i n gd i m e n s i o n a l i t y r e d u c t i o n g e o d e s i cd i s t a n c e i n t r i n s i cd i m e n s i o n a l i t ye s t i m a t i o n p r i n c i p a l f i b e rb u n d l e c o m p u t a t i o n a la e s t h e t i c s v 北京邮电大学博士学位论文符号说明 符号说明 m 输入数据的维数，即高维观测空间的维数； p 输入数据所占据的线性子空间的维数； d 数据的内蕴维数( i n t r i n s i cd i m e n s i o n a l i t y ) 和输出数据的维数，即低 维欧氏空间的维数； r 肼输入数据对应的高维欧氏空间； r p 输入数据所占据的线性子空间( 可通过主成分分析获得) ； 输出数据所对应的低维欧氏空间； 膨数据分布所构成的嵌入流形； p 数据分布所构成的嵌入丛流形( b u n d l em a n i f o l d ) ； s 1 维圆周； r 环面，即两个1 维圆周的拓扑积s 1x s l ； c 。光滑 n b g ( v ，e ，形) 以y 为顶点集，e 为边集，为权值集合的邻域关系图 ( n e i g h b o r h o o dr e l a t i o n s h i pg r a p h ) 创新性声明 本人声明所呈交的论文是本人在导师指导下进行的研究工作及取得的研究 成果。尽我所知，除了文中特别加以标注和致谢中所罗列的内容以外，论文中不 包含其他入已经发表或撰写过的研究成果，也不包含为获得北京邮电大学或其他 教育机构的学位或证书而使用过的材料。与我一同工作的同志对本研究所做的任 何贡献均已在论文中作了明确的说明并表示了谢意。 申请学位论文与资料若有不实之处，本人承担一切相关责任。 本人签名： 辛救 关于论文使用授权的说明 学位论文作者完全了解北京邮电大学有关保留和使用学位论文的规定，即： 研究生在校攻读学位期间论文工作的知识产权单位属北京邮电大学。学校有权保 留并向国家有关部门或机构送交论文的复印件和磁盘，允许学位论文被查阅和借 阅；学校可以公布学位论文的全部或部分内容，可以允许采用影印、缩印或其它 复制手段保存、汇编学位论文。 本学位论文不属于保密范围，适用本授权书。 本人签名： 导师签名： 日期：叩亿 日期：加7 ，2 ，2 誓1 北京邮电大学博士学位论文第一章绪论 第一章绪论 在数据挖掘、信息检索、机器视觉等模式识别领域中都越来越多的面临着同 样的一个问题：如何处理数据量大、维数高、非线性的数据集。事实上，不仅是 在模式识别领域，在物理学、信息生物学等其它领域，同样面临着这样的问题， 比如恒星光谱观测、人类基因分布等。概括起来，我们需要解决的问题是如何从 大规模、高维度的数据集中学习和发现其内在规律性。这正是数据的维数约减技 术所要解决的问题。 在传统的数据维数约减中，其基本思想是对样本的特征进行线性组合，比如 主成分分析( p c a ：p r i n c i p a lc o m p o n e n ta n a l y s i s ) ，因子分析( f a ：f a c t o r s a n a l y s i s ) ，以及典型相关分析( c c a ：c a n o n i c a lc o r r e l a t i o n a n a l y s i s ) 。它们只能 够发现数据中的全局线性结构，而对于数据集中的非线性几何结构无能为力。然 而，在大多数的实际应用中，我们所面对的数据集是分布在高维观测空间中的非 线性几何结构上的。因此，我们需要能够有效处理数据集中非线性几何结构的维 数约减技术。 本章将围绕“流形这一现代数学中最基本的概念，阐述流形概念的引入、 流形学习的提出、流形学习的研究任务和存在着的问题等，并论述论文的选题依 据，最后简要说明论文的研究思路和章节安排。 1 1 从欧氏空间到流形 1 1 1 流形的概念 流形( m a n i f o l d ) ，即拓扑流形，它的定义如下【1 】： 设m 是h a u s d o r f f 空间。若对于任意一点x m 都存在m 上的一个邻域u ， 其中，【厂同胚( h o m c o m o r p h i s m ) 于，z 维欧氏空间尺朋的一个开集矿，则称m 是 朋维拓扑流形，简称为流形。换句话说，m 维拓扑流形即为局部欧氏的、第二 可数的h a u s f o r t f 空间。 北京邮电大学博士学位论文第章绪论 进一步，若对于任意一点工m 都存在m 上的一个邻域u 微分同胚 ( d i f f e o m o r p h s i m ) 于m 维欧氏空间r ”的一个开集矿，则称m 是m 维微分流形。 微分流形是2 0 世纪数学中最有代表性的基本概念，它是描述许多自然现象 的一种空间形式。关于流形的数学理论可以参考【l 】【2 】【1 2 8 1 1 1 2 9 】。 由流形的定义可知，流形是欧氏空间在大尺度分析情况下的推广，而欧氏空 间是它的特例，即，欧氏空间是一个平凡流形。反过来看，流形在局部上与欧氏 空间存在着同胚映射，因此，从局部上看，流形与欧氏空间几乎一样。 值得注意的是，流形上的点一般并没有整体坐标，但我们可以通过在该点的 邻域内与欧氏空间建立同胚映射，从而把映射到欧氏空间中所得的像点作为流形 上该点的坐标。比如，选择测地线为坐标轴可以构造高斯法坐标系( g a u s s i a n n o r m a lc o o r d i n a t e ss y s t e m ) ，它是通过在某点p ( 选择为坐标原点) 的邻域内建 立指数映射( e x p ，：乙mjm ，其中乙m 为p 点的切空间) 来实现的。 1 1 2 流形的例子 具体地讲，一维流形即曲线，二维流形即曲面。高维流形即为曲线和曲面在 高维情况的类似物。如图1 1 所示，它们是嵌入在三维欧氏空间中的二维流形( 即 二维曲面) 。由于高于三维的空间我们难以获得直观认识，所以我们以二维曲面 作为获取流形直观的例子。事实上，最平凡的流形是通常我们熟知的欧氏空间， 最不平凡但最频繁接触的流形是地球表面。通常，在小尺度小范围内我们可以把 地面看作平面，但在航空和航海的航线测量这种大尺度分析的情况下，我们必须 考虑到地球表面存在着曲率。 图1 1 三维欧氏空间中的二维流形( 即曲面) ：s w i s sr o l l ，s - c u r v g ，f i s h - b o w l 2 北京邮电大学博士学位论文第一章绪论 欧氏空间是最平凡的流形，是全局线性的。所谓欧氏空间具有“全局线性 结构，是说存在着定义在整个空间上的笛卡尔直角坐标系；也就是说，用一个坐 标系( 或一组坐标基底) 就可以把整个欧氏空间盖住，因此欧氏空间是最简单的 空间。对于高维观测空间，我们的传统做法是把它看作高维欧氏空间，建立笛卡 尔坐标系，把欧几里德几何在三维内的一些概念推广过去，进而，处理高维观测 空间中的数据时，把高维的数据点看作是高维欧氏空间中分布的点，点之间的几 何距离沿用欧氏几何的直线距离。然而，这种做法对于分布在流形上的数据并不 恰当，因为高维空间仅仅在局部上才能认为是欧氏的，欧氏距离只有在局部尺度 下才能近似于其真实距离( 测地线距离) 。 1 1 3 理论物理中从欧氏空间到流形的观念转变 e i n s t e i n 在1 9 0 5 年所提出的狭义相对论中采用的背景物理时空( 即适合描述 物理定律的空间) 对应于数学上的四维闵氏空间；而在1 9 1 5 年提出的广义相对 论中，则以任意四维流形m 为背景物理时空。在e i n s t e i n 之前，物理学及哲学都 基于日常的经验，把将三维空间用欧氏几何来表示看成是自然的、天经地义的事 情。但e i n s t e i n 引进一个革命性的观点，他认为描述物理现象的物理时空不一定 是欧氏空间，物理背景时空的几何性质应该由空间中物质( 或能量) 的实际分布 来决赳3 】【4 l 一这是广义相对论中的基本内容之一 正像没有任何理由认为物理时空天经地义地必须是一种抽象的欧氏空间一 样，我们没有理由认为高维观测数据天经地义的分布在欧氏空间上。物理时空是 和物质的分布有关的；类似地，我们可以认为：高维观测数据的几何分布是由数 据的内蕴性质所决定的，而特定模式识别问题的解决需要参考其数据集内特定的 内蕴几何约束在这个假设下，我们不难理解模式分类中关于“没有天生优越的 分类器刀( n of r e el u n c h ) 的著名论断【4 。 1 2 高维数据分析中流形概念的引入 1 2 1 心理测量中的研究报告 把高维空间中的数据当作高维欧氏空间中的点的这种处理方式源于心理测 3 北京邮电大学博士学位论文第章绪论 量( p s y c h o m e t r i c s ) 领域。在心理测量领域中，研究人员把刺激信号通过高维空间 中的点表达，把接收到的刺激信号的相似性用空间中点的几何近邻关系来表达。 实际上，这是模式识别中数据处理时默认的基本假设。但心理学家们在研究中发 现：假设数据分布在一些特殊的几何结构上，能够对数据给出很好的解释和预测。 比如光谱色度的数据在圆周上表达，色彩空间用弯曲的黎曼流形表达，音调数据 分布用螺旋线表达，而气味和味觉数据的分布分别以棱柱和四面体表达，这很好 地解释和预测了观察到的现象【5 】。这些研究结果说明，我们有必要重新考证高维 空间中数据的真实分布结构。 近年来，在神经生理学方面的研究结果进一步证实了高维观测数据空间中流 形结构的存在。 1 2 _ 2 神经生理学上的发现 2 0 0 0 年，s e u n g 和l e e 在科学上发表了题为“t h em a n i f o l dw a y so f p e r c e p t i o n 的研究报告【6 1 。在报告中，他们提出视觉感知的流形结构假说，认 为：视觉记忆是以稳态流形( 或连续吸引子) 形式存贮的，人类的视觉感知神经 系统具有捕获非线性流形结构的能力。 图1 - 2 视觉感知中的流形 图1 2 中展示了视觉感知中的流形结构。实际上，视网膜的图像是来自于 感光器细胞信号的集合。如果这些数据被作为在抽象图像空间中的坐标，那么一 4 北京邮电大学博士学位论文第一章绪论 个图像就可以被表达为一个点。尽管被描述的是只有三维的图像，但最后图像空 间的维数却等于感光器细胞的数目。当人脸被旋转，则它们生成一个嵌入在图像 空间中的非线性曲线。如果图像的尺寸、光线等其他连续变异因素也发生改变， 那么图像将位于一个低维流形上。要识别人脸，人脑必须使得同一个人的全部图 像等同于同样的流形，但要区分来自不同流形的图像( 即来自不同人的图像) 。 流形是感知的基础，大脑一定拥有某种表达流形的方式。通向这种表达方式 本质的线索可能会来自大量神经元群体中是如何编码的研究工作中。神经元群体 的行为典型地被通过神经元激发率集合所描述，而且这样可以被表达成在抽象的 高维空间中的一个点，空间的维数等于神经元的数目。神经生理学家们常常发现： 在神经元群体中，各个神经元的激活率可以写成一个由少量变量控制的光滑函 数。这暗示着神经元群体活动性被限制于处在一个低维流形上 人能够在瞬间识别出同一个人在光照、角度等发生变化后的身份，而让计算 机来识别却非常困难。显然，计算机在模拟人的识别能力上一定遗失了某个重要 环节。事实很可能是：人能够自然地感知数据的内蕴( i n t r i n s i c ) 低维结构，而 计算机却没有。因此，如何让计算机具备这种感知数据的内蕴低维结构的能力是 值得我们认真思考的研究方向。 1 2 3 流形概念引入的原因总结 现代数据分析与处理、机器学习、模式识别中之所以要引入“流形，可以 概括为以下几方面的原因： 1 、流形是2 0 世纪数学最有代表性的基本观念，是描述许多自然现象的一种 空间形式。欧氏空间是一种特殊的抽象空间，而对于感知数据的观测数据空间， 我们没有任何理由假设它们必须处在欧氏空间它们可以处于一种更普遍和 一般的空间结构上。过去我们认为数据点存在于欧氏空间中，是为了简单化我们 的研究；而面对复杂的现实问题，我们需要利用现代数学理论，重新审视研究对 象。认知心理学的研究结果表明人类的认知系统具有有效获取非线性结构的能 力，特别是认知的流形结构假说，暗示人们要研究数据集中存在的低维流形。 2 、实验证实：在图像流形中的确存在大的曲率1 7 1 。这暗示着在高维的图像 空间中存在子流形结构，获取高维图像空间中的低维流形结构才能捕获图像空间 北京邮电大学博上学位论文 第一章绪论 的本质信息，才能实现与人类视觉感知能力相比拟的机器视觉。如图1 3 ，在图 像空间中，沿着图像流形才能找到“合理”的图像，而直接对图像进行线性组合 不能获得满意的插值结果。 3 、在数据挖掘、信息检索、生物信息等领域中，需要处理高维非线性数据 的有效方法，需要发现和重构数据集合中内在规律性的有效工具。 图1 - 3 沿着图像流形能够合成合理的图像睛1 1 3 流形学习的提出、定义以及基本问题 囤 “流形学习 ( m a n i f o l dl e a r n i n g ) 这一术语是由b r e g l e r 和o m o h u n d r o 在1 9 9 5 年发表的可视语音识别( v i s u a ls p e e c hr e c o g n i t i o n ) 文章中首次提出的【8 】【9 】。 1 3 1 流形学习的定义 流形学习作为通过获取数据集的内蕴几何来进行数据分析的技术，可以定义 为：由有限样本点集合来计算嵌入在高维欧氏空间r ”中的d 维流形m 的模型的 问题。 粗略地讲，从欧氏空间转变到流形，要求我们从整体、从数据集的内蕴几何 来分析数据，从而获取与数据内蕴几何相一致的低维参数化( 1 0 wd i m e n s i o n a l p a r a m e t e r i z a t i o n ) 。这个过程即所谓“流形学习”。 假设数据均匀采样于高维欧氏空间中的低维流形上，流形学习的目标是从高 维观测数据中恢复低维流形结构，即找到高维空间中的低维流形，实现数据的维 数约简或数据可视化，并获得相应的映射关系。 北京邮电大学博士学位论文第一章绪论 s i l v a 和t e n e n b a u m 给出了“流形学习的确切数学描述【捌： 给定数据集x = 五，i = 1 ，) cr ”，假定x 中的样本是由低维空间中的数 据集】r 通过某个未知的非线性变换厂所生成，即 而：f ( y i ) + c i ， 其中毛表示噪声，咒ycr d ，d 所，f ：r d 专r 舶是c 。的嵌入映射那么， 流形学习的任务是基于给定的观测数据集x ： ( 1 ) 获取低维表达】，= m ，i = 1 ，n c r d ； ( 2 ) 构造从高维空间到低维空间的非线性映射厂1 ：r 朋- - 4 1 3 2 流形学习中的基本问题与基本思想 实际上，流形学习所研究的基本问题可以概括为以下三个： ( 1 ) 维数估计：准确估计嵌入在高维观测空间中的低维流形的内蕴维数1 ( i n t r i n s i cd i m e n s i o n a l i t y ) d ； ( 2 ) 维数约减：获取数据在低维空间内蕴坐标2 ( i n t r i n s i cc o o r d i n a t e s ) y = 咒，f = l ，n ，若要实现对高维数据的可视化分析，则需要获得数据集的2 或3 维的参数化表达； ( 3 ) 构建映射：构建从高维空间到低维空间的非线性映射关系广：r ”一，r 这对于把流形学习算法应用于模式识别中的特征抽取和分类是必要的。 流形学习的基本思想可以概括为：强调数据集的整体性，试图通过局部合并， 以整体的方式来发现和重建数据集的内在规律。发现和重建数据集中潜在的内蕴 几何结构，这是流形学习的基本目标。 1 3 3 流形学习的研究现状 关于第一个基本问题的研究现状：数据集合的内蕴( 固有) 维数( i d ：i n t r i n s i c d i m e n s i o n a l i t y ) ，被定义为：描述数据集中所有数据所需要的自由参数( 或独立 坐标) 的最小数目。近年来，关于d 估计比较活跃的研究主要是基于分形维定 1 也称为拓扑维数，即描述位于该流形上一个点所需要的参数的最小数目 2 在m d s 文献中，被称作构造点( c o n f i g u r a t i o n p o i n t s ) ；在模式分类中，称为内蕴特征( i n t r i n s i c f e a t u r e ) 7 北京邮电大学博士学位论文第一章绪论 义的。基于分形维的维数估计，它能够成功探索数据集的特定几何性质，但这种 估计维数的方法需要充足的样本数。对于样本数少、观测空间的维数比较高的情 况，比如图像数据集，基于分形维的方法将出现欠估计( u n d e r - e s t i m a t i o n ) 4 0 1 。 在第二章第一节将给出详细的综述。 关于第二个基本问题的研究现状：这是到目前为止得到最广泛关注的问题， 有多个典型的流形学习算法被相继提出，包括i s o m a p 1 1 1 ，l l e t l 2 】【1 3 】，l a p l a c i a n e i g e n m a p s t l 4 1 ，h e s s i a nl l e t l 5 1 ，c h a r t i n 9 1 6 1 ，l t s a l l 7 】，l o g m a p 1 8 】【1 9 】，m v u s d e l 2 0 ， d i f f u s i o nm a p t 2 1 】等。详细的综述，在第二章给出。 关于第三个基本问题的研究现状：构造从高维空间到低维空间的非线性映射 的问题，实现起来比较困难，关于这一方面的研究不多。从微分几何和微分流形 的理论体系上看，单位分解定理可以为构造非线性映射提供理论支撑( 参考附录 3 ) 。 1 4 论文的选题依据 本论文主要研究流形学习和流形学习在模式识别中的应用，下面从两个方面 阐述本论文的选题依据。 1 4 1 流形学习中存在的问题 2 0 0 0 年s c i e n c e 上发表的三篇文章i s o m a p 1 1 1 ，l l e t l 2 1 和感知的流形 假说 6 1 ，被认为流形学习的研究热潮开始的标志。通过对流形学习领域大量文献 资料的阅读，我们归结出如下一些有待解决的问题： l 、大部分流形学习算法只定义在给定的数据集上3 ，只能用于对数据集的维 数约减( 低维参数化) 和数据可视化。也就是说，通常算法只获取给定数据集在 低维空间中的数据构造点“) ，而并不能提供从高维空间到低维空间的非线性映 射关系f _ 1 ：r ”专r 一。然而，非线性映射关系对于把流形学习算法应用于模式识 3 严格地讲，它们定义在给定数据集及其局部邻域上。 北京邮电大学博士学位论文第一章绪论 别中的特征抽取任务是十分必要的，缺少这一映射关系将难以处理未见新样本。 2 、在另一个角度看，流形学习的研究仍然限于自身完善和发展阶段，即作 为探索性数据分析工具的研究。而流形学习是作为高维数据分析方面的最新进 展，它必将引起模式识别概念和理论层面的革命。如何运用流形学习中的基本概 念和原理解决模式识别问题值得研究。在基于统计的模式分类理论中，对数据集 中存在内蕴几何结构的关注尚且很少。流形学习理论的出现启发我们要关注数据 集中的内蕴几何结构，要在分类过程中充分利用到数据集中的内蕴几何约束。 3 、现有的流形学习算法基于单一流形的假设前提下。当数据集中存在多个 流形时，现有的流形学习算法都将失效，它们只能被分别单独应用在各个“聚类 的数据上。而对于模式识别问题，人们关心的是由多个类别构成的数据集中存在 着怎样的几何结构。通常，一个类别对应着一个流形，不同类别对应于位于不同 位置的流形。比如c o i l 2 0 数据库【讲1 中，共有2 0 个类别的物体图像，每个类别 采集了具有不同旋转角度的7 2 个样本( 每隔5 度采样一次) 。对每个类别的数据 利用i s o m a p 算法完成数据可视化后，可以发现：每个类别所对应的流形都是s 1 ( 在微分同胚的意义下) 。显然，不同类别的数据集共享着同样的流形结构。这 说明流形结构不是类别之间相互区分的“特征一，流形是类别中数据采样过程中 涉及到的潜在变量( 即自由度) 的变化所张成。不同类别之间的区别在于它们在 高维空间所占据的位置不同。面对这种任务，我们需要一种能同时观察这些不同 类别中流形的流形学习算法。当然，我们需要先认识清楚由多个类别构成的数据 集的内在几何结构，这是个基本问题。 4 、s e u n g 和l e e 认为：要识别人脸，人脑必须使得同一个人的全部图像等 同于同样的流形，但要区分来自不同流形的图像( 即来自不同人的图像) 【6 】。那 么，不同人所对应的流形之间的相互关系如何? 怎样利用这种内在结构完成模式 识别任务呢? 类别内的距离，类别之间的距离分别具有怎样的几何意义呢? 鉴于以上几方面问题的存在，流形学习是一个具有实际意义和研究价值的课 题。这是本论文选题的科学依据。此外，我们还可以从模式识别角度来审视流形 学习研究的必要性。 9 北京邮电大学博士学位论文第一章绪论 1 4 2 模式识别所面临的困难 我们能够如此轻而易举地辨识人脸、识别语音、阅读手写文字、从口袋里掏 出钥匙、或者根据气味判断苹果是否成熟，这大大掩盖了隐藏在这些貌似简单的 识别行为背后的非常复杂的处理机制【4 1 1 。模式识别主要研究计算机实现人的模式 认知的能力，然而模式( p a t t e r n ) 在人的大脑中究竟如何存储却始终未能明确描 述。心理学认为，大脑中关于事物的模式有一个概括的形式。比如人脸识别任务 中，每一张脸对应于一组信号，它们占据一定的存储空间，即构成一个模式。而 一个人在不同姿态和不同光照下会表现出万种不同情况，这需要刀个存储空间来 描述，即疗种模式。基于这种思想，同时为简化计算机处理，常常使用多个模式 的平均构成“均值模板，这使得模式判决的准确度大为降低。这种多模式的处 理并没有考虑到模式之间的内在几何关系，使得这种平均显得没有理论依据。然 而，这却是模式识别的主要心理学基础。模式识别在现阶段面临的困难促使我们 要重新考察模式本身该如何定义，需要我们重新研究模式之间的内蕴几何。 关于学习的一般性分析理论中最具有代表性的是统计学习理论【2 4 】，它在数学 上是完备的，着重于研究学习的泛化能力；然而，统计学习理论并没有建立与人 类认知的联系，也没有探究数据中的内在几何结构，因此，它并未解决模式识别 所遭遇的困难。 流形学习作为一种探索性数据分析工具，探索的是掩盖在识别行为背后的复 杂的数据处理机制，它是对于高度复杂的神经和认知系统信息处理机制的模仿。 从根本上说，模式识别的目的在于重建产生我们所感知到的模式的内在模型。然 而，模式识别的两个分支统计模式识别和结构模式识别都停留在分类的层面 上，没有进一步探索“模式的内在模型 。流形学习的提出，要求我们重新审视 模式识别的框架。因此，我们需要从流形学习的视角研究模式识别，或者研究如 何改造流形学习算法使之能被应用于模式识别的任务中。 1 5 论文的研究思路和章节安排 本论文的研究工作是围绕着流形学习及其在模式识别中的应用从流形 学习在模式识别中的朴素应用到高级应用的过程中涉及到的关键问题展开 1 0 北京邮电大学博士学位论文第一章绪论 的。事实上，研究工作的展开过程也正是对数据集内在几何性质认识的不断深化 的过程：从构造高维数据与低维表达之间的微分同胚( 非线性等距映射) 到 估计数据集的内蕴维数通过基于测地线距离的分类来认识数据集的非线性 特性最后到纤维丛结构假设等。这是本论文工作的两条线索。 1 5 1 论文的研究思路 本论文的研究思路可以概括为：面向模式识别来研究流形学习，其目的在于 促进流形学习算法在模式识别中的成功应用。主要研究思路如下： l 、流形学习是国内外近年来的研究热点，因此，本文首先查阅了国内外大 量相关文献，对流形学习的研究进展情况进行了全面的综述。 2 、针对i s o m a p 算法，研究从高维空间到低维空间的非线性等距映射的构 造问题。在i s o m a p