（计算机软件与理论专业论文）基于图的半监督学习算法研究.pdf

基于图的半监督学习算法研究摘要 论文题目： 专业： 硕士生： 指导教师： 基于图的半监督学习算法研究 计算机软件与理论 陈文晖 印鉴教授 摘要 近年来，半监督学习成为机器学习领域中的研究热点，并越来越受到国际机 器学习研究者的关注。其理论研究也越趋成熟，并且开始逐步应用于实际问题。 本文首先对半监督学习的相关背景知识进行了介绍，并回顾了几种经典的半 监督学习算法，其中更详细介绍了目前半监督学习领域的热点基于图的半监 督学习算法。在回顾几种重要算法的同时，本文还对基于图算法的相关问题进行 了探讨，如图的构造，图核的转换以及不相似信息的处理等。接着重点描述了本 文的主要工作。由于在基于图的半监督学习中，类标签的数目和分布位置都会对 算法的性能产生很大影响，基于此，本文尝试将不受标签影响的聚类分析算法同 基于图的半监督学习算法相结合以减少初始标签数目和分布情况所带来的影响。 另外，鉴于聚类算法聚类方向的不确定性，为减少这种不确定性，本文引入了与 半监督学习密切相关的主动学习。综合上述思想，本文提出一种结合基于密度的 聚类算法( o p t i c s ) 和主动学习的基于图的半监督学习算法s o p a ，并进而给出 该算法的一个框架。实验证明，本文提出的算法能够有效减少初始标签数目和分 布情况所带来的影响，使得基于图的半监督学习算法对初始标签的鲁棒性更好。 关键词：半监督学习、聚类、图 t i t l e ： m a j o r ： n a m e ： r e s e a r c ho ng r a p h b a s e ds e m i s u p e r v i s e dl e a r n i n ga l g o r i t h m s c o m p u t e rs o f t w a r ea n dt h e o r y w e n h u ic h e n s u p e r v is o r ：p r o f j i a ny i n a b s t r a c t s e m i s u p e r v i s e dl e a r n i n g ，w h i c hi sa ni m p o r t a n ta r e ao fm a c h i n el e a r n i n g ，h a s d r a w nw i d ea t t e n t i o nt h e s ey e a r s w i t hs e m i - s u p e r v i s e dl e a r n i n gb e i n ge x t e n s i v e l y c o n c e r n e d ，i t st h e o r e t i c a ls t u d yh a se x p e r i e n c e dar a p i dd e v e l o p m e n t m e a n w h i l e ，i t h a sa l s ob e e nu s e dt os o l v er e a lw o r l dp r o b l e m s i n t h i st h e s i s ，w ef i r s ti n t r o d u c eb a c k g r o u n dk n o w l e d g eo fs e m i s u p e r v i s e d l e a r n i n g ，a n dt h e ng i v es e v e r a lc l a s s i cs e m i s u p e r v i s e dl e a r n i n ga l g o r i t h m s ，e s p e c i a l l y g r a p h b a s e ds e m i - s u p e r v i s e dl e a r n i n ga l g o r i t h m ，w h i c hh a sb e e nt h em o s ta c t i v ea r e a o fr e s e a r c hi ns e m i s u p e r v i s e dl e a r n i n gd u r i n gt h el a s tc o u p l eo fy e a r s a l s o ，w e d i s c u s s e ds o m er e l a t e dp r o b l e m sc o n c e r n i n gg r a p h b a s e dm e t h o d s ，s u c ha st h e c o n s t r u c t i o no fg r a p h ，t h es p e c t r a lt r a n s f o r m a t i o no fg r a p hk e r n e l ，d i s s i m i l a r i t y , a n d s oo n w et h e ni n t r o d u c e do u rw o r ko ft h i st h e s i si nd e t a i l s i n c et h en u m b e ra n dt h e p o s i t i o no fl a b e l sh a v ea ni m p o r t a n ti n f l u e n c eo nt h ep e r f o r m a n c eo fg r a p h - b a s e d s e m i s u p e r v i s e dl e a r n i n ga l g o r i t h m s ，w et r yt oc o m b i n eg r a p h b a s e ds e m i - s u p e r v i s e d l e a r n i n gw i t hc l u s t e r i n ga l g o r i t h m s ，w h i c ha r en o ti n f l u e n c e db yl a b e l s d u et ot h e u n c e r t a i n t yo fc l u s t e r i n ga n a l y s i s ，w ea l s oc o m b i n ea c t i v el e a r n i n gt od i m i n i s ht h i s u n c e r t a i n t y b a s e do nt h ea n a l y s i sa b o v e ，w ep r o p o s e dt h ea l g o r i t h ms o p a w h i c h c o m b i n e sd e n s i t y b a s e dc l u s t e r i n ga l g o r i t h m s ( o p t i c s ) a n da c t i v el e a r n i n gw i t h g r a p h b a s e ds e m i s u p e r v i s e dl e a r n i n ga l g o r i t h m s m o r e o v e r , w es u g g e s t af r a m e w o r k w h i c hc o m b i n e sc l u s t e r i n ga n a l y s i sa n da c t i v el e a r n i n gw i t hs e m i s u p e r v i s e dl e a m i n g a l g o r i t h m s e x p e r i m e n t s s h o wt h a ts o p ai n d e e di n c r e a s e sp e r f o r m a n c e o f g r a p h b a s e ds e m i s u p e r v i s e d l e a r n i n ga l g o r i t h m ，a n d m a k e sg r a p h b a s e d s e m i s u p e r v i s e dl e a r n i n ga l g o r i t h m sm o r er o b u s tt ot h ei n i t i a ln u m b e ra n dp o s i t i o no f l a b e l s k e yw o r d s ：s e m i s u p e r v i s e dl e a r n i n g ，c l u s t e r i n gg r a p h 论文原创性声明 本人郑重声明：所呈交的学位论文，是本人在导师的指导下，独 立进行研究工作所取得的成果。除文中已经注明引用的内容外，本论 文不包含任何其他个人或集体已经发表或撰写过的作品成果。对本文 的研究作出重要贡献的个人和集体，均己在文中以明确方式标明。本 人完全意识到本声明的法律结果由本人承担。 学位论文作者签名： 日期： 学位论文使用授权声明 镶女蛘 铷们- 知 本人完全了解中山大学有关保留、使用学位论文的规定，即：学 校有权保留学位论文并向国家主管部门或其指定机构送交论文的电 子版和纸质版，有权将学位论文用于非赢利目的的少量复制并允许论 文进入学校图书馆、院系资料室被查阅，有权将学位论文的内容编入 有关数据库进行检索，可以采用复印、缩印或其他方法保存学位论文。 靴做作者签名聪坟晖翩魏舻 日期：o 胡年4 r 碉抄日日期：j 辞c r 月玉 日 基于图的半监督学习算法研究引言 引言 传统的机器学习领域包括无监督学习( u n s u p e r v i s e dl e a r n i n g ) ，监督学习 ( s u p e r v i s e dl e a r n i n 曲以及强化学( r e i n f o r c e m e n tl e a r n i n g ) ，其中无监督学习( 如 聚类等) 只考察无标注的数据集“，毛 ；监督学习( 如分类等) 首先利用已 标注的数据集 ( ，y 。) ，( ，只) ) 进行学习，从而对新数据工进行分类或预测等， 而强化学习则是通过学习系统不断观察环境，产生动作，获得评价，通过在行动 评价的环境中获得知识，从而改进行动策略以适应环境。 从前面可以看出由于无监督学习仅使用未标注数据进行学习，而不用已标注 的数据，这样导致无监督学习方向具有不确定性，往往很难达到人们预期的分类 目标。例如给出一系列数码产品让计算机进行分类，人们期望计算机能按类别进 行归类，如分类成m p 3 ，摄像机等，但是很可能因为缺少标注信息导致计算机按 照品牌进行分类，如分类成s o n y ，a s u $ 等。另外，监督学习只使用标注数据作为 训练数据进行学习，但是训练数据的大量获得需要耗费大量的资源( 毕竟训练数 据的标记需要人工进行) 。所以，同时使用未标注数据( u n l a b e l e dd a 啪和标注数据 ( 1 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 ) 越来越受到重视。 近年来，半监督学习也成为了机器学习中的重要研究领域之一。无论在理论还是 实际应用中半监督学习也都得到了长足的发展，并被广泛应用于各领域，如文本 分类，网页检索，视频和图像挖掘，语音识别，生物结构预测等。 正如上文所述，半监督学习不同于传统的机器学习方式，它是介于无监督学 习与监督学习之间的一种机器学习方式，主要研究当训练数据的标记( 1 a b e l ) 只有 部分存在的情况下，或者训练数据的部分信息不存在的情况下，如何获得具有良 好性能以及推广能力的学习机器。 早在1 9 世纪六七十年代就有了关于利用半监督思想的文献i x 3 】，当时这些 方法被称为自训练( s e l f - t r a i n i n g ) 、自学习( s e l f - l e a r n i n g ) 、自标号( s e l f - l a b e l i n g ) 等等。 这些方法主要是在分类算法中加入未标注数据来进行学习，从而获得效果更好的 学习机器。同期，文献【4 ，5 1 提出了一种直推( t r a n s d u c t i o n 或t r a n s d u c t i v ei n f e r e n c e ) 的概念，直推不同于归纳推理( i n d u c t i v ei n f e r e n c e ) ，直推只对训练和测试数据 基于图的半监督学习算法研究 引言 中的未标注数据进行分类或预测，而不能对训练和测试数据外的数据进行分类或 预测，而归纳推理可以将学习到的分类器用于训练和测试数据以外的数据。而目 前基于图的半监督学习算法大多属于直推算法。 从2 0 世纪八十年代以来对半监督学习的研究才真正进入了飞速发展的时代 6 1 0 ，而研究所涵盖的范围也非常广泛，其中包括半监督分类( s e m i s u p e r v i s e d c l a s s i f i c a t i o n ) ，半监督聚类( s e m i s u p e r v i s e dc l u s t e r i n g ) 以及半监督回归 ( s e m i s u p e r v i s e dr e g r e s s i o n ) 等。目前的研究主要集中于半监督分类方面，如文献 【1 l 一1 4 假设每一类数据符合某一种模型分布，那么整个数据集的数据分布是混合 的，于是用有限混合模型对数据的概率分布进行建模，最后利用标注数据和未标 注数据作为训练集并通过e m 等算法来学习模型参数；文献 1 5 ，1 6 1 首先用标注数 据集训练分类器，然后用该分类器对未标注数据进行分类，选择其中分类置信度 高的未标注数据连同预测的标记一起加入到训练数据中，然后再对该分类器进行 训练，不断重复此过程直至达到某一停止条件；文献 1 7 - 2 2 利用标注数据和未标 注数据以及这些数据的不同特征子集在数据的不同视图上用不同分类器进行训 练：文献 2 3 2 7 幂1 j 用同类数据之间的高密度以及不同类别数据之间的低密度区域 来进行半监督学习；文献 2 8 3 0 研究利用核方法( k e r n e lm e t h o d s ) 等统计学习理论 来用于半监督学习；文献【3 卜3 5 研究利用图论的知识和矩阵的谱分析来进行半监 督学习；文献 3 6 3 7 将半监督学习结合主动学习( a c t i v el e a r n i n g ) 来训练学习机器； 文献【3 8 】利用未标注数据以及正样本进行学习。除半监督分类以外，文献【3 9 】研 究半监督回归问题，文献【4 0 】对半监督聚类和无监督学习做了一个综述。还有一 些将半监督学习结合机器学习或模式识别其他一些问题的研究，如利用半监督的 高维数据降维或特征提取 4 1 1 ，基于半监督的距离度量学习 4 2 1 等。 在半监督学习的理论与实际应用方面的研究将是未来机器学习研究的重点 和热点。而对它的研究对我们更深入理解机器学习的本质有着重要的意义，例如 数据各种信息的有效利用，监督学习与半监督学习之间的区别与联系，数据的有 效表达等。 本文将主要对基于图的半监督学习，尤其是基于图的半监督分类进行初步探 讨。此外，由于在基于图的半监督学习中，类标签的数目和分布位置都会对算法 的性能产生很大影响。于是，本文尝试将不受标签影响的聚类分析算法同基于图 的半监督学习算法相结合以减少初始标签数目和分布情况所带来的影响。另外， 2 基于图的半监督学习算法研究引言 由于聚类算法聚类方向的不确定性，为减少这种不确定性，本文引入了与半监督 学习密切相关的主动学习。基于上述思想，本文提出一种结合基于密度的聚类算 法( o p t i c s ) 和主动学习的基于图的半监督学习算法s o p a ，并进而给出该算法 的一个框架。实验证明，本文提出的算法能够有效减少初始标签数目和分布情况 所带来的影响，使得基于图的半监督学习算法对初始标签的鲁棒性更好。 以下是本文的章节安排： 第一章中，本文首先介绍半监督学习的相关知识，然后简单介绍几种重要的 半监督学习算法。 第二章首先介绍了基于图的半监督学习，然后详细回顾了几个重要的基于图 的半监督学习算法，最后探讨了与基于图的方法相关的一些问题。 第三章详细介绍了本文的主要工作，包括本文的主要思路和提出的s o p a 算 法，并给出实验结果及分析。 第四章总结了本文的主要内容，并指出了下一步的工作重点。 3 基于图的半监督学习算法研究第l 章半监督学习综述 第1 章半监督学习综述 本章将简述半监督学习的背景知识，并在此基础之上回顾半监督学习中的几 种重要的算法。 1 1 半监督学习问题描述 半监督学习是介于监督学习与无监督学习之间的一种机器学习方法，它以未 标注数据和部分数据的监督信息( 包括标记或约束信息等) 作为训练数据。下面 将给出半监督学习的问题描述。 半监督学习( s e m i s u p e r v i s e dl e a r n i n g ) - - 般可分为半监督分类( s e m i s u p e r v i s e d c l a s s i f i c a t i o n ) ，半监督聚类( s e m i s u p e r v i s e dc l u s t e r i n g ) 和半监督回归 ( s e m i s u p e r v i s e dr e g r e s s i o n ) 。 半监督分类以石= 瓴，矗) 作为其训练数据集，其中五= “，而) 为己标 注数据( 1 a b e l e dd a t a ) ，其标记是巧= 挑，乃) ( 已知) ，置= 西坩，而+ 。 为未标 注数据( u n l a b e l e dd a t a ) ，其标记未知，n = ，+ 甜。半监督分类的目标就是利用这些 数据和标记信息对未标注数据进行分类。这里，如果只对置数据进行分类，则 这类问题被称为直推( t r a n s d u c t i v e ) l h q 题 4 5 】，如果是对整个数据空间进行分类， 即对训练和测试数据外的数据进行分类，此类问题被称为归纳推理( i n d u c t i v e ) i h - j 题。 半监督回归与半监督分类的区别在于是其预测的标记并不是离散的，而是连 续的数值。 半监督聚类，通常也被称为基于约束的半监督学习或基于约束的聚类。此类 问题以x = “，吒) 作为其训练数据集，训练数据中含有一种约束信息，但是不 提供标记信息。半监督聚类就是用这些数据和信息来进行学习。通常这类约束是 指等约束( m u s t 1 i n k s ) 和不等约束( c a n n o t 1 i n k s ) ，这里等约束指的是两个数据属于 同一类，而不等约束指的是两个数据不属于同一类。 4 基于图的半监督学习算法研究第1 章半监督学习综述 通常意义上的半监督学习指的是半监督分类，而本文所研究的主要内容也是 半监督分类，故下文所指的半监督学习如未特殊说明指的是半监督分类。 1 2 半监督学习的各种假设 半监督学习并不一定能有效提高机器学习的性能，在某些情况下甚至会降低 其学习效能。那么半监督学习什么时候才能有效工作呢? 对于这个问题，有不少 研究者给出了解释。例如，【4 3 】从数据分布估计的角度给出了一个直观的分析， 认为当从未标注数据中所获得的关于p ( x ) 的知识在对p lx ) 的推断过程中有益 的话，那么将会提升机器学习性能，否则非但不会提升反而还会降低其性能。实 际上，只要能合理建立未标记数据的分布和学习目标之间的关系，就可以利用未 标记数据来辅助提升学习性能。于是，研究者提出了一系列假设( a s s u m p t i o n s ) 来 建立未标记数据和目标之间的联系，而大部分机器学习能够有效工作的前提也是 这些假设成立，下面将简要介绍半监督学习中常用的几个假设【4 3 】： 半监督平滑性假设( s m o o t h n e s sa s s u m p t i o n ) ：如果两个数据点在高密度区域 ( h i g h - d e n s i t y ) 是邻近的，那么它们的标记也应该是相近的。根据传递性，这个假 设表示如果两个数据点之间有一条在数据分布高密度区域的路径相连，即它们属 于同一个聚类( c l u s t e r ) ，那么他们的标志也将是相近的。 聚类假设( c l u s t e ra s s u m p t i o n ) ：如果数据点位于相同的聚类( c l u s t e r ) 中，那么 它们将有较大可能拥有相同标记。这其实与平滑性假设所表达的意思是一致的， 聚在一起的数据点就是数据分布的高密度区域，也即是同一个聚类内的数据点存 在一条位于高密度区域的路径相连，所以它们的标志是相近的。但是值得注意的 是，该假设并没有说，不在同一个聚类的数据点不可能属于同一类。 低密度分割假设( 1 0 w - d e n s i t ys e p a r a t i o na s s u m p t i o n ) ：决策边界应该位于数据 的低密度区。此假设表达的意思也与上面的一致，不同类的数据点之间应该被数 据分布的低密度区域所分割开来。 流形假设( m a n i f o l da s s u m p t i o n ) ：在高维空间中一个很小的局部邻域内的数据 点在低维投影空间也应该是具有相似性质的，其标记也应该相似。此假设其实也 与上面所表述的意思一致，只是流形假设与前面几种假设的着眼点不同，流形假 5 基于图的半监督学习算法研究第1 章半监督学习综述 设更主要考虑局部特性。 由此可见，上述几种假设虽然表述不同，但所包含的意思大致是相同的，即 数据空间中的数据分布有稠密和稀疏区域，而决策边界应该位于数据稀疏的地方 而不是稠密的区域，而这些假设就是保证大量未标记数据能够分辨出其中的稠密 和稀疏区域。 1 3 几种重要的半监督学习算法 本节将介绍几种重要的半监督学习算法。根据半监督学习算法的工作方式， 现有的半监督学习算法大致可分为以下四类。第一类是用混合产生式模型 ( g e n e r a t i v em o d e l s ) 为数据建模，以未标注数据的标记作为未知量，然后用e m 等 算法来求得模型参数。因为这类算法假设在同一个聚类的数据点属于同一类，所 以这类算法主要体现的是聚类假设，其代表文献有 11 1 4 。自训练( s e l f - t r a i n i n g ) 算法属于这类算法的一个变体【4 4 】，自训练的代表文献有【l 一3 ，1 5 ，1 6 1 。第二类算 法是协同训练( c o - t r a i n i n g ) 算法或多视图学习( m u l t i - v i e wl e a r n i n g ) 算法，这类算法 使用两个或多个学习器。这些学习器先用标注数据进行训练然后选择置信度高的 未标注数据进行标记，接着把新得到的标注数据给对方学习，这样不断重复从而 得到性能良好的分类器。这类算法的代表有 1 7 - 2 2 。第三类算法主要基于低密度 分割假设，使决策边界远离数据点，位于数据分布的低密度区，将不同类的数据 分割在低密度区域的两端，这类算法的代表包括 2 3 2 7 。第四类算法是基于图的 半监督学习算法，也是近年来半监督学习研究的热点。这类算法中，数据及其之 间的关系用图来表示，其中图的结点表示数据点，结点之间的边通过某种相似性 度量来赋予其权重，表示的是数据之间的相似度。为数据建好图后，一般定义优 化目标( 通常是最小化某个代价函数) ，并求解这个优化目标来得到最优模型参 数。这类算法的代表有 3 1 3 5 1 。本章接下来部分将对各种半监督学习算法作进一 步介绍。 1 3 1 产生式模型( g e n e r a t i v em o d e l s ) 半监督学习的产生式模型算法最早出现于2 0 世纪七八十年代，这类算法假 设用模型p “力= p r y ) 烈x l 力对数据建模，其中p ( x i 力是一个混合分布，例如 6 基于图的半监督学习算法研究第l 章半监督学习综述 假设每类数据都是高斯分布的，那么由这些数据所组成的整个数据集将服从于由 c 个高斯分布混合而成的分布( 假设共有c 类) 。这样大量的无标注数据加上少量 的各类的带标注数据就能用来求出组成该混合分布的各个模型的参数。 所以这类方法一般是用各种模型对数据进行建模，然后通过求解模型参数的 方法最大化p “力= p f y ) p ( xi 力。通常求解的过程中一般不能得到闭形式的解， 故常用e m 算法来找对应于各个类的模型参数。算法首先利用标注数据估计一组 参数，然后在e s t e p 利用该参数为未标注数据进行标记，最后在m s t e p 中用标 注数据和未标注数据及其新得到的标签重新估计参数并更新参数，这样e s t e p 和m s t e p 不断重复直至收敛。 在产生式模型算法中，对数据或领域的知识可以用来建立模型，这对于模型 的选择和建立以及最后的效果都有很大帮助。而且如果所建立的模型适合数据的 话，分类器性能将会大大提高。 但是，这里有一个问题，就是通常很难去验证模型的正确性。而且用e m 算 法来估计参数，很可能导致求得的并不是全局最优解，而是局部最优。此外，如 果模型选择得不好的话，未标注数据很可能反而会使影响其性能【4 3 ，4 4 。 1 3 2 自训练( s e l f - t r a i n i n g ) 自训练可以说是各种半监督学习算法中最简单，也用得最广泛的半监督学习 算法。该算法首先用标注数据训练分类器，然后用训练好的分类器为无标注数据 进行分类或标记，再选取其中置信度最高的若干个无标注数据放入到标注数据训 练集里，接着用新的训练集对前面的分类器再次训练，并不断重复此过程，直至 达到某停止条件。该算法的大致流程可见图1 1 。 输入：标注数据集( 五，鬈) ，未标注数据集五 过程： 1 用标注数据集及其标记( 蜀，z ) 来训练分类器厂 2 用厂来为未标注数据集五中的数据x 进行分类或标记，得厂( 力 3 将置信度最高的k 个预测结果( 五( x ”加入到标注数据训练集中 4 重复l 3 ，直至达到停l 匕条件 图1 1 自训练算法的流程 从前面的描述和图1 1 可见，自训练很像产生式模型算法，都是先用未标注 7 基于图的半监督学习算法研究第1 章半监督学习综述 数据进行训练，然后对未标注数据进行标记，并利用得到的标记再次学习的过程。 也可看出该算法用自己的预测结果来训练自己，所以被称为自训练( s e l f - t r a i n i n g ) 。 正是因为这个原因，如果分类器对未标注数据的分类或标记出现错误的话，将会 使得这个错误在后面的训练中不断扩大增强。针对这个问题，有许多研究者提出 了自训练的一些变体，如图1 1 中第3 步可以选择将置信度高的预测结果( 瑚 放入到训练集中，或者将所有预测结果放入到训练集中，但是按照置信度为它们 加上权重。 1 3 3 协同训练( c o - t r a i n i n g ) 和多视图学习( m u l t i v i e wl e a r n i n g ) 协同训练最早i 由b l u m 和m i t c h e l l 1 7 在1 9 9 8 年提出。在该文中，作者利用数 据集的两个视图( v i e w ) 来对数据进行分类。他们假设能将数据集的属性x 分为 两个子属性集( 视图) 1 ；x ( 2 】，这些子属性集满足以下条件：第一，每个子 属性集x ( 1 或x ( 2 都足以用来训练一个好的分类器；第二，在给定类标记时，每 个子集x ( 1 和x ( 2 ) 之间是条件独立的。例如，在网页分类中，一个网页可以用两 个属性子集表示，一个是该网页本身的文本内容( x ( 1 ) ) ，另一个是链接到该网 页的超链接或锚文本( a n c h o rt e x t ) ( x ( 2 ) ，这两个属性子集就构成了网页的两 个满足条件的视图。b l u m 和m i t c h e l l 用标注数据的这两个属性子集分别训练两个 独立的分类器。然后，每个分类器都各自为未标注数据进行分类，并从中挑选出 置信度高的决策结果，把它们加入到另一个分类器的标注数据训练集中。每个分 类器利用各自新得到的标注数据训练集和原有标注数据进行再训练。这个过程不 断重复，直到达到某个停止条件。该算法流程如图1 2 所示。 输入：标注数据集( 葺，影) ，未标注数据集五 过程： 1 用( 五n ，z ) 和( 五孙，巧) 分别训练两个独立的分类器1 和。 2 分别用f o ) 和厂2 为未标注数据集l 中数据x 进行分类或标记 3 将分类器f 的置信度最高的k 个决策结果( 五f ( o ( 曲) 加入到分类器 f 2 的标注数据训练集中：将分类器厂2 的置信度最高的k 个决策结果 ( 毛，2 ( x ”加入到分类器1 的标注数据训练集中。 4 重复l 3 ，直至达到某个停l e 条件。 图1 2 协同训练算法的流程 8 基于图的半监督学习算法研究第l 章半监督学习综述 协同训练利用数据不同视图的思想为多视图学习( m u l t i v i e wl e a r n i n g ) 奠定 了基础。下面介绍另一种经典的半监督多视图学习算法c o e m 。 n i g a m 和g h a n i 1 8 在2 0 0 0 年给出t c o e m 算法，它是协同训练的一个变体。 c o e m 与协同训练的区别在于，它在每轮循环中每个分类器为所有数据( 包括标 注数据和未标注数据) 进行决策，并将一个分类器的概率标注结果应用于另一个 分类器，而且是所有的标注结果，而不是置信度最高的k 个，其算法流程如图1 3 所示。 输入：标注数据集( 五，巧) ，未标注数据集五 过程： 1 用( 蜀n ，) 和( 墨2 1 ，巧) 分别训练两个独立的分类器1 和。 2 分别用厂1 和厂2 为所有数据x ( 包括未标注数据和标注数据) 进行分 类或标记，并得到概率标记p ( f ，功。 3 将分类器厂1 的所有决策结果( x ，p ( 厂n ，_ x ) ) 作为分类器f 2 的训练集 中；将分类器，2 的所有决策结果( 五p ( ，瑚作为分类器，1 的训练集 中。 4 重复1 - 3 ，直至达到某个停i e 条件。 图1 - 3c o - e m 算法的流程 协同训练能有效避免自训练算法中错误不断增强的问题，鲁棒性也更好。此 外，文献【1 7 】对协同训练进行了分析，证明若数据集的属性能分成满足条件的属 性子集，那么协同训练能有效利用未标注数据来提升学习器的性能。然而，实际 上，这些条件往往很难满足。虽然，n i g a m 和g h a n i 在文献【l8 】通过大量实验证明 了，当属性集充分大时，对属性集进行随机划分，利用这种划分的协同训练也能 取得较好效果。但是，这也同样难以满足，因为我们不能保证实际问题中数据的 属性集充分大。之后，许多研究者针对这个问题提出了一系列改进算法或措施 1 9 2 1 ，并得到了较好的效果。 1 3 4 基于低密度分割的半监督学习算法 基于低密度分割的半监督学习算法主要思想是利用低密度分割假设，使决策 边界位于数据的低密度区域，不同类别的数据用最大的间隔( m a xm a r g i n ) 分割 开来。基于这个思想，使人们很自然的想到了常用的最大间隔算法，如支持向量 9 基于图的半监督学习算法研究 第l 章半监督学习综述 机( s u p p o r tv e c t o rm a c h i n e ，s v m ) 。传统的支持向量机s v m 问题是一个二分类 问题，可以描述如下： 嘶罂之董+ 翔w l l 2 ”，6 i _ 一= l 一 2 ” s j ：y a w 葺一6 ) l 一毒 茧o ，v i = 1 ，| 其中，w 是h i l b e r t 空间中的权向量，孝是松弛变量，也可以描述成【4 4 】： m h 理乏磊+ 制t , b ，f 智“ ”“ s j ：y a h ( x , ) 一6 ) l 一磊 缶0 ，v i = l ， 其中，k 是核( k e r n e l ) 矩阵，旯 0 ，巩再生h i l b e r t 核空间( r e p r o d u c i n g h i l b e r tk e r n e ls p a c e ) ，h 吼，也即 m ，i n ( 卜乃( t ) ) + + 删t 7 i f f i i 。 其中，( 力+ = m a x ( f ，0 ) ，是一个h i n g el o s s 函数。传统的s v m 得出决策函 数八曲= 顶功+ 6 后就可以为数据x 进行分类，标志为s i g n ( f ( x ) ) 。 传统的s v m 是一个分类算法，其目标函数使得决策边界远离标注数据，并 选择最大间隔的决策边界将不同类别的数据分隔开来。而在半监督学习中，由于 其同时使用未标注数据和标注数据，所以需要对s v m 进行改动使其适应半监督 学习。改动后的s v m 称为直推式支持向量机( t r a n s d u c t i v es v m ，t s v m ) ，由 于其得出的决策函数也可用于训练与测试数据以外的数据，所以也被称为半监督 支持向量机( s e m i s u p e r v i s e ds v m ，s 3 v t v l ) 。t s v m 问题描述为： 叩e ( i - y j ( x ，) ) + + 训厅噍+ 五( 1 - | ( 毛) i ) + 7 i = l i = 1 + 1 这样，t s v m 就将未标注数据融合进s v m 的目标函数了，并使得决策边界 远离标注数据的同时远离未标注数据。图l 一4 是t s v m 的大致算法流程。 但是由于t s v m 的目标函数中加入的新项并非凸( c o n v e x ) 函数，使得整个 目标函数变为非凸( n o n - c o n v e x ) 函数，而求解这个最优化问题也变成了n p 难问 题 4 4 1 ，而且随着数据量的增大，运算量也急剧增大。于是，许多研究者在求解 l o 基于图的半监督学习算法研究第1 章半监督学习综述 方面进行了大量的研究，以提高求解效率。例如，d eb i e 和c r i s t i a n i n i 4 5 利用半 定规划( s e m i d e f i n i t ep r o g r a m m i n g ，s d p ) 的方法来求解最优化函数。 输入：标注数据集( 五，鬈) ，未标注数据集五，核k ，权重五，五 过程： 1 求解最优化问题： 吁嘻( 1 一乃( 置) ) + + 硎b 五i - - + l ( 1 一) | ) + 得到决策函数厂2 2 用s i g n ( f ( x ) ) 为数据x 进行标记。 图1 4t s v m s 3 v m 算法的流程 此外，还有其他一些利用低密度分割假设的半监督学习算法，如l a w r e n c e 和j o r d a n 2 7 提出一个高斯过程( g a u s s i a np r o c e s s ) 方法，他们修改高斯过程的 噪音模型，在其中增加一个“0 类，使其区别于原本的正反类，然后限制所有 未标注数据点都不能被分类为“0 ”类，这使得决策边界远离未标注数据，即数 据的高密度区域。又如，s z u m m e r 和j a a k k o l a 2 5 提出信息正则化的框架，通过 p ( 功来控制条件概率p ( y l 力，其基本思想是数据的标志在p ( 力大的区域的变化 应该很小，而其中p ( 曲是从无标注数据的分布估计得到的。此外，还有g r a n d v a l e t 和b e n g i o 2 6 提出用最小化熵的方法来进行半监督学习等。 1 4 本章小结 本章主要介绍半监督学习的相关背景知识和问题描述，并在此基础上给出了 半监督学习常用的几种假设。此外，本章还介绍了几种重要的半监督学习算法。 基于图的半监督学习算法研究第2 章基于图的半监督学习算法 第2 章基于图的半监督学习算法 上一章简要介绍了半监督学习的相关背景知识及几种主要算法，这章首先介 绍基于图的半监督学习算法的相关知识，然后再介绍几种重要的基于图的半监督 学习算法以及一些相关问题。 2 1 相关知识及问题描述 基于图的半监督学习算法最大的特点就是用图来表示数据之间的关系，其中 图的结点表示数据点，点与点之间存在着边，这些边被赋予权重，权重代表数据 点之间的相似度，一般相似度越大，权重越大，若结点之间不存在边连接则表示 两点之间相似度为零。而相似性度量一般通过各种距离度量获得，这些距离度量 包括欧几里得( e u c l i d ) 距离，马氏( m a h a l a n o i s ) 距离，切比雪夫( c h e b y s h e v ) 距离等，本章将在后面介绍这些距离。 令g = ( y ，d 表示一个图，其中矿表示结点集，即数据点集。边p = 以，) 的权 重为w ( p ) = ，表示结点f ，之间的相似度，有= w 。于是可以得到图g 的 权重矩阵形，其中 矾 w ( p ) 2 f p = ( ，加e 【0 o t h e r w i s e 由此可见矿是一个对称矩阵。令d 为对角矩阵，其中以# ，然后可 以得到图l a p l a c i a n 。图l a p l a c i a n 有几种形式，其中最常用的有以下两种：一种 是非归一化的图l a p l a c i a n ：a = d 一形；另一种是归一化的图l a p l a c i a n ： 三= i 一矿2 w d - 2 ，其中，是单位矩阵。 目前大部分基于图的半监督学习算法都使用了图l a p l a c i a n ，并且通过图来 估计一个分类函数f 。通常需要满足：第一，在标注数据点上，的值应该与 乃相近，这通常由一个损失函数来保证；第二，f 对于图上的点的值应该是平滑 的，即满足聚类或平滑性等假设，这通常通过引入正则项( r e g u l a r i z e r ) 来保证。 1 2 基于图的半监督学习算法研究 第2 章基于图的半监督学习算法 这里，引入正则项的方法称为正则化( r e g u l a r i z a t i o n ) 法。正则化法是通过在一 个问题中引入一些额外的信息或附加条件( 即正则项) 来引导学习。引入的这些 额外信息或附加条件的目的通常是限制解的范围，减少求解的复杂性，或避免过 拟合等。 许多基于图的半监督学习算法都是相似的，都是先建立优化目标或代价函数 ( c o s tf u n c t i o n ) ( 通常由损失函数和正则项构成) ，并通过各种最优化方法进行 求解，使代价函数最小化。大部分基于图的半监督学习算法之间不同的地方只是 在于对损失函数和正则项的选择不同而已。下一节将具体介绍几个重要的基于图 的半监督学习算法。 2 2 几个重要的基于图的半监督学习算法 从上一节的描述可知，基于图的半监督学习算法通常是建立一个优化目标或 最小化某个代价函数( c o s tf u n c t i o n ) 。该代价函数通常由一个损失函数( 1 0 s s f u n c t i o n ) 和正则项( r e g u l a r i z e r ) 构成，然后通过最优化方法来求解。这节将具 体介绍几个重要的基于图的半监督学习算法，以及各自目标函数中的损失函数和 正则项。 2 2 1 基于高斯场( g a u s s i a nf i e l d s ) 和调和函数( h a r m o n i cf u n c t i o n s ) 的 算法 基于高斯场和调和函数的算法( 下文简称g f h f ) 是i 扫z h u 等人【3 1 】在2 0 0 3 年提出的。在该算法中，z h u 给出目标函数如下： w # ( f ( x i ) - f ( x ) ) 2 i , j = l , - - - , 聆 l 一， 其中，为调和函数，即满足：1 在无标注数据点上的值为o ；2 在标 注数据点上取值为其标志值，即( 薯) = 只f o ri = 1 ，。最小化上式表示对于相 邻的点或相似度大的点( 嘞大) ，它们的标记，( 薯) 和，( ) 应该相近或相等。 若用图l a p l a c i a n ：4 ，重写上式，可得： w o ( f ( x j ) - f ( x j ) ) 2 矿缈i , j = l ，以 1 3 基于图的半监督学习算法研究第2 章基于图的半监督学习算法 于是，优化目标变为： 删n ( ( ) 一八_ ) ) 2 = t 缈 ( 2 1 ) 该优化目标的求解过程如下。矩阵w 通过变换，将标注数据所在行和列变 为前，行和列，然后可写成： 形= 暖毙 矩阵。和4 也进行相同的变换，类似地，令厂= 至 ，彳表示数据点，的标 记值。 由于4 厂在无标注数据点上等于0 ，且在标注数据点上取值为其标志值， 故有： 工= ( d 厶一呒。) 。1 z = 一4 。】； ( 2 2 ) 下面图2 1 是g f h f 的大致算法流程： 输入：标注数据集c _ ，巧，未标注数据集