（电路与系统专业论文）基于图的半监督学习模型研究与分类器设计.pdf

摘要 摘要 在机器学习领域，有监督学习和无监督学习是两种常用的学习算法，但是他 们在处理由于类别标注困难带来的标签数据极少、未标签数据众多的分类问题时 效果往往不佳。针对此类问题，半监督学习近来被提出并获得广泛的研究。半监 督学习结合两种传统学习算法的优势，能同时采用标签数据和未标签数据构造分 类器，且一般能够获得较传统学习算法更好的学习效果。本文对半监督分类算法 开展了较深入的研究，具体工作如下： 文章首先对半监督学习中的典型算法进行了分析，并将其与有监督学习进行 比较，发现半监督分类器的分类精度与其模型假设密切相关。只有在算法模型假 设能够较好符合数据的真实结构时，未标签数据的采用能够帮助提升分类精度； 否则，未标签数据可能不起作用，甚至起反作用。 其次，本文通过对标签传递算法的实验研究，发现用随机选择的数据作为训 练集会造成算法分类精度的较大波动。这说明可通过主动选择较优训练集去提升 标签传递算法的分类精度。而在主动学习中，分类器可根据当前状态主动挑选能 最大程度提升自身性能的待标注数据。通过引入此思想，本文提出了结合主动学 习的标签传递算法，并对算法模型及待标注数据选择策略开展了研究，使得该算 法可动态选择能最大程度降低标签传递算法当前分类风险的数据，提高训练集的 质量。在u c i 等数据集上的实验结果显示，训练数据数量相同时，该算法的分 类精度超越了随机选择训练集数据的标签传递算法。实验中，我们发现该算法经 常选择聚类中心的数据，因此，这些数据适合于作为标签传递算法的训练集。 基于图的半监督分类算法需构造一个以数据为顶点、以数据间相似性值为边 的图。在这种构造图的方法中相似性度量函数及其参数不易控制，数据的近邻个 数也难以选择。通过对局部线性嵌入算法的研究，我们发现该算法构造线性近邻 时不采用相似性函数，并且通过对数据局部流形的估算，判断数据是否位于分类 间隙附近，可动态调整数据的近邻个数，达到减少不同类数据间连接的目的，进 而减少标签误传递的概率。结合这两个优点，本文提出了基于局部线性嵌入算法 构建图的标签传递算法。在u c i 等数据等集上的实验结果表明，该算法中的图 较传统图更容易使用，与典型标签传递算法相比，基于该图的标签传递算法分类 精度更高。 关键词：半监督学习主动学习基于图的方法标签传递算法局部线性嵌入 a b s t r a c t a b s t r a c t i nt r a d i t i o n a lm a c h i n el e a r n i n ga r e a , t h e r ea r et w oc o m m o n l yu s e dl e a m i n g a l g o r i t h m s ，s u p e r v i s e dl e a r n i n ga n du n s u p e r v i s e dl e a r n i n g ，b u tn e i t h e ro ft h e mi s s u i t a b l ef o rd e a l i n g 、i t l lt h es i t u a t i o nw h e r et h e r ea r ef e wl a b e l e dd a t aa n dl a r g e a m o u n to fu n l a b e l e dd a t a t ot h i sp r o b l e m ，s e m i s u p e r v i s e dl e a r n i n gw a sp r o p o s e d r e c e n t l ya n dh a sa t t r a c t e dg r e a tr e s e a r c hi n t e r e s t s e m i s u p e r v i s e dl e a r n i n gc o m b i n e s t h ea d v a n t a g eo fb o t ht r a d i t i o n a ll e a r n i n gm e t h o d s ，i tc a nb u i l dab e t t e rc l a s s i f i e rb y u s i n gt h eu n l a b e l e dd a t at o g e t h e rw i t ht h el a b e l e dd a t a t h i sp a p e rd o e ss o m er e s e a r c h o ns 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 na l g o r i t h m s ，t h em a i nw o r ki sa sf o l l o w s ： f i r s t l y , t h i sp a p e ra n a l y s e st h et y p i c a ls 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 na l g o r i t h m s ， b yc o m p a r i n gi t t os u p e r v i s e do n e s ，f i n d st h a tt h ec l a s s i f i e r sa c c u r a c yi sc l o s e l y r e l a t e dt oi t sm o d e la s s u m p t i o n o n l yw h e nt h em o d e la s s u m p t i o nm a t c h e st h e p r o b l e ms t r u c t u r ew e l l ，t h eu n l a b e l e dd a t ac a nh e l pt oi m p r o v et h ec l a s s i f i e r s a c c u r a c y ；o t h e r w i s e ，u n l a b e l e dd a t am a yb eo fn ou s e ，o re v e nh a v eb a da f f e c to nt h e c l a s s i f i e r s e c o n d l y , b yd o i n ge x p e r i m e n to fl a b e lp r o p a g a t i o na l g o r i t h m ( l p ) ，w ef i n dt h a t l pi ss e n s i t i v et ot h eq u a l i t yo ft r a i n i n gs e tw h i c ha r er a n d o m l yc h o s e nb yt r a d i t i o n a l w a y s t h i sm e a n st h a tl pc a nb ei m p r o v e db ya c t i v e l ys e l e c t e dg o o dt r a i n i n gs e t i n a c t i v el e a m i n g ，c l a s s i f i e rc a nq u e r yu n l a b e l e dd a t at h a ti m p r o v ei t sp e r f o r m a n c em o s t b yc o m b i n i n ga c t i v el e a r n i n gt h o u g h t ，a na c t i v el e a r n i n gb a s e dl pa l g o r i t h m ( a l - l p ) i sp r o p o s e d 1 1 1 i sa l g o r i t h mc a i la c t i v e l ys e l e c tu n l a b e l e dd a t at h a tc a nd e g r a d et h e c l a s s i f i c a t i o nr i s km o s ts oa st om a k et h ea c c u r a c yi n c r e a s ef a s t e r p r o m i s i n g e x p e r i m e n t a lr e s u l t so fu c ie ta ld a t as e t ss h o wt h a t ，w h e nl a b e l e dd a t an u m b e ri st h e s a m e ，a l - l pc a na c h i e v eh i g h e ra c c u r a c yt h a nl pb yr a n d o m l ys e l e c t e dt r a i n i n gs e t t h r o u g ht h ea n a l y s i so ft h ef r e q u e n t l yq u e r i e dd a t a , w ef i n da l - l p i sp r o n et os e l e c t t h ec l u s t e rc e n t e rn e a r b yd a t a t h i sm e a n st h a ti ti sv e r ym e a n i n g f u lt os e l e c tt h e c l u s t e rc e n t e rd a t aa st h et r a i n i n gs e tf o rl p 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 gf i r s tc o n s t r u c tag r a p hw h e r el a b e l e da n d u n l a b e l e dd a t aa r er e p r e s e n t e da sv e r t i c e s ，a n de d g e se n c o d et h es i m i l a r i t yb e t w e e n d a t a b u tt h i s 虹n do fg r a p h - c o n s t r u c t i n gm e t h o do f t e nf a c e st h ed i f f i c u l t yo fc h o o s i n g t h es i m i l a r i t yf u n c t i o n , a sw e l la si t sp a r a m e t e r s ，a n dt h en u m b e ro fn e a r e s tn e i g h b o r s a i m i n ga tt h i s ，w ei n v e s t i g a t el o c a l l yl i n e a re m b e d d i n ga l g o r i t h m ( l l e ) ，a n df i n d i i a b s t r a c t l l ed o e s n tu s es i m i l a r i t yf u n c t i o nw h e nc o n s t r u c t i n gl i n e a rn e i g h b o r s ，a n db y d e t e c t i n gt h el o c a lm a n i f o l da n dj u d g i n gw h e t h e rt h ed a t ai sn e a rt h ec l a s s i f i c a t i o n m a r g i n ，w ec o u l de a s i l yr e c t i f yt h en u m b e ro fd a t a sn e a r e s tn e i g h b o r ss o a st o d e c r e a s et h ec o n n e c t i o n sb e t w e e nd a t ao fd i f f e r e n tc l a s s e sa n dr e d u c et h e m i s - l a b e l p r o p a g a t i n gp r o b a b i l i t y b a s e do nt h e s et w op o i n t s ，t h i sp a p e rp r o p o s e s l l eb a s e dg r a p h c o n s t r u c t i n gm e t h o d ，a n da p p l i e si tt ol p e x p e r i m e n t a lr e s u l t so f u c ie ta ld a t as e t ss h o wt h a tt h i sm e t h o di se a s yt ou s e ，a n dt h a tl pb a s e do nt h i sl 【i i l d o fg r a p hp e r f o r m sb e t t e rt h a nl pb a s e do nt r a d i t i o n a lg r a p h 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 ，a c t i v el e a r n i n g ，g r a p h - b a s e dm e t h o d ，l a b e l p r o p a g a t i o na l g o r i t h m ，l o c a l l yl i n e a re m b e d d i n g i i i 中国科学技术大学学位论文原创性声明 本人声明所呈交的学位论文，是本人在导师指导下进行研究工作所取得的 成果。除已特别加以标注和致谢的地方外，论文中不包含任何他人已经发表或 撰写过的研究成果。与我一同工作的同志对本研究所做的贡献均已在论文中作 了明确的说明。 作者签名：牡 中国科学技术大学学位论文授权使用声明 作为申请学位的条件之一，学位论文著作权拥有者授权中国科学技术大学 拥有学位论文的部分使用权，即：学校有权按有关规定向国家有关部门或机构 送交论文的复印件和电子版，允许论文被查阅和借阅，可以将学位论文编入有 关数据库进行检索，可以采用影印、缩印或扫描等复制手段保存、汇编学位论 文。本人提交的电子文档的内容和纸质论文的内容相一致。 保密的学位论文在解密后也遵守此规定。 d 公开口保密( 年) 作者签名：三哞j 茎j 强一 签字日期：趁塑：墨：! 新签名：名踢 签字日期： 第1 章绪论 第1 章绪论 1 1 课题意义 机器学习( m a c h i n el e a r n i n g ) 无处不在，随着计算机技术的飞速发展，人 类收集数据、存储数据的能力得到了极大的提高，无论是科学研究还是社会生活 的各个领域中都积累了大量的数据，对这些数据进行分析以发掘数据中隐含的有 用信息，成为几乎所有领域的共同需求。另一方面，在很多领域，获取数据类别 的标签有的要消耗大量时间、精力、资金，有的还需要相当强的专业知识背景， 类别标签的匮乏成了处理数据的一个瓶颈，如自然语言处理( 语音的人工翻译比 较耗时) 、文本分割( 做手动分类工作的人要有各方面的专业知识，且工作耗时 费力) 和蛋白质结构预测( 为确定单个蛋白质的三维立体结构，相关专家常常会 耗费数月时间做非常昂贵的化学实验) 等。传统的机器学习方法大多只考虑有标 签数据( l a b e l e dd a t a ) 或者只考虑未标签数据( u i l l a b e l e dd a t a ) ，但是在很多现 实问题中往往是两者并存，此时，标签数据不足以用于监督学习的训练，而采用 无监督学习又会浪费标签数据中包含信息。如何更有效地同时利用这两种数据成 为一个备受关注的问题。针对该问题，人们提出了半监督学习，它能同时利用标 签数据的信息和未标签数据中的隐含信息，达到比仅使用一种数据信息更好的学 习效果。由于在处理此类情况时的优秀表现，半监督学习自诞生以来，受到了国 际机器学习和数据挖掘界的高度重视。 1 2 半监督学习的概念及研究动态 1 2 1 半监督学习的定义 在机器学习领域，传统的学习方法有两种：无监督学习( u n s u p e r v i s e d l e a m i n g ) 和监督学习( s u p e r v i s e dl e a r n i n g ) 。无监督学习中，采用的数据集为刀 个独立同分布的样本构成的集合五，= “，x 2 ，x n ，其中薯r d ，1 f 行，而没 有样本的教师信息( 有时也称目标信息，在分类问题中为类别信息) 。无监督学 习的目标是确定一种概率分布，使其最有可能产生数据五，。监督学习中，采用 的训练集为x l = ( ，m ) ，( x 2 ，y 2 ) ，( x 。，以) ) ，样本和教师信号成对出现。五中 毛r d ，1 f 疗，以为教师信号；对于分类问题，y j ，比 ，c 为样 本类别数目。监督学习的目标是寻找从x 到y 的映射。一般情况下还有一个测试 集用于评价这种映射关系的优劣。监督学习大体可分为两类：g e n e r a t i v e a l g o r i t h m s 和d i s c r i m i n a t i v em e t h o d s 。g e n e r a t i v ea l g o r i t h m s 首先确定类条件概率 第l 章绪论 密度p ( x ij ，) ，然后采用贝叶斯公式 p ( y 眇两p ( 丽x l y ) p ( y ) ( 1 1 ) 对测试集中样本进行处理。而d i s c r i m i n a t i v em e t h o d s 则不关心数据五如何产生， 只关心如何确定p ( y i x ) 。典型的d i s c r i m i n a t i v em e t h o d s 算法为支持向量机 ( s u p p o r tv e c t o rm a c h i n e ，s v m ) ，s v m 通过求解支撑向量来构造最优分类面， 可直接实现数据的分类。 半监督学习( s e m i s u p e r v i s e dl e a r n i n g ，s s l ) 也属于机器学习领域，是介于 无监督学习和监督学习之间的一种学习理论。狭义上，同时采用标签数据和未标 签数据的机器学习方法是半监督学习；广义上，利用一定的先验知识( 标签数据、 样本分布函数、数据各类别数目比例或样本类别数目等) ，同时采用了未标签数 据进行的学习均属于半监督学习。在半监督学习中，一般设标签样本集为 置= ( x 。，y 1 ) ，( x ：，y ：) ，( x ，y f ) ) ，未标签样本集为如= _ + l 而彩，矗) ，且 u = 刀一， u 。在少量标签数据和大量未标签数据情况下，半监督学习往往 可以获得比监督学习和无监督学习更好的学习效果，这使其受到广泛的关注。半 监督学习主要有三类：半监督分类( s 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 ) 、半监督聚类 ( 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 2 2 半监督学习的国内外研究动态 出现最早及研究和应用最多的半监督学习算法是自训练算法( 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 - t e a c h i n g ，s e l f - l a b e l i n g ，b o o t s t r a p p i n g 或d e c i s i o n - d i r e c t e d l e a r n i n g ) ( c h a p e l l eo ，s c h r l k o p fb ，z i e na ，2 0 0 6 ) 。s e l f - t r a i n i n g 首先在标签数据 集上训练分类器；然后依据当前分类器对未标签数据的分类结果，把一部分未标 签数据添加到标签数据集中；第三步：在新的训练集上重新训练分类器，直到训 练结束条件满足。这种思想最早出现在文献( s c u d d e r h j ，1 9 6 5 ) ( f r a l i c ks c ，1 9 6 7 ) ( a g r a w a l aa k ，1 9 7 0 ) 中。然而，s e l f - t r a i n i n g 算法中一旦出现错误分类情况， 往往会造成错误的积累和扩散。 另一种出现较早的半监督分类算法是模型生成算法( g e n e r a t i v em o d e l s ， g m ) ，该算法非常类似于监督学习中的g e n e r a t i v ea l g o r i t h m s 。g m 算法假设已 知数据的类条件概率密度函数p ( xj 儿) 的形式，如高斯分布、多项式分布( c o o p e r d b ，f r e e m a nj h ，1 9 7 0 ) ，未知的仅是p ( x ly ，) 的参数。g m 算法可采用迭代算法， 如期望最大化算法( e x p e c t a t i o nm a x i m i z a t i o n ，e m ) ( d e m p s t e r a pe ta l ，1 9 7 7 ) ，确 定p ( xiy ，) 的参数，再依据贝叶斯全概率公式对所有未标签数据进行分类。g m 2 第l 章绪论 算法对假设要求较高，如果假设的p ( xiy ，) 与样本的实际分布相差太大，结果往 往不佳。目前，针对g m 算法的改进研究主要集中在如何使假设的p ( xly ，) 能够 更加接近样本真实分布，n i g a mk e ta l ( 2 0 0 0 ) 采用混合布代替简单多项式分布 表示p ( xly ，) ，并将其用于文本分类。n i g a mk e ta l ( 2 0 0 0 ) 、c o r d u n e a n uaa n d j a a k k o l at ( 2 0 0 1 ) 、c a l l i s o n b u r c hce ta l ( 2 0 0 4 ) 在文献中通过降低未标签数据 在参数估计时的权重来实现更佳的学习效果。 以上两种算法现在应用较多，主要是因为其算法思想清晰，实现相对简单。 合作训练算法( c o t r a i n i n g ) 中，假设样本的特征可以分成两个相互独立的 特征子集，且两个特征子集均可充分用于训练学习。c o t r a i n i n g 用两个特征子集 训练两个分类器；然后用两个分类器对未标签数据进行分类，并把分类信心度最 高的样本添加到另一个分类器中；重复训练，直到满足训练结束条件( b l u ma m i t c h e l lt ，1 9 9 8 ) ( m i t c h e l lt ，1 9 9 9 ) 。c o - t r a i n i n g 可以避免s e l f - t r a i n i n g 中的自身 错误积累，但是该算法对样本特征要求较高，会造成样本采集费用的增加。 g o l d m a ns 和z h o uy ( 2 0 0 0 ) 提出可以采用所有特征去训练两种不同类型的分类 器，分类器将分类信心度高的未标签样本添加到对方的训练集中。z h o uy 和 g o l d m a ns ( 2 0 0 4 ) 又提出了多分类器表决算法( s i n g l e v i e wm u l t i p l e 1 e a r s n e r d e m o c r a t i cc o l e a r n i n ga l g o r i t h m ) ，该算法也是采用所有特征，使用同一个训练 集去训练多个分类器，然后采用“举手表决的方式决定是否将某个未标签样本 添加到训练集，然后所有的分类器在更新的训练集上重新训练。与此类似，z h o u x 和l iw s ( 2 0 0 6 ) 提出了三分类器协同训练算法( t f i t r a i n i n g ) ，让两个分类器 的分类表决结果决定是否将某未标签数据添加到第三个分类器中。 如同监督学习中有d i s c r i m i n a t i v em e t h o d s ，半监督学习中有低密度划分算法 ( l o wd e n s i t ys e p a r a t i o n , l d s ) ，传导支持向量机( 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 m ) ( v a p n i kv n ，1 9 9 8 ) 即是 这样的算法。t s v m 算法可以在未标签数据的引导下使初始的分类超平面移动到 样本分布稀疏区域，以实现类别间隙的最大化、在未标签数据中的泛化误差最小 化。然而，求取精确的t s v m 解是一个n p 难问题，在数据量大时，t s v m 几乎 无法使用。文献( b e n n e t tk ，d e m i r i z a ，1 9 9 9 ) 、( d e m i r e z a ，b e n n e t tk ，2 0 0 0 ) 和 ( f u n ggm a n g a s a r i a no ，1 9 9 9 ) 试图近似的实现该算法，但是也只能处理几百个 数据，而文献( j o a c h i m st 1 9 9 9 ) 中提出的s v m 1 i g h t 是第一个广为使用的t s v m 实现软件，不过s v m 1 i g h t 使用的是加权后的未标签数据，其解并不一定是t s v m 的全局最优解。 t s v m 优化目标为： 第1 章绪论 m i n i ( 1 一厂( 薯) ) f + 名m a x ( 0 ，1 一l 厂( 鼍) i )( 1 2 ) x l x lx i x u 式中的旯为一个设定未标签数据在优化目标中权重的常数。t s v m 可以看成在标 准s v m 优化目标后添加了未标签数据分类错误惩罚项的算法。但是，由于惩罚 项不可微分，造成了函数优化在实现时的困难。c h a p p l l eo ，z i e n a ( 2 0 0 5 ) 提出 v s v m ，利用高斯函数代替惩罚项。文献( s i n d h w a n iv e ta l ，2 0 0 6 ) 和( c h a p e l l e oe ta l ，2 0 0 6 ) 中则采用了递进的求解方法，即优化目标函数中的惩罚项由简单 逐渐过渡到最终的形式。t s v m 的另一个研究热点是其究竟能达到怎样的学习效 果，c h a p e l l eoe ta l ( 2 0 0 6 ) 利用分支与边界搜索技术( b r a n c ha n db o u n ds e a r c h t e c h n i q u e ) 求解出了小规模数据集下t s v m 的全局最优解，且实验结果表现出 了极好的精度。虽然分支与边界搜索技术几乎无法用于处理大批量数据，但是它 至少说明了t s v m 处理问题的潜在能力。然而，z h a n ga n do l e s ( 2 0 0 0 ) 反对 t s v m 。 最近二十年，基于图的半监督学习( 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 g ) 引起了学术界的广泛关注。在基于图的方法中，首先构造一个图g = ( v ，e ) ，其 中顶点y 表示样本( 标签数据和未标签数据) ，边e 表示样本间的某种相似性； 基于图的半监督分类算法需构造一个同时满足以下两个条件的函数厂：( 1 ) 对于 标签数据，厂应当能够正确分类，( 2 ) 对于未标签数据，厂应当使类别标签在整 个图上平滑分布。第一个条件可以看作目标函数的损失函数，第二个条件可以看 作目标函数的调整项。选择不同的损失函数和调整项可以得到不同的基于图的半 监督分类方法，如图的最小分割( g r a p hm i n c u t ) ( b l u m a ，c h a w l as ，2 0 0 1 ) 、离 散马尔可夫随机过程( d i s c r e t em a r k o vr a n d o mf i e l d s ) ( z h ux j ，g h a h r a m a n iz 2 0 0 2 ) 、高斯随机过程( g a u s s i a nr a n d o mf i e l d s ) ( z h ux je ta l ，2 0 0 3 ) 、l o c a la n d g l o b a lc o n s i s t e n c y ( z h o uye ta l ，2 0 0 4 ) 、t i k h o n o vr e g u l a r i z a t i o n ( b e l k i nm ，m a t v e e v a i ，n i y o g ip ，2 0 0 4 ) 、m a n i f o l dr e g u l a r i z a t i o n ( b e l k i nm ，n i y o g ibs i n d h w a n iv ，2 0 0 4 ) ( b e l k i nm ，n i y o g ies i n d h w a n iv ，2 0 0 5 ) 、g r a p hk e r n e l sf r o mt h es p e c t r u mo f l a p l a c i a n ( c h a p e l l eo e ta l ，2 0 0 2 ) ( s m o l aa ，k o n d o r 2 0 0 3 ) 、s p e c i a lg r a p h t r a n s d u c e r ( j o a c h i m st 2 0 0 3 ) 、t r e e b a s e db a y e s ( k e m pce ta l ，2 0 0 3 ) 等。文献 ( z h ux j ，2 0 0 6 ) 认为构造一个能够更好的表示实际问题的图比选择哪个厂更有 意义，然而，针对图的构造的研究并不多。文献( z h u x j ，2 0 0 5 ) 和( b a l c a n m f e ta l ，2 0 0 5 ) 构造图时采用了很多相关领域的知识，文献( w a n gf z h a n gc ，2 0 0 6 ) 借鉴局部线性嵌入( l o c a ll i n e a re m b e d d i n g ，l l e ) 思想，构造仅在近邻样本间 有连接的图。如果采用高斯核函数度量样本间的相似性连接，这时参数o 的选择 至关重要，文献( z h a n gx ，l e ew s ，2 0 0 6 ) 通过最小化在标签数据上的均方误 4 第1 章绪论 差求解每一特征维的o 。尽管如此，还是不存在一种鲁棒性的构造图的方法。 1 3 本文的主要工作及结构安排 基于上述背景以及相关动态，本文的研究内容如下： 1 ) 未标签数据在半监督学习中的作用。 2 ) 模型假设条件对各半监督分类算法的影响。 3 ) 如何进一步减少半监督算法对标签数据的需求量。 4 ) 什么样的数据对标签传递算法最重要? 5 ) 控制参数对标签传递算法的影响。 6 ) 如何构造鲁棒性更好的图? 结合自己研究内容以及文章阐述的便捷性，本文结构组织如下： 第一章简要分析了半监督学习理论的提出以及半监督学习国内外研究动态， 对半监督学习中的典型算法作了简要的总结。 第二章详细分析了半监督学习中的典型算法，如g m 算法、低密度分割算法、 基于图的分类算法，为后面对相关改进的算法做好铺垫。第二章还分析了半监督 学习中未标签数据对分类算法性能的影响，各算法假设条件对算法自身性能的重 要意义。 第三章围绕如何进一步减少标签数据数量的问题，引入主动学习的思想，提 出了结合主动学习的标签传递算法。本章对该算法思想来源、实现及实验进行了 详细的阐述。通过在人工合成数据、u c i 数据集、m n i s t 手写体数据集上一系列 的实验发现，聚类中心或其附近的数据对提升分类器性能作用最大。 第四章围绕如何构造质量更高的图的问题，借鉴l l e 算法中“数据可由其近 邻线性加权重构的思想，引入自适应近邻个数调整的思想，提出了基于l l e 构 建图的标签传递算法。本章详细介绍了新图中近邻的选择方法、自适应近邻个数 调整策略、在该图上标签传递算法等。本章最后通过实验验证了新图具有更好的 鲁棒性。 第五章对全文进行总结。首先对自己的工作进行了总结概括，然后指明了算 法中依然存在的问题，为今后进一步的研究工作指明了方向。 5 第2 章半监督学习分析 第2 章半监督学习分析 半监督学习的思想启蒙于上世纪6 0 年代，在7 0 年代得到发展，9 0 年代及 以后获得了更广泛的关注和研究。三个时期典型的代表算法分别是s e l f t m i n i n g 算法、g m 算法、l d s 算法和基于图的算法。算法发展的同时，人们还不断探讨 半监督学习各种算法有效性的前提以及未标签数据的意义。本章针对这些内容做 一些简单介绍，由于s e l f 二t r a j m n g 算法相对简单，在绪论中有所提及，且g m 算 法中也包含一定s e l f - t r a i n i n g 的思想，本章中不再介绍。 2 1 未标签数据的意义分析 很多研究者可能都存在这样的疑问：未标签数据，没有类别标签或教师信号 的数据，真的有用吗? 其中是否隐藏了有用的信息? 它们真的能够提高分类器的 性能吗? 这听起来有点不可思议。在机器学习领域，主动学习( a c t i v el e a m i n g ) 也是一种利用未标签数据的学习方法。与半监督学习的不同之处是：主动学习先 选择隐含提升分类器性能可能性最大的未标签数据，然后交由监督者进行类别标 定后再用于训练分类器。也就是说，未标签数据是被转化成标签数据后再用于学 习的。半监督学习不同，其在学习过程中没有监督者。尽管如此，z h u x j ( 2 0 0 6 ) 在其论文中提到：未标签数据的确可用于提高学习机性能，只不过需在特定的假 设条件之下，即模型假设正确。在能很好匹配实际问题的情况下，未标签数据是 有用的。 许多关于半监督学习的文章，开始时总提“在机器学习的许多领域中，标签 数据的获取往往需要耗费大量的时间、人力、资金等，有时还需要相关领域专业 知识或相关专家的参与，这使得数据的类别标签不易获得，相比之下，未标签数 据更容易大量收集。因此，能够减少标签数据的工作量，同时提高分类器性能的 半监督学习就引起了广泛的研究，半监督学习能够利用未标签数据中隐含的信 息一，但是，不要把这些话不假思索的全盘接受。尽管半监督学习可以减少 给数据添加类别标签的工作量，但若要获得学习性能的显著提高，使用者还是需 要花费些时间和精力来设计模型、核函数、相似性函数等。有时，这些工作对使 用者要求可能更高、更苛刻。 未标签数据也并非总能提高分类器性能。哲学中有句话叫“没有免费的午 餐”。如果半监督学习中的模型假设与实际问题不匹配，未标签数据就有可能起 负面作用。例如，半监督学习中有的算法假设分类边界应当避开样本分布密集， 即p ( x ) 值大的区域，而位于样本分布稀疏的区域，如t s v m 、基于图的算法等。 7 第2 章半监督学习分析 然而，如果实际的数据来自两个重叠非常多的高斯分布，分类边界恰好穿过样本 分布密集区域。此时，采用t s v m 、基于图的算法等往往不能获得较好的学习效 果。相反，如果采用g m 算法，就可以获得较之更好的效果。提前检测模型与实 际数据的匹配程度对模型选择有非常大的指导意义，但该问题仍悬而未决。 实际上，许多研究者均发现了“未标签数据并非总是有用的 的现象，如有 的研究者早就意识到在有的初始条件下，用未标签数据训练隐性马尔可夫过程 ( h m m ，h i d d e nm a r k o vm o d e l ) 会导致分类性能的降低( e l o w o r t h y , 1 9 9 4 ) 。文 献( c o z m a ne ta l ，2 0 0 3 ) 中对该问题进行了深入的讨论。本文图2 3 为一关于未 标签数据作用的实例，但其主要用于说明模型假设的意义。由于本文主要研究半 监督分类算法及分类器设计，不深究模型选择、模型验证的问题。 如果模型假设正确，未标签数据可以用于提高学习机性能，那么，半监督学 习是如何利用未标签数据的呢? 半监督学习利用未标签数据校正或完善仅从标签数据中获得的假设。如图 2 1 所示，实心点表示两类的标签数据，空心点表示未标签数据。若仅采用标签 数据，决策边界如图中虚线所示，而在未标签数据的影响下，我们很容易就认为 实线所示的决策边界更合适。人在解决该问题时很自然的会使用未标签数据，半 监督学习其实也是一个类似的过程，也以校正分类边界或其它的方式使用未标签 数据。 o o o 标签数据 仪采用标签数据时决策边界 未标签数据 结合未标签数据时的决策边界 l a 一 i c o 渤o ooo 亟圆o 、 10l 图2 1 未标签数据作用举例 具体一点来讲，在g m 算法中，样本分布概率密度函数p ( xi 咒) 的参数使用 e m 算法借助未标签数据进行修订。在s e l f - t r a i n i n g 和c o - t r a i n i n g 算法中，假设 分类器对分类信心度高的数据的分类是正确的，未标签数据中分类信心度高的数 据即可用于扩大训练集。在t s v m 算法中，假设分类超平面穿过样本分布稀疏 区域，未标签数据可引导分类超平面调整移动到该区域。 8 第2 章半监督学习分析 2 2 半监督学习典型算法研究 2 2 1 g m 算法研究 绪论中提及，g m 算法要求样本分布类条件概率密度函数p ( xly ，) 的形式作 为先验知识，未知的仅是p ( xiy ，) 的具体参数p 。例如，可以假设p ( xi 乃) 为混合 高斯分布。结合训练样本，利用参数估计的方法，如最大似然估计( m a x i m u m l i k e l i h o o de s t i m a t i o n ，m l e ) ，计算出参数0 ，然后就可以利用贝叶斯公式进行分 类。然而，在标签数据稀少时，估计出的参数往往不能很好的逼近真实值。解决 这一问题的方法是利用e m 算法，在标签数据和未标签数据上进行迭代，求解出 能够同时反映两者分布的参数秒。采用e m 求解参数的g m 算法步骤如下： ( 1 ) 在最初的标签数据集上，利用m l e 估计初始的参数0 ； ( 2 ) 根据贝叶斯公式，计算所有未标签数据的类别，并把分类结果连同数 据添加到训练集中； ( 3 ) 在当前的训练集上，重新利用m l e 估计参数9 ( 4 ) 重复步骤( 2 ) 和( 3 ) ，直到满足训练结束条件。 该算法的步骤( 2 ) 对应于e m 算法的e s t e p ，即求期望值，步骤( 3 ) 对应 于m s t e p ，使期望最大化。该算法可以有效考虑未标签数据的作用，使学习得到 的参数更能反映样本的真实分布。 在采用g m 算法时，还必须注意以下问题： 1 、模型参数的可确定性 样本分布类条件概率密度函数p ( x iy ，) 须具有可确定性，即p ( x ly j ) 的参数 须具备可确定性。设 岛) 表示不同参数口所对应的p ( x ly 。) 构成的集合，若对于 q 岛，有p o 。p o ：，则模型或参数具有可确定性，此时可以利用足够多的未标 签数据确定该参数。 模型的可确定性可以通过下例解释。对于y + l ，一1 ) 的两类情况，p ( x i y ) 是 均匀分布，借助大量未标签数据又知p ( x ) 满足【0 ，l 】上的均匀分布，待定参数只有 一个，即两类数据间的边界秒。假设有两个样本( 0 1 ，+ 1 ) 和( 0 9 ，一1 ) ，如何确定未 标签数据x = 0 5 的类别? 根据两已知样本，我们无法确定目的值，究其根本原因 是对任意q 岛，总有p o 。= p o ：，即均分分布模型不具备可确定性。如式2 1 、 式2 2 所示两种模型： p ( y = 1 ) = 0 2 ，p ( x i y = 1 ) = u n f ( o ，0 2 ) ，p ( x lj ，= 一1 ) = u n i f ( o 2 ，1 ) ( 2 1 ) p ( y = 1 ) = 0 6 ，p ( xly = 1 ) = u n f ( o ，0 6 ) ，p ( xly = 一1 ) = u n i f ( o 6 ，1 ) ( 2 2 ) 式中u n i f ( a ，b ) 表示【口，6 】上的均匀分布。秒取