（计算机软件与理论专业论文）基于流形的降维方法及其在计算机视觉中的应用.pdf

摘要 摘要 真实世界应用中的许多高维数据都能被建模成为位于低维的线性非线性流 形附近的数据点。以图像数据集为例，数据集中的潜在变化对应于诸如物体姿态、 光照或人脸表情等等的连续物理变化。从那些流形上带噪声采样得来的数据点中 发现流形的结构，是非监督学习中非常具有挑战性的问题。近年来，人机交互方面 与流形相关的方法已经成为了日益热点的研究领域。 真实世界的流形也与人的视觉感知密切相关。人工神经网络是对真实世界 流形进行建模和解释的强有力工具。通过操纵所学习到流形的低维自由参数， 我们还能够合成或者估计出我们所期望的真实世界数据。这种学习和合成的双 向( b i - d i r e c t i o n a l ”) 过程与典型的人类认知行为非常近似。在人类的行为中通常 都是从无组织的观察中学习，然后使用学习到的知识去推测未知的事物。 传统的降维方法如主元分析( p c a ) 受制于它的线性性质。其他的方法，包括 自组织图、流形学习和核方法等，被提出来处理低维流形的非线性性质。但是这些 方法又有他们自身的局限。本文的方法从那些前人的工作中受到启发并且进行了 改进。按照所描述的潜在低维结构复杂程度递增的顺序，本文的主要贡献如下： 1 提出了一种新的基于自相关矩阵的均值更新增量主元分析算法。这种方法 在使用了在输入数据表示上的两个变换。更新的特征子空间进行重新居中，而无 需重新计算旧数据的自相关矩阵。旧信息所需的存储空间和自相关矩阵的维数保 持恒定，而不是随着输入数据的总数增加。在更新完成后不需要存储旧的数据。与 目前已有的方法比较，本文提出的方法对于视觉中，要求更低计算时间的子空间 学习和识别任务是一个好的选择。 、 2 提出了一种新的计算高效的局部主元分析算法来结合n g a s - p c a 和p c a s o m 的优点。每一个局部单元都有与之对应的平均向量和协方差矩阵。算法中 使用的新的竞争度量隐式地结合了重构误差和输入数据到单元中心的距离。在该 算法中，数据分布的学习过程中消除了额外的主元空间更新步骤。该模型适用于 非线性的模式学习和回忆。在算法训练过程完成之后，数据分布被表示成为了一 系列的局部线性单元。并且在这种模式表示中不需要关于最优主元空间的先验信 息。 3 提出了一种新的变形模型，即泛化的拓扑保持自组织图( g t p s o m ) ，来将拓 扑保持的自组织映射机制引入神经元竞争的变形模型。这种模型是从视觉感应自 摘要 组织 蛩( v i s o m l 中获得启发。在v i s o m 中，数据的映射在神经元图上同时保持了 输入数据点之间的距离和整个输入空间的拓扑结构。本文提出的g t p s o m 模型由 对局部边界变化施加约束的自适应力场来并行驱动的。算法通过区域辅助的活动 轮廓( r e g i o na i d e da c t i v ec o n t o u r ) 和水平集( l e v e ls e t s ) 方法来实现。g t p s o m 模型适用于精确的边界检测和具有较强边界强度起伏的复杂形状恢复。 4 提出了一种基于流形的新方法来建一个输入空间和特征空间之间的非线性 映射，从而不再孤立的考虑流形的学习和合成。这个非线性映射是由在输入空间 中建立局部生成单元模型并且在特征空间中构建全局仿射变换来实现的。这种形 式的方法导致样本外数据点在输入空间和特征空间之间来回转换可以由简单的解 析解得到。本文的方法避免了在流形学习与双向样本外数据扩展中的交替最小二 乘解或局部极小的问题。此外，本文的方法还能估计潜在的流形维数，且对最近邻 居的个数有较好的鲁棒性。 关键词：降维，流形学习与合成，自组织映射，增量主元分析 i i a b s t r a c t a b s t r a c t m a n yh i g hd i m e n s i o n a ld a t ai nr e a lw o r l da p p l i c a t i o n sc a nb em o d e l l e da sd a t a p o i n t sl y i n gc l o s et oal o wd i m e n s i o n a ll i n e a r n o n l i n e a rm a n i f o l d t h eu n d e r l y i n g v a r i a t i o n si ni m a g ed a t as e t sc o r r e s p o n dt ot h ec o n t i n u o u sp h y s i c a lc h a n g e ss u c h a sp o s e ，i l l u m i n a t i o no fo b j e c t so re x p r e s s i o n so ft h eh u m a nf a c e s d i s c o v e r i n gt h e m a n i f o l ds t r u c t u r ef r o mas e to fn o i s yd a t ap o i n t ss a m p l e df r o mt h em a n i f o l di sv e r y c h a l l e n g i n gi nt h eu n s u p e r v i s e dl e a r n i n g r e c e n t l y , t h em a n i f o l dr e l a t e dm e t h o d s f o rh u m a n - c o m p u t e ri n t e r a c t i o nh a v eb e c o m ea ni n c r e a s i n g l yh o tr e s e a r c ha r e a t h eh u m a nv i s u a lp e r c e p t i o ni sa l s oc l o s e l yr e l a t e dt ot h er e a lw o r l dm a n i - f o l d a r t i f i c i a ln e u r a ln e t w o r k sc a nb eu s e da sap o w e r f u lt o o l f o rm o d e l l i n ga n d i n t e r p r e t i n gt h em a n i f o l ds t r u c t u r e si nr e a lw o r l dd a t a b ym a n i p u l a t i n gt h el o w d i m e n s i o n a lf r e ep a r a m e t e r so ft h el e a r n e dm a n i f o l d ，o n ec a na l s os y n t h e s i z eo re s - t i m a t et h ee x p e c t e dr e a l - w o r l dd a t a t h e “b i - d i r e c t i o n a l p r o c e s so fl e a r n i n ga n d s y n t h e s i si sv e r ym u c ha k i nt ot h et y p i c a lh u m a nc o g n i t i v eb e h a v i o r s ，i nw h i c ho n e l e a r n sf r o mt h eu n o r g a n i z e do b s e r v a t i o n sa n di n f e r st h eu n k n o w nu s i n gt h el e a r n e d k n o w l e d g e t r a d i t i o n a ld i m e n s i o n a l i t yr e d u c t i o nt e c h n i q u e ss u c ha sp r i n c i p a lc o m p o n e n t a n a l y s i s ( p c a ) s u b j e c tt ol i n e a r i t y o t h e rm e t h o d si n c l u d i n gs e l f - o r g a n i z i n gm a p s ( s o m ) ，m a n i f o l dl e a r n i n g ，a n dk e r n e lm e t h o d ，h a v eb e e nd e v e l o p e dt od e 蛆w i t h t h en o n l i n e a r i t yo ft h el o w - d i m e n s i o n a lm a n i f o l d s b u tt h e s em e t h o d sh a v et h e i r l i m i t a t i o n s o u ra p p r o a c hd r a w si n s p i r a t i o nf r o m a n di m p r o v e su p o nt h ep i o n e e r i n g w o r k t h em a i nc o n t r i b u t i o n so ft h i st h e s i sa r ea sf o l l o w s ： 1 an e wm e a n - s h i f t i n gi n c r e m e n t a lp c am e t h o di sp r o p o s e db a s e do nt h e a u t o c o r r e l a t i o nm a t r i x t h i sm e t h o de m p l o y st w ot r a n s f o r m a t i o n so nt h er e p r e - s e n t a t i o no ft h et r a i n i n gd a t a t h eu p d a t e de i g e n - s u b s p a c ei sr e - c e n t e r e dw i t h o u t r e c o m p u t et h ea u t o c o r r e l a t i o nm a t r i xo ft h eo l dd a t a m o r e o v e r ，t h es t o r a g er e - q u i r e m e n to ft h eo l di n f o r m a t i o na n dt h ed i m e n s i o no ft h ea u t o c o r r e l a t i o nm a t r i x r e m a i nc o n s t a n ti n s t e a do fi n c r e a s i n gw i t ht h en u m b e ro ft o t a li n p u td a t a t h e r e s n on e e dt os t o r et h eo l dd a t aa f t e rt h eu p d a t i n g c o m p a r e dt ot h ee x i s t i n ga l - g o f i t h m s ，t h ep r o p o s e dm e t h o di sc o m p u t a t i o n a le f f i c i e n tf o ra p p l i c a t i o n ss u c ha s i i i a b s t r a c t v i s u a ls u b s p a c el e a r n i n ga n dr e c o g n i t i o n 2 an e wc o m p u t a t i o n a le f f i c i e n tl o c a lp c aa l g o r i t h mi sp r o p o s e dt oc o m b i n e t h ea d v a n t a g e so fn g a s - p c aa n dp c a s o m e a c hu n i ti sa s s o c i a t e dw i t hi t sm e a n v e c t o ra n dc o v a r i a n c em a t r i x t h en e wc o m p e t i t i o nm e a s u r ei m p l i c i t l yi n c o r p o r a t e t h er e c o n s t r u c t i o ne r r o ra n dd i s t a n c eb e t w e e nt h ei n p u td a t aa n dt h eu n i tc e n t e r i nt h ep r o p o s e da l g o r i t h m ，t h ee x t r au p d a t i n gs t e po ft h ep r i n c i p a ls u b s p a c e si s e l i m i n a t e df r o mt h ed a t ad i s t r i b u t i o nl e a r n i n gp r o c e s s o n ep o t e n t i a la p p l i c a t i o n o ft h ep r o p o s e dm o d e li st h en o n l i n e a rp a t t e r nl e a r n i n ga n dr e c a l l i n g a f t e rt h e t r a i n i n gp r o c e s s ，t h ed a t ad i s t r i b u t i o ni sr e p r e s e n t e db yac o l l e c t i o no fl o c a ll i n e a r u n i t s n op r i o r ii n f o r m a t i o nf o rt h eo p t i m a lp r i n c i p a ls u b s p a c ei sn e e d e df o rt h e p a t t e r nr e p r e s e n t a t i o n 3 ad e f o r m a b l em o d e l ，i e t h eg e n e r a l i z e dt o p o l o g yp r e s e r v i n gs o m ( g w p s o m ) ，i sp r o p o s e dt oi n c o r p o r a t et h et o p o l o g yp r e s e r v i n gs e l f - o r g a n i z i n gm a p p i n g i n t ot h en e u r o nc o m p e t i t i o n i ti si n s p i r e db yt h ev i s u a li n d u c e ds e l f - o r g a n i z i n g m 印( v i s o m ) w h e r et h em a p p i n gp r e s e r v e st h ei n t e r - p o i n td i s t a n c e so ft h ei n p u t d a t ao nt h en e u r o nm a pa sw e l la st h et o p o l o g y t h eg t p s o mi sd r i v e ni np a r a l l e l b ya na d a p t i v ef o r c ef i e l d ，w h i c hi m p o s e sc o n s t r a i n so nt h el o c a lb o u n d a r y v a r i a t i o n r e g i o na i d e da c t i v ec o n t o u ra n dl e v e l s e t sa r ee m p l o y e dt oi m p l e m e n tt h ep r o p o s e d m o d e l t h eg t p s o mm o d e li ss u i t a b l ef o rb o t ht h ep r e c i s ee d g ed e t e c t i o na n dt h e c o m p l e xs h a p er e c o v e r yw i t hb o u n d a r ys t r e n g t hv a r i a t i o n 4 an e wm a n i f o l db a s e dm e t h o di sp r o p o s e dt oc o n s t r u c tan o n l i n e a rm a p p i n g b e t w e e nt h ei n p u ta n dt h ef e a t u r es p a c e ，i n s t e a do fc o n s i d e r i n gm a n i f o l dl e a r n i n g a n ds y n t h e s i si ni s o l a t i o n t h en o n l i n e a rm a p p i n gi sr e a l i z e db ym o d e l l i n gt h e l o c a lg e n e r a t i v eu n i t si nt h ei n p u ts p a c ea n dag l o b a la f f i n et r a n s f o r m a t i o ni nt h e f e a t u r es p a c e t h e s ef o r m u l a t i o n sr e s u l ti ns i m p l es o l u t i o n st ot r a n s v e r s eb e t w e e n t h ei n p u ts p a c ea n dt h ef e a t u r es p a c ef o rt h eo u t o f - s a m p l ed a t ap o i n t s t h e p r o p o s e dm e t h o da v o i d st h ea l t e r n a t i n gl e a s ts q u a r e sp r o b l e mo rl o c a lm i n i m a f o r b o t ht h em a n i f o l dl e a r n i n gp r o c e s sa n dt h eb i d i r e c t i o n a lo u t o f - s a m p l ee x t e n s i o n m o r e o v e r ，t h i sm e t h o dc a ne s t i m a t et h eu n d e r l y i n gd i m e n s i o na n di sr o b u s tt ot h e n u m b e ro fn e i g h b o r s k e y w o r d s ： i n c r e m e n t a l d i m e n s i o n a l i t yr e d u c t i o n ，m a n i f o l dl e a r n i n g ，s e l f - o r g a n i z i n gm a p p i n g ， p r i n c i p a lc o m p o n e n ta n a l y s i s i v 独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工 作及取得的研究成果。据我所知，除了文中特别加以标注和致谢的地 方外，论文中不包含其他人已经发表或撰写过的研究成果，也不包含 为获得电子科技大学或其它教育机构的学位或证书而使用过的材料。 与我一同工作的同志对本研究所做的任何贡献均已在论文中作了明 确的说明并表示谢意。 签名：型 日期：砂哆年月弓日 关于论文使用授权的说明 本学位论文作者完全了解电子科技大学有关保留、使用学位论文 的规定，有权保留并向国家有关部门或机构送交论文的复印件和磁 盘，允许论文被查阅和借阅。本人授权电子科技大学可以将学位论文 的全部或部分内容编入有关数据库进行检索，可以采用影印、缩印或 扫描等复制手段保存、汇编学位论文。 ( 保密的学位论文在解密后应遵守此规定) 签名：垄承导师躲丛1 日期：叩占月9 日 第一章绪论 第一章绪论 本章着重介绍本文的的研究背景和意义，以及本文相关领域的研究现状，为 后续章节的内容作出铺垫，最后还概述了本文的研究重点和章节安排。 1 i 研究背景与意义 视觉是人类认知世界的最重要手段之一。随着科学技术的突飞猛进和计算机 及网络技术的高速发展，与人类感知密切相关的高维图像信息在社会、经济和国 家安全等领域中扮演着重要角色，并在今后一段时间内仍将迅猛增长。可视的人 机交互技术已经成为了人类对信息进行认知和处理的重要手段。随着信息获取技 术和网络技术的高速发展，高维信息技术向着高性能、低成本和智能化等主要方 向发展。然而由于这些数据普遍是海量、高维、非线性和语义多样化的，寻求新的 计算与处理方式是未来信息技术领域面临的巨大考验。 从现有计算机结构基础上，结合视觉信息的认知机理和人工智能方法，寻求 高维视觉信息处理的新方法是本文的主要研究目的。具体来说在多维度大数据量 的数据分布学习方面；数据在不同空间映射、维度表达、高维特征的集合处理等问 题上；借鉴神经系统信息处理机理，解决信息冗余和提高算法效率方面；结合人类 对视觉信息语义的组织和规则抽取，基于机器学习理论解决非结构化的格式数据 建模和内容理解问题。针对上述问题，本文的研究重点考虑对高维数据的基于流 形的描述方法和基于神经网络的认知方法两个方面。 流形指一个数学上的抽象空间，在这个空间中每一个点都有与欧几里德空间 局部相似的邻域，但是抽象空间的全局性质可能更加复杂。因而线性的欧氏空间 可以看作是流形最简单的实例，而非线性结构则是在线性空间基础上的泛化。以 图像数据为例，图像本身的维数通常大于1 0 4 ，然而图像数据集中物体的姿态、光 照、人的面部表情、手势、步态等连续变化往往可以用远低于数据维数的自由度描 述。并且对于足够多的均匀无序的采样，这些潜在变化在数据空间内往往是连续 的。因此流形可以作为描述这样高维数据潜在结构的最佳工具。线性子空间是最 简单的描述方式，然而真实世界的流形往往是具有高曲率或高度非线性的，这样 的全局非线性问题则需要求助于基于局部几何信息的流形学习方法 1 ，2 1 ，或基于 特征空间内积函数的核方法3 1 。 电子科技大学博士学位论文 另一方面，基于人类认知和感知机理的人工神经网络以其深厚的生物学背景 和强大的计算能力，吸引着国际一流学术研究机构如m i t 、h a r v a r d 大学、b o s t o n 大学等的国际优秀科学家，其研究成果不断涌现在如( s c i e n c e ) ) 、( n a t u r e ) ) 等世界 一流学术刊物。自2 0 世纪8 0 年代以来，神经网络的理论及应用研究都取得了大量 的成果，已成功地应用到经济、军事、工程、医学等领域。 大量生物学和神经心理学研究成果表明，人脑的神经元之间存在结构非常 复杂，且具有认知学习功能的反馈连接。这种反馈连接结构可以被描述为一套高 度非线性的动力学系统。非线性动力学理论是对其认知学习机制进行分析的最 重要的数学工具。神经网络利用反馈学习机制将从外界获取的信息以神经元连 接( s y n a p s e ) 的形式存储下来，而被提取( 感知) 到的知识则表现为神经网络的稳 定平衡态( s t a b l ee q u i l i b r i u mp o i n t s ) 。稳定平衡态( 也称为吸引子) 的在人工神经 网络的联想记忆、优化计算、模式识别等等许多领域中的应用中扮演了至关重要 的角色。近年来，神经网络多稳定性的大量研究成果为人的头动、眼动、光照、表 情等行为和认知机制提供了直接的生物神经解释和理论支持。神经心理学成果也 进一步印证了神经元的群体行为是受限的，并且位于低维流形上，并且神经元集 合中单个神经元的点火率可以表示为带少量参数的连续函数f 4 ，5 ，6 ，7 ，9 】。研究表 明，人类视觉感知中存在以连续吸引子为基础的、对物体在光照和角度连续变化 的记忆和识别机制。 美国麻省理工学院( m i t ) 的s e u n g 实验室的科学家对回复式神经网络的多 稳定性分析中的连续吸引子( c o n t i n u o u sa t t r a c t o r ) 问题进行了深入研究，并将其 用于模式分析综合、连续吸引子的学习、以及解释眼球控制等问题【1 0 ，1 1 ，1 2 】。 在2 0 0 0 年s c i e n c e 上s e u n g 教授发表文章f 1 3 1 深入讨论了人对连续变化信号的神经 视觉感知机制。他将大脑神经系统对流形的感知表示方式与真实世界的视觉流形 联系起来。这种联系解释了人如何通过视觉感知机制对具有潜在关联的视觉信息 进行编码，从而抽象出变化模式和事件语义的问题。 与此同时，许多关于国内研究机构如中国科学院自动化研究所、南京大学、上 海交通大学，浙江大学、中科院神经科学研究所等等也有大量的专家从事相关研 究工作，并且在机器学习和脑神经科学等相关方向取得了丰硕的研究成果。 综上所述，正是由于大量的真实数据都具有低维潜在的连续变化和非线性结 构，并且这些信息可以被人的神经系统所认知，因此将人的感知认知模型作为智 能系统与机器学习算法模型结合起来是一个具有非常广阔前景的研究方向。本文 重点关注自组织人工神经网络和流形这两个处理数据中的非线性问题的两个紧密 关联的重要体系，开发高效的降维算法来解析高维、特别是图像数据集的潜在结 2 第一章绪论 构，进而为人们深入理解生物神经系统的认知机制，探索开发类似于人的智能感 知系统提供了重要的理论支持。 1 2降维方法的研究现状 本文的研究重点考虑全局的线性方法、基于神经网络的方法和基于流形的方 法三个方面。按照所描述的数据中潜在结构的复杂程度递增的顺序，本节以线性主 元分析、自组织人工神经网络和基于拓扑流形的非线性降维这三种典型降维方法 为中心概略地介绍了上述本领域具体方法的研究现状。 1 2 1 主元分析算法 主元分析【1 4 】在数学上定义为一个正交的线性变换。这个变换将数据变换到 一个新的坐标系统中去，使得对数据的任意投影的最大方差沿着第一个坐标轴( 称 之为第一个主元分量) ，并且第二大的方差方向在第二个坐标轴上，以此类推( 如 图1 1 ) 。主元分析在理论上是对已知数据在最小二乘意义下的最优变换。 图1 一l 在具有低维线形子空间的数据上，线性主元分析能够找到方差最大的坐标系统。 主元分析可以被用于数据集的降维。通过保留低阶次的主元分量且忽略高阶 次的分量，降维过程保持了数据集中对其全局方差贡献最大的特征。这些低阶次 的分量常常包含数据中最重要的方面。然而对于不同的应用却并不总是如此。 对于均值为零的数据矩阵x 剧黼( 数据分布的经验均值已经被减去) ，其中 3 电子科技大学博士学位论文 每一列代表不同次数的实验读数甄r d ( i = 1 ，佗) ，主元分析变换由以下形式 给出： y = u r x = e v t ， 其中x = u p n 。r 是x 的奇异值分解( s i n g u l a r v a l u ed e c o m p o s i t i o n ，s v d ) 。 主元分析区别于其他线性变换的的主要特点就是它保留了最大方差的子空 间。另一方面，主元分析也可以解释为这样一个投影矩阵，它最小化投影后的向 量来重构原向量的重构误差。以上两种解释引出了主元分析的两种传统求解方法： 迭代方法和协方差矩阵对角化方法。 ( 1 ) 主元分析的迭代求解 假设零均值，数据集x 的主元分量u 1 定义为： 让l2 甜9 m a ；x l v 口r 【u r x x = a r g m a ：x e ( u t x ) 2 ) ， 其中v a r ) 表示方差，e 表示数学期望。当有了前k 1 个分量后，第七个分量 可以通过从数据x 中减去前七一1 个主元分量： “一l=一uiutxxk x x ，一12一 ， t 并且用氟一l 代替原数据作为新数据来寻找下一个主元分量 乱七= n 叼高篝e ( 牡t 丸一- ) 2 ) 于是上述过程等价于对数据矩阵x 进行奇异值分解x = u e v r ，然后通过 把x 投影到前l 个奇异值向量吮，我们可以得到缩减空间的数据矩阵y = 班。x = l 斫? 。这里x 的奇异值向量构成的矩阵u 等价于协方差矩阵c = x x t 的特征值 向量所构成的矩阵( x x t = u e e t u t ) 。 ( 2 ) 主元分析的协方差矩阵求解 已知输入数据矩阵x = z l ，z n ) r d 煳，其中戤( i = 1 ，几) 。 首先计算经验均值m = 元1 各l 。然后计算所有数据点相对于均值的偏差。 于是居中后的数据为： 叉= x m e t ， 4 第一章绪论 其中e r n 为元素全为1 的向量。于是输入数据的经验协方差矩阵c 可以由矩 阵叉与自己的外积计算得来 个 c ：e 睫尹1 = x x lj亿 最后对协方差矩阵c 进行对角化： c = u d u t ， 其中d 是c 的特征值为对角元素的对角矩阵。这个步骤通常使用计算机求解，并且 已经成为许多常用数学工具，如m a t l a b 、m a t h e m a t i c a 、s c i p y 、或i d l ( i n t e r a c t i v e d a t al a n g u a g e ) ，的矩阵代数部分的必备模块。 ( 3 ) 主元分析的性质与局限 主元分析理论上是一种最小均方误差意义下的最优线性体系，其目的是为了 将一个高维向量集压缩到一组低维向量上，然后重构原来的向量集。它是一种非 参数化的分析，其解是唯一的并且与任何关于数据概率分布的假设都无关。然而 后面两个性质的不足与长处同样明显。由于是非参数的先验知识无法被加入进来， 而且主元分析压缩常常导致信息的丢失。 主元分析的可用性是受它推导过程中的假设所限制的。这些假设包括： 线性假设：假设观察到的数据是一些基的线性组合。非线性的方法( 如k e r n e l p c a ) 则不需要线性假设。 均值和协方差的统计学重要性假设：主元分析使用协方差矩阵的特征向 量，并且它只能找到数据在高斯假设下的不相关的坐标轴。对于非高斯或者 多模的( m u l t i - m o d a l ) 高斯数据，主元分析仅仅是对那些坐标轴进行去相关( d e - c o r r e l a t e ) 。由于主元分析不使用特征向量的类标签，因此它的主要局限是它没有 考虑类间的分离性。于是最大方差方向并不保证包含数据集中好的判别特征。 假设大的方差具有重要的动力学信息：主元分析只是进行一个坐标旋转来使 得变换后的坐标轴与最大方差方向对齐。只有当我们相信观察到的数据具有较高 的信噪比的时候，带有较大方差的主元分量才对应于感兴趣的动力学信息，而较 小方差的分量对应于噪声。 1 2 2自组织映射 自组织 ( s e l f - o r g a n i z i n gm a p ，s o m ) 最早是由芬兰教授t e u v ok o h o n e n ，以 人工神经网络【6 7 】的形式描述出来的，有时也称为k o h o n e n 图。 它通过非监督 5 电子科技大学博士学位论文 学习来产生一个低维的( 典型的是两维的) 、离散化的输入数据空间表示，称之 为“图 ( m a p ) ( 如图1 2 ) 。这种图试图保持输入空间的拓扑性质。这种性质使 得自组织图适用于高维数据的低维可视化。这样的方式特别类似于多维尺度分 析( m u l t i d i m e n s i o n a ls c a l i n g ，m d s ) 。 图1 2 传统的自组织图将原数据空间的数据点投影到二维网格上的神经元上。 自组织图提供了一种通过将数据维数降低到图的方式，来进行数据可视化的 技术。按照t e u v ok o h o n e n 的描述，自组织图是对高维数据进行可视化的一 种有效的软件工具。它将高维数据点之间复杂的非线性统计关系转化成为了简 单几何关系从而在低维下显示。因此，自组织图压缩了原始数据的信息但同时 保留了最重要的拓扑和尺度关系。此外，自组织图还可以被用于信息的某种抽 象。与大多数人工神经网络类似，自组织图有两种工作方式：训练和映射。训练 方式使用输入样本构建自组织图。这是一个竞争的方式，也称为向量量化( v e c t o r q u a n t i z a t i o n ) 。映射方式则自动的对一个新的输入向量进行划分。当数据进入系 统，由神经元组成的网络根据输入数据包含的信息进行训练，神经获胜神经元 及其相邻神经元的权值不断调节。 ( 1 ) 网络结构 自组织图由神经元n e u r o n 组成。对于每个神经元有一个与输入数据向量维数 相同的权值向量( w e i g h tv e c t o r ) 和神经元在自组织图上的位置相关联。神经元通 常排列在均匀间隔的六角或者四角网格的节点上。自组织图描述了一个由高维输 入数据到低维图的映射。把数据空间中的一个向量放置到图上的过程是通过寻找 与该数据向量最近的权值向量相关联的那个神经元，然后把神经元在图上的坐标 6 第一章绪论 赋予该数据向量。当自组织图的神经元数目较少的时候，它与传统的k - m e a n s 方 法比较类似。然而大规模的自组织图能够以完全按照拓扑性质的方式来对输入数 据进行重排。 ( 2 ) 训练算法 在自组织图中，训练的目的是为了使神经网络的不同部分对于特定的输入模 式有特定的反应。这种方式的思想部分地来源于人类大脑皮层的不同部分对视觉、 听觉或其他感觉信息处理方式。 神经元的权值向量使用较小的随机值或数据最大主元的特征向量来进行初始 化。对于后一种选择，学习过程通常要快得多，这是由于初始的权值向量已经是对 自组织图的一个好的逼近了。 神经网络必须要输入大量的、尽可能代表将要用于映射的向量的数据样本。 并且这些数据通常需要被遍历多次。训练过程使用竞争学习方式( c o m p e t i t i v e l e a r n i n g ) 。当一个训练样本被输入网络，需要计算它与所有权值向量的欧几里德 距离。与训练样本最相近的权值向量相关联的神经元被称为最佳的匹配单元( b e s t m a t c h i n gu n i t ，b m u ) 。b m u 和与之在自组织图网格上相近的神经元的权值向量 都被向着输入向量的方向进行调整。神经元权值调整的幅度随时间和该神经元 到b m u 的距离增加而减少。神经元权值眠( 亡) 的更新方式如下 眠 + 1 ) = 眠( t ) + o ( v ，亡) q ( t ) ( x ( t ) 一巩( 亡) ) 其中q ( 亡) 是单调下降的学习速率，x ( t ) 是输入向量。邻居函数o ( v ，t ) 取决于b m u 和神经元口在网格上的距离，最常见的形式是高斯函数。无论邻居函数形式如何， 它都随时间而减小。初始时邻居范围比较宽广，自组织在全局尺度范围内进行。当 邻居范围缩小到只包含几个神经元时，权值矩阵收敛到对数据的局部估计。 这个过程对于每个输入向量都重复循环多次。神经网络将输入数据集中的模 式分配到输出的神经元上。如果这些模式本身有语义可以描述，那么这些语义将 被赋予到训练后的相关神经元上。 在映射过程中，对于输入向量将只会有一个具有最相近权值向量的神经元为 获胜神经元。通常这种相近关系都是通过欧几里德距离衡量的。 值得注意的是除了自组织图最原始的形式，任何合适的可量化对象、神经网 络结构和距离度量都可以被用来构建新的特定用途的自组织图。 1 2 3非线性降维与流形学习 对高维数据集进行处理和表示是非常困难的。一种简化的方法是假设感兴趣 7 电子科技大学博士学位论文 的数据是位于一个在高维空间中嵌入的非线性流形( 如图1 3 ) 。如果流形具有足够 低的维数，那么这些数据集将能够在低维的空间中被可视化。 图1 3 高维空间中的非线性流形。 许多的非线性降维方法都与线性方法有着密切的关联。非线性方法可以被划 分为两类：一类的确是提供了一个映射( 不论是从高维空间到低维嵌入还是反向 的) ，另一类只是给出一个可视化。 核主元分析k e r n e lp c af 3 】是提供从高维空间到嵌入空间映射的一种最直接 的方法。这种方法利用“k e r n e lt r i c k 对线性主元分析进行非线性化。核主元分析 通过定义核函数来做为高维空间的内积，从而隐式地把原输入空间的数据投影到 一个高维空间。低维的数据表示可以通过在核矩阵上进行特征值分解得到。 自组织图及其概率变形( g e n e r a t i v et o p o g r a p h i cm a p p i n g ，g t m ) 也可以看作 一种基于流形的非线性降维。它们使用嵌入空间中的点来形成潜在变量模型，这 个模型可以被看作流形的离散化表示。 高斯模型潜在变量模型( g a n s s i a np r o c e s sl a t e n tv a r i a b l em o d e l s ，g p l v m ) 1 6 1 是一种概率化的非线性主元分析。与核主元分析类似，g p l v m 使用核函数以高斯 过程的形式来构造映射。然而g p l v m 中的映射是从嵌入空间向输入数据空间的， 与核主元分析的映射方向相反。 主曲线( p r i n c i p a lc u r v e s ) 和流形( m a n i f o l d s ) 为非线性降维提供了一种自 然的几何框架，并且通过显式地构建一个嵌入流形及其几何投影，扩展了原 来主元分析的的几何解释。流形的复杂程度通常是由固有的维数或流形的光 滑程度的来衡量f 1 7 】。最近基于拓扑流形学 - 3 的非线性方法成为了新的研究 8 第一章绪论 热点，这些方法包括l o c a l l yl i n e a re m b e d d i n g ( l l e ) 、h e s s i a nl l e 、l a p l a c i a n e i g e n m a p s 和l t s a 等。这些方法使用了一个保留数据局部性质的代价函数，进 而构造一个低维的数据表示。事实上这些方法可以被看作定义了一个基于图 的( g r a p h - b a s e d ) 核主元分析。因此，这些方法能够展开诸如s w i s sr 0 u 的非线性 数据结构。还有一些方法是用邻居图来保留一些数据全局的性质，这些方法包 括i s o m a p 和m a x i m u mv a r i a n c eu n f o l d i n g 等。这些方法本质上都是基于一个相似 矩阵( s i m i l a r i t ym a t r i x ) 或距离矩阵，因而可以被看作一类广义的度量多维尺度分 析( m e t r i cm u l t i d i m e n s i o n a ls c a l i n g ) 。它们的相互区别只在于如何计算相似矩阵， 例如：i s o m a p 计算全局测地线距离，l o c a l l yl i n e a re m b e d d i n g 计算局部线性组合 系数，m a x i m u mv a r i a n c eu n f o l d i n g 计算局部邻居距离等等。 1 3主要工作和结构安排 本文的主要工作是针对具有低维潜在流形的高维数据，研究和提出了基于流 形的降维方法，并且扩展了它们在图像处理中的应用。由于流形定义为每个点领 域内具有局部类似于欧几里德空间的性质，而全局结构可能更为复杂抽象的数 学空间，本文中使用”流形”这一的概念来统一概括高维数据中潜在的线性和非线 性结构，力求使各章节内容更加紧密和统一，因而章节之间的潜在逻辑是按照所 描述的数据中潜在结构的复杂程度递增来逐步推进的：由线性结构( 增量主元分 析i p c a ) ，到局部离散化的非线性结构( 自组织图s o m ) ，最终到局部光滑的非线 性结构，其中线性的欧氏空间就是流形最简单的实例，而非线性结构则是在线性 空间基础上的泛化。本文的结构安排如下： 第一章“绪论 ：概述了本文的背景和研究意义，分析了基于人工神经网络和 流形学习的降维方法的研究现状和相关的典型算法，概略地介绍了将会贯穿本文 的典型方法：线性主元分析、自组织人工神经网络和基于拓扑流形的非线性降维 方法，为后文内容做好铺垫。 第二章“基于自相关矩阵的均值更新增量主元分析算法”：本章提出了一种基 于自相关矩阵的均值移的增量主元分析( i