（计算机应用技术专业论文）用未标记数据增强分类器能力的研究.pdf

r e s e 尽 的 东南大学学位论文使用授权声明 东南大学、中国科学技术信息研究所、国家图书馆有权保留本人所送交学位论文的复印 件和电子文档，可以采用影印、缩印或其他复制手段保存论文。本人电子文档的内容和纸质 论文的内容相一致。除在保密期内的保密论文外，允许论文被查阅和借阅，可以公布( 包括夸 刊登) 论文的全部或部分内容。论文的公布( 包括刊登) 授权东南大学研究生院办理。 研究生签名：童每哩卜导师签名： e t 期：型：! 亟兰l 摘要 摘要 传统的分类问题需要通过大量的标记样本进行学习，以预测未来样本的标汜。然而在实 际的分类应用中，比如图像分析、网页分类、蛋白质结构预测等，标记样本往往数鼍比较少， 获取成本比较高；而未标记样本往往大量存在，其获取成本也相对较低。因此如何利用大量 未标记数据末改善学习的效果，成为了机器学习领域备受关注的课题，针对此问题的研究方 法被称之为半监督学习。 以往许多半监督学习研究工作都侧重于设计专有的学习方法，使其能够利用大量未标记 数据辅助标记数据的学习。然而，经常会有这样的情况，对于特定应用，已经有了最合适的 监督学习方法，希望能够借助大量未标记数据来提高已有方法的效果。同时，对于那些已有 的半监督学习方法而占，希望在其基础之上，运用某种方法再次提高它的效果。所以寻找一 种能够结合大量的未标记数据来增强已有学习器的效果的方法，非常有实际意义。为区别于 一般的半监督学习方法，本文称这种半监督学习的思路为半监督增强( s e m i s u p e r v i s e d i m p r o v e m e n t ，s s i ) 。 大部分的半监督增强方法都采用基于置信度的迭代式框架，存在的主要问题有：受到置 信度方法的限制，只能增强软标记的分类方法；依靠分类器现有模型扩展标记数据集，增强 效果不明显；容易放大训练初期的错误，以导致精度退化。 针对这些问题，本文在传统的半监督增强框架上进行了研究和拓展，提出了基于独立置备， 信度的半监督增强框架( s e m i s u p e r v i s e di m p r o v e m e n tf r a m e w o r k b a s e do ne x t e r n a lc o n f i d e n c e ， s i f e c ) ，该框架利用与已有分类器无关的置信度计算方法，客观的评判出标记的正确性，从 而有效地改善了传统的置信度方法在迭代过程中更新信息少和强化早期错误的问题，同时打 破了传统框架中对于学习器种类的限制，能够修下任意学习方法：还在传统的增量式数据集。 更新方式的基础上，提出了一种新的过滤式数据集更新方式，改善了贪婪式框架不能修正已 有训练集中存在的错误的问题；最后进一步对传统的半监督增强框架进行了泛化，使其从针 对特定学习方法进行增强的框架，变成了针对未标记数据的某个预测结果进行增强的框架， 靶 允许框架根据特定数据集更换重训练方法，进一步提高了框架的增强效果。置信度计算方法 是半监督增强框架中的关键问题，本文借鉴基于图的半监督学习方法，提出了三种独立的标 记置信度计算方法：g s w 方法、m s g 方法、m a c c 方法，能够有效的选出已有标记中置信 度高的数据。 跨膜蛋白质数据集以及u c i 基准数据集上的实验结果表明，配合适当的重训练方法，本 文提出的泛化的半监督增强框架以及独立的置信度方法能有效的提高已有分类器的分类效 果，达到甚至超过目前较好的半监督学习方法的水平。 关键字 半监督增强，独立置信度方法，基于图的半监督学习方法 a b s t r a c t a b s t r a c t a l a r g e n u m b e ro fl a b e l e dd a t aa r er e q u i r e dt ot r a i nag o o dc l a s s i f i e ri n t r a d i t i o n a l c l a s s i f i c a t i o np r o b l e m s h o w e v e r , i nr e a l - w o r l da p p l i c a t i o n s ，s u c ha sa p p l i c a t i o n si nb i o i n f o r m a t i c s a n dm e d i c a ld o m a i n ，l a b e l e dd a t aa r eo f t e ni n a d e q u a t eo rh a r dt oo b t a i n w h i l eu n l a b e l e dd a t aa r e u s u a l l ya v a i l a b l ei nl a r g eq u a n t i t i e s m a n ys e m i s u p e r v i s e dl e a r n i n g ( s s l ) a l g o r i t h m sa r ep r o p o s e d t ot a k ea d v a n t a g eo fu n l a b e l e dd a t a m o s tp r e v i o u ss t u d i e sh a v ef o c u s e do nd e s i g n i n gs p e c i a la l g o r i t h m st oe f f e c t i v e l ye x p l o i tt h e u n l a b e l e dd a t ai nc o n j u n c t i o nw i t hl a b e l e dd a t a h o w e v e r , i ti so f t e nt h ec a s et h a tau s e ra l r e a d yh a s a f a v o r i t e ( w e l l s u i t e d ) s u p e r v i s e dl e a r n i n ga l g o r i t h mf o r b i sa p p l i c a t i o n ，a n dw o u l dl i k et oi m p r o v e i t sp e r f o r m a n c eb yu t i l i z i n gt h ea v a i l a b l eu n l a b e l e dd a t a a tt h em e a nt i m e as e m i s u p e r v i s e d l e a r n i n gm e t h o dm a yn e e df u r t h e ri m p r o v e m e n t s oi ti sm e a n i n g f u lt od e s i g nat e c h n i q u et o e n h a n c ee x i s t i n gl e a r n i n ga l g o r i t h m sb yu t i l i z i n gu n l a b e l e dd a t a t h i s t e c h n i q u ei sn a m e da s s e m i - s u p e r v i s e di m p r o v e m e n t ( s s i ) ，d i s t i n g u i s h i n g f r o m g e n e r a ls e m i - s u p e r v i s e dl e a r n i n g a p p r o a c h e s m o s te x i s t i n gs s im e t h o d sb e l o n gt ot h ei t e r a t i v ef r a m e w o r kb a s e do nl a b e lc o n f i d e n c e t h e p r o b l e m se x i s t i n gi nt h et r a d i t i o n a ls s if r a m e w o r ki n c l u d e ：t h et y p e so fl e a r n i n ga l g o r i t h m sw h i c h c a nb ei m p r o v e da r el i m i t e d ；t h ei m p r o v e m e n to fl e a r n i n gm e t h o d si sn o ts i g n i f i c a n ts i n c et h e t r a i n i n gs e ti se n l a r g e da c c o r d i n gt ot h ec l a s s i f i e ri t s e l f ；t r a i n i n ge r r o r si nt h ee a r l yr o u n d st e n dt ob e e n h a n c e di nt h ei t e r a t i o na n dm a yc a u s ea c c u r a c yd e g r a d a t i o n t os o l v et h e s ep r o b l e m s ，t h et r a d i t i o n a lf r a m e w o r ki ss t u d i e da n de x t e n d e di nt h ep a p e r a n o v e ls e m i - s u p e r v i s e di m p r o v e m e n tf r a m e w o r kb a s e do ne x t e r n a lc o n f i d e n c em e t h o d ( s i f e c li s p r o p o s e d ，w h i c hb r e a k st h er e s t r i c t i o no ft y p e so fl e a r n i n ga l g o r i t h m st ob ei m p r o v e da n di sa b l et o e n h a n c et h ep e r f o r m a n c eo fa n yg i v e nl e a r n i n ga l g o r i t h m b e c a u s eo ft h ei n t r o d u c t i o no fe x t e r n a l c o n f i d e n c em e t h o d s ，t h ee f f e c t i v e n e s so ft h ef r a m e w o r ki s s i g n i f i c a n t l yi m p r o v e d af i l t e r i n g m e t h o df o re n l a r g e m e n to ft r a i n i n gs e ti sp r o p o s e da st h ea l t e r a t i v eo ft h et r a d i t i o n a li n c r e m e n t a l m e t h o di ne x i s t i n gs s im e t h o d s ，w h i c hc a nr e v i s et h ee a r l ym i s t a k e si nt h et r a i n i n gs e t m o r e o v e r , b yf u r t h e re x t e n d i n gt h et r a d i t i o n a lf r a m e w o r k ，t h ep a p e re n a b l e st h ef r a m e w o r kt oc h o o s ep r o p e r r e t r a i n i n gm e t h o d i n s p i r e db yg 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 ，t h r e ee x t e r n a l c o n f i d e n c em e t h o d sa r ep r o p o s e df o rl a b e lc o n f i d e n c ec a l c u l a t i o n ：g s wm e t h o d m s gm e t h o da n d m a c cm e t h o d e x p e r i m e n t a lr e s u l t so nt r a n s m e m b r a n ep r o t e i nd a t a s e ta n ds e v e r a lb e n c h m a r kd a t a b a s e s s h o wt h a tt h ep r o p o s e ds e m i - s u p e r v i s e di m p r o v e m e n tf r a m e w o r ka n dc o n f i d e n c em e t h o d sc a n i m p r o v et h ep e r f o r m a n c eo fa n yg i v e nl e a r n i n ga l g o r i t h me f f e c t i v e l yi ft h er e t r a i n i n gm e t h o di s p r o p e r l yc h o s e n n ep e r f o r m a n c eo fi m p r o v e dl e a r n i n ga l g o r i t h m si sc o m p a r a b l et ot h e s t a t e o f - t h e a f ts e m i - s u p e r v i s e dl e a r n i n gm e t h o d s k e y w o r d s s e m i s u p e r v i s e di m p r o v e m e n t ，e x t e r n a lc o n f i d e n c em e t h o d ，g r a p h b a s e dm e t h o d s 目录 目录 摘要i a b s t r a c t ；i i 目j 录i i i 第一章引言。“1 1 1 半监督学习研究的背景1 1 2 半监督学习基本原理与假设2 1 2 1 聚类假设3 1 2 2 流形假设3 1 3 半监督学习常见方法3 1 3 1 自训练方法3 1 3 2 生成模型方法，：4 1 3 3 基于信息不一致的方法4 1 3 4 直推式支持向量机5 1 3 5 基于图的方法5 1 4 研究的意义6 1 5 论文的组织结构6 第二章半监督增强框架的研究。8 2 1 半监督增强问题描述8 2 2 分类器增强已有方法分析9 2 2 1 迭代式半监督增强框架的描述9 2 2 2 迭代式半监督增强框架的可行性分析1 0 2 2 3 传统的置信度方法中存在的问题1 0 2 3 基于独立置信度的半监督增强框架1 2 2 3 1 基于独立置信度的半监督增强框架的描述1 2 2 3 2 基于独立置信度的半监督增强框架正确性分析1 2 2 3 3 基于独立置信度的半监督增强框架的优点1 3 2 4 训练集更新方式研究1 3 2 5 半监督增强问题的泛化1 4 2 6 本章小结1 s 第三章基于图的半监督学习方法及相关问题分析1 6 3 1 问题描述与基本思想。1 6 3 2 图的构造问题的分析1 6 3 2 1 距离的度量1 7 3 2 2 图的稀疏化1 7 3 2 3 图权重的重新确定1 9 3 3 儿个重要的基于图的半监督学习方法1 9 3 3 1 最小切方法。1 9 3 3 2 高斯混合场与谐波函数方法。2 0 3 3 3 基于局部和全局一致性的方法2 0 3 3 4 流形正则化方法。2 1 i i i 目录 3 3 5 交替最小化图直推方法2 2 3 4 对于数据不平衡和噪声问题的处理2 4 3 4 1 对于图的处理2 4 3 4 2 对于正则化优化目标的处理2 4 3 4 3 对于分类结果的处理2 5 3 s 基于图的半监督学习相关问题总结2 5 3 6 本章小结2 6 第四章独立的标记置信度的计算问题研究：。2 7 4 1 基丁图的半监督包装器方法2 7 4 1 1 方法基础。2 7 4 1 2 详细算法描述2 8 4 1 3 方法分析2 8 4 2 基u 丁梯度的置信度方法3 0 4 2 1 方法基础3 0 4 2 2 方法分析与详细算法描述3 2 4 3 本章小结3 3 第五章基于独立置信度的半监督增强框架实验研究3 4 5 1 实验数据集3 4 s 1 1 跨膜蛋白质数据集：3 4 s 1 2u c i 基准数据集3 4 。 5 2 实验基础设定3 4 5 2 1 跨膜蛋白数据集实验设定一3 5 5 2 2u c i 基准数据集实验设定3 6 5 3 实验结果与分析3 7 5 3 1 跨膜蛋白数据集实验结果分析3 7 s 3 2u c i 数据集半监督置信度方法比较3 8 5 3 3 重训练方法对于二卜监督增强框架的影响研究3 9 。 s 3 4 半监督增强框架与s t a t e o f - t h e a r t 的? 卜监督学习方法效果比较4 1 5 3 5 实验总结。4 3 s 4 相关问题研究与分析4 4 s 4 1 置信度方法参数敏感度分析一4 4 s 4 2 半监督增强迭代次数的考虑4 5 5 5 本章小节4 6 第六章总结与展望。4 7 6 1 论文总结4 7 6 2 研究展望4 8 致谢q 1 9 参考文献5 0 附录a 详细实验结果5 3 u c i 数据集重训练方法为l d a 的实验结果5 3 u c i 数据集重训练方法为s d a 的实验结果5 6 附录b 攻读硕士学位期间完成的论文5 9 i v 第一章引吉 1 1 半监督学习研究的背景 第一章引言 机器学习这门学科关注的问题是：计算机程序如何随着经验积累自动提高性能【l 】。机器 学习研究的目的在于，希望能够设计某些方法，使之可以通过对已知数据的学习，找到数据 内在的相互依赖关系，从而对未知数据进行预测或对其性质进行判断；与此同时，还希望这 种方法能有很好的适应性。 监督学习属于机器学习的子领域。监督学习用来学习系统观测到的一个标记训练集，其 训练样本由特征和标记组成，表示为 0 l ，y 1 ) ，y 。) 】，其中姐y 称为标记。监督学习 的目的是对任意新来的特征x 预测其标记y ，学习的性能由训练得到的模型在测试样本集上的 预测性能来衡量。当y 尺时，称相应的监督学习为回归；当y 取一些离散的值时，称相应 的监督学习为分类。 传统的监督学习中，学习器通过利用大量的带标记的训练数据( 1 a b e l e dd a t a ) 在特征空间进 行查找，以建立数据特征到标记之问映射的模型，能够对未来可能出现的数据进行分类或者 预测。然而，在模式识别与数据挖掘的许多实际应用中，常常会有着这样的问题：标汜数据 在数量上不足，或者样本标记的获取比较困难，需要消耗大量的人力物力和时间。比如： ， 文本分类。过滤垃圾邮件、分类用户消息、推荐网络文章许多这样的任务需要用户。 将相关文档标记为“感兴趣的”或者“不感兴趣的”。而对一般用户而言，阅读和分类成 千上万个文档是一件十分枯燥的工作。 蛋白质结构预测。确定一个蛋白质的三维结构可能需要专家在特定的实验环境下花费几 个月时间。 视频监控。在大量监控图像中手工标注不同的人员，需要消耗很多的人力和时间。 而另一方面，随着数据收集和存储技术的飞速发展，未标记数据( u n l a b e l e dd a t a ) 的获取已相当。 容易，通常只需要少量代价就能获得大量的未标记数据。因特网中有无数个未标记的网页， ” 蛋白质的d n a 序列信息能够很方便的从基因数据库中查询，摄像机可以一天工作2 4 小时来 收集监控视频。因此在这样的情况下，对于分类器的学习，研究的关键在于能不能够利用未 标记的数据来进行增强学习效果。 半监督学习就是在这样的背景下孕育而生。顾名思义，半监督学习是一种介于监督学习 和非监督学习之间的方法，它要解决的问题可以归纳为：给定相对较小的标记数据集l = g ) 和一个大的未标记数据集啦扛 ，能不能同时利用l 和u 来训练学习器，取得比单独利用标 记数据集l 更好的学习效果? 因为半监督学习只需要少量的标注成本就能够获得较高的预测 精度，因此它无论是在理论上还是应用上都引起了人们广泛的关注。 半监督分类只是半监督学习领域的一个方面，除此之外半监督学习还可用于解决聚类和 回归问题，但是通常意义上的半监督学习指的是半监督分类，本文所研究的内容也是针对半 监督分类，故在下文中如未特殊说明，则半监督学习指的是半监督分类。 目前，利用未标记数据来提高学习效果的主流学习技术主要有三大类【2 】。除了半监督学 习( s e m i s u p e r v i s e dl e a r n i n g ) 之外，还有直推学习( t r a n s d u c t i v el e a r n i n g ) 和主动学习( a c t i v e l e a r n i n g ) 。直推学习f 3 1 1 4 1 假定未标记数据就是测试数据，试图在这些未标记数据上取得最佳 泛化能力。换句话说，直推学习的目的是用少量的标记数据，结合大量未标记数据，推测出 这些未标记数据本身的类别。它与一般的半监督学习最大的区别在于只能处理已有数据，对 于学习训练过程中未出现的数据，不能给出预测结果。主动学习【5 】【6 1 f 7 1 的训练方式与前两者 1 东南人学颀i ：学位论义 不同，它可以在学习的过程中主动要求外部的系统或者专家标记一些重要的未标记数据，以 此获得最大的学习效果提升，因此其技术难点在于如何使用尽可能少的查询来获得强泛化能 力。对比半监督学习、直推学习和主动学_ ：习可以看出，主动学习在利用未标记样本的过程中 需要与外界进行交互，而前两者则完全依靠学习器自身，所以也有一些研究者将直推学习作 为一种半监督学习技术来进行研究。本文中将狭义的半监督学习和直推学习都视作半监督学 习的技术，在关注半监督学习的同时，也考虑卣推学习的思想。 1 2 半监督学习基本原理与假设 为什么可以利用未标记样本来改善学习性能? 从概率的角度来说，分类问题的核心在于 计算条件概率p p k ) 。由于数量的限制，只从已有的标记数据，可能不足以得到准确的样本特 征与标记之间的关系p t y k ) 的分布情况，而未标记数据能够提供关于样本特征边缘概率p ( x ) 的一些信息。我们可以对潜在的联合概率p ( x ，y ) 做一定的假设，认定p g ) 与p ( y l x ) 之间存在一 定的关系，从而根据未标记样本获得的关于p 0 ) 的知识来推测p k ) 的结果。如图表1 ，当只 存在少量的标记数据的时候，学习方法得到的分类器泛化效果很差；而当加入大量的未标记 数据之后，学习方法可以通过更充分的p 0 ) 信息束得到泛化效果更好的分类器。 图表1 - 半监督学习原理示意【9 】。 蓝线为类判别边界，左图为监督学习结果，右图为半监督学习结果 喜 0 蕊蒸 注意，半监督学习并不一定在所有的情况下都能够提高学习的效果。如果未标记数据携 带的关于p o ) 的知识，在合适的假设之下，对于推导出p ( y k ) 有帮助，则半监督学习能够在监 督学习的基础上提高学习效果；否则，半监督学习非但不能提高学习效果，还会造成分类精 度的退化【8 】。所以半监督学习的关键就在于如何选取合适的假设，来提高对于p f y l x ) 估算的 准确度。 一般来说，半监督学习有如下两个基本假设【9 】：聚类假设( c l u s t e ra 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 ) 。 2 第一章引苦 1 2 1 聚类假设 聚类假设( 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 1 。 聚类假设可以表述为下面一种等价的方式： 低密度分离( l o wd e n s i t ys e p a r a t i o n ) ：决策分界线应该在低密度区域。 也就是说被高密度区域的一条路径连接着的两点( i p 属于同一个聚类的两点) 应该有相 同的标记；另一方面，如果两个点被一个低密度区域分开，那么它们的标记值应该不会相同。 用数学的语言描述就是：条件概率密度p k ) 和边缘概率密度p g ) 存在联系，边缘概率密度p ( x ) 较大的区域内，条件概率密度p p k ) 变化不大。 1 2 2 流形假设 流形假设( m a n i f o l da s s u m p t i o n ) 是指，高维数据位于一个低维的流形中。这意味着如果数 据点刚好位于一个低维的流形中，那么学习算法可以在一个相应低维度的空间罩完成，从而 避免了维数灾难( c u r s eo f d i m e n s i o n a l i t y ) 问题。换句话说，按照流形假设，处于一个很小的局 部邻域内的数据具有相似的性质，因此，其标记也应该相似。这一假设反映了决策函数的局 部平滑性。和聚类假设着眼整体特性不同，流彤假设主要考虑模型的局部特性。在该假设下， 大量未标记样本的作用就是让数据空间变得更加稠密，从而有助于更加准确地刻画局部区域 的特性，使得决策函数能够更好地进行数据拟合。 值得注意的是，一般情形下，流形假设和聚类假设是一致的。由于聚类通常比较稠密， 满足流形假设的模型能够在数据稠密的聚类中得出相似的分类结果。然而，由于流形假设强 调的是相似数据具有相似的输出而不是完全相同的标记，因此流形假设比聚类假设更为一般， 这使其在聚类假设难以成立的半监督回归中仍然有效 1 1 1 1 1 2 】。 1 3 半监督学习常见方法 基于以上两个假设产生了很多半监督学习的方法：自训练方法( s e l f - t r a i n i n g ) ，生成模型方 法( g e n e r a t i v em i x t u r em o d e l s ) ，基于信息不一致的方法( d i s a g r e e m e n t b a s e dm e t h o d s ) ，直推式 支持向量机( t r a n s d u c t i v es u p p o r tv e c t o rm a c h i n e s ) ，以及基于图的方法( g r a p h b a s e dm e t h o d s ) 。 1 3 1 自训练方法 自训练方法( s e l f - t r a i n i n g ) 是最简单的半监督学习方法，它是一种重复地使用监督学习方 法的封装算法( w r a p p e ra l g o r i t h m ) 。在自训练中，一个监督学习分类器首先在少量的标记样本 上训练，然后将得到的分类器用于分类未标记样本，选取置信度最高的若干未标记样本点以 及它们对应的预测标记添加到训练集，接着用分类器在新的训练集上重新训练，不断重复这 个过程。可以注意到，在自训练方法中分类器利用自己的预测结果去训练自己，因此这个过 程被称之为自训练或自展法( b o o t s t r a p p i n g ) 。 自训练算法被广泛的运用到各个领域中，例如生物基因预测、自然语言处理等等。【1 3 1 利用自训练来消除词义的二义性，在给定背景下决定单词“p l a n t ”是指生物体还是指工厂； f 1 4 用它来识别主观名词；1 5 利用它来进行对话归类，以决定此对话是“情绪化”或“非情 绪化 。自训练方法也被应用于句法分析和机器翻译。【1 6 】将自训练方法应用于物体侦测系统 3 东南人学硕i ：学位论文 从而从图像中侦测出感兴趣的目标。 自训练方法的优点主要在于简单易于操作，可以直接运用到已有的监督学习方法上。自 训练方法的缺点主要在于： 只能包装带软标记的分类器，对于判别式分类器( d i s c r i m i n a n tc l a s s i f i e r ) 无能为力； 训练初期产生的错误，会在迭代过程中自我强化，不断放大； 自训练学习的效果很难分析，关于其收敛问题的研究也比较少，现在只有在某些特殊情 况下的自训练学习的收敛问题才得到了阐述。 1 3 2 生成模型方法 半监督学习的生成模型算法( g e n e r a t i v em o d e lm e t h o d ) 最早出现于2 0 世纪七八十年代 【1 7 】。这类算法先假设数据服从某种特定的分布p ) ，然后利用半监督假设p o ) 印p ) p o i y ) 对数据建模，其中p ( x b , ) 是- - 个混合分布。例如假设数据集共有c 个类别，每类数捌都分别 属于高斯分布，那么由这些数据所组成的数据集将服从于由c 个高斯分布混合而成的分布。 这样大量的未标记数据加上少量的各类的标记数据就能用来求出组成该混合分布的各个模型 的参数。 令( p o ) 是一族分布，如果0 1 ：却2 推出p o i ：j p 铊，则称秒是可以辨识的。如果模型族可辨识， 理论上可以从无限的未标记样本估计出混合参数口。一般地，混合成分可以由期望最大化方 法( e x p e c t a t i o nm a x i m i z a t i o n ，e m ) 1 8 辨识出来。 对于生成模型方法的目标函数，通常很难得到封闭形式的解，所以常用e m 算法来估算 对应于各个类别的模型参数。算法首先利用标记数据估计一组初始参数，然后丌始迭代过程， 絮 在e s t e p 利用当前参数对未标记数据进行标记，在m s t e p 中用标记数据和未标记数据及其新 得到的标记重新估计参数，不断重复直至模型收敛。e m 算法的缺点在于收敛时间过长，而 且只能得到局部最优解。当初始值选取不恰当的时候，e m 算法得到的局部最优解跟全局最 优解之间差距比较大。 在生成模型方法中，如果事先对于数据或者领域的知识有充分的了解，则可以根据这些 先验知识来控制模型的选择，以提高方法的效果。如果所建立的模型与数据相匹配，分类器 性能将得到大大提高。反过来，如果模型选择不恰当，未标记数据很可能会降低分类器效果 墨 f 8 1 1 9 ，所以构建一个能够真实反映实际问题的混合模型是生成模型方法的关键。应用比较广 泛的生成模型有朴素贝叶斯模型( n a i v eb a y e s i a nm o d e l ) ，混合高斯模型( g a u s s i a nm i x t u r e m o d e l ) ，隐马尔可夫模型( h i d d e nm a r k o vm o d e l ) 等。其中朴素贝叶斯模型常用于网页分类， 混合高斯模型常用于语音识别、图像识别和分割，隐马尔可夫模型常用于生物信息学中的 d n a 序列分析。 1 3 3 基于信息不一致的方法 基于信息不一致的方法( d i s a g r e e m e n t b a s e dm e t h o d s ) 在半监督学习的过程中利用多个分 类器之间的差异相互影响，以提高分类精度。其典型代表就是协i 司i ) l l 练算法( c o t r a i n i n g ) 1 9 】。 标准协同训练算法假设数据集有两个充分冗余( s u f f i c i e n ta n dr e d u n d a n t ) 的视图( v i e w ) ， 即两个满足下述条件的属性集：第一，每个属性集都足以描述该问题，也就是说，如果训练 样本足够，在每个属性集上都足以学得一个强学习器；第二，在给定标记时，每个属性集都 条件独立于另一个属性集 1 0 1 。 充分冗余视图这一要求在一些任务中是可满足的 1 9 1 。比如在网页分类问题中，既可以 根据网页内容正确分类，也可以利用链接到该网页的超链接正确分类，这样的网页数据就有 两个充分冗余视图，刻画网页内容的属性集构成第一个视图，而刻画超链接的属性集构成第 二个视图。协同训练算法在两个视图上利用已有标记数据分别训练出一个分类器，然后，在 4 第一章，j l 苦 协同训练过程中，每个分类器对未标记样本进行标记，分别把自己认为置信度高的未标记数 据及其预测标记加入到对方的训练集中去，在更新后的训练集上重新训练这两个分类器，并 重复这一过程，直到达到某个停止条件。f 1 9 1 中证明了，在充分冗余视图这一条件成立时， 协同训练算法可以有效地通过利用未标记数据提升学习器的性能。 协同训练的缺点在于，假设过于苛刻，在真实问题中充分冗余视图这一要求往往很难得 到满足。g o l d m a n 等人f 2 0 1 提出了一种不需要充分冗余视图的协同训练算法。他们使用不同的 决策树算法，从同一个属性集上训练出两个不同的分类器，每个分类器都可以把样本空间划 分为若干个等价类。在协同训练过程中，每个分类器通过统计技术来估计标记置信度，并且 把标记置信度最高的数据进行标记后提交给另一个分类器作为有标记训练例，以便对方进行 更新。这种一般化的协同训练方法放松了充分冗余的假设，其缺点在于对于判定式分类器， 需要频繁使用k 折交叉验i i e ( k f o l dc r o s s v a l i d a t i o n ) 来估算未标记数据的置信度，大大增加了 时间复杂度。后来还有一些文献对协同训练方法有了进一步的改进，提出了t r i t r a i n i n g ， c o f o r e s t 等方法【1 0 】。 1 3 4 直推式支持向量机 按照聚类假设，类判别边界应该在密度较低的区域出现。目前，已有一些半监督学习算 法直接借助于聚类假设，通过使用特征的边缘概率p 仁) 来对类条件概率p ( y k ) 进行约束，以此 融入未标记数据信息，从而达到半监督学习的目的。直推式支持向量机( t r a n s d u c t i v es u p p o r t v e c t o rm a c h i n e s ) 2 1 1 就是其中具有代表性的方法。 直推式支持向量机是标准的支持向量机加入对未标记样本考虑之后的推广。在标准的支凳 持向量机中只用到了标记样本，其学习的目的是在一个再生核h i l b e r t 空f n j ( r k h s ) 找到最 大间隔线性分界面。而在直推式支持向量机中，加入了对未标记数据的考虑，其学习的目的 是寻找对于所有未标记数据的一种标记方式，同时在r k h s 中寻找一个最优的超平面，使得 。 该超平面能够同时最优的划分标记数据和带预测标记的未标记数据，实现经验风险最小化。 直推支持向量机的目标函数可以看作是标准的支持向量机目标函数加上关于未标记样本 的一个额外的正则项。但是由于加入的新项并非凸( c o n v e x ) 函数，使得整个目标函数变为非凸 ( n o n c o n v e x ) 函数，从而求解这个最优化问题也变成了n p 难问题 2 1 。i ，因此其高昂的计算代 善 价，尤其是空间代价限制了直推支持向量机方法的广泛运用。 1 3 5 基于图的方法 近来，基于图的半监督学习方法( g r a p h b a s e dm e t h o d s ) 受到极大的关注。基于图的半监督