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

一? | j -独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工作及取得的 研究成果据我所知，除了文中特别加以标注和致谢的地方外，论文中不包含其 他人已经发表或撰写过的研究成果，也不包含为获得东北师范大学或其他教育机 构的学位或证书而使用过的材料与我一同工作的同志对本研究所做的任何贡献 均已在论文中作了明确的说明并表示谢意 学位论文作者签名：型l 盘! 经一日期：竺丝：! ：! 学位论文版权使用授权书 本学位论文作者完全了解东北师范大学有关保留、使用学位论文的规定，即： 东北师范大学有权保留并向国家有关部门或机构送交学位论文的复印件和磁盘， 允许论文被查阅和借阅本人授权东北师范大学可以将学位论文的全部或部分内 容编入有关数据库进行检索，可以采用影印、缩印或其它复制手段保存、汇编学 位论文 ( 保密的学位论文在解密后适用本授权书) 学位论文作者签名：判盘! 銎 日 指导教师签名：搬 学位论文作者毕业后去向： 工作单位： 通讯地址： 电话： 邮编： i j i 统 为 中 进而提高效率 随着各个应用领域科学技术的改善以及计算机技术的飞速发展，高维数据频 繁出现，在这种情况下如何降低变量维数和降低问题的复杂程度则成为一个非常 现实、非常重要、非常迫切的问题分解性和可压缩性研究为缓解这个问题提供 了一种非常有竞争力的途径可压缩性指的是通过去除与问题无关的一些变量把 原来的全局问题转化成局部问题，简单说来就是“取其精华，去其糟粕”；而所 谓的分解性，则指的是把一个全局的问题转化成一些局部问题并通过整合这些局 部问题的结果来解决原来的全局问题，简单说来就是。分而治之”在图模型研 究中，分解性和可压缩性是非常重要的研究课题通过分析图模型的交互图就可 以非常方便地判断模型是否具有相应的分解性和可压缩性，这使得图论中的很多 有效的方法能够为模型中的各种问题提供强有力的支持进而提高解决问题的效 率分解性和可压缩性是非常朴素的思想，它们在图模型的统计推断和结构学习 问题中应用非常广泛，根据所研究问题的不同可以定义不同方面的分解性和可压 缩性至今为止已经出现了很多关于图模型的分解性和可压缩性的优秀的研究成 果，但是尽管如此，随着应用学科中的新问题和新目的的不断产生，分解性和可 压缩性的研究也在不断的更新和延续 本文围绕图模型中的分解性和可压缩性这个重点对以下几个题目做了详细 地研究：贝叶斯网模型的结构学习中的分解性研究、无向图模型的检验的分解性 和可压缩性研究、无向图模型的条件模型的可压缩性研究在贝叶斯网模型的结 构学习中，本文的第三章在基于d 分离树的分解的结构学习方法的基础上，提 出了极小d 分离树的概念并详细描述了它的性质以及构造方法；利用这个极小 d 分离树，我们可以在基于d 分离树的分解的结构学习问题中获得最大的效率 i - i 性进行了 种用交互 的条件模 些等价的 结构学习 - l a b s t r a c t f o rn e a r l yt h r e ed e c a d e s ，g r a p h i c a lm o d e l sh a v eb e e nm o r ea n dm o r ew i d e l y u s e di ns o m ea r e a s ，s u c ha sb i o - i n f o r m a t i c s ，e c o n o m i c s ，s o c i o l o g y , c a u s a li n f e r - e n c e ，a r t i f i c i a li n t e l l i g e n c ea n ds t a t i s t i c s e s p e c i a l l yi ns t a t i s t i c s ，g r a p h i c a lm o d e l s a r eu s e dm o s tw i d e l y u s i n gg r a p h i c a lm o d e l sn o to n l ya l l o w st h ec o m p l e xr e l a - t i o n s h i p sa m o n gr a n d o mv a r i a b l e st ob ed e s c r i b e dv i s u a l l y , b u ta l s oa l l o w ss o m e s t a t i s t i c a lp r o b l e m st ob et r a n s f o r m e di n t os o m ec o r r e s p o n d i n gg r a p h - r e l a t e d p r o b l e m s ，w h i c hc a ns i m p l i f yt h es t a t i s t i c a lp r o b l e m st oac e r t a i ne x t e n t w i t hi m p r o v e m e n to fs c i e n c ea n dt e c h n o l o g yi nv a r i o u sa p p l i c a t i o na r e a s a n dr a p i dd e v e l o p m e n to fc o m p u t e rt e c h n o l o g y , t h e r ea r em o r ea n dm o r eh i g h - d i m e n s i o n a ld a t a i nt h i sc a s e ，h o wt or e d u c et h ev a r i a b l ed i m e n s i o n sa n dt h e c o m p l e x i t yo ft h ep r o b l e m sh a sb e c o m eav e r yp r a c t i c a l ，i m p o r t a n ta n du r g e n t p r o b l e m s t u d i e so fd e c o m p o s i t i o na n dc o l l a p s i b i l i t yp r o v i d ev e r yc o m p e t i t i v e w a y st ot h i sp r o b l e m c o l l a p s i b i l i t yr e f e r st ot r a n s f o r m i n gag l o b a lp r o b l e mi n t o ac o r r e s p o n d i n gl o c a lp r o b l e mb yi g n o r i n gt h eu n r e l a t e dv a r i b l e s ，t h a ti s ，“a b s o r b - i n gt h ee s s e n c ea n dd i s c a r d i n gt h ed r ，o s s ”d e c o m p o s i t i o nr e f e r st od e c o m p o s i n ga g l o b a lp r o b l e mi n t os o m ec o r r e s p o n d i n gl o c a lp r o b l e m sa n dt h e ni n t e g r a t i n gt h e r e s u l t so ft h e s el o c a lp r o b l e m st os o l v et h eo r i g i n a lg l o b a lp r o b l e m ，t h a ti s ，“d i v i d - i n ga n dc o n q u e r i n g f o rg 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 na n dc o l l a p s i b i l i t ya r e v e r yi m p o r t a n tr e s e a r c ht o p i c s ，a n di n t e r a c t i o ng r a p hc a nb eu s e dt od e t e r m i n e w h e t h e rap r o b l e mc a nb ed e c o m p o s e do rc o l l a p s e d ，w h i c hi n d i c a t e st h a tm a n y e f f e c t i v em e t h o d si ng r a p ht h e o r yc a np r o v i d es t r o n gs u p p o r tf o rt r e a t m e n to f t h ep r o b l e m d c c o m p o s i t i o na n dc o l l a p s i b i l i t ya r ev e r yi n o r n a t ea n db a s i ci d e a s ，w h i c ha r e w i d e l yu s e di ns t a t i s t i c a li n f e r e n c eo rs t r u c t u r a ll e a r n i n gp r o b l e m so fg r a p h i c a l m o d e l s d e c o m p o s i t i o na n dc o l l a p s i b i h t yc a nb ed e f i n e df r o ms e v e r a ld i f f e r e n t a n g l e sf o rd i f f e r e n tp u r p o s e s ，a n dt h e r eh a v eb e e nm a n yg o o dr e s u l t sa b o u td e - c o m p o s i t i o na n dc o l l a p s i b i l i t y h o w e v e r ，w i t ht h ep r o d u c t i o no fn e wi s s u e sa n d i i i i p u r p o s e si na p p l i c a t i o na r e a s ，t h es t u d yo fd e c o m p o s i t i o na n dc o l l a p s i b i l i t y a l s oh a sb e e nd e v e l o p i n gr a p i d l y t h ep r e s e n tp a p e rc o n c e n t r a t e so nt h ef o l l o w i n gt h r e e t o p i c si nd e t a i la r o u n d t h es p e c i f i ct h e m eo fd e c o m p o s i t i o na n dc o l l a p s i b i l i t yi ng 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 nf o rs t r u c t u r a ll e a r n i n go fb a y e s i a nn e t w o r k s ，c o l l a p s i b i l i t ya n dd e - c o m p o s i t i o no fl i k e l i h o o dr a t i ot e s t si ng r a p h i c a lm o d e l so fu n d i r e c t e dg r a p h s ， a n d c o l l a p s i b i l i t yi nc o n d i t i o n a lm o d e l so fg r a p h i c a lm o d e l so fu n d i r e c t e dg r a p h s f o rs t r u c t u r a ll e a r n i n go fab a y e s i a nn e t w o r k ，s e c t i o n3p r o p o s e dad e f i n i t i o n o fm i n i m a ld - s e p a r a t i o nt r e et oi m p r o v et h e e f f i c i e n c yo ft h es t r u c t u r a ll e a r n i n g ， a n dd i s c u s s e dc h a r a c t e r i z a t i o na n dc o n s t r u c t i o no fam i n i m a ld - s e p a r a t i o nt r e e i nd e t a i l u s i n gt h ec o n s t r u c t e dm i n i m a ld s e p a r a t i o nt r e e ，w ec o u l do b t a i na m a x i m a le f f i c i e n c yi nt h ep r o c e s so ft h ed e c o m p o s i t i o na p p r o a c ho fs t r u c t u r a l l e a r n i n gb a s e do nad s e p a r a t i o nt r e e i ns e c t i o n4 w ed i s c u s s e dc o l l a p s i b i l - i t ya n dd e c o m p o s i t i o no fl i k e l i h o o dr a t i ot e s t si ng r a p h i c a lm o d e l so fu n d i r e c t e d g r a p h s ，a n do b t a i n e ds o m ef u r t h e rr e s u l t s w ep r o p o s e daw e a k e rs u f f i c i e n tc o n - d i t i o nf o rd e t e r m i n i n gt h ec o l l a p s i b i l i t yi nt h ec o r r e s p o n d i n gi n t e r a c t i o ng r a p h s ， a n dp r o p o s e dan e ww a yt od e c o m p o s et e s ts t a t i s t i c i ns e c t i o n5 ，w ed i s c u s s e d c o l l a p s i b i l i t yi nc o n d i t i o n a lm o d e l so fg r a p h i c a lm o d e l so fu n d i r e c t e dg r a p h sf o r p u r e l yd i s c r e t ea n dp u r e l yc o n t i n u o u sc a s e s w ei n t r o d u c e dt w od i f f e r e n tk i n d s o fc o l l a p s i b i l i t yi nt h ec o n d i t i o n a lm o d e l s ，p r o v e dt h ee q u i v a l e n c yb e t w e e nt w o k i n d so fc o l l a p s i b i l i t ya n dp r o p o s e dan e c e s s a r ya n ds u f f i c i e n tc o n d i t i o nf o rt h e e q u i v a l e n tc o l l a p s i b i l i t yi nt e r mo ft h ec o r r e s p o n d i n gi n t e r a c t i o ng r a p h k e yw o r d s ：b a y e s i a nn e t w o r k ；c o l l a p s i b i l i t y ；c o n d i t i o n a lm o d e l ；d e c o m - p o s i t i o n ；d - s e p a r a t i o nt r e e ；g r a p h i c a lm o d e l ；s t r u c t u r a ll e a r n i n g i v ， k r ， 一 ( 砖 目录 中文摘要一二 i 英文摘要i i i 第一章引言 1 1 1 图模型简介 2 1 1 1 图模型的起源和发展 2 1 1 2 图模型的分类 3 1 1 3 马尔可夫性 4 1 1 4 图模型的统计推断 4 1 1 5 图模型的结构学习 5 1 2 分解性和可压缩性 7 1 2 1 图模型的统计推断中的分解性和可压缩性 7 1 2 2 条件图模型中的可压缩性1 0 1 2 3 图模型的结构学习中的分解性 1 l 1 3 本文的主要工作1 3 第二章基本概念和结论1 6 2 1 无向图及相关概念1 6 2 1 1 无向图1 6 2 1 2 分离树和分解树1 9 2 1 3 弦图和团树2 0 2 1 4 素块树 2 2 v 弋 2 2 有向无圈图及相关概念2 3 2 2 1 有向无圈图2 3 2 2 2d 一分离树：2 5 2 3 马尔可夫性 2 6 2 3 1 条件独立性2 6 2 3 2 无向图中的马尔可夫性 2 7 2 3 3 有向无圈图中的马尔可夫性 2 9 2 4 概率图模型 3 0 2 4 1 无向概率图模型3 0 2 4 2 贝叶斯网3 1 2 5 统计图模型3 1 2 5 1 列联表3 1 2 5 2 离散无向图模型3 2 2 5 3 离散层次模型3 3 2 5 4 连续无向图模型3 4 2 5 5 混合无向图模型3 5 2 5 6 贝叶斯网模型 3 6 2 6 图模型的统计推断3 6 2 6 1 极大似然估计3 7 2 6 2 似然比检验3 9 2 7 图模型的结构学习4 0 v i - a l 弋 t 2 8 图模型的分解性和可压缩性 4 2 2 8 1 模型的可压缩性4 2 2 8 2 极大似然估计的分解性和可压缩性 4 3 2 8 3 似然比检验的分解性和可压缩性4 5 2 8 4 条件图模型的模型可压缩性4 6 2 8 5 条件图模型的估计可压缩性 4 7 2 8 6 结构学习的分解性4 7 第三章基于极小d - 分离树的分解的贝叶斯网模型结构学习 4 9 3 1 极小d 一分离树4 9 3 2 极小d 一分离树的性质5 1 3 3 极小分离树与极小树分解5 6 3 4 小结一 6 0 第四章似然比检验的可压缩性和分解性6 2 4 1 似然比检验的可压缩性6 2 4 2 似然比检验的分解性6 7 4 3 似然比检验的分解性和可压缩性的优点6 8 4 4 模拟研究6 9 4 4 1 计算检验统计量的四种方法 6 9 4 4 2 模拟设计7 0 4 4 3 模拟结果7 1 4 5 一个实际例子7 5 v i i 4 6 小结 第五章条件图模型中的可压缩性 。5 1 离散的条件无向图模型中的可压缩性 5 2 连续的条件无向图模型中的可压缩性 5 3 小结 第六章总结与讨论 参考文献 在学期间公开发表论文及著作情况 致谢 v i i i t + j 囊 俺 蔼 蔼 盯 g ； | 量 埘 ( _ t 也l 腔 ，| ，p 第一章引言 近些年来，图表示的方法在生物信息学、经济学、社会学、因果推断人工 智能和统计学等领域中得到了越来越广泛的应用【2 ，6 , 5 ，3 3 , 6 0 ，6 1 , 6 6 ，5 1 】。特别是在统 计学中，统计学家们常常通过图来直接建立各种统计模型，也就是所谓的图模型 【5 1 | 这种建立统计模型的方法不仅能使随机变量之间错综复杂的关系得以直观 地描述，而且可以使模型中的很多统计问题转化成与图有关的问题这样一来， 图论中的很多成熟理论和有效方法就可以直接为统计问题服务，使得统计问题的 处理变得更加方便 随着各个应用领域科学技术的改善以及计算机技术的飞速发展，人们从实 际问题中所获取的数据在形式和规模上都有大幅度改变，很多数据都有向高维 和海量方向发展的趋势尤其是在生物信息学、经济学和社会学等学科中，基因 芯片微阵列数据、图像数据以及文本数据等数据中涉及的变量特别多，常常以千 计、万计或者更多因此，对于一些传统的针对于变量数较小的情况的统计方法 来说，分析和处理这样的数据往往需要消耗大量的时间，并且常常不能得到令人 满意的结果在这种情况下，如何降低变量维数和降低问题的复杂程度成为一个 非常现实和迫切的问题 分解性和可压缩性研究常常能够为缓解这个问题而提供一种非常有竞争力 的途径在统计学中，所谓的可压缩性指的是通过去除与问题无关的一些变量把 一个全局的统计问题在不损失任何信息的条件下转化成一个只与局部的一些变 量有关的统计问题，简单说来就是“取其精华，去其糟粕”；而所谓的分解性，则 是指把一个全局的统计问题在不损失任何信息的条件下转化成一些局部的统计 问题并通过整合这些局部的统计问题的结果来解决原来的全局的统计问题，简单 说来就是“分而治之”利用分解性和可压缩性，一个涉及变量数较大的统计问 题就可以转化成一个或若干个只涉及较少变量的局部问题，由此变量的维数和问 题的复杂程度自然而然得以降低在图模型研究中，分解性和可压缩性研究是非 常重要的课题分解性和可压缩性的信息往往与模型所对应的图( 严格地说是模 型的交互图) 的性质密切相关，通过分析图即可判断模型是否具有相应的分解性 1 和可压缩性 在图模型中，分解性和可压缩性的思想应用地非常广泛，这两种思想几乎可 以应用到图模型研究的所有方面迄今为止已经出现了很多关于图模型的分解性 和可压缩性的优秀的研究成果，尽管如此，随着应用学科中新问题和新目的的不 断产生，分解性和可压缩性的研究也在不断的更新和延续 接下来，我们先简单地介绍一下图模型的起源、发展、分类、建立、统计推 断、结构学习以及分解性和可压缩性在图模型中的应用 1 1 1 图模型的起源和发展 1 1 图模型简介 l a u r i t z e n 于1 9 9 6 年撰写了一本关于图模型的理论和方法的专著( ( g r a p h i c a l m o d e l s ) ) 5 1 】，并在这本专著的引言部分详细地介绍了图模型的起源和发展，本文 在这段里将重新回顾一下该专著的这部分内容图模型起源于几个不同的科学 领域，例如统计物理学、遗传学和列联表分析早在1 9 0 2 年，在统计物理学中的 大量粒子系统的研究中，g i b b s 为了更好的描述粒子之间的交互关系提出了用无 向图来表示交互的方法 3 2 】，并且用图来建立模型描述系统的能量分布在遗传 学中，w r i g h t 于1 9 2 1 年提出了路径分析，利用有向图表示天然物种的遗传特性， 描述遗传数据产生的机制【8 2 8 3 ，酬；此后，路径分析的思想也被广泛地应用在经 济学和社会学中【8 1 1 1 另外，b a r t l e t t 在进行三向列联表的研究中，也提出了用 无向图来表示变量之间的交互关系的方法【3 】，这种方法被后来的d a r r o c h 等人 吸收并发扬光大，使得图模型在统计学中能够更加深入地应用【圳 随后，图表示的方法在更多的领域得以应用特别是在概率论、统计学、因 果推断和机器学习等领域中，用图来表示自然界和人类社会中的大量事物之间的 关系并用图来建立模型成为一种很流行的方法人们发现，利用图来建立模型可 以非常直观地描述事物之间的复杂关系，非常便于应用学科的研究者与统计学家 2 一 _ l k r 盘 后p o r t e o u s 和s p e e d 等人对连续无向图模型进行了系统地研究【6 2 ，叫，a s m u s s e n 和e d w a r d s 对层次模型进行了研究【l 】，也就是后面所说的离散变量层次模型。除 此之外还有很多关于列联表数据的马尔可夫随机场( 也就是后面将要提到的离散 变量无向图模型) 的系统的研究和分析【1 4 4 1 , 1 5 , 2 5 , 7 8 1 l a u r i t z e n 和f r y d e n b e r g 等人又对图交互模型也就是后文中所谓的混合变量无向图模型中的相应问题进 行了研究【5 2 ，2 7 ，4 9 ，5 0 ，2 1 a o e d w a r d s 于1 9 9 0 年研究了层次交互模型 嚣】，也就是 后面所说的混合变量层次模型另外，还有很多文献讨论了离散有向无圈图模型 的相关性质【7 8 ，4 6 ，8 7 1 随后，又出现了很多综合地系统地研究图模型理论的著作，例如文献【7 9 ，5 1 ，矧 等，这些著作详细系统地介绍了各种图模型中的估计、检验、模型选择等基本问 题的理论和方法最近几年，又出现很多关于图模型的综述性文章，例如文献 【5 7 ，4 5 ，4 3 ，4 4 , 7 6 】等，偏重于介绍图模型中的概率推断的算法等相关理论 1 1 2 图模型的分类 图模型可以从很多方面进行分类从交互图的边是否具有方向上看，图模型 可分为无向图模型、有向无圈图模型和链图模型( 既有无向边又有有向边) 等； 从数据类型上看，图模型可分为离散变量图模型、连续变量图模型和混合变量图 模型以上的两个方面一经确定，就可以明确图模型的具体类型我们将在第二 章中具体介绍这些各种各样的图模型 另外，在其它文献中也有把图模型分为概率图模型和统计图模型的，其中所 3 谓的概率图模型由一个图和一个概率分布构成，而统计图模型则由一个图和一族 概率分布构成【鹞1 例如，。称一个有向无圈图概率图模型为贝叶斯网，而称一个 有向无圈图统计图模型为贝叶斯网模型一般来说，提起图模型都是指统计图模 型，因此本文接下来所介绍的图模型除额外说明外都指的是统计图模型 1 1 3 马尔可夫性 在概率论和统计学中人们非常关心变量集之间的条件独立性，而在图中变量 之间有无边相连则体现出变量集之间的分离性怎样在条件独立性和分离性之 间建立一座桥梁使得图和统计模型建立对应的关系成为一个关键的问题为了解 决这个问题，马尔可夫性( m a r k o vp r o p e r t y ) 的概念应运而生马尔可夫性在图 论和统计学之间建立了一座坚固的桥梁，使得图和统计模型建立了一一对应的关 系由此，统计模型中的很多问题都可以转化成图上的相应问题 一般来说，马尔可夫性可以分为三种：全局马尔可夫性( t h eg l o b a lm a r k o v p r o p e r t y ) 、局部马尔可夫性( t h el o c a lm a r k o vp r o p e r t y ) 和对马尔可夫性( t h e p a i r w i s em a r k o vp r o p e r t y ) 对无向图来说，一般情况下，全局马尔可夫性不弱 于局部马尔可夫性，而局部马尔可夫性不弱于对马尔可夫性( 详情参见文献f 5 1 】 的命题3 4 ) ；而在一些特殊的情况下，这些马尔可夫性又都是等价的( 详情参见 文献【2 6 】) 我们将在下一章详细地介绍这几种马尔可夫性以及它们之间的关系 1 1 4 图模型的统计推断 图模型的统计推断问题一般包括参数估计和假设检验两部分，本文主要研究 参数的极大似然估计和模型的拟合优度检验一旦确定了变量所符合的图模型， 参数估计和假设检验的问题常常可以转化成与图有关的问题例如，在后面将要 提到的分解性和可压缩性研究中，先利用图的性质来判断估计或检验问题是否可 以转化成局部变量上的相应问题，如果可以转化成局部上的问题，那么只需在局 部上进行处理即可，这样一来，问题自然得到简化 4 一 k k 龟 1 1 5 图模型的结构学习 正因为图模型在表示和推断上有着其它统计模型无法与之媲美的优点，图模 型理论在很多应用学科中被越来越多地应用人们越来越喜欢用图来刻画数据中 所蕴含的结构的规律那么如何去确定所研究的实际问题到底用哪个结构来描述 更好呢? 这就引出了图模型的结构学习问题，也就是说，通过分析数据来学习出 一个最适合该实际问题的图模型 在进行图模型的结构学习时，常常要对产生数据的真实概率分布进行一个假 设，即诚实性假设( f a i t h f u l n e s sa s s u m p t i o n ) 也就是说，首先假设存在一个合适 的图，使得真实分布所蕴含的独立性和条件独立性关系与该图上相应的分离性是 一一对应的，换句话说就是，首先要保证真实分布可以用某个图来完全地描述 例如，当变量间的关系都是对称的没有指向的关系时，在建立无向图模型前就要 假设存在一个无向图，使得产生数据的真实分布中的独立性和条件独立性关系和 这个无向图上的分离性一一对应；而当变量间的关系都有指向性时，在建立有向秽 无圈图模型前就要假设存在一个有向无圈图，使得产生数据的真实分布中的独立 性和条件独立性关系和这个有向无圈图上的d 分离性一一对应 实际上，在一些情况下，产生数据的真实分布并不能满足诚实性假设，也 就是说，不存在一个能够完全描述真实分布的图这说明尽管图模型有很多优 点，但在应用方面也有一定的局限性在这个问题的驱动下，一些学者开始研究 能够比图模型更加深刻地描述独立性和条件独立性关系的工具，例如整值集函 ( i m s e t ) 理论，详情参见文献【6 7 ，7 1 ，6 8 ，6 9 , 7 0 ，7 5 等整值集函理论在描述独立性和 条件独立性关系上比图模型要深刻的多，整值集函理论能够描述更多更复杂的独 立性和条件独立性关系，换句话说就是，整值集函理论比图模型更好地满足诚实 性假设单纯地从描述独立性和条件独立性关系的角度上看，用整值集函理 论要远胜于图模型然而，整值集函理论也存在一些缺点，那就是整值集函理论 在直观性和可见性上远逊于图模型，并且利用该工具来进行统计推断更加困难 整值集函理论和图模型理论两者各有优缺点，这就决定了两者中的一方并不能完 全取代另一方，可以根据具体问题的需要和重点来确定选取哪种理论来为具体问 题建立模型 5 中这部分也被称作模型选择 鼹】；而搜索部分则指的是在确定了模型评分函数后， 如何找出评分最高的网络结构，在一些文献中也被称作模型优化【骼】 而基于条件独立性假设检验的结构学习方法则是通过数据来进行变量间的 一些独立性和条件独立性假设检验来确定变量之间的关系进而学习出变量背后 的图结构文献酬中曾提到过，在该类结构学习方法中，通过数据来寻找每一 对变量间的d 分离子是确定贝叶斯网中的边以及边的方向并最终确定贝叶斯网 的结构的主要任务这里所谓的d - 分离子指的是在贝叶斯网中任何能够d 一分离 两个不同变量的变量集在诚实性假设下，通过数据寻找d - 分离子也就等价于 通过数据来检验给定某变量集时两个不同的变量是否条件独立 下面我们将重点介绍几种基于条件独立性假设检验的结构学习方法v e r m a 和p e a r l 提出了i c 算法【7 4 】，在该算法中需要对每一对不同的变量都要通过数据 来检验是否存在某个变量集使得这两个变量在该变量集给定的条件下是条件独 立的，并根据所有检验的结果来获得最终的结构学习的结果，我们将在下一章里 详细介绍这个算法i c 算法是基于条件独立性假设检验的学习方法中的一个基 础的算法，然而该算法在实际应用中却常常遇到问题，因为刚才我们提到了该算 法需要对每一对不同的变量u 和u 都要检验是否存在某个变量集使得这两个变 量在该变量集给定的条件下是条件独立的，也就是要对每一对乱和t ，都要搜寻 相对于t 和v 的d 分离子；然而d 分离子的搜寻范围往往是很大的，所有不包 含乱和移的变量集都在这个范围中，所以搜寻d 一分离子的工作往往要消耗大量 的时间，甚至超出人们能够忍受的范围 因此，在i c 算法之后，又有很多文献提出其它的算法并致力于缩小d - 分离 子的搜索范围例如，p c 算法侧，该算法是一个迭代的算法，在每一步迭代过 程中，只需要在两个不同变量的边界中搜寻相应的d 一分离子即可，这样一来自 6 “ 、 q 然降低了d - 分离子的搜索范围 另外，利用分解的思想来缩小d 分离子的搜索范围也是一个非常直观且有 帮助的方法【3 l 8 5 1 ，在这类方法中原来的结构学习问题可以被转化成各个局部上 的结构学习问题，这样二来，d 分离子的全局搜索也就相应地变成了各个局部上 的搜索，搜索的范围也就自然而然地缩小了我们将在下一节中更加详细地介绍 一种分解的贝叶斯网模型结构学习的方法，即基于d 分离树的分解的贝叶斯网 模型结构学习方法，详情参见文献 1 2 分解性和可压缩性 不管是在图模型的结构学习还是在图模型的统计推断过程中，分解性和可压 缩性研究都起到了非常积极的作用分解性和可压缩性研究可以把一个结构学。 习或统计推断的问题转化到局部一些变量上，这其中充分体现了降维的思想并 一 且，随着变量个数增长，问题的复杂程度增长地越来越快，常常超出可以顺利解 决的范围，这时分解性和可压缩性研究的重要性就会越来越明显 乞 我们将把这一节的内容分为两部分，第一部分介绍一下分解性和可压缩性在 图模型的统计推断上的重要作用，尤其是在图模型的极大似然估计和似然比检验 的问题中的重要作用第二部分介绍图模型的条件模型中的相应的可压缩性第 嚣。 三部分则介绍一下分解性研究在图模型的结构学习，尤其是贝叶斯网的结构学习 中的重要作用 1 2 1 图模型的统计推断中的分解性和可压缩性 首先介绍分解性和可压缩性在图模型的统计推断问题中的应用正如d a v i s 在文献【1 6 中提到过的，根据不同的研究目的，可以从不同的角度( 例如：参数、 模型、估计和检验等方面) 来定义分解性和可压缩性例如从模型的某些参数的 强度的角度上，可以相应地定义参数可压缩性( p c o l l a p s i b i l i t y ) ，且根据参数的 不同，也对应了不同的参数可压缩性研究，例如w h i t t e m o r e 在文献删中研究 7 对数线性模型中交互作用( i n t e r a c t i o n ) 的参数可压缩性；g u o 和g e n g 在文献 酬中研究逻辑斯蒂回归( 1 0 9 i s t i cr e g r e s s i o n ) 的回归系数的参数可压缩性；c u o e ta 1 在文献p 吲中研究优比( o d d sr a t i o s ) 的参数可压缩性等 除了参数可压缩性，人们还常常关心模型的可压缩性和估计的可压缩性，即 模型可压缩性( m c o l l a p s i b i l i t y ) 和估计可压缩性( e c o l l a p s i b i l i t y ) a s m u s s e n 和 e d w a r d s 在文献【1 】中提出了列联表的层次对数线性模型( h i e r a r c h i c a ll o gl i n e a r m o d e l ，简称离散层次模型) 的模型可压缩性和估计可压缩性的概念，并在该文 献中证明了离散层次模型中这两种可压缩性的等价性，还给出了这两种等价的 可压缩性的一个充分必要条件实际上，层次模型是一种包含离散无向图模型 且比离散无向图模型更加广泛的统计图模型，a s m u s s e n 和e d w a r d s 得到的关于 层次模型的结论自然可以应用到离散无向图模型的范畴里，因此我们可以利用 这些结论来判断离散无向图模型的模型可压缩性和估计可压缩性在文献【1 】的 基础上，m a d i g a n 和m o s u r s k i 在文献侧中提出了很多扩展的结果，其中包括 s a h r 算法，用来寻找最小估计可压缩子集，也就是寻找一个在包含关系方面达 到最小的集合使得原来的极大似然估计可以压缩到该集合上。类似地，在连续变 量无向图模型和混合变量无向图模型中也有所谓的模型可压缩性和估计可压缩 性p o r t e o u s 在文献 6 2 】中研究了连续变量无向图模型中的模型可压缩性和估计 可压缩性，并给出了相应的交互图上的充分必要条件f l y d e n b e r g 在文献【2 7 中 研究了混合变量无向图模型的模型可压缩性和估计可压缩性，证明了两者的等价 性，并提出了在图上判断这些等价的可压缩性的充分必要条件e d w a r d s 在文献 【嚣】中研究了比混合变量无向图模型还要广泛的混合变量层次模型( h i e r a r c h i c a l i n t e r a c t i o nm o d e l ) 上的可压缩性，然而在这个更广泛的混合变量层次模型上，可 压缩性也变得更加复杂，该文献只给出了一个判断这个可压缩性的充分性条件而 并非充分必要条件。 另外，d a v i s 在文献 1 6 】中研究图模型的似然比检验问题时，提出了离散无向 图模型的似然比检验的可压缩性的概念，即检验可压缩性( t - c o l l a p s i b i l i t y ) ；并 提出了一些关于检验可压缩性的有帮助的结论本文第四章在文献 1 6 的基础上， 继续研究了离散变量无向图模型的检验可压缩性，给出了一些进一步的结论 在图模型的范畴里，上面提到的各种可压缩性往往都可以用模型所对应的交 8 k o 互图上的性质来描述，也就是说，可以利用图上的信息来判断可压缩性倒如刚 才提到的文献m1 ，眈，2 7 】等，都分别给出了相应类型的图模型的相应类型的可压 缩性在图上的充分必要条件。这样一来，一些图论中的成熟理论就可以为我们的 统计推断服务，进而简化统计推断的过程和提高统计推断的效率 对于检验可压缩性研究，虽然d a v i s 已经获得了很多有帮助的结果【1 6 】，然 而至今为止仍没有其它文献能够给出一个关于检验可压缩性的充分必要条件因 此本文的第四章将在d a v i s 1 6 的基础上，进一步研究检验可压缩性的性质本 文提出了一个比文献【1 6 】的定理9 更弱的从交互图上判断检验可压缩性的充分性 条件；而对于离散变量无向图模型的一种特殊情况，即离散变量可分解模型( 严 格说来，就是交互图是弦图的离散变量无向图模型) 而言，本文在第四章中给出 了一个判断检验可压缩性的充分必要条件进一步，一旦给定了一个判断检验可 压缩性的充分性条件，则可以根据这个条件来获得一个检验可压缩子集，即可以 使原检验问题压缩到其上