（应用数学专业论文）半监督流形学习的算法分析与应用.pdf

中文摘要 摘要 在本文中，我们首先介绍了基于流形的机器学习算法一一流形学习。其中 包括等距映射、局部线性嵌入映射、拉普拉斯特征映射和扩散映射。我们展现 了这些经典算法的思想、推导过程以及实验效果。并且我们在此基础上推出了 维数约简算法的一个整体框架一图投影，在图投影框架中重新审视了各个算法的 相似性定义，以及在信息挖掘和行为感知领域的应用。 实际上，许多维数约简应用的例子都是处理一些具有部分标记样本的数据 集。所以，在本文中我们将着重考虑基于标记信息的流形学习算法。我们推出 了两种解决此类问题的算法来进行维数约简和数据表示，一种算法是基于拉普 拉斯特征映射的，一种是基于扩散映射的。这两种算法都能够做到既保持流形 的局部几何结构，又能保持整体统计标记信息。这两种算法与以往经典算法不 同之处就是利用标记信息改造了基本几何信息构造的相似性矩阵。算法分别在 手写数字，人脸图像和天气等数据库中得到了很好的应用。 半监督的拉普拉斯特征映射是改造了经典的拉普拉斯特征映射框架而得到 的，该算法使得目标函数考虑了标记信息。首先，通过局部邻域关系构建一个 加权图，然后通过样本的标记信息改造这个局部结构关系使得样本之间的关系 依赖于标记信息，最后通过解决广义特征分解问题得到样本在低维空间的表 示。实验证明该算法通过考虑标记信息，使得性能得到了很大的提升。 半监督扩算映射是一种基于传统的扩散映射的算法。该算法的相似性矩 阵是通过样本标记的后验概率改造得到的，样本的标记后验概率是通过有限 步e m 迭代算法得到。值得一提的是，半监督扩散映射能够将不同标记的样本投 影到不同的子空间中去，这样使得后续的分类和识别任务变得异常简单。并且 该算法具有稳定性和抗噪音干扰性，因为样本之间的关系是逐步通过局部到整 体扩散得到的。我们将半监督扩散映射算法应用到手写数字和耶鲁大学的人脸 数据库，结果表明该算法对于分类问题具有非常好的效果。 关键词：流形学习；维数约简；半监督学习；拉普拉斯特征映射；扩散映射；标记信 息 湖北大学硕士学位论文 a bs t r a c t i nt h i sp a p e lw ef i r s t l yr e v i e wt h ei d e a s ，a l g o r i t h m s ，a n de x p e r i m e n t a lp e r f o r m a n c eo f m a n i f o l d b a s e dm a c h i n el e a r n i n ga n dd i m e n s i o n a l i t yr e d u c t i o nm e t h o d s t h er e p r e s e n t a t i v em e t h o d si n c l u d ei 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 ( l l e ) ，l a p l a c i a ne i g e n m a p s ，a n dd i f f u s i o nm a p s w ed e s c r i b e dt h ei n s i g h t sf r o mt h e s ed e v e l o p m e n t sa sw e l l a sp o t e n t i a la p p l i c a t i o n si ni n f o r m a t i o nm i n i n ga n db e h a v i o rp e r c e p t i o n i np r a c t i c e ，m a n ya p p l i c a t i o n sr e q u i r ead i m e n s i o n a l i t yr e d u c t i o nm e t h o dt od e a l w i t ht h ep a r t i a l l yl a b e l e dd a t a t h e nt h ep r o b l e mo fd i m e n s i o n a l i t yr e d u c t i o nw i t hp r i o r i n f o r m a t i o ni sc o n s i d e r e d i nt h i sp a p e r w ep r e s e n tt w on e wt r a c t a b l es e m i s u p e r v i s e d a l g o r i t h m sb a s e do nl a p l a c i a ne i g e n m a p sa n dd i f f u s i o nm a p sf o rd i m e n s i o n a l i t yr e d u c t i o na n dd a t ap a r a m e t e r i z a t i o n o u ra l g o r i t h m sp r e s e r v et h el o c a lm a n i f o l ds t r u c t u r ei n a d d i t i o nt os e p a r a t i n gs a m p l e si nd i f f e r e n tc l a s s e sf r o me a c ho t h e r u n l i k ep r e v i o u s w o r k sw h i c ho n l yu s eg e o m e t r i ci n f o r m a t i o nt oc o n s t r u c ts i m i l a r i t ym a t r i x ，e g ，u l e ， l a p l a c i a ne i g e n m a p s ，d i f f u s i o nm a p sa n di s o m a p , e t c ，t h es i m i l a r i q tm a t r i xo ft h e p r o p o s e da l g o r i t h m si sa d j u s t e db yl a b e li n f o r m a t i o n ，t h et w oa l g o r i t h m sa r ea p p l i e d i nh a n d w r i t i n gd i g i ti m a g e s ，f a c ei m a g e s ，a n di o n o s p h e r ed a t a b a s e t h es e m i - s u p e r v i s e dl a p l a c i a ne i g e n m a p sm o d i f i e dt h ec l a s s i c a ll a p l a c i a n e i g e n m a p ss c h e m es u c ht h a ti t so b j e c t i v ef u n c t i o nt a k e si n t oa c c o u n tt h ep r i o ri n f o r m a t i o n t h i sa l g o r i t h mf i r s tf i n d sn e i g h b o r i n gp o i n t st oc r e a t eaw e i g h t e d n e i g h b o r h o o d g r a p h t h e n ，t h ec o n s t r a i n t sa l eu s e dt om o d i f yt h en e i g h b o r h o o dr e l a t i o n sa n dw e i g h t m a t r i xt or e f l e c tt h i sw e a kf o r mo fs u p e r v i s i o n t h eo p t i m a le m b e d d i n gi si d e n t i f i e d b ys o l v i n gt h eg e n e r a l i z e de i g e n v a l u ep r o b l e m i ti ss h o w nt h a tt h ep e r f o r m a n c eo f d i m e n s i o n a l i t yr e d u c t i o na l g o r i t h m sc a l lb ei m p r o v e db yt a k i n gi n t oa c c o u n tt h el a b e l i n f o r m a t i o no ft h ed a t a t h ed a t aa n a l y s i sa n de x p e r i m e n t ss h o wt h ev a l i d i t yo fo u r a l g o r i t h m t h es e m i s u p e r v i s e dd i f f u s i o nm a p sa r et h ea l g o r i t h m sb a s e do nd i f f u s i o nm a p s t h es i m i l a r i t ym a t r i xo ft h ep r o p o s e da l g o r i t h mi sa d j u s t e db yt h ep o s t e r i o rp r o b a b i l i t y o ft h el a b e l so fe a c hs a m p l e ，w h i c hi sl e a r n e dt h r o u g he m i ti sr e m a r k a b l et h a to u ra l g o r i t h m sc a nm a ps a m p l e si nd i f f e r e n tc l a s s e so n t od i f f e r e n tf e a t u r ed i m e n s i o n si nt h e l o w d i m e n s i o n a le m b e d d i n gs p a c e ，t h u si tm a k e sc l a s s i f i c a t i o nb e c o m ea ne a s yt a s k m o r e o v e r , o u ra l g o r i t h m sa r er o b u s tt on o i s eb e c a u s eo fs t e a d yr e l a t i o n s h i pa c c o m m o d a t e dt h r o u g ht h ec h a i n i n go fm a n yl o c a li n t e r a c t i o n s e n c o u r a g i n ge x p e r i m e n t a l r e s u l t so nh a n d w r i t t e nd i g i t sa n dy a l ef a c e ss h o wt h a to u ra l g o r i t h m sc a n s i g n i f i c a n t l y i m p r o v et h ec l a s s i f i c a t i o na c c u r a c y k e yw o r d s ： m a n i f o l dl e a r n i n g ；d i m e n s i o n a l i t yr e d u c t i o n ；s e m i - s u p e r v i s e d l e a r n i n g ；l a p l a c i a ne i g e n m a p s ；d i f f u s i o nm a p s ；l a b e li n f o r m a t i o n 一 湖北大学学位论文原创性声明和使用授权说明 原创性声明 本人郑重声明：所呈交的论文是本人在导师的指导下独立进行研究所取得 的研究成果。除了文中特别加以标注引用的内容外，本论文不包含任何其他个 人或集体已经发表或撰写的成果作品。对本文的研究做出重要贡献的个人和集 体，均已在文中以明确方式标明。本人完全意识到本声明的法律后果由本人承 担。 学位论文使用授权说明 本学位论文作者完全了解学校有关保留、使用学位论文的规定，即： 按照学校要求提交学位论文的印刷本和电子版本；学校有权保存并向国家 有关部门或机构送交论文的复印件和电子版，并提供目录检索与阅览服务；学 校可以允许采用影印、缩印、数字化或其它复制手段保存学位论文；在不以赢 利为目的的前提下，学校可以公开学位论文的部分或全部内容。( 保密论文在 解密后遵守此规定) 作者签名： 导师签名： 日期：二矽年j 月功日 日期：叩年f 月弓尸 第1 章 绪论 1 1 研究背景 第1 章绪论 随着信息时代的到来，随着计算机技术的飞速发展，人类收集数据、存储 数据的能力得到了极大的提高，现如今即使普通人的电脑，硬盘也已经达到了 数t 级别的存储能力。无论是科学研究还是社会生活的各个领域中都积累了大 量的数据，而往往人们在面对这样海量的数据时都是一筹莫展。有的甚至不知 道自己存储的海量数据是一个巨大的财富。对这些数据进行分析以发掘数据中 蕴含的有用信息，几乎成为所有领域的共同需求。如全球气候模型、人类基因 分布、文本聚类中的词频、商业领域的销售记录、网友的浏览记录、安全监控 录像等。对于这些数据的挖掘与分析可能会改变当今人类的生活状况与生活习 惯，甚至能够增强人类改造自然的能力。 我国信息化的发展异常快速，金融业，政府内都存储了大量的数据，而且 企业的发展也带来了智能化设备的需求。如何利用计算机从高维海量的数据中 获取内在规律，并指导人的认知以及行为是机器学习( m a c h i n el e a r n i n g ) 和数据 分析( d a t aa n a l y s i s ) 的主要目标。人脑也面临着同样的问题：人脑在每天的感知 活动中要从3 万个听觉神经的输入和1 万个视觉神经的输入中抽取出有意义的信 息。面对数据集呈现的高数据量、高维数、非结构化、以及不能被人的感知所 单独处理这些特点，我们要用机器去做人脑做的事情，并模拟人类的认知。所 以我们需要发展维数约简( d i m e n s i o n a l i t yr e d u c t i o n ) 的方法去认识潜藏在数据内 部的信息。我们期望能从高数据量中自动地提取有效的、紧的描述，即在保证 数据信息足够完整的情况下合理约简数据，以满足存储和人的感知需求。希望 能用较少或人可利用的独立变量来代替高维的数据表示方式；对于非结构化 的数据( 如图像、语音) ，我们期望能够从中提取出某种结构化的变量( 自由 度) 来反映数据的特性。同时，我们也希望能够找到人类认知的内在规律，进而 为制造更先进、更加智能化的机器人提供算法基础。 在传统的维数约简中，一般假设数据存在于全局线性结构，即构成数据 集的各变量间是独立相关的。例如：主成分分析( p r i n c i p a lc o m p o n e n ta n a l y s i s ) 。 线性判别法( 1 i n e a rd i s c r i m i n a n ta n a l y s i s ) 。然而，全局线性结构的假定却使得 我们很难获得对数据集的真实结构有一个清楚的认识。要从高度相关性、 复杂分布形式中寻找内在的整体结构，实质上是要解决“流形学习”( m a n i f o l d l e a r n i n g ) 问题。从几何的观点来看，维数约简可以看成是挖掘嵌入在高维数据 中的低维线性或非线性流形。这种嵌入保留了原始数据的几何特性，即高维 湖北大学硕士学位论文 空间中在流形上靠近的点在低维空间中也相互靠近。流形学习是一种新的非 监督学习( u n s u p e r v i s e dl e a r n i n g ) 方法，近年来引起越来越多机器学习和认知科 学( c o g n i t i v es c i e n c e ) i 作者的重视。流形学习实际上是保持了数据在高维空间 中样本之间的一种局部关系，这种关系描述了数据之间的相似性。认知科学家 认为同一事物在随着时间、空间等因素连续发生变化时形成了一个低维的流 形，并且人的强大的认知能力正是基于对这一稳定状态流形的视觉记忆的。也 就是说从人类的认知角度来看，人的认知就是基于某种流形的学习过程。这个 在i s o m a p ，u 。e 等流形学习算法中的描述比较清楚。 对数据样本进行标记，需要专家知识或者设备检测，代价昂贵。因而实际 应用中，往往仅有少量标记的训练数据，还有大量的未标记数据。未标记数据 虽然不能直接用来训练传统的分类器，但是可以从中分析数据的结构和分布信 息。希望能够充分利用这些信息将有效地提高分类算法的性能，这就是半监督 学习发展的最直接的原因。传统的机器学习方法大多只考虑有标记数据( 1 a b e l e d d a 协) ，例如线性判别法、支持向量机。或者只考虑未标记数据( u n l a b e l e dd a t a ) ， 例如聚类。但是在很多真实问题中往往是二者并存，如何更有效地利用这 些数据成为一个备受关注的问题。作为解决这一问题的关键技术，半监督学 习( s e m i s u p e r v i s e dl e a r n i n g ) 也受到了国际机器学习和数据挖掘( d a t am i n i n g ) 界的 高度重视。 要利用未标记样本是半监督学习发展的出发点。然而，我们再从是否利 用样本的标记信息来看传统的流形学习，可以得出这种保持局部结构的流 形学习算法实际上忽略了一个重要的可以利用的信息，那就是其中的一种 全局结构一数据的标记信息，我们也可以认为标记信息是数据的一种统计信 息。同时，标记信息是花高代价所取得的最有用的信息。对于分类问题而 言，c a s t e l l i 【l 】和c o v e r 在1 9 9 5 年就已经证明标记样本的个数对于风险的降低起 着指数级的作用，而未标记样本的个数的作用只是多项式级别。那么我们也有 理由相信利用标记信息会增加传统的流形学习算法的性能。传统的流形学习算 法都是非监督的，它着重挖掘的是数据本身的局部结构。然而，在现实中的很 多情况下我们在进行流形学习的时候是拥有部分数据的标记信息。利用这些信 息就可以改进传统的流形学刊算法的特性，使得算法在保持了数据的局部结构 的同时也保持了数据的整体多流形结构。这样使得我们很自然的想到利用半监 督学习领域的方法去改进流形学习领域中的算法。在这种情形下，就发展了一 种新的交叉的学习研究领域一半监督流形学习。同时我们可以看出，在这样的指 导思想下发展起来的流形学爿算法，即利用数据的几何( g e o m e t r y ) 信息又利 用数据的统计( s t a t i s t i c s ) 信息，在不失局部结构的情况卜保持了整体结构。本文 将集中通过融合标记信息去设计新的流形学习算法，期望对于需要完成识别、 2 第1 章绪论 分类、匹配的任务的数据有很明显的优势。 1 2 国内外研究现状和发展趋势 1 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 ) 【2 ，3 】，线性判别法l d a ( 1 i n e a rd i s c r i m i n a n t a n a l y s i s ) 【6 , 7 ，8 ，9 】，多维标度分析m d s ( m u l t i d i m e n s i o n a ls c a l i n g ) 【1 l ，1 2 ，1 3 ，1 4 ，1 5 。 p c a 【2 ，3 】在1 9 0 1 由k a r lp e a r s o n 首先提出来的。现在它在数据分析与预测 模型中得到了广泛的应用，它的主要思想就是把一组可能相关的变量转化 成一组较少的独立的不相关的变量，这组独立的变量就称为主成分。主成 分具有较多的差异性( v a r i a b i l i t y ) ，一般越靠前，其差异性越大。在不同的领 域，p c a 有时被称为k l 变换( k a r h u n e n - l 0 6 v et r a n s f o r m ) 。p c a 需要进行协方差 矩阵( c o v a r i a n c em a t r i x ) 的特征值分解或者数据矩阵的奇异值分解。而分解后 得到的一组正交的特征向量就是特征空间中一组基。这组基中对应于特征 值较大的特征向量对应着数据集差异性较大的方向，也就是要找的特征投 影。1 9 9 9 年b e r n h a r ds c h o l k o p f 等人在p c a 的基础上提出来一种新的非线性的算 法k p c a ( k e m e lp c a ) 。k p c a 【4 ，5 】首先通过一个非线性变换，将原始空间的数 据映射到高维特征空间，然后在这个高维特征空间中进行线性主成分分析。通 过核技巧，k p c a 方法只需在原空间进行内积计算，而不必知道非线性变换的 确切形式。 线性判别法l d a ( 1 i n e a rd i s c r i m i n a n ta n a l y s i s ) 7 ，8 ，9 】在统计学中以及机器学习 中用的比较广泛。l d a 最早出现在1 9 3 6f i s h e r 的一篇论文中 t h eu s eo fm u l t i p l e m e a s u r e si nt a x o n o m i cp r o b l e m s ” 6 】。l d a 主要是寻求一组能够很好地把两类或 者多类样本区别开的线性组合，也可以认为是寻求一组好的投影方向，使得投 影后的数据具有很好的可分离性。l d a 、p c a 和因子分析都有着紧密的联系， 都是寻找一组能够更好解释数据的变量。但l d a 显著不同的是试图为数据的类 别信息进行建模，而p c a 和因子分析没有考虑数据的类别信息。实际上这种简 单而直观的算法思想为之后流形学习向监督学习和半监督学习发展奠定了基 础。m s u g i y a m a 【1 0 等人与2 0 0 7 年根据l p p 【2 8 的思想改造了传统的l d a ，使 得保持了局部结构。 多维标度分析m d s ( m u l t i d i m e n s i o n a ls c a l i n g ) 【l l ，1 2 ，1 3 ，1 4 ，1 5 】是一系列信 息可视化领域中探索相似性或者非相似性的算法的总称。m d s 乃试图将个 3 湖北大学硕士学位论文 体( s t i m u l u s ，或刺激体) 问原始相异性( d i s s i m i l a r i t i e s ) 的结构，经过转化成为 一个多维度( d i m e n s i o n ) 的空间图，且转化后个体在空间中的相对关系尽量与 原始的输入保持一致。故可将多维标度分析当作一种资料( 样本) 缩减技术， 它可以解决许多本身非数字化的集合。m d s 是根据个体间的相异性得出这些个 体问的结构，而相似性的反面即为相异性。所以通常需要将相似性转换成相异 性，才可以输入m d s 进行分析。就是在这个方法的基础上，后来发展了一种最 有名的流形学习算法i s o m a p 。 自2 0 0 0 年s r o w e i s ，l s u a l 在s c i e n c e 上发表了u 正【2 0 ，以及j t e n e n b a u r a ， vs i l v a 和j l a n g f o r d 等人在s c i e n c e 同一期上发表了i s o m a p 【1 6 ，可谓开创了机 器学习一个新的时代，之后便有很多新的流形学习方法雨后春笋般地涌现出 来。 i s o m a p 【1 6 ，1 7 ，1 8 ，1 9 是现今在模式识别、统计学中用的非常广泛的特征 提取或数据表示的算法，它是等距映射算法的代表作。i s o m a p 与经典的多维 标度分析有着紧密的联系，它通过在一个无向有权图上加入测地距离来描述 样本之间的相异性，这样就扩展了m d s 算法。i s o m a p 用测地距离构成一个权 矩阵作为距离矩阵。特别地，m d s 的实现依赖于数据之间的成对的距离，而 这种距离仅仅就来源于两点之间的欧式距离( e u c l i d e a nd i s t a n c e ) ，i s o m a p 不 同之处就在于通过局部邻域最短路径导出了逼近于真实流形上的测地距离( 见 图2 7 ) 。测地距离的计算就是通过在稀疏图上的一系列的局部最短路径的相加得 到，这个算法就是著名的d i b k s t r a 算法。测地距离矩阵的最前面的个特征向量就 构成了数据在低维空间的表示。i s o m a p 提供了一种简单的估计具有某种流形 结构的数据的本质几何结构的方法，它高效，并且能够广泛应用于各个领域。 局部线性嵌入映射算法( 1 0 c a l l yl i n e a re m b e d d i n g ) 【2 0 ，2 1 ，2 2 ，2 3 ，2 4 强调在数 据结构不满足全局线性结构时，观测空间与内在低维流形之间在局部意义下是 可以利用线性空间进行近似的，因此可以通过近邻法来获得各个数据点在邻域 内的关系。并通过最d x - - 乘思想来构造邻域内数据集的权值( w e i g h t ) 。l l e 算法 假定了在低维空间与观测空间的数据具有相似的结构性质，认为低维的相应数 据点之间具有相同权值。通过最优化理论，求取数据集的目标函数转为求解特 征值及特征向量问题。最后按照谱的性质，选择其中非零的最小特征值对应的 特征向量就可以获得观测空间数据集在近似低维结构的相应数据点，如图1 1 。 2 0 0 3 年，b e l k i n 和n i y o g i 推出了一种新的方法l a p l a c i a ne i g e n m a p s 【2 5 ，2 6 ， 2 7 】，他们给出了完整的几何分析，并且在特定的假设下可以将它与l l e 、聚 类联系起来。而且这种方法也是目前唯一给出了收敛性证明的算法。与u 正类 似，拉普拉斯特征映射也是基于局部保形思想，来获得高维观测空间与低 4 第1 章 绪论 图1 1 l l e 算法 6 9 7 。 维结构在局部意义下的对应。与u 卫算法不同的是，该算法利用了l a p l a c i a n b e l t r a m i 算子的特性。这种算子定义为流形切空间上梯度向量的负散度函数，流 形的低维嵌入可通过求l a p l a c i a n - b e r r a m l 算子的特征函数来实现。在这一基础 上，可以证明离散的拉普拉斯矩阵可以近似对应于连续的l 叫a c i a n b e l t r a r a l 算 子，特征函数对应于拉普拉斯矩阵的特征向量。由此，数据集的嵌入映射可阻 近似地用米描述定义在整个流形的l a 讲a c i a n b e l t r a m i 算子的内在特征映射。实 际上在处理现实问题时，我们只需要计算拉普拉斯矩阵的特征向量。xh e 等 人于2 0 0 4 提出了一个基于拉普拉斯特征映射的线性局部保形映射皿p p 【2 8 ) 。 d o n o h o 和g r i m e s 在2 0 0 4 年推出了h e s s i a n e i g e n m a p s 【2 殳3 0 ，3 1 】，与l a p l a c i a n e i g e n m a p s 一样具有很深的数学背景。这个方法是通过考察局部h e s s i a n 的二次 型来得出结论的，如果个流形局部等距于欧式空间中的一个开子集，那么由 这个流形到开子集的映射函数是一个线性函数，而线性函数的二次混合导数为 零所以局部上e h h e s s i a n 系数构成的二次型也为零。这样由每一点过渡到全 局的h e s s i a n 矩阵就有d + l 维的零空间，其中一维是常函数构成的，也就是1 向 量。其它的d 维子空间构成等距坐标。另个类似于h e s s i a ne i g e n m a p s 著名 的算法是浙江大学的z h e n y u e z h a n g 于2 0 0 4 年提出来的l t s a f l o c a l t a n g e n ts p a c e a l i g n m e n t 3 2 1 ) 。流形的局部几何表达用切坐标，也就是f c a 的主子空间中的坐 标表示。那么对于流形一点处的线性切空问，可以和欧式空间中的一个开子集 建立同构关系。最简单的同构关系就是线性变换。在微分流形中，就叫做切映 射( t a n g e m i a lm a p ) - 是个很自然并且基础的概念。把切坐标求出来，建立出切映 射，最终通过数值计算可以把这个算法转化为一个很简单的跌代问题。 扩敞映射( d i f f u s i o n m a p s 【3 3 ，3 4 , 3 6 】) 是r o n a l d rc o i m a n 等人在2 0 0 6 年提出来 的，这个算沾与拉昔拉新特征跌射有着紧密地联系，描述样本点的柏似性矩阵 具有相同的构造方法。通过这个相似性矩阵再定义了一个描述随机步长( r a n d o m 湖北大学硕士学位论文 w a l k ) 的马尔科夫矩阵( m a r k o vm a t r i x ) ，把马尔科夫矩阵的特征向量作为投影算 子，这个算子被叫做扩散映射( d i f f u s i o nm a p s ) ，在这个算子的作用下得到了数据 新的表示。扩散映射使得数据在低维空间的欧式距离与在高维空间中的扩散距 离( d i f f u s i o nd i s t a n c e ) 保持一致。扩散距离实际上描述的是两个样本点分别与全 局样本之间的关系的一种差别。在流形上比较近的点，与全局样本点的关系应 该是一致的。这种通过全局信息构造新的度量具有更加稳定的特点。 6 2 7 8 5 1 0 3 4 6 2 3 4 6 2 55 图1 2个体对整体的关系 678 o 一 图1 3样本1 ，7 ，8 对整体的关系之问的对比 o 3 4 流形学习的发展非常迅速，从算法设计到算法应用，都受到了科学研究者 的热烈追捧。但与此同时另外个领域的发展也进行的如火如荼，那就是半监 督学习。 6 3一 2川il l、 第1 章绪论 1 2 2 半监督学习算法的发展 在现实中，我们往往会面对只具有少量的标记样本，但会有大量的未标记 样本的情况，因为得到标记样本是要花费很大的代价的，运行成本也很高，而 产生未标记的样本的代价是很低的。例如：网页的自动分类问题。互联网上没 有得到分类的网页是相当多的，但对于一个网页进行分类，往往需要人为花销 很长时间去阅读这个网页，然后才能对其进行分类。在过去几年里，半监督学 习( s e m i s u p e r v i s e dl e a r n i n g 【4 3 ，3 7 ，3 8 】) 逐步发展成为机器学习研究领域的一个重 要方向，它与转导推理这种哲学思想有着及其紧密的联系。作为一个新的研究 领域，半监督学习拥有大量的技巧与方法，在机器学习的各个分支都有很好的 发展和应用。其中比较典型的传统的是将标记信息应用到核方法和贝叶斯方法 中。 可能最早关于如何在分类问题中使用未标记样本的算法是自学习算法，这 是一个不断利用监督学习算法进行包装的算法。算法的开始仅仅在标记样本上 进行训练，每进行一步，就有部分未标记样本利用当前分类函数进行分类， 再把这一部分已经分类的样本加入到标记样本集合中，如此重复直至所有未 标记样本都被分类。在这样的过程中既用到了标记样本又用到了未标记样本 进行最终分类器的训练。这类思想主要出现在这些文献中( 例如：s c u d d e r 【3 9 ， f r a l i c k 【4 0 ，a g r a w a l a 【4 1 】。 与半监督学习紧密相联系的转导推理( t r a n s d u c t i v e ) 的哲学思想，这种哲学思 想在上世纪7 0 年代由v a p n i k 等人首次提出( v a p n i ka n dc h e r v o n e n k i s 【4 3 ，v a p n i k a n ds t e r i n ，【4 4 】) 。相比与归纳推理( i n d u c t i v e ) 而言，我们只需要预测未标记样本 的标记，而不需要去构造更加复杂的分类器。我们没有必要为了做一件比较简 单的事情而去煞费苦心地去做一件相当复杂的事情。这种思想观念在后来发展 起来的支持向量机中得到了较为明显的体现，并由此发展了转导支持向量机算 法。转导支持向量机是半监督学习发展过程中最为重要的算法。 当h o s m e r 【4 5 等人在8 0 年代左右，提出一系列在混合模型中利用未标记样 本估计f i s h e r 线性判别准则时，半监督学习算法似乎得到了飞速发展。这些算法 考虑的情况是数据集的每一类都是服从高斯分布，并且各类之间的分布函数的 协方差矩阵是一样的。通过标记和未标记样本建立最大似然模型( 1 i k e l i h o o do f t h em o d e l ) ，然后通过e m ( e x p e c t a t i o nm a x i m i z a t i o n 【4 6 】) 迭代算法求出参数，得 到最后的分类。 半监督的发展是离不开算法依赖的假设条件的，往往一个新的假设会带来 一个算法新的生机以及新的应用领域。半监督学玎所依赖的假设有： 7 湖北大学硕士学位论文 ( 1 ) 光滑假设，如果两个样本点在高密度区域增r 近”( c l o s e ) ，则对应有一 样的输出。 ( 2 ) 聚类假设，见图1 4 ，如果两个样本点在同一个聚共中，则对应有一 样的输出。也可以说算法的分类器会落入在低密度区域。 图i4 檗粪假设 ( 3 ) 流形假设，见图1 5 ，即高维空间的数据一般嵌入在一个低维流形 中。假设所有数据都在高维表示空间的一个低雏嵌入子流形上，这时可以利用 未标记样本揭示数据的内在结构进而提高分类性能。这一假设反映了决策函数 的局部平滑性。与聚费假设着眼整体特性不同流形假设主要考虑模型的局部 特性。在该假设下大量未标记示例的作用就是让数据空问变得更加稠密，从 而有助于更加准确地刻画局部区域的特性，使得决策函数能够更好地进行数据 拟合。 啊 o 图1 5 流形假设 - ，_ j ? 正因为第三种假设条件的出现使得半监督学习在展近几年成为机器学习 研究领域最热门的醒题之一。无论的维数约简，还是模式识别将流形结构和 第1 章绪论 统计信息有机地结合在一起成为学习领域中要解决的主要问题。半监督学习主 要在分类问题上发展比较完全，基于正则化的半监督学习是目前比较成熟的一 块。后来发展了基于图去逼近流形【4 7 ，4 8 ，4 9 】，把分类器控制在流形上的半监督 正则化。而且现在基于流形的正则化半监督学习的推广性和一致性都研究的比 较成熟。t o n gz h a n g 5 0 ，5 1 1 等人得出这种基于图的正则化算法与图切2 n ( g r a p h c u t s ) 也有着紧密的联系。 1 2 3 流形学习与其他领域的交互发展 相比于经典的非监督的流形学习算法仅仅学习数据的流形结构而言，在 标记信息很少的情况下，当今众多研究者已经开始利用总体样本潜在的流 形结构增强学习算法的性能。这样的例子不乏在各个领域出现，例如：分 类( k r i s h n a p u r a m e ta 1 ，【5 2 ) ( b e l k i ne ta 1 ，【5 3 9 、流形对齐( h a me ta 1 ，【5 4 1 ) 、回 归( b e l k i n e ta 1 ，【5 5 】) ( z h ua n d g o l d b e r g ，【5 6 ) ( h u a nw a n g ，【5 7 ) 和姿态估计( j i h u n h a m ，【5 8 1 ) 等。这些都是成功将流形这种几何结构成功运用到其他领域的实例。 看过这些算法，再回头看我们的流形学习，就会有把统计信息运用到流形学 习算法中去增强算法这种很自然的想法。南京大学的周志华科研团队于2 0 0 7 提 出一种半监督维数约简的算法【5 9 1 ，这种算法通过标记信息定义了可连接约束 和不可连接约束，通过在保持这种约束条件下得到最后的线性投影，但这种 算法忽略了局部结构信息。m a s a s h is u g i y a m a 等人于2 0 0 7 年将l f d a ( i o c a lf i s h e r d i s c r i m i n a n ta n a l y s i s ) 和p c a 结合起来得出了能够既能保持未标记样本的全局结 构又能保持标记信息的算法【6 0 。清华大学的张长水科研团队【6 1 ，6 2 于2 0 0 8 年 在通过标记信息定义流形内( w i t h i n m a n i f o l d ) ，流形间( b e t w e e n m a n i f o l d ) ，和利 用总体样本定义了总流形( t o t a l m a n i f o l d ) 这三个量，最终通过最小化流形内的 间距，最大化流形间的间距，同时保持总体的流形结构得到最后的低维表示。 这两种算法基本都保留了l d a 算子的影子，都必须针对类内与类间定义相应的 量。x i ny a n g 等人2 0 0 6 年提出了一种半监督的维数约简算法【6 4 ，并且问题最 终转化为求解线性方程组。他们将i s o m a p , u e l t s a ，都做了改进。这个算 法主要是要在部分样本在低维空间的表示已知的情况下使用，不适合分类问 题。 1 3 拟解决的关键科学问题和主要研究内容 本文研究的主要内容是利用标记信息设计流形学习的新算法，以及将其算 法应用到信息挖掘和行为感知中。 如果我们从一个这样一个嵌入在三维空间中的一维流形上均匀采样，如 9 湖北大学硕士学位论文 图1 6研究目标 图1 6 ( a ) ，可能会出现类内距离并不比类间距离大的情况，如果我们用传统流形 学习算法把两个靠在一起的两个螺旋流形映射到二维空间中会得到如图1 6 ( b ) 中的情况。然而，我们总希望数据在低维空间中更能够体现它内在的本质特 征，图1 6 ( b ) 中的结果并没有达到这样的效果。在图1 6 ( c ) 我们可以清晰地看到 数据在类内仍然保持着流形的结构，而类问则拉开了距离，使得分类成为了一 个简单的任务。 虽然流形学习以及半监督学习领域云集了世界上相当多的科学家来专注此 课题。但通过这个简单的人工例子我们就能看出传统流形学习存在的盲区，从 中我们也可以看出这一块还具有相当多的问题可以挖掘。本文正是在这种情况 下提出来，并力求能够改进流形学习算法使得能够在这样的数据集上也具有很 好的性能。 要完成这样一个课题，需要从大量半监督学习算法提炼出标记信息在分类 问题、回归问题中所起的作用、运用的方式。比如正则化框架下在损失函数中 利用标记信息以及早期的e m ( e x p e c t a t i o nm a x i m i z a t i o n 4 6 ，6 5 】) 迭代算法中的隐 式变晕( h i d d e nv a r i a b l e ) 的运用。同时，我们也应该去研究其他维数约简中利用 标记信息的方式。 1 4 论文的主要组织结构 论文结构如下： 第1 章介绍维数约简和流形学习的背景、意义和主要研究方法。首先介绍了 1 0 第1 章绪论 几种主要的线性维数约简算法的发展历程，以及各个算法之间的相关性。接着 集中介绍了最为经典的流形学习算法，等距映射、局部线性嵌入映射、拉普拉 斯特征变换、扩散映射等算法的发展。为了引入半监督学习的概念，我们同时 也介绍了半监督学习的发展历程以及半监督学习算法发展过程几个非常重要的 几个假设条件，其中流形假设与本文所研究的内容是密切相关的。其次介绍了 迄今为止为数不多的几种半监督维数约简算法的发展过程。最后介绍了发展半 监督流形学习算法的必要性。 第2 章给出了几种最为主要流形学习算法的推导过程以及应用。首先，我们 介绍了传统线性维数约简算法的推导过程，从推导过程中讨论了线性算法的缺 点，并做实验指出了算法的不足之处。接着介绍了流形的概念以及流形学习的 定义。在此基础上，把流形学习最为典型的算法等距映射、局部线性嵌入映射 的推导过程以及实验结果呈现出来。然后，给出了一个图框架，把传统线性维 数约简算法以及经典的流形学习算法统一在此框架下，通过相似性的定义重新 审视了这些算法。最后，通过这些学习算法的介绍给出了半监督流形学习算法 发展的空间与环境。 第3 章主要介绍基于拉普拉斯特征映射算法的半监督拉普拉斯特征映射。首 先介绍了经典的拉普拉斯特征映射的推导过程，然后在此框架中