（运筹学与控制论专业论文）基于图的半监督机器学习.pdf

a bs t r a c t o v e rt h ep a s tf e wy e a r s ，s e m i s u p e r v i s e dl e a r n i n gh a sg a i n e dc o n s i d e r a b l e i n t e r e s ta n ds u c c e s si nb o t ht h e o r ya n dp r a c t i c e t r a d i t i o n a ls u p e r v i s e dm a c h i n e l e a r n i n ga l g o r i t h m sc a no n l ym a k eu s eo fl a b e l e dd a t a ，a n dr e a s o n a b l ep e r f o r m a n c e i so f t e na c h i e v e do n l yw i t hal a r g en u m b e ro fl a b e l e dd a t a h o w e v e r ，l a b e l e dd a t a i so f t e ne x p e n s i v ea n dt i m ec o n s u m i n gt oc o l l e c t ，w h i l eu n l a b e l e dd a t ai su s u a l l y c h e a p e ra n de a s i e rt oo b t a i n t h es t r e n g t ho fs e m i s u p e r v i s e dl e a r n i n gl i e si ni t s a b i l i t yt ou t i l i z eal a r g eq u a n t i t yo fu n l a b e l e dd a t at oe f f e c t i v e l ya n de f f i c i e n t l v i m p r o v el e a r n i n gp e r f o r m a n c e r e c e n t 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 sa r eb e i n gi n t e n s i v e l ys t u d i e d ，t h a n k st oi t sc o n v e n i e n tl o c a lr e p r e s e n t a t i o n c o n n e c t i o nw i t ho t h e r m o d e l sl i k ek e r n e lm a c h i n e s g r a p hl a p l a c i a ni st h ec e n t r a lq u a n t i t yo fg 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 ，w h i c hp l a y sar o l ei ne x p l o r i n gt h eu n d e r l y i n g m a n i f o l dg e o m e t r yo ft h ed a t a u s i n gg r a p h l a p l a c i a nt of o r mt h er e g u l a r i z a t i o n p r o b l e ma n df u r t h e re m p l o y i n gt h ek e r n e lt e c h n i q u e si sap r o m i s i n ga p p r o a c ho f s e m i s u p e r v i s e dl e a r n i n g t h ea u t h o rf i r s ti n t r o d u c et h eb a s i cc o n c e p t so fs e m i s u p e r v i s e dl e a r n i n g ，a s w e l la st h eu t i l i z e dt o o l sa n dt h e o r y , s u c ha ss u p p o r tv e c t o r m a c h i n e s ，k e r n e l m e t h o d sa n dr e g u l a r i z a t i o nt h e o r y 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 em a i n l yp r e s e n t e di nc h a p t e r5a n d c h a p t e r6 i nc h a p t e r5 ，t h ea u t h o rf i r s ti n v e s t i g a t eac l a s so fg 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 gm e t h o d sb ys p e c t r a lt r a n s f o r m a t i o n ，t h e nt h ef o r m u l a t i o no f s e m i s u p e r v i s e ds p e c t r a lk e r n e ll e a r n i n gb a s e do nm a x i m u m m a r g i nc r i t e r i o nw i t h s p e c t r a ld e c r e a s i n go r d e rc o n s t r a i n t si sf o r m e d ，a n dh ea l s om a i n t a i nt h a tt h em 心 i m u mm a r g i nc r i t e r i o ni sam o r ee s s e n t i a lg o a lo f s e m i s u p e r v i s e dk e r n e ll e a r n i n g t h a nk e r n e lt a r g e ta l i g n m e n tb yt h e o r e t i c a la n a l y s i s b ye q u i v a l e n t l yt r a n s f o r m - i n gt h er e s u l t e di n t r a c t a b l eo p t i m i z a t i o np r o b l e mi n t oaq u a d r a t i c a l l yc o n s t r a i n e d r a ca b s t t q u a d r a t i cp r o g r a m m i n g t h ep r o b l e mc a nb ee f f i c i e n t l ys o l v e d m o r e o v e r ，t h e 羽1 t h o ra l s op r o p o s eam e t h o dt oa u t o m a t i c a l l yt u n et h ei n v o l v e dt r a d e - o f fp a r a m e t e r f u r t h e r m o r e t h ea u t h o rs e e ka n o t h e rw a yt ol e a r nt h es p e c t r a lc o e f l i c i e n t sf r o ma m o r ee s s e n t i a lv i e w d u et ot h ef a c tt h a tt h es p e c t r a lo r d e rc o n s t r a i n t sa r ea c t u - a l l yn o th a r dr e q u i r e m e n t sb u to n l yf o rt h ep u r p o s eo fe n s u r i n gt h es m o o t h n e s so f t h es c o r ef u n c t i o n ，t h ea u t h o rl e a v e so u tt h o s ec o n s t r a i n t sb yd i r e c t l yi n c l u d i n gt h e s m o o t h n e s sr e g u l a r i z e ri n t ot h em a x i m u mm a r g i no b j e c t i v e ，w h i c hc o i n c i d e sw i t h t h et h e o r yo fm a n i f o l dr e g u l a r i z a t i o n i t se f f i c i e n ti t e r a t i v ea l g o r i t h mi sa l s od e - s i g n e dn e x t e x p e r i m e n t a lr e s u l t so nr e a l - w o r l dd a t as e t sh a v ed e m o n s t r a t e d t h a t b o t ho fh i sp r o p o s e ds p e c t r a ll e a r n i n gm e t h o d sa c h i e v ep r o m i s i n gr e s u l t sa g a i n s t o t h e ra p p r o a c h e s m o t i v a t e db yt h er e q u i r e m e n t so fm a n yp r a c t i c a lp r o b l e m s ，i nc h a p t e r6t h e a u t h o rt u r n st os t u d yt h ep r o b l e mo fs e m i - s u p e r v i s e dl e a r n i n gw i t hs t r u c t u r e d o u t p u t s ，w h i c hi sam o r eg e n e r a lt o p i ct h a nt h es t a n d a r ds e m i - s u p e r v i s e dl e a r n - i n g b ye x t e n d i n gt h ed e f i n i t i o no fs m o o t h n e s sr e g u l a r i z e rt om u l t i - c l a s ss e t t i n g ， h en e x te x p l o r et h em u l t i - c l a s ss 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 a l t h o u g ht h eo b _ t a i n e dd a t ad e p e n d e n tk e r n e ls i m i l a rt ot h a to fs i n d h w a n ie ta 1 ，h i sm u l t i - c l a s s m o d e lr e a l l ye x t e n dt h et h e o r yo ft h e i r s s t i l ln e x t ，t h ea u t h o rf u r t h e rg e n e r a l i z e t h em u l t i - c l a s sm a n i f o i dr e g u l a r i z a t i o np r o b l e mt ot h es c e n a r i ow i t hs t r u c t u r e d o u t p u t s ，a n dt h ec o r r e s p o n d i n gd u a lp r o b l e m sa r ea l s oo b t a i n e d f r o mt h ed u a l f o r m u l a t i o n s ，w ec a nf i n dt h a tt h es e m i - s u p e r v i s e dl e a r n i n gt a s kf i n a l l yc a nb e a c h i e v e db yt h es u p e r v i s e ds t r u c t u r a lp r e d i c t i o nw i t han e w l yd e f i n e d “d a t ad e - p e n d e n tj o i n tk e r n e lm a t r i x t h i sd a t ad e p e n d e n tk e r n e lm a t r i xg e n e r a l i z e st h a t o fs i n d h w a n ie ta 1 t os t r u c t u r a lp r e d i c t i o n m o r e o v e r ，h i sp r o p o s e di n d u c t i v e a p p r o a c hc a nn a t u r a l l yp r e d i c tt h eu n s e e nd a t ap o i n t so t h e rt h a nt h eu n l a b e l e d d a t a s o m ee x p e r i m e n t so i lt e x tc a t e g o r i z a t i o nw i t hh i e r a r c h i e sa r ec o n d u c t e d ， a n dt h ee m p i r i c a lr e s u l t ss h o wh i sa p p r o a c h e sa c t u a l l yu t i l i z et h es t r u c t u r a la n d m a n i f o l di n f o r m a t i o no ft h ed a t as i m u l t a n e o u s l y , a n df i n a l l yh e l pu st oi m p r o v e t h ep r e d i c t i o np e r f o r m a n c e a sas u p p l e m e n t ，t h ea u t h o ra l s op r o p o s e st h ec o n - c e p to fj o i n tl a p l a c i a n ，w h i c hs h a r e st h es i m i l a rp r o p e r t i e so fs t a n d a r dl a p l a c i a n m a t r i x l i s to f 乃b l e s 5 1b a s i cp r o p e r t i e so fb e n c h m a r kd a t as e t s 6 9 5 2c l a s s i f i c a t i o np e r f o r m a n c eo nd a t as e t s 7 2 6 1 s e t t i n g sf o rc o m p a r e dm e t h o d s 1 0 0 6 2p e r f o r m a n c ec o m p a r i s o n so i ls u b s e t 7 0 0 1 0 6 l i s to ff i g u r e s 1 1 文章分类结构4 1 2 举例说明泛化能力的重要性 7 1 3 线性可分的支持向量机模型8 1 4 特征映射的图示1 0 1 5 位于流形上的数据集1 4 1 6 用一张图来扑捉流形上所有的样本1 5 1 7 各种方法在2 m o o n 8 数据集上的效果比较1 6 3 1i l l u s t r a t i o no ff e a t u r em a p 。3 l 4 1a e x a m p l eo fd a t aw i t hm a n i f o l dg e o m e t r y 3 9 4 2t h eg r a p hc o n s t r u c t e da l o n gt h em a n i f o l d 3 9 4 3i l l u s t r a t i o no fc l a s s i f i c a t i o np e r f o r m a n c ew i t hd i f f e r e n ta p p r o a c h e s 4 1 5 1i l l u s t r a t i o no fs p e c t r a lc o e t f i c i c n t so fd i f f c r e l 吐m c t h o d s 7 4 6 。1 t a x o n o m yt r e eo fs u b s e t t 0 0s e l e c t e df r o m2 0 n e w s g r o u p s 10 1 6 2 t a x o n o m yt r e eo fs u b s e t 8 0 0s e l e c t e df r o m2 0 n e w s g r o u p s 1 0 1 6 3p e r f o r m a n c ec o m p a r i s o n so ns u b s e t 8 0 0i nt e r m so fl a b e l e dd a t as i z e1 0 5 a c k n o w l e dg e m e n t s t h i st h e s i sh a sb e e nf i n i s h e du n d e rt h eg u i d a n c ea n de n c o u r a g e m e n to fm y s u p e r v i s o r ，p r o f e s s o rl i uk a n g s h e n g h i sp l e n t i f u lk n o w l e d g e ，k e e nm a t h e m a t i c a l t h i n k i n g ，a n dr i g o r o u sr e s e a r c ha t t i t u d ew i l lb e n e f i tm ef o r e v e r w i t h o u th i s a d v i c e sa n de n c o u r a g e m e n t ，t h i st h e s i sw o u l dn o ta p p e a rh e r et o d a y d u r i n gm y p h dp r o g r a m ，h ei sa l w a y sp a t i e n tw i t hm yf a u l t s ，e n c o u r a g em et oo v e r c o m e d i f f i c u l t i e sn o to n l yi nr e s e a r c hb u ta l s oi nl i f e ie x t e n dm yw a r m e s tt h a n k st op r o f e s s o rj a m e sk w o ki nc s ed e p a r t m e n t o fh o n g k o n gu n i v e r s i t yo fs c i e n c ea n dt e c h n o l o g y ( h k u s t ) h ei ss on i c eo f i n v i t i n gm et ov i s i th k u s tt w i c e ，a n df r e e l ys h a r e dh i sp a s s i o na n dd e e pu n d e r - s t a n d i n go fm a c h i n el e a r n i n g h eh a sb e e nv e r yh e l p f u la n dg e n e r o u st om ea n d i h a v el e a r n e dal o tf r o mo u rc o l l a b o r a t i o n io w em a n yt h a n k st oi n s i g h t f u ld i s c u s s i o n sw i t hm yf r i e n d sw a n gc h e n g q u n ， p a nw e i k ea n dx i az h e n g d i s c u s s i o nw i t ht h e ma l w a y sv a l u a b l ef o rm e ，t h e i r k i n d n e s sh e l pm eal o t ，b o t hi na c a d e m i ca n dl i f e id e e p l yi n d e b t e dt om y h o n e yx u en a f o rh e re n c o u r a g e m e n ta n dp a t i e n c e t h r o u g h o u tt h i se n d e a v o r t h ep e r i o do fw r i t i n gt h e s e st o g e t h e ri sa r d u o u s ，b u t i m p r e s s i v e l a s tb u tn o tl e a s t ，is h o u l dg r e a t l ya p p r e c i a t em yp a r e n t sa n dm yb r o t h e r ， t h e ya l w a y ss u p p o r tm e ，e n c o u r a g em e t h i st h e s i si sd e d i c a t e dt ot h e m c h a p t e r1 i n t r o d u c t i o n ( c h i n e s e ) 从数据中学习的问题在历史上已经被很多哲学家研究过，并称之为。归纳推 理。人工智能领域的研究者从一开始就考虑了学习的问题。a l a n t u r i n g 8 7 在1 9 5 0 年 指出了学习器的思想，以反驳“机器只会做我们指挥它做的事情”的论断。数年 之后f r a n kr o s e n b l a t t 的感知器【7 2 】是最初开发出来的学习器之一。将学习问题建 模使其成为在适当假设空间中的搜索问题是人工智能方法的特点之一。 学习算法的发展成为人工智能的一个重要的子领域，最终形成了机器学 习这样一个独立的学科领域，在现代智能技术中扮演着活跃的角色。在历史 上，对机器学习有过很多不同的说法，目前大家比较公认的说法是s i m o n 对学习 的阐述 7 6 1 ：“如果一个系统能够通过执行某种过程而改变它的性能，这就是学 习”。s i m o n 对学习的说明是对机器学习的一个一般性概括，可以说是一种理念。 这种说法包括三个要点：( 一) 、学习是一个过程；( 二) 、学习是对一个系统而言 的；( 三) 、学习可以改变系统的性能。过程、系统和性能改变是学习的三个要点。 对计算机科学而言，人们更关心对不同系统实现机器学习的过程，以及改变性能 的效果。简单地说，我们可以将机器学习理解为一种优化过程。 基于数据的机器学习就是研究如何从一些观测数据( 样本) 出发得到目前尚 不能通过原理分析得到的规律或者内在因素，即基于观测设计优化过程，然后利 用这些规律去分析客观对象，对未来的数据或无法观测的数据进行预测和分析。 它的主要任务是：对于一种未知的依赖关系，以观测为基础对它进行估计。现实 世界中存在大量我们还无法准确认识但却可以进行观测的事物，因此这种机器 学习在从现代科学、技术到社会、经济等各领域中都发挥着十分重要的作用。 1 1 c o n c e p t s 为了理清相关概念和术语，我们试图通过构造一个实际的例子来考察机器 1 2 c h a p t e r1 i n t r o d u c t i o n ( c h i n e s e ) 学习中的一些基本概念，包括任务、类型等。 假定有一信患发布商有偿提供一些在线信息( 新闻、文章等文本信息) 。每 位订阅者必须先建立自己的帐户，然后才能闲读自己感兴趣的新闻。在网页的每 一屏显示1 0 条新闻，每条新闻有题目、简短的摘要和全文链接等。如果读者看了 题目或摘要对某篇文章有兴趣的话，贝i j 可以点击全文链接进一步阅读。所以在一 定程度上，用户的点击就能反应他对文章是否感兴趣。信息发布商希望根据用户 的点击记录等资料，来为客户提供个性化的信息服务。其实，信息提供商的信息 库( 不管是否在其自身的服务器上还是在网络上) 是非常庞大的，如果没有用户 的参与，而把所有文章毫无过滤地呈现给用户，这样从用户获取资讯的效率上来 看是不可取的。而系统能根据用户自身的特点来过滤掉那些他一般情况下不感 兴趣的话题，会为他掌握广泛的资讯提供一条有效的途径。为了提高服务质量， 信患发布商可以让系统通过以下方式来学习用户的兴趣。 监督学习( s u p e r v i s e dl e a r n i n g ) 假设你已经成为该信息发布商的注册用户，为了让系统有效地学习你的 阅读兴趣，一种直接的方式就是要求你自己能够参与到学习中来。当你 第一次登录系统的时候，系统会提供很多具有代表性的新闻，并且要让 你从其中选择自己感兴趣的。那么，系统可以根据你的选择，得到一组信 息 甄，犰 名l ，其中甄甩以表示第i 条新闻的数据1 ，粤表示供你选择的新闻总 数量，y i 一1 ，+ 1 ) 是你刚刚做出的选择，+ 1 表示你感兴趣，一1 表示你不 感兴趣。最终，系统可以根据这组数据来学习一个判别函数h ( z ) ，以此来决 定你是否会对任意给定的一篇文章z 感兴趣。如此，系统会根据该判别函数 在它的信息库里面挑选出那些你感兴趣的文章，并在你再次登录系统之后 展示给你。 无监督学习聚类( u n 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 g ) 顾名思义，这部分的工作不需要用户的参与，而往往是在系统端( 服务器 端) 来完成的。它的日的是根据文章的自身特征来将文章分成不同的组别。 比如，根据词汇、结构等来度量文章之间的相似程度，然后把相似的文章聚 到一起。 半监督学习( s e m i s u p e r v i s e dl e a r n i n g ) 在当今资讯爆炸的时代，很难用为数不多的文章来反映一个人的阅读兴趣。 一方面，现在的人们涉猎广泛，每个领域的变化日新月异且相关的资讯爆 炸式增长，即使每个领域能挑选出一千篇文章来反映用户的兴趣，也是相 1 可以有很多种表达方式，在信息提取和文本挖掘领域有很多有效地方法来表述一个文本。 3 当草率的，毕竟这些文章只能是冰山一角，难以揭示该领域的全貌。另一 方面，如监督学习的设想那样，让用户来挑选自己感兴趣的东西，会给用 户带来不好的使用体验。一般情况下，调查问卷的效果是值得怀疑的，用 户既懒地回答也难以回答他对某篇文章是否感兴趣，更何况由于个人兴 趣的转移，用户现在做出的选择对以后的学习并不一定有参考价值。综上 两点，信息服务商不能像监督学习那样来获取用户的兴趣信息，需要另辟 蹊径。如果用户在看了标题和摘要之后再点击阅读全文，我们就认为用户 对该篇文章戤感兴趣，其对应的标号为+ 1 ，同时取该屏中用户没有点击的 文章的标记为一1 ，即是该用户不感兴趣的。于是，我们得到一组已标记数 据( 甄，玑) 冬1 ( 称之为l a b e l e dd a t a ) 但是这些文章相对于总体的信息库来说， 数量相当少，还有数量相当庞大的文章用户没有涉及，记其为 甄 墨f + 1 ，无 从知道该用户是否对这些文章感兴趣，即其对应的犰未知。如果仅仅根据已 标记的文章来做监督学习的话，就如上述分析一样，显然难以准确反映用 户的兴趣。所有的文章之间有其结构性和关联性，如果没有充分挖掘这些 信息，难以设计一个好的分类器。半监督学习就是基于部分带标记的数据 集 规】，鍪1 的学习方法，希望能通过挖掘未标记的样本所揭示的分布或结构 来提升训练的质量。半监督学习在设定上可以认为介于监督学习和无监督 学习之间，既充分利用了标记数据的信息又考虑了所有数据集所隐含的结 构信息。 传导学习( t r a n s d u c t i v el e a r n i n g ) 和归纳学习( i n d u c t i v el e a r n i n g ) 传导学习和归纳学习是机器学习中的两种截然不同的方式。传导学习的最 大特征在于，那些需要分类的点疋在训练期间是必需，而学习的最终目的 仅仅是为了给疋赋予标记( 类别) ，而不需要给出分类器的具体表达。所以， 传导学习的弊端在于，如果有新的点需要预测的话，那么整个算法都得重 新计算。相比之下，监督学习中分类器是必需得到的，因为我们需要用该分 类器去对未来的点做出分类。在这一点上，归纳学习有类似的性质。举例来 说，如果一个半监督学习算法是归纳的，那么它不仅仅能给出未标记点的 类别，同时它还可以很容易地对未来不能预知的点进行分类，仅仅只要把 需要预测的点代入到判别函数( d e c i s i o nf u n c t i o n ) 中去计算即可，而不需 要重新计算分类器。回到我们先前的例子中来，如果系统端只想确定用户 对数据库中当前所存储的所有文章是否感兴趣的话，那么可以用传导学习 的方法来做，但是这样的方法对新收集来的文章则无能为力，除非系统对 所有的文章重新计算分类结果。相比之下，用归纳的方法计算出来的分类 器对未知的样本仍能适用，方便得多。打个直观的比方，传导的方法就如学 4c h a p t e r1 i n t r o d u c t i o n ( c h i n e s e ) f i g u r e1 1 ：文章分类结构。 生带回家做的家庭作业，而归纳的方法更像是考场上的现场发挥。当然，也 不能说现场发挥好的学生就一定是好学生，有些时候只需要把家庭作业做 好了就足够了，得看具体问题而定。 基于结构输出的监督学习( s u p e r v i s e dl e a r n i n gw i t hs t r u c t u r a lo u t p u t ) 在我们的例子中，学习每位用户的兴趣取向其实是一个两类分类问 题( b i n a r yc l a s s i f i c a t i o n ) ，对每篇文章只需要确定用户是否感兴趣即可。现 在进一步设想用户可以开通一种增值服务，即把所有该系统认为用户会感 兴趣的文章按照一定的类别进行归类排列，以便阅读和整理。假设某用户 根据个人兴趣设置了如图1 1 所示的主题结构： 那么系统需要直接该用户感兴趣的文章归入到上述所有1 2 个底层类别( 叶 节点) 中去，我们称这样的问题为多类分类问题( m u l t i - c l a s sc l a s s i f i c a t i o n ) 。 如果系统要求用户根据自己的习惯标记了很多文章，然后它根据用户标记 过的文章来进行训练，并用得到的分类器来对其他的文章进行归类，那么 这个任务实际上是传统的多类监督分类问题。但是这样的话，没有考虑到 类别之间的相互关系，而是将它们单独看待了。由于文章可能涉及到多个 主题，有些文章实际上很难精确归入一个具体的类剔，也可能根据个人看 法会有不同。值得一提的是，一篇文章被错误分类的“代价”会根据被归入 类别的不同而会有差异。举例来说，个股分析的文章最好是放到。个股目 录下，如果放到。财经评论”里面有时也无可厚非，但是放到。人工智能 5 或者“足球”里面去，那就很糟糕了。另外，。篮球”和。足球。较为接近，因 为它们至少都是属于。体育”范畴的，但是“篮球。和。数学就相去甚远， 它们在主题上已经“隔了两代。了。而这些因素在传统多类分类问题里面被 忽视了，因为在这些模型里面不能考虑类别之问的各种关系( 比如类别的 相互差异、从属和层次关系等) 。而基于结构输出的监督学习是在传统多类 监督学习的基础上，进一步将类别之间的结构和关系考虑进去。 基于结构输出的半监督学习( s e m i - s u p e r v i s e dl e a r n i n gw i t hs t r u c t u r a lo u t p u t ) 继续上述的讨论，如果系统要达到较好的分类效果，要求用户帮助系统标 记为数不少的文章，就如前面分析的一样，这一点在用户体验和可行性上 都是不理想的。系统可以根据用户在对应类别的收藏夹里面收藏的少量文 章来知道分类( 特别如图1 1 中。特别关注”这样的个性化类别) 。光光靠这 些少量标记过的文章来做基于结构输出的监督学习的话，效果之差不足为 奇，毕竟这样已经忽略了各个类别之中所有文章的整体结构，而这些靠小 样本数据是难以揭示的。而如果采取半监督学习，我们可以通过其他未标 记的文章来揭示更多文章之间的关联和结构，并以此来达到更好的分类效 果。 生成模型( g e n e r a t i v em o d e l ) 和判别模型( d i s c r i m i n a t i v em o d e l ) 在所有分类方法中，主要可以分成两大类：基于生成模型的学习和基于判 别模型的学习。生成模型需要估计输入和输出空间的联合分布p ( x ，可) 。一 般情况下，基于生成模型的分类方法主要有以下几个步骤：1 ) 通过学 习得到给定类别的条件分布p ( z i 夕) ；2 ) 结合类别的先验分布p ( 剪) ，用贝 叶斯准则得到后验分布p ( y l x ) ；3 ) 对于所有y y ，计算基于点x i 的后验 分布p ( 秒慨) ，用出现概率最大的类别来标记点x i 。而判别模型则是直接计 算f ( x ) = p ( y l z ) 而不需要计算先验分布和联合分布。本文主要基于判别模 型来设计学习算法。 定义1 ( 训练集和测试集) 使用疋表示输入空间( i n p u ts p a c e ) ，通常z 。 用y 表示输出空间( o u t p u ts p a c e ) ，对于两类问题而言，y = - 1 ，1 ) ；对于多类问 题，y = 1 ，2 ，m ) ；对于结构化输出问题，则y 中的元素之间是有关联和结构 的。训练集( t r a i n i n gs e t ) 是训练样例的集合，也常常被称为训练数据( t r a i n i n g d a t a ) ，在监督学习中通常表示为： s = ( z l ，y 1 ) ，( 轨，肌) c 疋y ，( 1 1 ) 6c h a p t e r1 i n t r o d u c t i o n ( c h i n e s e ) 其中，z 是训练样本数目。在半监督学习中，训练数据除了已标记数据之外还包含 未标记样本，具体表示为： s = ( z 1 ，秒1 ) ，( z ，玑) ) t _ jx t + l ，z n )( 1 2 ) 并1 - x l ，观) 被称为已标记点集( 1 a b e l e ds e t ) ， z 绊l ，】财代表未标记点 集( u n l a b e l e ds e t ) 。 在机器学习的问题当中，一般还会涉及鲥测试数据( t e s t i n gd a t a ) ，在监督学 习申具体表示为： & = ( z 件1 ，y l + 1 ) ，( x t + t ，肌+ t ) ) 疋y ，( 1 3 ) 在半监督学习中舅i j 为： s ：= ( z n + 1 ，y n + 1 ) ，( x n + t ，y n + ) ) z y ( 1 4 ) 测试数据在训练期间是不可知的，而在训练结束后用以衡量一个分类器的好坏。 定义2 ( 得分函数和决策函数) 在两类问题中，利用训练数据进行监督学习或归 纳式半监督学习之后，得到一个得分函数( 8 c o r ef u n c t i o n ) f ( x ) ：z _ r ，而分 类器( c l a s s i f i e r ) 九( z ) 则由如下规则给出： h ( x ) = s g n ( f ( x ) ) ，( 1 5 ) 即给定一个样柚，它的类型f f t h ( x ) 给出。 ( z ) 也叫决策函数( d e c i s i o n 知n c t i o n ) 。 在多类问题或结构化输出问题中，得分函数不仅依赖于输入还依赖于输出， 耳p f ( x ，y ) ：刀xy _ r ，f ( x ，) 的值可以直观地理解成样本点z 属于类别可的可信 度，基于这样的理解，分类器九( z ) 可由如下规则给出： h ( x ) = m 2 x f ( x ，y ) ( 1 6 f 【， 在传导式半监督学习中，则不需要求出具体的判另l j 函数，只需要得到每个点在每 个类别上的得分值f ( x ，可( 七) ) 即可。为了陈述方便，我们认为传导式半监督学习还 是可以得到相应的分类器和得分函数的，只是它们不适用于未知样本点而已。 本文中我们只考虑判别学习( d i s c r i m i n a t i v el e a r n i n g ) 的方法，也就是以学 习一个“好”的得分函数为目标。那么怎么来度量一个得分函数是。好”的呢? 在 两类问题中，不管是监督学习还是半监督学习，我们都需要达到一个日的，就是 对于所有已标记点翰满足，( 戤) 玑，这里采用而非等号是由于等号往往难以 取到。直观上来看，一个好的分类器要求，( z ) 在所有已标记点上取值接近于其真 1 2 s v m k e r n e lm e t h o d s7 f i g u r e1 2 ：举例说明泛化能力的重要性。 实标号y ，并选取合适的损失函数c ( ，) 来惩罚两者之间的差异。换言之，一个好 的分类器要求如下损失项取值较小： ：c ( ，( 兢) ，玑) ( 1 7 ) i - - - - 1 当其取值为。时，则该分类器在标记点上的分类结果与实际完全相符。但是，仅 仅达到这个目的还是不够的，机器学习中重点关注的是一个分类器的泛化能力。 举例来说，从图1 2 的左边可以看出，直线的分割面有两个点分类错误，而较为复 杂的曲线分割面则分类完全正确，那是否说明后者比前者要好呢? 而事实并非如 此。如果我们把测试点放上去之后再比较一下效果，从右图可以看出，直线分割 面的分类效果实际上比曲线分割面要好。为什么会发生这样的情况呢? 事实上， 过分复杂的分割面虽然可以使损失项很小，但是这样会导致过拟合( o v e r - f i t t i n g ) 的现象，而简单的函数却更能反映出数据的内在性质。从这个例子中可以看出， 泛化能力同损失项一样也是模型需要考虑的因素之一。 1 2 s v m ，k e r n e lm e t h o d s 在这一节中，我们先简要介绍支持向量机( s v m ：s u p p o r tv e c t o rm a c h i n e s ) 的数学模型，它是贯穿我们全文的基本模型。我们先从直观的几何解释给出两类 线性分类问题的数学模型，然后通过求解其对偶问题，将线性分类器推广到非线 性的情况，在这关键的一步上，核函数发挥了重要的作用。 考虑监督学习问题，训练数据由 ( 戤，玑) ) ：= l 给出，其中玑 - 1 ，+ 1 ) 表示 类别