（概率论与数理统计专业论文）图模型的结构、分解和可压缩性.pdf

6 独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工作及取得的 研究成果据我所知，除了文中特别加以标注和致谢的地方外，论文中不包含其他 人已经发表或撰写过的研究成果，也不包含为获得东北师范大学或其他教育机构 的学位或证书而使用过的材料与我一同工作的同志对本研究所做的任何贡献均 已在论文中作了明确的说明并表示谢意 学位论文作者签名：盏曼k 一 日期：塑f 竺! i 多 学位论文版权使用授权书 本学位论文作者完全了解东北师范大学有关保留、使用学位论文的规定，即： 东北师范大学有权保留并向国家有关部门或机构送交学位论文的复印件和磁盘， 允许论文被查阅和借阅。本人授权东北师范大学可以将学位论文的全部或部分内 容编入有关数据库进行检索，可以采用影印、缩印或其它复制手段保存、汇编学 位论文。 ( 保密的学位论文在解密后适用本授权书) 学位论文作者签名：互丝丝一指导教师签名：二鬣壑耸 日 期：互! ! ：! 乡日期：堑! 垒：5 学位论文作者毕业后去向： 工作单位：趟恕船 通讯地址：副研享院 6-o一 口上疗一型 一 一 4 摘要 起源于理论物理的图模型，近些年被越来越多地应用于高维数据集和复杂系 统的研究中。比如：图模型被引入到系统生物学领域，用来描述带有成千上万个 变量的基因表达数据和基因间的关联网络本文关心的图模型主要是多项图模 型、高斯图模型和条件高斯图模型。多项和高斯图模型都是用一般的无向图刻画 的，而条件高斯图模型是用标示图刻画的。 可压缩性是图模型进行结构降维和模型选择的重要方法通过指出图模型能 够压缩到的变量子集，我们可以避开不可观测或缺失的变量。而且，直接在子模 型上进行估计和检验，在很大程度上降低了对样本量的要求。 我们最关心的问题是：在多项图模型，高斯图模型和条件高斯图模型下，给 定关心的变量集彳，如何寻找包含彳的最小的变量集b ，使得模型能够压缩到b 所诱导的子模型上。a s m u s s e n 和e d w a r d s e 4 及f r y d e n b e r g 2 9 都曾指出过可压缩 性和图的分解的某种等价关系。m a d i g a n 和m o s u r s k i t 5 9 】对于可分解图上的多项 图模型，给出了一个寻找变量集b 的算法他们的算法对于可分解图上的高斯图 模型也有效但是，对于一般无向图上的图模型他们的算法无法找到极小子集b 。 在本文中，我们提出的方法将面向最一般的情况，即：对于一般无向图上的多项 和高斯图模型，寻找包含关心变量的极小可压缩子集进一步，标示图上的条件 高斯图模型也可以得到相应的处理。 本文的目的就是基于图的带有统计意义的分解，对图模型的结构给出精细的 刻画，从而进一步研究图模型的压缩降维问题。除了上述三种图模型外，我们还 会讨论层次模型的压缩性和条件高斯贝叶斯网的传播计算问题，同样的，模型结 构的精细刻画能很好地帮助我们对这两个问题进行研究。 为了研究多项图模型和高斯图模型的压缩降维，我们需要从无向图的分解入 手。这种分解结果的存在唯一性及相应的分解算法已由l e i m e r t 5 6 】给出。我们将 指出分解后的图的基本单元一素块组成的集合族，会构成树状结构一连接树， 并给出这种树状结构的多个等价刻画。利用这种结构，我们可以研究这两个模型 的压缩降维问题并且，我们提出的方法可以进一步应用到层次模型上去 对于条件高斯图模型，为了研究它的可压缩性问题，我们需要建立标示图的 历一分解和星图的分解之间的等价关系。这种关系能够帮助我们将条件高斯图模 型的可压缩性问题转化到一般无向图上进行处理。另外，我们也研究标示图的基 本单元肌一素块，与一般无向图相似，m 一素块形成的连接树同样可以被建立起 来。并且，通过引入标示图的极小m 一三角化和星图的极小三角化的关系，我们 可以将条件高斯贝叶斯网的道义图进行极小聊一三角化，从而得到一棵m 一连接 树这样得到的树能够尽可能多地体现出条件高斯贝叶斯网上的整体上的条件独 立关系，从而，利用这棵树进行概率传播计算，能有效降低计算量和复杂度。 关键词：图模型；分解；连接树；可压缩性；结构降维；极小三角化；标示图； i i n 矿 a b s t r a c t g r a p h i c a lm o d e l s ，w h i c hh a v et h e i ro r i g i ni ns t a t i s t i c a lp h y s i c s ，a r ei n c r e a s i n g l y v a l u a b l ei np r o b l e m so f h i g h e rd i m e n s i o na n d g r e a t e rc o m p l e x i t y f o re x a m p l e ，g r a p h - i c a lm o d e l sh a v eb e e ni n t r o d u c e di n t os y s t e m sb i o l o g yt oe x p l o r eg e n ee x p r e s s i o n d a t aa n dd e s c r i b eg e n ea s s o c i a t i o nn e t w o r k sw i t ht h o u s a n d so fv a r i a b l e s t h i sp a p e r m a i n l yd i s c u s sm u l t i n o m i a lg r a p h i c a lm o d e l s ，g a u s s i a ng r a p h i c a lm o d e l sa n dc o n d i t i o n a lg a u s s i a ng r a p h i c a lm o d e l s 。m u t i n o m i a la n dg a u s s i a ng r a p h i c a lm o d e l sa l e c h a r a c t e r i z e db yu n d i r e c t e dg r a p h s ，a n d 。c o n d i t i o n a lg a u s s i a ng r a p h i c a lm o d e l sa l e r e p r e s e n t e db ym a r k e dg r a p h s c o l l a p s i b i l i t yp l a y sa ni m p o r t a n tr o l ei ns t r u c t u r a lr e d u c t i o n sa n dm o d e ls e l e c t i o n s b yp o i n t i n go u tt h ec o l l a p s i b l ev a r i a b l es e t ，w e c a na v o i d m i s s i n g o ru n o b s e r v e d v a r i a b l e s e s t i m a t i n ga n dt e s t i n gd i r e c t l yo ns u b - m o d e l sc a ng r e a t l yr e d u c et h ed e - m a n df o rs a m p l es i z e t h ep r o b l e mw ec o n c e l t ia b o u ti st h a tu n d e rm u l t i n o m i a l ，g a u s s i a na n dc o n d i t i o n a lg a u s s i a ng r a p h i c a lm o d e l s ，h o wt of i n dt h em i n i m a ls e tbc o n t a i n i n go u ri n t e r e s t e ds e tas u c ht h a tt h ew h o l em o d e lc a nc o l l a p s i b l eo n t ot h es u b m o d e li n d u c e d b yb b o t ha s m u s s e n e d w a r d s 4 a n df r y d e n b e r g 2 9 p o i n t e do u ts o m er e l a t i o n s h i p b e t w e e nt h ec o l l a p s i b i l i t yo fm o d e l sa n dt h ed e c o m p o s i t i o no fg r a p h s m a d i g a na n d m o s u r s k i 5 9 】p r o p o s e da l la l g o r i t h mt of i n dt h em i n i m a ls e tb u n d e rd e c o m p o s a b l e m u l f i n o m i a lg r a p h i c a lm o d e l s ，a n dt h i sa l g o r i t h mi sa l s ov a l i df o rd e c o m p o s a b l eg a u s - s i a ng r a p h i c a lm o d e l s b u tf o rg e n e r a lu n d i r e c t e dg r a p h st h i sa l g o r i t h mc a nn o tf i n d t h em i n i m a ls e tb i nt h i sp a p e r , w eh a n d l ew i t ht h em o s tg e n e r a lc a s e f o rg e n e r a l m u l t i n o m i a la n dg a u s s i a ng r a p h i c a lm o d e l s ，w eg i v ea na l g o r i t h mt of i n dt h em i n i m a l s e tba n dg e n e r a l i z et h i sm e t h o dt oc o n d i t i o ng a u s s i a ng r a p h i c a lm o d e l s b a s i n go nt h ed e c o m p o s i t i o no fg r a p h sw i t hs t a t i s t i c a ls e n s e ，t h i sp a p e rp r e s e n t s f i n es t r u c t u r e sf o rg r a p h i c a lm o d e l s ，a n df u r t h e r m o r es t u d yt h ec o l l a p s i b i l i t yo fg r a p h i c a lm o d e l s e x c e p tf o rt h et h r e eg r a p h i c a lm o d e l sm e n t i o n e da b o v e ，w ea l s od i s c u s s i i i t h ec o l l a p s i b i l i t yo fh i e r a r c h i c a lm o d e l sa n dp r o b a b i l i t yp r o p a g a t i o nc o m p u t a t i o no f c o n d i t i o n a lg a u s s i a nb a y e s i a nn e t w o r k , a n dt h ef i n es t r u c t u r eo f m o d e l si su s e f u li n t h e s et w op r o b l e m s 。f o rd o i n gr e s e a r c ho nt h ec o l l a p s i b i l i t yo fm u l t i n o m i a la n dg a u s s i a ng r a p h i c a l m o d e l s ，w eb e g i nf r o mt h ed e c o m p o s i t i o no fu n d i r e c t e dg r a p h s t h ee x i s t e n c ea n d u n i q u e n e s so ft h i sd e c o m p o s i t i o na r eg i v e nb yl e i m e r 5 6 1 a n dt h ec o r r e s p o n d i n ga l g o r i t h mi sa l s op r o p o s e db yh i m i nt h i sp a p e r , w es h o wt h es e tc l a s sc o n s i s t i n go f p r i m eb l o c k s ，g e n e r a t e db yd e c o m p o s i t i o n s ，c a nf o r mt h ej u n c t i o nt r e es t r u c t u r e ，a n d p r o v i d es o m ee q u i v a l e n tr e p r e s e n t a t i o n sf o r t h i ss t r u c t u r e t h i s j u n c t i o nt r e es t r u c t u r e c a nh e i pu ss t u d yt h ec o l l a p s i b i l i t yo fm u l t i n o m i a la n dg a u s s i a n g r a p h i c a lm o d e l s ，a n d t h em e t h o dw ep r o p o s e dc a na l s ob ea p p l i e dt oh i e r a r c h i c a lm o d e l s f o rc o n s i d e r i n gt h ec o l l a p s i b i l i t yo fc o n d i t i o n a lg a u s s i a ng r a p h i c a lm o d e l s ，w e b u i l dt h er e l a t i o nb e t w e e nt h em - d e c o m p o s i t i o no f m a r k e dg r a p h sa n dt h ed e c o m p o s i - t i o no fs t a rg r a p h s t h i sr e l a t i o nc a nc o n v e r tt h ec o l l a p s i b i l i t yo fc o n d i t i o n a lg a u s s i a n g r a p h i c a lm o d e l st oc o r r e s p o n d i n gp r o b l e m so nu n d i r e c t e dg r a p h sf o rc o n s i d e r i n g f u r t h e r m o r e ，w es t u d ym - p r i m eb l o c k sf o rm a r k e dg r a p h sa n dc o n s t r u c taj u n c t i o n t r e eo ft h e s em - p r i m eb l o c k s ，w h i c hi ss i m i l a ra sg e n e r a lu n d i r e c t e dg r a p h s b yi n t r o d u c i n gt h er e l a t i o nb e t w e e nt h em i n i m a lm - t r i a n g u l a t i o no fm a r k e dg r a p h sa n d t h em i n i m a lt r i a n g u l a t i o no fs t a rg r a p h s ，w ec a no b t a i nam i n i m a lm - t r i a n g u l a t i o no f m o r a lg r a p h so fc o n d i t i o n a lg a u s s i a nb a y e s i a nn e t w o r k s ，a n db u i l dam - j u n c t i o nt r e e t h i st r e ec a np r o v i d et h ec o n d i t i o n a li n d e p e n d e n c er e l a t i o n sa sm u c ha sp o s s i b l ef o r c o n d i t i o n a lg a u s s i a nb a y e s i a nn e t w o r k s b yu s i n gt h i st r e e ，w ec a l le f f i c i e n t l yr e d u c e t h ec o m p l e x i t yo fp r o b a b i l i t yp r o p a g a t i o nc o m p u t a t i o n s k e yw o r d s ：g r a p h i c a lm o d e l s ；d e c o m p o s i t i o n ；j u n c t i o n st r e e s ；c o l l a p s i b i l i t y ； d i m e n s i o n a lr e d u c t i o n ；m i n i m a lt r i a n g u l a t i o n ；m a r k e dg r a p h s ； i v 丐 - ： ， 目录 中文摘要 i 英文摘要i i i 第一章引论 1 1 1 绪论1 1 2 图模型的发展历史与现状 2 1 3 图模型中可压缩性的研究历史与现状5 1 4 本文的结构安排 7 第二章本文涉及的基本概念 9 2 1 图的一些基本概念9 2 1 1 基本概念j 9 2 1 2 弦图1 4 2 2 统计中的一些基本概念2 1 2 3 本文涉及的统计模型2 2 第三章树状结构2 5 3 1 连接树2 5 3 2 分离树3 3 3 3 扛分离树3 5 第四章一般无向图的结构3 7 4 1 一般无向图的基本单元素块3 7 4 2 一般无向图分解结果的存在唯一性4 0 v 4 3 一般无向图分解算法4 5 4 4 一般无向图的二级结构5 5 4 5 讨论5 7 第五章多项与高斯图模型的可压缩性6 4 5 1 引言6 4 5 2 多项和高斯图模型的可压缩性6 5 5 3 多项图模型和高斯图模型的可压缩性算法6 5 5 4 讨论7 2 第六章标示图的分解与结构7 8 6 1 标示图的m 一分解7 8 6 2 标示图的m 一分解结果的存在唯一性7 9 6 3 标示图和星图的关系8 2 6 4 ，印一分解子的刻画8 4 6 5 讨论8 7 第七章条件高斯图模型的可压缩性9 1 7 1 引言9 1 7 2 条件高斯图模型的可压缩性9 2 7 3 讨论9 4 结论9 9 参考文献1 0 1 在学期间公开发表论文及著作情况1 0 8 v i 致谢1 0 9 ， 东北师范大学博士学位论文 第一章引论 1 1 绪论 科学主要是建立模型，并不是试图去说明而且也很少去解释什么。这里所说的模型是指一种 数学结构，再加上某种特定语言解释来描述所观察到得现象建立这样一种数学结构的理由惟一 而且明确地由人们所期待的它的机能来决定川 冯诺伊曼( y o nn e u m a n n ) 从人类诞生那一天起，人类的发展与进步始终离不开对现实世界的认知和理 解当一些自然现象出现在人们面前，当一些实践活动需要人们去完成，如何描 述这些现象和活动便成为了人们所要面对的首要任务。在这种描述的过程中，通 过对现象的抽象特征加以提取，使得人类能够超越经验地建立起普适性的和叮重 复性的科学与知识。从计数到测量，从绘画到文字。古人通过对现实世界所进行 的抽象描述推动了科学的进步和社会的发展。 随着时间的推移，一些现象被加以抽象的总结，成为人类科学宝库的一部分。 而这种由表象升华为科学知识的过程，也是人类对现象进行认知和建模的过程。 通过深入研究现象的抽象特征，根据背景提出公理化的假设，然后人们就可以在 假设之下对模型进行演绎和推理。无数的古圣先贤通过相似的建模过程掌握了大 量的科学知识。从泰利士遥望星空，到用抽象的语言描述几何学，从阿基米德掉 进澡盆，到浮力定律的产生，从伽利略观测木星，到日心说的证实，从牛顿见到 苹果落地，到自然哲学的数学原理的诞生，这些都体现了先贤们对自然现象 的抽象建模能力当然，随着人类认知的进步，以前认为足公理化的假设和规律 在某些情况下也会失效，比如：牛顿力学定律在微观时就失效了。但是，新的知 识，新的规律依然来源于人类对现实世界的认知与建模。 随着社会的进步和科学的发展，人们开始主动地收集并整理来自现实世界 的各种信息和数据，并通过对数据的建模来刻画某些自然现象或社会现象尤其 东北师范大学博士学位论文 近年来，伴随着科学技术的进步以及人类探索未知世界步伐的加快，出现了越来 越多的高维数据集，比如：微阵列数据，单倍型数据，图像数据，文档词频数据 等。这些数据的维度通常可以达到成百上千维，甚至更高。由于这些高维数据存 在的普遍性，如何对这些数据进行建模成为了科学研究的首要问题。在高维数据 集中，协变量之间的条件独立关系是这种数据集带有的重要信息，而图模型作为 利用图上的分离性质来描述变量间的条件独立关系的统计模型，能直观地描述复 杂高维数据的内在结构。虽然图模型描述的是整体上的条件独立关系，但是在很 多情况下，我们依然可以利用图的分解与结构，分而治之地在局部的小模型上研 究我们关心的问题，所以从某种程度上来说图模型是一种结合了整体论与还原论 的统计模型 1 2 图模型的发展历史与现状 图模型的一个主要起源是理论物理。假设整个粒子系统可以用一个无向图 表示出来，粒子间相邻表示有交互关系，那么整个系统的能量可以表示成粒子 间交互关系的加和，其中的思想可以追溯到g i b b s t 3 8 3 ( 1 9 0 2 ) 。另一个起源来自 w r i g h t t 9 2 9 3 , 9 4 1 ( 1 9 2 1 ，1 9 2 3 ，1 9 3 4 ) ，他在有向图中使用路径分析的方法( p a t ha n a l y s i s ) 米研究遗传性质。w r i g h t 的方法被w o l d 引1 ( 1 9 5 4 ) 和b l a l o c k l l l l ( 1 9 7 1 ) 所借 鉴，应用于经济和社会科学的研究中。图模型的第三个起源来自列联表中随机变 量之间的交互作用，可以参考d a r r o c h 等人【1 5 】( 1 9 8 0 ) 的这篇奠基性文章。这些 工作为图模型的发展奠定了良好基础。 随着时间的推移，图模型的理论与方法有了很大地拓展，一些经典的著作相 继问世n e a p o l i t a n 6 6 】( 1 9 9 0 ) 基于图模型来研究概率专家系统，并介绍了不确定 性推断和因果网络的基础。w h i t t a k e r 8 9 1 ( 1 9 9 0 ) 的书把论述重点放在了图模型的 思想方法及各种例子，是一本较好的入门书籍。l a u r i t z e n 5 2 1 ( 1 9 9 6 ) 详细地介绍了 图模型的数学基础，包括图论的内容和条件独立及马氏性方面的理论，并且，深 入地探讨了各种图模型的统计方法，包括纯离散变量的图模型，纯连续变量的图 模型以及混合变量的图模型。c o w e l l ”1 ( 1 9 9 9 ) 主要介绍了贝叶斯网的思想，结构 和算法，并涵盖了概率推理，统计推断和结构学习等内容。e w a r d s 2 6 1 ( 2 0 0 0 ) 这本 2 东北师范大学博士学位论文 书的主要目的是简明地介绍图模型的应用，书中着重考虑了用来处理混合数据的 图模型，并介绍了可以使用m 1 m 程序进行处理的各种问题。d r t o n 等 2 4 1 ( 2 0 0 9 ) 以代数几何为工具对列联表中的图模型涉及的统计问题进行深入的探讨 在发展初期，图模型所研究的对象一般是对数线性模型和高斯模型，也就是 说一种是纯离散变量模型，一种是纯连续变量模型关于对数线性模型的经典 文章请参考b i r c h c 7 1 ( 1 9 6 3 ) 和g o o d m a n t 4 1 4 2 ( 1 9 7 0 ，1 9 7 1 ) 关于高斯模型，可以参 看d e m p s t e r t 2 0 1 ( 1 9 7 2 ) 的协方差选择模型的文章，和w e r m u t h 8 5 】( 1 9 7 6 ) 的研究列 联表中的模型与协方差选择模型两者之间关系的文章条件高斯图模型作为一 种既有离散变量又有连续变量的混合模型是由l a u f i t z e n 和w e r m u t h 5 4 】( 19 8 9 ) 引 入的在这篇文章中，作者主要介绍了条件高斯分布和条件高斯回归以及条件 高斯图模型中的马氏性有关条件高斯图模型的潜在应用可以参考w e r m u t h 和 l a u f i t z e n t 8 7 1 ( 1 9 9 0 ) 的文章。e w a r d s 2 5 1 ( 19 9 0 ) 则进一步将条件高斯图模型推广到 层次模型中去。关于条件高斯分布的统计性质，可以参考o l k i n 和 f a t e 6 8 】( 1 9 6 i ) 关于离散图模型中的极大似然估计，可以用d a r r o c h 和r a t c l i f r 16 ( 1 9 7 2 ) 迭代比例 尺度算法进行处理，相似地，对于高斯图模型，可以用s p e e d 和k i i v e f i t 7 7 】( 1 9 8 6 ) 中提出的算法来处理。关于既有离散又有连续变量的条件高斯图模型的估计，可 以参考f r y d e n b e r g 和l a u f i t z e n t 引 ( 19 8 9 ) 。在这篇文章中，作者利用模型的分解用 分而治之的方法研究了模型的极大似然估计。特别地，对于可分解模型，似然估。 计有显式解。对于一般的情况，可以参考f r y d e n b e r g 和e d w a r d s 3 0 1 ，这篇文章给 出了一个修改了的迭代比例尺度算法，通过这个算法可以给出正规指数族的极大 似然估计，这种方法可以应用到条件高斯图模型上。 条件独立性关系的研究是图模型的理论基础。有关这方面经典的文献，可 以参阅d a w i d 1 8 - 1 9 1 ( 1 9 7 9 ，1 9 8 0 ) 。在文章1 1 8 中，作者展示r 条件独立关系对于 统计推断的帮助，并对统计的多个分支中条件独立关系所扮演的角色做了介绍。 另外，s t u d e n 夕 7 8 ，7 9 3 ( 1 9 8 9 ，1 9 9 3 ) 使用半图来研究条件独立性。g e i g e r 和p e a r l t 3 3 】 ( 1 9 9 3 ) 系统性地研究了条件独立关系间的逻辑蕴涵c o x 和w e r m u t h 1 4 】( 1 9 9 3 ) 则 讨论了如何通过图来解释条件独立性假设。a n d e r s s o n 和p e r l m a n t 3 ( 1 9 9 3 ) 在多元 高斯模型中通过某种空间格子来讨论条件独立关系。条件独立性限制和图中性质 的精确关系在a n d e r s s o n 等人 1 】( 1 9 9 5 ) 有所讨论 3 东北师范大学博士学位论文 随着图模型的发展，统计学家们提出了各种各样的图结构，如：无向图，有向 无圈图( d i r e c t e da c y c l i cg r a p h s ) ，标示图( m a r k e dg r a p h s ) ，链图( c h a i ng r a p h s ) 等等。 使用这些图的目的是基于不同的数据背景，对变量间的条件独立关系进行建模。 在各个图模型下，通过图上的某些性质，比如：分离或是少边，可以读出变量集间 的条件独立关系，这就是图模型上的马氏性，也是图模型最重要的性质s p e e d 7 6 ( 1 9 7 9 ) 给出了离散图模型中的h a m m e r s l e y _ c l i f f o r d 定理，这个定理告诉我们 图模型上的成对马氏性等价于概率密度可以表示成图上所有团函数的乘积。进一 步，条件高斯图模型中的相应定理由l a u r i t z e n 和w e r m u t h 5 4 1 ( 1 9 8 9 ) 给出与马 氏性有关的问题中，马氏等价性的研究是一个重要的问题。若两个图有相同的条 件独立结构，称这两个图是等价的。链图( c h a i ng r a p h s ) 作为无向图模型和贝叶斯 网的一种推广，其马氏等价性是由f r y d e n b e r g t 2 8 3 ( 1 9 9 0 ) 的这篇经典文章给出，进 一步的结果和工作可以参考a n d e r s s o n 等人【2 1 ( 1 9 9 7 ) 。此外，k o s t e r 5 0 ( 1 9 9 6 ) 研 究了相惠图( r e c i p r o c a lg r a p h s ) 上的马氏性，这种图是链图的推广，可以用来研究 回馈模型这种模型与g o l d b e r g e r 和d u n c a n 3 9 1 ( 1 9 7 3 ) ，j 6 r e s k o g t 4 7 3 ( 1 9 7 7 ) 研究的 结构方程模型有着密切关系 可压缩性是图模型中的重要概念，通过指出图模型能够压缩到的变量子集， 我们可以避开不可观测或是缺失的变量。而且，直接在子模型上进行估计检验， 在很大程度上降低了对样本量的要求。所以，在图模型中考察可压缩性能够帮我 们提高估计的精度和检验的效率根据目的的不同，有各种各样的可压缩性，如： 参数可压缩性，检验可压缩性，条件独立可压缩性，模型可压缩性，估计可压缩 性。本文主要考虑的是估计可压缩性。有关图模型中可压缩性的经典文章，请参 看a s m u s s e n 和e w a r d s 4 1 ( 19 8 3 ) ，f r y d e n b e r g 2 9 1 ( 19 9 0 ) 。 贝叶斯网可以对因果关系给出很自然地表示，所以一直以来统计学家和哲学 家对贝叶斯网推崇备至。除了贝叶斯网上的因果推断问题( 参见p e a r l 7 们，1 9 9 5 ) 外，贝叶斯网上的概率传播计算也是一个比较重要的课题。这种计算方法是通过 利用贝叶斯网上整体的条件独立关系，来达到降低计算量并提高计算速度和精 度的方法。离散贝叶斯网上的传播计算参见l a u r i t z e n 和s p i e g e l h a l t e r 5 3 】( 1 9 8 8 ) 。 关于连续贝叶斯网的研究参见s h a c h t e r 和k e n l e y 7 4 1 ( 1 9 8 9 ) 有关条件高斯贝叶 斯网的传播计算发起于l a u r i t z e n 5 ( 1 9 9 2 ) ，但是l a u r i t z e n 给出的计算过程比较 4 东北师范大学博士学位论文 复杂，而且数值结果并不稳定随后，由c o w e l l 1 2 1 ( 2 0 0 5 ) 给出了条件高斯贝叶 斯网上一种新的传播计算方法他的方法主要是基于消去树( e l i m i n a t i o nt r e e s ) ， 并充分运用了s h a c h t e r 和k e n l e y t 7 4 1 ( 1 9 8 9 ) 中的箭头翻转操作，这个操作被称为 e x c h a n g e 操作m a d s e n 6 1 1 ( 2 0 0 8 ) 也研究了条件高斯贝叶斯网上的概率传播，他 的方法是基于强连接树( s t r o n gj u n c t i o nt r e e s ) 的，并将e x c h a n g e 操作与惰性传播 ( m a d s e n 【6 0 】，2 0 0 6 ) 相结合 近些年来，统计学家们已经不再局限于给定图模型后，对关心问题进行统计 推断，而是从数据出发进行模型选择，学习出相应的图模型结构。相关文献可参阅 s c h i f e r 和s t r i m m e r l 7 3 ( 2 0 0 5 ) ，m e i n s h a u s e n 和b f i h l m a n n t 6 4 ( 2 0 0 6 ) ，f r i e d m a n 等【2 7 】 ( 2 0 0 7 ) ，k a l i s c h 和b f i h l m a n n t 4 8 1 ( 2 0 0 7 ) 及x i e 和g e n g 9 5 9 6 】( 2 0 0 6 ，2 0 0 8 ) s c h 萏f e r 和s t r i m m e r 使用经验贝叶斯的方法学习高斯图模型的结构，并将结果用于基因 网络的学习。m e i n s h a u s e n 和b f i h l m a n n 的文章是基于高斯图模型使用l a s s o 进行 结构学习。f r i e d m a n 等人的文章针对图模型的结构学习给出了g r a p h i c a ll a s s o 方 法。k a l i s c h 和b f i h h n a n n 使用p c 算法学习高斯贝叶斯网的结构，而x i e 和g e n g 的文章则是基于分解的想法研究贝叶斯网的结构学习。 1 3 图模型中可压缩性的研究历史与现状 可压缩性方法是图模型中的一个重要方法，它意味着边缘化掉某些变量后统 计推断的结果不会发生改变。所以，通过对原模型进行压缩，我们可以在较小的 子模型上进行统计推断，有利于我们避开不可观测变量和缺失的变量。进一步， 如果模型的估计可压缩性成立的话，直接在子模型上进行估计检验，能够帮我们 提高估计的精度和检验的效率。事实上，在子模型上进行推断，其结果与原模型 的推断可能不同或是根本就是相反的，这一现象就是y u l e s i m p s o n 悖论( y u l e 8 3 】， 1 9 0 3 ，s i m p s o n 7 5 1 ，1 9 5 1 ) 。所以，有关可压缩性能够成立的条件的研究是非常重要 的 a s m u s s e n 和e w a r d s 4 1 ( 1 9 8 3 ) 的文章研究的是列联表中层次对数线性模型的 可压缩性，并指出了对于层次模型来说模型的可压缩性等价于估计的可压缩性 5 东北师范大学博士学位论文 进一步，作者建立了层次模型中的可压缩性与关联图的某种等价关系，即：层次 模型三能够压缩到变量集b 上等价于b 外的每个连通分支的边界集在模型三的 某个生成元中层次模型的可压缩性的结论可以推广到多项和高斯图模型中，相 似地，我们有：多项或高斯图模型能够压缩到变量集b 上等价于b 外的每个连通 分支的边界集是完全的。所以，多项和高斯图模型的可压缩性完全可以用图上的 方法和理论进行判断 m a d i g a n 和m o s u r s k i 5 9 】基于文章【4 1 ，研究了可分解多项图模型的可压缩性， 并给出算法s h a r 用来寻找给定关心变量集4 后可分解多项图模型所能压缩到 的最小变量集。那么对于关心变量集彳的统计推断问题可以在这个最小变量集 诱导的子模型进行考虑。作者利用可分解图是一定可以找到单纯点这个性质，在 算法中逐步的寻找并移除单纯点，这样在保证可压缩性的基础上，完成寻找最小 变量集的过程m a d i g a n 和m o s u r s k i 的这个算法非常优美而且计算速度很快，但 是它非常依赖于可分解图的性质，即一定存在单纯点，而对于一般的图这个性质 并不恒成立，也就是说他们的算法不能应用于非可分解的多项图模型。一个很自 然的问题是：对于一般的无向图的多项、高斯图模型，是否能给出一个算法用来 寻找给定关心变量集彳后图模型所能压缩到得最小变量集? f r y d e n b e r g 2 9 】( 1 9 9 0 ) 研究了条件高斯图模型的可压缩性，并且指出模型的可 压缩性的多个等价条件，估计的可压缩性就是等价条件之一与层次模型一样， 作者指出了呵压缩性与图的某种等价关系：条件高斯图模型能够压缩到b 上等价 于b 外的每个连通分支的边界集完全并且每个连通分支要么都是连续变量要么 连通分支的边界集都是离散变量。相似的问题依然存在：对于条件高斯图模型， 是否能给出一个算法用来寻找给定关心变量集彳后图模型所能压缩到得最小变 量集? 在多项、高斯和条件高斯图模型下，如何寻找可压缩最小变量集正是本文 所研究的最主要问题 、 d i d c l c z 和e d w a r d s 2 1 】( 2 0 0 4 ) 研究了条件高斯回归模型的可压缩性。通过作 者所定义的可压缩性，有关高维的条件高斯回归的问题可以在较低维的条件高斯 回归模型中考虑，其中这个较低维的模型对应着原图的某个子图。进一步，作者 给出了在图上判断町压缩性的方法。 k i m 和k i m 4 9 】( 2 0 0 6 ) 研究了列联表中贝叶斯网的估计的可压缩性，并给出 6 东北师范大学博士学位论文 了判断可压缩性的充分必要条件通过这个充要条件，模型可压缩性的判断可以 利用图的结构来完成他们引入了逐次移除的方法，并证明了列联表上的贝叶斯 网能够压缩到变量集b 等价于b 外的变量可以逐次移除 x i e 和g e n g e 9 7 1 ( 2 0 0 9 ) 延续了贝叶斯网上可压缩性的工作并研究了三种可压 缩性：估计可压缩性、条件独立可压缩性和模型的可压缩性作者考察了k i m 和 k i m t 4 9 】提出的估计可压缩性的性质，并在贝叶斯网的马氏等价类上做了进一步 地推广然后，他们讨论了条件独立可压缩性和模型可压缩性的成立条件并研究 了三种可压缩性之间的关系作者指出：与层次模型和条件高斯图模型不同，贝 叶斯网中的估计的可压缩性仅是模型可压缩性的充分条件，并进一步给出模型可 压缩性的充分必要条件最后，作者给出了一个算法用来寻找给定关心点集后贝 叶斯网能够模型压缩到得最小变量集。 另外，有关参数可压缩性的文章请参考b i s h o p t 8 】( 1 9 7 1 ) ，w h i t t e m o r e 9 0 】( 1 9 7 8 ) ， w e r m u t h 8 6 1 ( 1 9 8 7 ) ，g e n g 3 5 1 ( 1 9 9 2 ) 进一步的工作还有：g u o 和g e n g 4 3 】( 1 9 9 5 ) 考虑了l o g i s t i c 回归参数的可压缩性，g u o 等【删( 2 0 0 1 ) 研究了o d d s 比的可压缩 性，g e n g 等【3 7 1 ( 2 0 0 2 ) 研