（计算机应用技术专业论文）概率图上的流形学习.pdf

浙江大学硕士学位论文摘要 摘要 对训练数据的建模是机器学习中的一个核心问题，本文将数据建模的两种经典方法 一一流形学习与统计学习作了结合，相互取长补短。在我们之前一些相关工作的基础之 上，本文基于黎曼流形等方面的背景提出了一个完整的理论框架，设计了两个互补的优 化算法，并通过大量的收敛性证明，凸性分析，以及计算复杂性等分析，将算法的外沿 和应用范围作了极人的拓展，同时本文还设计了一套高效灵活的通用概率推断引擎，称 为y a s i e ( y e ta n o t h e rs t a t i s t i c a li n f e r e n c ee n g i n e ) ，使得所有这些方法可以用类似搭积 木的方式进行自由组合。在此基础上，我们给出了这些方法和工具应用在两个经典的机 器学习问题上的实验结果。对于训练数据大部分没有标记的半监督学习，本文总结的方 法能取得尤其好的效果，相关的工作发表在a c mm u l t i m e d i a ，i e e et k d e 等囡际一流 会议和杂志上。 流形学习是假定训练数据的本征维度比它们实际的维度要小很多，可能出现的数据 分布在其所在高维空问中的一个低维的予流形上。而流形学习的任务是要用给出的有限 个样本来推测流形的结构，计算并逼近一些对应的真实流形相应的几何性质，如低维二f 流形嵌入，切空问，拉普拉斯算子等。现有的流形学习通过在样t i 数据之问建立一个邻 接关系图，并由这个图的结构诱导出一个朋于优化图上侮个节点的标记的目标隧数。它 的特点是高度二 卜参数，刈。j ：数据问的结构的把握商效精准，恰到好处，并_ 目常常可以证 明用图结构离散地计算得到的结果在样本数足够多时能收敛到连续的情况。但它的问题 存于应对多模态，具有复杂数据结构的输入训练数据时，显得力不从心。数据的结构上 的关系不能得到有效地建模，并且很难应用先验信息。此外，为适应动态变化的数据而 提出的在线学习的需求常常很难用流形学习得到满足。另一方面，统计学习通过使用具 有一定分解形式的联合概率分布来建模给出的数据得利于统计学深厚的积累，对于上 述流形学习所遇到的问题能有比较好的解决方案。但它的问题在于模型通常是高度参数 化的，它能否很好地拟合给出的数据依赖于参数形式指定地是否准确，对于数据分布在 比较复杂的流形上的情况，同样捉襟见肘。 本文从两个不同的途径结合两种学习方法，一种是把流形学习诱导出的目标函数添 浙江大学硕士学位论文 摘要 加到统计学习的优化准则中，作为一个正则项。本文大部分成形的工作基于这个思路。 另一个途径是用统计学习的一个基本工具一一概率图模型，直接去建模用于流形学习的 邻接关系图，使得它所反应的概率依赖关系在概率图上得到直接的表达，从而更自然得 融入到原有的统计学习中去。并且我们可以证明：( i ) 部分流形正则项可以用一定形式的 概率图表达；( i i ) 部分概率图表达的邻接关系图可以用一定形式的流形正则项解释。相 关工作还在探索中。 关键词：流形学习，统计学习，流形正则化，概率图模型，半监督学习 浙江大学硕士学位论文a b s t r a c t a b s t r a c t m o d e l i n gt r a i n i n gd a t ai saf u n d a m e n t a lp r o b l e mi nm a c h i n el e a r n i n g i nt h i st h e s i s ， w ep u t t o g e t h e rt h et w om o s tp o w e r f u ld a t am o d e l i n gt e c h n i q u e s ，n a m e l ym a n i f o l d l e a r n i n ga n ds t a t i s t i c a lm o d e l i n g ，s ot h a tt h ec o m b i n e dm e t h o dw i l lb e n e f i tf r o mt h e a d v a n t a g e so fb o t ha p p r o a c h e s b a s e do no u rr e l e v a n tp r e v i o u sw o r k s ，t h i st h e s i sp r o p o s e dat h e o r e t i c a lf r a m e w o r ki nt e r m so fb a c k g r o u n d so nr i e m a n n i a nm a n i f o l d w e d e s i g n e dt w od i f f e r e n ta l g o r i t h m st od ot h eo p t i m i z a t i o na n di n f e r e n c e ，e a c hw i t hd i f - f e r e n tp e r f o r m a n c eg u a r a n t e e s b e s i d eo ft h a t , w ea l s og i v ei nd e p t ha n a l y s i so ft h e a l g o r i t h m s ，i n c l u d i n gc o n v e r g e n c ep r o p e r t y , c o n v e x i t y , a n dc o m p u t a t i o n a lc o m p l e x i t y , w h i c hg r e a t l ye n l a r g e dt h ee x t e n to fo u r a p p r o a c ha n d b r o a d e n e di t sa p p l i c a t i o n r a n g e t oa c c e l e r a t et h ew h o l ep r o c e s s ，w ea l s oc r e a t e da g e n e r a lp u r p o s es t a t i s t i c a li n f e r e n c e e n g i n e ，n a m e dy a s i e ( y e t a n o t h e rs t a t i s t i c a li n f e r e n c ee n g i n e ) ，s ot h a td i f f e r e n tm o d e l s c a nb ec o m p o s e d b yu s i n gb u i l d i n gb l o c k s ，a n dt h ec o m p u t a t i o n a lc o s ta r ec a r e f u l l yr e f i n e ds ot h a ti ta p p r o a c h e sh a n dw r i t t e ni n f e r e n c ec o d e s b a s e do nt h e s e m e t h o d o l o g i e s a n dt o o l s ，w es h o wo u r e x p e r i m e n t a lr e s u l t si nt w oc l a s s i cm a c h i n el e a r n i n gp r o b l e m s o u r a p p r o a c hi sp a r t i c u l a r l yg o o df o rs e m i s u p e r v i s e dl e a r n i n gw h e r em o s to ft h et r a i n i n gd a t ai n s t a n c e sa r e n o tl a b e l e d r e l a t e dp a p e r sa r e p u b l i s h e di nt o pc o n f e r e n c e sa n d j o u r n a l ss u c ha sa c m m u l t i m e d i aa n di e e et k d e m a n i f o l dl e a r n i n ga s s u m e st h a tt h ei n t r i n s i cd i m e n s i o n a l i t yi sm u c hs m a l l e r 豳a n t h ea p p a r e n td i m e n s i o n a l i t yo ft h ed a t a p o s s i b l ed a t as a m p l e sw i l ll i eo nal o wd i m e n s i o n a lm a n i f o l de m b e d d e di nt h eh i g hd i m e n s i o n a la m b i e n ts p a c e t h et a s ko fm a n i f o l dl e a r n i n gi st og e ts o m ek n o w l e d g eo ft h et r u es t r u c t u r eo ft h em a n i f o l db yu s i n g t h ef i n i t en u m b e ro fd a t as a m p l e sa th a n d ，s ot h a tw ec a nc o m p u t ea n d a p p r o a c ht h e t r u eg e o m e t r i c a lp r o p e r t i e so ft h em a n i f o l d ，s u c ha sl o wd i m e n s i o n a le m b e d d i n g ft a n g e n ts p a c e ，l a p l a c e b e l t r a m io p e r a t o r s ，e t c c u r r e n tm a n i f o l dl e a r n i n gm e t h o d su s u a l l y c r e a t e sa d j a c e n c yo rs i m i l a r i t yg r a p h sa m o n gt h ed a t ap o i n t s ，f r o mw h i c ha no b j e c t i v e 浙江大学硕士学位论文 a b s t r a c t f u n c t i o nf o rt h eo p t i m i z a t i o no ft h el a b e l so ft h ed a t ap o i n t si si n d u c e d t h eb e n e f i t o fm a n i f o l dl e a r n i n gi st h a ti ti sh i g h l yn o n p a r a m e t r i c ，i tm o d e l sn o n t r i v i a ls t r u c t u r e s a m o n g d a t ae f f e c t i v e l ya n da c c u r a t e l y , a n ds o m e t i m e st h ed i s c r e t e l yc o m p u t e dr e s u l t s c a ne v e nb ep r o v e dt oc o n v e r g et ot h ec o n t i n u o u sc a s e t h ep r o b l e mi st h a ti ti sd i f f i c u l t t od e a lw i t hm u l t i m o d a ld a t a ，s u c ha st h o s ei ni m a g ea n n o t a t i o n b e s i d e s ，i ti sd i f f i c u l t t oi n t r o d u c ep r i o rk n o w l e d g ea n dd e a lw i t hd y n a m i cd a t ai na no n l i n es e t t i n gu s i n g m a n i f o l dl e a m i n g c o n t r a r i l y , s t a t i s t i c a lm e t h o d sm o d e l sd a t aw i t hp r o p e r l yf a c t o r i z e d j o i n td i s t r i b u t i o n t h a n k st ot h el o n gt e r ma c c u m u l a t i o n ，s t a t i s t i c a lm e t h o d sh a v eg o o d s o l u t i o n sf o rt h ea b o v em e n t i o n e dp r o b l e m s h o w e v e r , t h ep r o b l e mo fs t a t i s t i c a lm o d e l i n gi st h a ti ti su s u a l l yh i g h l yp a r a m e t r i c w h e t h e rt h e s em e t h o d sf i t sd a t aw e l ld e 一 p e n d so nh o ww e l lw es p e c i f yt h ep a r a m e t r i cm o d e l s m o s tc o m p u t a t i o n a l l yt r a c t a b l e a n de f f e c t i v em o d e l sh a v ed i f f i c u l t i e sd e a l i n gw i t hd a t ai nn o n t r i v i a lm a n i f o l d s i nt h i st h e s i s ，w ec o m b i n et h et w oa p p r o a c h e si nt w od i f f e r e n tm a n n e r o n ei st o a p p e n dt h eo b j e c t i v ef u n c t i o no fs t a t i s t i c a ll e a r n i n gw i t han e wc o n s t r a i n ti n d u c e db y t h ea d j a n c yg r a p hf o ra p p r o a c h i n gt h em a n i f o l ds t r u c t u r e t h ea d d e dc o n s t r a i n ti sr e g a r d e da sar e g u l a r i z a t i o nt e r m m o s tm a t u r e dm e t h o d o l o g i e si nt h i st h e s i sa r eb a s e d 0 1 7 1t h i sp r i n c i p l e a n o t h e rp o s s i b l ed i r e c t i o ni st om a k eb e t t e ru s eo ft h ep r o b a b i l i s t i c g r a p h i c a lm o d e l ，t om o d e lt h ea d j a c e n c yg r a p hd i r e c t l ) ；s ot h a tt h ep r o b a b i l i s t i cd e p e n d e n c yr e l a t i o n s h i pc a r tb ee x p r e s s e ds t r a i g h t f o r w a r d l yi nt h ec h a i ng r a p hm o d e l a n d w ec a np r o v et h a t ：( i ) s o m em a n i f o l dr e g u l a r i z a t i o nt e r m sc a nb er e i n t e r p r e t e db ya s p e c i f i cf o r mo fc h a i ng r a p h r e p r e s e n t a t i o n ；( i i ) s o m ec h a i ng r a p hr e p r e s e n t a t i o no ft h e a d j a c e n c yg r a p hc a n b er e i n t e r p r e t e db yu s i n gm a n i f o l dr e g u l a r i z a t i o n t h i sp a r to ft h e w o r ki ss t i l li ne x p lo r a t i o n k e yw o r d s ：m a n i f o l dl e a r n i n g , s t a t i s t i c a ll e a r n i n g ，m a n i f o l dr e g u l a r i z a t i o n ， p r o b a b i l i s t i cg r a p h i c a lm o d e l s ，s e m i s u p e r v i s e dl e a r n i n g 图目录 1 1 引入半监督学习和无监督学习的必要性。 3 1 2 概率图模型例子7 1 3 统计建模的困境。8 1 4 生成式学习1 0 1 5 图模型中的函数学习1 2 3 1 关系学习模型。2 3 3 2 最简单的非凸情形2 7 3 3 高斯混合模型及双月数据。3 5 3 4 流形正则化的高斯混合模型3 9 3 5 混合连文模型3 9 3 6 复合的混合一连文模型4 0 3 7 概率潜语义分析模型4 2 3 8 简化的概率潜语义分析模，秘4 2 3 9 潜彳f = 狄乖| 兜雷乡f 氍：，4 3 3 1o 埘潜在狄利克甭分蝤一进行的图像主题学习 镉 3 1 l 数据聚类实验所用数据库5 5 3 1 2 数据聚类实验结果。5 8 3 1 3 图像标注对比模型。5 9 3 1 4 p l s a w o r d s f f o j 5 ：作模式6 0 3 1 5 图像标注所用模型与邻接关系示意图6 1 3 1 6 图像标注结果对比6 4 3 1 7 图像标注结果示例6 5 4 1 ( a ) 具有个“对象”的图模型。每一个对象被关联到一。个( 或+ 组) 随机变量z 。( b ) 示例模型 i v 浙江大学硕士学位论文图目录 4 2 ( a ) m a n i f o l dr e g u l a r i z e dg r a p h i c a lm o d e lw i t ho b j e c t s ，r e p r e s e n t e di nt h ef o r mo fac h a i r 4 3t h ed i r e c t e da l t e r n a n v eo ff i g 4 2 6 9 v 浙江大学硕士学位论文表目录 表一1 5 t 录衣求 1 1 对数据作假设的必要性。 2 1 2 函数学习的类别 4 算法1 ：完全分解的变分法概率推断1 5 算法2 ：保证收敛且高效的算法：多变量分步优化，2 5 算法3 ：加速的流形正则化变分法2 ( 多目标优化) 2 7 浙江大学硕士学位论文符号说明 符号说明 图模型相关记号 口：潜在的随机变量，用点估计来进行估计。 o ：潜在的随机变量，用贝叶斯估计来进行估计。 口：有观测值的随机变量，观测到值。 o ：有观测值的随机变量，观测到它的置信度，也就是它可能取值的边缘分布。 浙江大学硕士学位论文第1 章背景及意义 第一章背景及意义 在本章中，我们将依次简要地介绍几个基本的概念，主要是机器学习的几种常见的 形式，它们各自的优缺点，从而引出本文的立意和构想。 1 1机器学习 机器学习，最根本地来说，就是希望计算机能自动设计算法，做我们想让计算机去 做的事。而一个算法，抽象出来就是给出一组输入z 。￥，用有限步图灵可计算的步骤 计算出一个输出y = 厂( z ) ，! ，y 。从这个角度讲，机器学习，就是希望计算机能自动找 一个这样的。f ( ) 。 与非机器学习的算法设计相区别，机器学习不是由人工去设计一个厂( ) ，而是从 “数据”中自动学习得到。而数据，可能是历史上曾经如何由z 得到可的历史记录，或 叫案例，也可能是由基准数据给出的已知的输入与输出对。形式上，它们都是一个一 个的( z i ，可0 的配对，i 1 ，一 ，在机器学习领域我们把它叫做训练数据。我们的强 标，就是利用这些洲练数据，去搜寻一个某种意义一l “最优”的算法。厂8 ( ) 。 从方法一l 来说，由于一个“算法”是很难被“优化的，因为它们定义的空间不具 有连续性。机器学习是用一个函数去近似一个算法，我们同样记作f ，4 ：某个函数空 间里陶f 芦。机器学习的假设，就是说厂空间中不同的实例| 就对应- 某种意义上不弼 的“算法”。肴：这种意义上，机器学习就是 j “优化”的办法，在厂窄问叶i 找一个“最 优”的。f + 。它可以对一个新的输入z ，计算一个输出矽= f 8 ( ，f ) 。实际巾，我们是在厂的 某种参数化形式上，对它的参数f ； o 进行优化。移的复杂度可以同定也可以可变。如果 固定，那么就是“参数化 机器学习方法因为学习得到的函数是由一个固定复杂度的 参数规定的一个参数模型。相应的，“非参数”方法是指目可以随着数据的复杂度自动 得伸缩。 1 2函数学习与正则化 根据上一节的分析，机器学习与“曲线拟合 有一定程度的联系。而事实上，通常 1 浙江大学硕士学位论文第1 章背景及意义 机器学习的优化目标函数也与“曲线拟合”十分类似，如下， n ，+ = a r 辫i n 丙1 ，f ( x i ) ) + 入i l f l l 2 ( 1 1 ) 其中，是函数，变化的空间，v ( p t f ( z i ) ) 是，作用在数据( t i ：犰) 上时的损失函数( l o s s f u n c t i o n ) 。忖1 1 2 是。厂好坏的某种度量，在不同的领域有不同的口q 法，比如说，曲线拟合 时，它被种为“平滑性约束 ，机器学习中，它被称为“正则项 ，在统计中，它被称 为“先验”。实际上它们都是同一个意思。 正则项的必要性是这样的：由于数据点只有有限个，并且只分布在一些离散的位置 上，所以如果不加这个约束，那么拟合出来的函数只要在有数据点的位置上y 的值与训 练数据一致就可以，而别的位置上输出的可以任意，这样的话，对于新的输入x ，它能 计算的y 是随机的，这显然不合理。所以我们要给别的位置上的输出做一些的约束。然 而，因为给出的训练数据只包括了这些有限个位置上的输出，所以如果不加上一些对于 训练数据( z i ，y i ) 的来源的假设，那么是无论如何也不可能得到一个合适的对于厂的约束 的。考虑下面的真值表 表1 1 ：对数据作假设的必要性：如何预测问号处的值? a ba0b 1 1丁f 丁f7 1 1，1 7 一 f鼻1f 我们可以把a ，b 看成是输入，a 0b 看成是输m ，我们的目标是由已知值的三组训 练数据去学习一个输入到输出的函数，并预测问号位置卜的值。然而，对于一个真值表 来说，按我们通常的理解，不论第三列j 一是一个什么样的值的组台，它都是一个合理的 真值表。所以如果不加假设，我们是无论如何没有办法得到一个合理的预测的。现在。 如果我们假定这个表是一个“异或”，那么我们就可以很容易地拟合已有的训练数据， 并得到预测结果为丁。 类似这样的假设，就是对于数据的来源，或者叫生成方式的假设，形式上，就是假 设了( z ，可) 的一个联合分布，p ( x ，y 7 ) ，并且假设训练数据就是从这个分布中独立同分布 2 浙江大学硕士学位论支第1 章背景及意义 的采样出来的 日，y i ) 一p ( x ，y ) ，i f 1 ，_ ( 12 ) 而我们韵目标是希望我们学习得到的函数，在训练数据上得到好的结果的同时，在将 来新的数据上也能工作得很好，也就是最小化损失函数在这样一个分布上的期望 1 n r r = a r ，e ，g m i a 寺萎v ( 刈( 硝) + 7 嘶洲瑚”( ) ( 1 3 ) 而对联合分布p ( x ，y ) 的不同的假设，就对应了公式( 11 ) 中不同的“正则项”形式。 1 3 函数学习的局限性 在实际问题中，并不是所有的训练数据都同时给出。和y 。很多时候，获取真实的输 出是一件根费时间和资源的工作，所以只能给出很小一部分涮应的输出，为了能有 效利用那些没有真实输出的y ，使它们也同样能参与学习的过程并提供有效的信息量 必须要引入半监督学习，甚至无监督学习。图1 1 揭示了这样做的必要性。 l i p 静f 一1o12 ( b ) 图1 2 ：引八半监督学习和无监督学习的必要性。图中，棱彤和田彤袁示这两个训练数据 点上的真实输出( 两种类别) ，绿色和白色区域代袁学习得到的两类之闻的分界面。左 囤( a ) 没有利用不带真实输出的那些数据点，右图( b ) 利用了。 更进一步地在函数学习中，由z 和y 的值的不同属性，以及是否缺失，可以把它分 成几个大类，见于下面的表12 。 3 浙江大学硕士学位论文第1 章背景及意义 表1 2 ：函数学习的类别 类别 给出可与否可值离散可值连续 有 n * 督( s u p e r v i s e d ) y e s 分类( c l a s s i f i c a t i o n ) 回归( r e g r e s s i o n ) 半j 监督( s e m i s u p e r v i s e d )p a r t i a l l y 7 无监督( u n s u p e r v i s e d ) n o 聚类( c l u s t e r i n g ) 降维( d i m r e d ) 其中，不同的设定都分别有不同的技术来解决。这样，最主要的一个问题是在函数 学习中，z 和可的地位是不对等的。这在实际应用中会遇到很多问题，比如 如果还有给出口但不给出z 的训练数据怎么办? 如果这样的数据很多，那么我们还 是要想办法利用的。 如果测试数据中要对一个给定的可求z 怎么办? 如果数据的类别不仅z 和，还有别的( 假设叫。) ，那么所有这些数据的值域类型不 同，又怎么对这些算法分类? 是否每种不同的设定都要专门开发相应的算法? 如果有时是要给出。求，有时是要给出。求n 等等，那怎么办? 为此，需要有一种统一的办法来处理所有这些一i 同的机器学习问题。 1 4 统计建模 统计学的思想和方法弓l 入机器学习以后，为我们用种统的观点来行待不同的机 器学习问题提供了平f ，思路。在统计学考察实际问题的过程中，个比较重要的阶段 就是对问题的建模。统计建模的基本思想是，要考察的问题中，所有可以量化的值， 都应该看成是随机变量，只不过有些随机变量我们是已知它的值的，它就是观测到 f l d ( o b s e r v e dv a r i a b l e ) ，有些我们是要求的，那么它就是没有直接观测到的。还有一些 变量，虽然我们不用去求，但是在建模的过程中如果引入这些变量，会使我们的模型更 加紧凑和高效，这样的变量我们称为潜在变量( 1 a t e n tv a r i a b l e ) 。而由观测到的变量去估 计我们要求的变量的过程，通常情况下我们是先估计这些变量的在给定观测变量时的后 验分布，这过程称为概率推断。比如，如果我们要求的变量集合记为h ，观测到的变 4 浙江大学硕士学位论文 量集合称为v + ，潜在变量集合记为e ，那么概率推断在形式上如下式所示， pc 叩，= 帮= 矗墨器蔷( 1 4 ) 由上式我们可知，概率推断中最重要的是如何表达所有变量的联合概率，如 上式中的p ( h ：v je ) 。对于函数学习的过程，它就是p l ，又 f h ， ) 。其 中 ( x i ：l ；) ) 竺，既包含训练数据，也包含测试数据。事实上，从统计建模的角度来看，并 没有训练数据与测试数据的区别，不同的数据有不同的缺失模式( p a t t e r n ) ，而我们的目 标就是求出缺失数据当中，我们所关心的那一部分的后验概率。 从( 1 4 ) 式可以看出，只要联合概率p ( h ，v ，o ) f i 肇被很好地表达，那么理论上 任意方向的概率推断都可以通过一定步骤的概率边缘化( m a r g i n a l i z a t i o n ) 和归一 化( n o r m a l i z a t i o n ) 来得到的。然而，需要指出的是，联合概率是一个关于所有的量化的 值的联合函数。这样，问题中多一个数量，这个函数就多一个维度，更不用考虑这个函 数的自归一要求，所以在实际应用中，联合函数的想法是不太可取的。所以，如何有效 地表达这个联合概率密度函数，是统计建模中的一个关键问题。 1 5 概率图模型 假设所有变量的集合记作u 建模和表示p ( u ) 有很多不同的方法，其中比较极端而 4 i 可墩的炳利，方式是这样的。一种是假设u 中所有变量之问都没有条件独立性，那么只 能用列袭法来表示，比如u 中有n 个隧机变量，不访设所有的变量都是离散变量，傅个 变量各有种可能的取值，那么用一个表格记录下所有这个取值下的概率密度。但 是这样的话，表格的大小随的值的增大指数增长，是不可取的。另一个极端是假设所 有随机变：茕都相互独立，那么 p ( u ) = i i p ( ( ，j l 7 u ( 1 5 ) 这样做的好处是，有多少个变量就只需要用多少个规模不大的概率密度函数来记录它 们就可以了。但是这样做的问题是，推断任何未知的信息都与已知的信息没有关系，如 通常我们用v 来表示它的观测值，然后用v = v 来表示v 是有观测值的，但是这里在不引起混淆的情 况下，我们省略这一记法。 5 浙江大学硕士学位论文第1 章背景及意义 下式所示， p ( 驯u u ) = p ( u ) ( 1 6 ) 综合以上来说，一个合理的表示方式既要能把联合分布做有效的分解，但是又不能 完全抹去全部的概率相关性。一种有效表达所有量的联合概率的方法就是通过概率图模 型。它的假定是要建模的这些量并不完全是相关的，在给定其中一些量的时候，另一些 量之间是条件独立的。而概率图模型，就是利用这种条件独立性的存在，用一个图状的 结构来表达一个联合概率密度函数。 概率图模型包含有向的贝叶斯网络( b a y e s i a nn e t w o r k ) ，无向的马尔可夫随机 场( m a r k o vr a n d o mf i e l d ) ，以及混合的链图( c h a i n g r a p h ) 。在本文稍前一些的章节 中，我们研究有向图，在第4 章讲到用链图来表达流形假定时，我们再详细介绍链图。 有向的图模型是用有向图的节点来表示随机变量，用节点之间的有向边来表示节点 的父子关系，父节点所代表的随机变量作为子节点所代表的随机变量的先验出现。如果 我们用p a x ，c h _ ，c p x 分别表示一个节点x 的父节点集合，子节点集合，以及母节点集 合( 即子节点的其它父节点) ，那么一个图模犁所表示的联合概率密度函数可以分解为 pc u ) = p ( u p a e j ) u c u ( 1 7 ) 而它所反映的相应的条件无关关系为，当给定个节点( 如x ) 的全部父节点的值 时，x 与这个图的所有拓补排序； 1 它之游的节，_ 的并集条件无关。图1 2 腱示，一个这样 的图模型例子。 由此可以计算给定任何。个量时，另一个量的可能性，比如 p ( c = r 卜y = 丁) = 堡垒；专等= 墨x - 亳 艺p 二c 万可歹t l _ s 高t = o 5 7 5 8 ，f= 。r 。w 一) ( 1 8 ) 1 6 统计学习的现实困难 在实际应用中，统计学习面临两大现实的困难，这也是当下统计学习领域研究的主 要的方向。 6 浙江大学硕士学位论文 第1 章背景及意义 垦! 旦曼= 1 2 旦堡：卫 i1 00 0 c| p ( r ；f ip r ；t f0 80 2 t 0 20 8 图1 2 ：一个概率图模型的例子。( 来自k e v i nm u r p h y 的一个综述报告【1 】) 建模的困难 首先，由于概率分布的白归一性和正定性，要设计一个灵活的参数形式的概率分布 不足那么容易的，为此，很多时候，我们是用一些基本的分布类型去进行组合。比如 说，当不同的( x j ：) 之间是独- , - y - n 分布，并且每一个自己联接起来是一个欧氏空问中的 向量的时候，我们通常j j 高斯混合模型去爻芝模这些数据的分布。彳i 管是哪种分布类型 它们都有尚度参数化的形式，这觌定了每一个这样的分布对r 数据概率密度的表现能 力。如图1 3 ，体现厂用高耨分布的组合来建模双月数据时的难。 存这方面，近年来一l ：要有两个研究方向去解决这个问题，一个是核密度估计( k e r n e l d e n s i t ye s t i m a t i o n ) ，另一个是非参数贝叶斯( n o n p a r a m e t r i cb a y e s ) ，如图1 3 就是非 参数贝叶斯的一种，d i r i c h l e t p r o c e s s 模型的结果。本文尝试用流彤来解决这样的问题， 所以不再详纲讨论这方面的内容。 另一方面，就图模型本身来说，为了使( 1 4 ) 式的积分可积，通常要求图模型建模所 用的条件概率分布相互之间是共轭指数( c o n j u g a t ee x p o n e n t i a l ) 的，即每个条件概率分 布是指数族分布，而且每一个先验都要是似然的共轭先验。这给图模型建模的灵活性带 来了进一步的限制。 7 爨鸯 塑兰奎兰堡圭兰堡垒塞堑! 塞童苎丝耋苎 囤13 统计建模中通科的困难。时于教据在n o n - 晡v m l 的流彤上的情况，概率模型很 难去扭合所蛤的数据。图示为用d i r i c b j e t p r o c e s s m i x t u r e m o d e l ( d p m 模型) 采拟合戍 月数据的结果，d p m 模型与普通的高斯混合模型的不同之处在于，高斯成分的个数 是可变的，在计算的过程中自适应地调整，但是用它来拟合双月数据的过程显得不那 么“m a t c h “。 推断的困难 如前述，统计学习中，一个最主要的学习工具就是统计推断。但即便在图模型满足 共轭指数的条件下，当随机变量比较多时要精确计算( 14 ) 式中的积分依然是不可行 的。所以在实际应用中统计推断依赖于适当的近似推断方法。 当下对于巾等规模的问题计算比较高教的近似推断方法主要分成两个人类。一类 是基r 采样的方法，如马尔可夫链蒙特卡罗( m a r k o v c h a i n m o n t e c a r t o ) 和吉布斯采 样( g i b b ss a m p l i n g ) ，称为随机推断方法( s t o c h a s t i ci n f e r e n c e ) 。另一类则是确定性的推 断方法( d e t e r m i n i s t i ci n f e r e n c e ) ，如变分法，以及由此为基础可以得f 的并种消息传递 方法像信念传播( b e u e f p r o p a g a t i o n ) - ( e x p e c t a t i o n p r o p a g a t i o n ) ，还有本文 所基于的变分消息传j $ ( v a r i a t i o n a lm e s s a g ep a s s i n g ) a 不同的近似推断方法县有不同类型的近似和跟制。如随机推断方法对于小概率事件 t 吁优的情况，样本窄问探索能力水够，并且何时收敛不好判断，需要运行很长的时阃才 能保证足够的推断精确度。而确定性的推断方法性能依赖于对后验分巾的近似方式比 如简单的均值场变分方法是假设变分分布完全可分解，这是一种锻相的近似在实际中 常常得不到好的计算结果。而且确定性的方法通常不是一个凸优化问题( 见算法分析一 8 浙江大学硕士学位论文 节) ，而且由于参数数量大，对于初值比较敏感。 相对来说，确定性的推断方法中，目标函数和待优化的参数的定义比较明确，加入 正则项比较容易，所以在本文的第3 章中，我们针对变分法消息传递这一种方法来进行 改进。而在第4 章中，当我们把问题重新归约成一个图模型以后，则可以用上述的任何 一种合适的推断方法来进行推断。 1 7 流形学习 为了从一个更高的角度来理解流形学习，我们把它和统计建模都归入到生成式学习 这一个大类中去。所谓生成式学习，与判别式学习最大的不同在于，判别式学习只要学 习一个在给定输入以后，知道如何对输入的分类进行判别或者标定的方法就行了，并不 需要对于输入本身满足什么样的模式进行学习，比如前面所说的有监督函数学习。而在 无监督或者半监督的情况下，学习的过程依赖于对输入数据的建模。甚至从第1 4 节的角 度来看，学习的过程实质上是对于所有问题中包含的数据的建模。 丽对于数据的建模，主要有两种基本的方式，一种是统计建模，另一种是流形学 习。前者是假设数据是由一个特定的概率模型采样得到的，后者假定数据是分布在高维 空问中的一个低维流形上。如图1 7 所示。前面我们讨论了统计建模的优势和困难，现 在我们来看看什么是流形学习，以及它能在什么方面对j j ：统计建模的困难带来解决方 案。 流形学列的基本假设足洲练数据虽然存个高维空0 j j 里，比如r ”，但是实际- ：它们 并不充满整个空间，只分布在。个低维的流形朋里。比如说，训练数据都是三维的，但 是实际上，它们只分布在三维空间中的个球面上，那么他们的实际维度只有二维。如 果能在一个二维的平面上重新表示这些点，并保持一些原来的性质不变，如点与点之问 的距离，k 近邻算法的结果等，那么很多原先在高维空间中做的算法，现在可以在低维 空间巾来做。这不仪仪可以减少计算量，而鼠可以提高计算的鲁棒性。 流形( m a n i f o l d ) 是指局部同胚( h o m e o m o r p h i c ) 于一个欧氏空间的几何体。形象来 说，流形从一个局部来看，是与一个欧氏空间很像的。流形所在的外部的空间我们称为 外围空间( a m b i e n ts p a c e ) 。比如说三维空间中有一个球面的例予，这个球面就是一个流 形，它是处处同胚于一个二维的欧氏空间的，它所在的三维空间就是相应的外围空间。 9 淅江大学硕士学位论文 第1 章背景及意义 ( a ) 图14 ：生成式学习：首先对数据本身建楗。( a ) 建模数据的分布( 用高斯混合模 型) ；( b ) 建模数据所在的流彤( 用k 近邻圉) 。 定义1 1 ：流形 一个m 维的流彤是指一十l - l a u s d o r