（计算机应用技术专业论文）基于贝叶斯网络的并行概率分布估计算法研究.pdf

武汉理工大学硕士学位论文 中文摘要 大自然是人类获得灵感的源泉。几百年来，将生物界所提供的答案应用于 实际问题求解已被证明是一个成功的方法，并且已形成仿生学这个专门的科学 分支。在解决一些较为复杂的问题时我们不必非常明确地描述阀题的全部特征， 只需要根据自然法则来产生新的更好解。基于这种思想发展起来了多种通用问 题的求解方法，遗传算法既为经常被使用到的一种。 在遗传算法中有多种杂交、变异算子可供选用，而在实际操作中不合适的 算子往往会被使用。例如，当问题的积木块与编码没有精密结合的时候选择单 点杂交是不合适的。这在先验知识未知的情况下尤为突出。因此了解无用积木 块的分布显得非常重要。而且分布的关联信息能被用来提升算法的效率。概率 分布估计算法( e d a s ) 就是基于以上考虑而发展出来的一种智能算法。相对于 遗传算法，概率分布估计算法没有对解进行合并的操作，取而代之的是根据每 代种群的概率分布挑选出有前途的个体，并生成新的种群。 本文首先将传统的遗传算法与概率分布估计算法进行了对比。详述了遗传 算法所具有的缺陷。然后介绍了概率分布估计算法的核心概率图模型；并 重点介绍了其中的贝叶斯网络结构，它又称为信念网络，是一种图型化的模型， 能够图形化地表示一组变量间的联合概率分布函数。接着以求一个6 维o n e m a x 函数的最大值为例，介绍了概率分布估计算法的基本概念。最后提出了一种通 过建立并行的贝叶斯网络结构的方式，实现概率分布估计算法的并行化。 相对于传统的概率分布估计算法，并行的概率分布估计算法在解决连续函 数优化及实时优化问题时能提供极大程度的效率提高。 关键词：遗传算法，概率分布估计算法，贝叶斯网络，概率图模型，并行执行 武汉理工大学硕士学位论文 a b s t r a c t n a t u r ei st h es o u r c ef r o mw h i c hh u m a n b e i n g sr e c e i v et h ei n s p i r a t i o n i th a s b e e n p r o v e d as u c c e s s f u lm e t h o dt os o l v et h ep r a c t i c a lp r o b l e m s b yi n t r o d u c i n gt h e a n s w e r sp r o v i d e dw i t hn a t u r ef o rc e n t u r i e s a n di th a sf o r m e dae m b r a n c h m e n to f b i o n i c s w ed on o tn e e dt oh a v ead e f m i t ew h o l ed e s c r i f i t i o nf o rt h ec o m p l i c a t e d p r o b l e m ，b u tj u s ta b i d eb yt h el a wo fn a t u r et og e n e r a t en e ws o l u t i o n s b a s e do n t h i si d e a ，g e n e t i ca l g o r i t h m s ( o a s ) b e c o m e so n eo ft h em o s tc o m m o nm e t h o d st o s o l v es u c h q u e s t i o n s i ng a s ，m a n yc r o s s ，v a r i a t i o nf a c t o r sc a nb eu s e d h o w e v e r , s o m ea r i t h m e t i c o p e r a t o r sa r eo f t e nc h o s ei m p r o p e r l yi np r a c t i c e f o re x a m p l e ，c h o o s i n go n e p o i n t c r o s so p e r a t o ri su n f i tw h e n b u i l d i n g b l o c k sa n d e n c o d i n g d on o tc o m b i n e p r e c i s e l b w h i c hi sa w f u lw i t h o u tk n o w i n gt h ep r i o rk n o w l e d g e s oi ti ss i g n i f i c a n tt or e a l i z e t h ed i s t r i b u t i o no fu s e l e s s b u i l d i n g b l o c k sa n dt h e j o i n t i n f o r m a t i o no ft h e d i s t r i b u t i o nt o i m p r o v ea l g o r i t h m se f f i c i e n c y e s t i m a l o n ed i s t r i b u t i o na l g o r i t h m 厄d a s ) i so n e o ft h e i n t e l l i g e n ta l g o r i t h m sd e v e l o p e df r o m t h ea b o v ei d e a c o m p a r e dw i t hg a s ，e d a ss e l e c t s t h eb e s ti n d i v i d u a l sg r o u p e dt o g e t h e rf o r m f a t h e rs o l u t i o ns e t si n s t e a do f j u s ti n c o r p o r a t i n gf a t h e rs o l u t i o ns e t ss i m p l y a c o m p a r i s o nb e t w e e ng a s a n de d a sw e r eg i v e nf i r s t ，a n dt h el i m i t a t i o no f g a sw a sd e s c r i b e di nd e t a i l l a t e rt h ec o r eo f e d a s p r o b a b i l i t ym a p m o d e lw a s i n t r o d u c e da n d b a y e s i a n n e t w o r ks t r u c t u r e ( b a y e s i a nb e l i e f s n e t w o r k s ) w a s e m p h a s i z e d i ti s ac h a r tm o d e lt h a tc a i ls h o wt h ej o i n tp r o b a b i l i t yd i s t r i b u t i o n f u n c t i o na b o u tas e to fv a r i a b l e s n e x ta q u e s t i o no f 6d i m e n s i o no n e m a xf u n c t i o n o p t i m i z a t i o np r o b l e mw a ss o l v e d a n dw ep r o p o s e d am e t h o dt oc o n s t r u c ta p a r a l l e lb a y e s i a n n e t w o r kw h i c hr e a l i z e dt h ep a r a l l e l i s mo f e d a sa tl a s t i nc o n t r a s tt ot r a d i t i o n a le s t i m a t ed i s t r i b u t i o na l g o r i t h m , p a r a l l e le d a sh a s g r e a t l yi m p r o v e dt h ee f f i c i e n c y w h e no p t i m i z i n gc o n t i n u o u sf u n c t i o n sa n dr e a l t i m e q u e s t i o n s k e yw o r d s ：e s t i m a t ed i s t r i b u t i o na l g o r i t h m ，g e n e t i c 姆血h i l l ，b a y e s i a nn e t w o r k ， p r o b a b i l i s t i cg r a p h i c a lm o d e lp a r a l l e li m p l e m e n t a t i o n 此页若属实，请申请人及导师签名。 独创性声明 二枣j i 薯嚣i 交鹧论文是我个人在导师指导下进行的研究工 作发圾衙的研究威果。据我所知，啥了文中特别加以标注和致谢的 地方外，论文中不包含其他人已经发表或撰写过的研究成果，也不 包含为获得武汉理工大学或其它教育机构的学位或证书而使用过 的材料。与我一同工作的同志对本研究所做的任何炎献均已在论文 中作了明确的说明并表示了谢意。 研究生签名：耋：墨k 日期三! 兰：三f 上 关于论文使用授权的说明 本人完全了解武汉理工大学有关保留、使用学位论文的规定， 即：学校有权保留送交论文的复印件，允许论文被套阅和借阅；学 校可以公布论文的全部内容，可以采用影印、缩印或其他复制手段 保存论文。 ( 保密的论文在解密后应遵守此规定) 研究生签名：迎导师签名 注：请将此声明装订在论文的目录前。 武汉理工大学硕士学位论文 1 1 问题的提出 第1 章引言 在自然界的进化过程中，种群中的个体不断地参与竞争与繁殖。相对优秀 的个体能有更长的生存时间，并能繁殖更多的后代。而通过变异所产生的更优 的范例以及平均适应值也会随着时间而增长。根据达尔文的理论，这种自然选 择的机制在地球上所有生命形式的进化过程中都发挥着作用。 遗传算法即是将自然界这一进化机制应用于计算目的的一种算法。在遗传 算法中候选解被表示为字符串形式，并通过两两重组的方式生成新的个体。这 一过程所产生的后代解将取代原来种群中不合适的两个个体。在遗传算法中有 多种杂交、变异算子可供选用，例如单点杂交。在实际操作中不合适的算予往 往会被使用。例如，当问题的基因块与编码没有精密结合的时候选择单点杂交 是不合适的。这在先验知识未知的情况下尤为突出。因此了解无用积木块 ( b u i l d i n g b l o c k ) 的分布显得非常重要。而且分布的关联信息能被用来提升遗 传算法的效率。u j 1 2 研究现状 概率分布估计算法( e d a s ) 于1 9 9 6 年由m u h l e n h e i n 和p a a f l 所提出，它的核 心即是概率图模型的生成及表示。应用于概率分布估计算法的概率图模型目前 主要有2 种，分别是贝叶斯网路( b a y e s j a nn e t w o r k s ) 和高斯网络( g a n s s i a n n e t w o r k s ) 。其中，对基于贝叶斯网路结构的概率分布估计算法实现其并行化颇 具可行性，其关键就在于建立起并行贝叶斯网络结构。 基于建立并行贝叶斯网络构造的思路延伸出了多种并行e d a 算法。管线模 式的并行贝叶斯优化算法( p a r a l l e lb o aa l g o r i t h m ，b o a ) 为其中的一种，它适 用于由信道所紧密连接的细粒度并行环境。而分布式贝叶斯优化算法 ( d i s t r i b u t e db a y e s i a no r l t i m i z a t i o na l g o r i t h m ，d b o a ) 适用于使用消息传输 模式( m p i ) 的粗粒度并行环境。此外使用多线程机制的混合贝叶斯优化算法 武汉理工大学硕士学位论文 ( m i x e d b a y e s i a no p t i m i z a t i o na l g o r i t h m ，m b o a ) 也是一种高效的并行架构。【1 】 1 3 本文研究内容 为了避免积木块带来的破坏，1 9 9 6 年由m u h l e n b e i n 和p a a b 提出了概率分布 估计算法。这种算法通过从一个概率模型中采样新的个体保持了变量之间的相 互依赖，并避免了遗传算法中的杂交操作字符串中重要信息的破坏。然而，一 般的概率分布估计算法在解决连续函数优化及实时优化问题时效率不佳。建立 并行的概率分布估计算法即为一种能改善上述问题的可行方案，如何建立一个 并行的贝叶斯网络结构以实现并行概率分布估计算法，这就是我的研究重点。 1 4 本文的组织 本文后续章节组织如下：第二章介绍传统的遗传算法的相关概念，并详述 了传统遗传算法的缺陷及其形成原因。第三章介绍了概率分布估计算法的核心 概率图模型以及相关的基本概念和术语，并重点介绍了贝叶斯网络结构的 相关概念及建立方法。第四章以求一个o n e m a x 函数的最大值为例，描述了概 率分布估计算法的相关概念及原理。在第五章中首先对比了传统的并行遗传算 法于并行概率分布估计算法的不同之处，然后提出并介绍了基于并行贝叶斯网 络结构的并行概率分布估计算法。第六章对该研究工作进行了总结，提出了对 进一步研究工作的设想。 2 武汉理工大学硕士学位论文 第2 章传统的遗传算法 2 1 遗传算法的基本思想 遗传算法【2 4 】是模拟生物在自然环境中的遗传和进化过程而形成的一种自 适应全局优化概率搜索算法。算法中存在一个代表问题潜在解集的种群，该种 群由经过基因编码的一定数目的个体组成。每个个体携带不同的染色体，染色 体作为遗传物质的主要载体表现为某种基因组合，决定了个体的性状的外部表 现。于是，初代种群产生之后，按照适者生存和优胜劣汰的原理，逐代演化产 生出越来越好的近似解。对应于遗传算法，就是根据问题中个体的适应度大小 按照相应的规则挑选个体，借助于自然遗传学的遗传算子进行组合交叉和变异， 产生出代表新的解集的种群。该过程将导致种群像自然进化一样的后生代种群 比前代更加适应于环境，末代种群中的最优个体经过解码，可以作为问题近似 最优解。1 4 j 2 2 遗传算法基本步骤 如前所述，遗传算法的基本步骤模拟自然界的生物进化，由以下步骤而来： s t e p l ：初始化。设置进化代数计数器t 一0 ；设置最大进化代数t ；随机 生成m 个个体作为初始群体p ( 0 ) ； s t e p 2 ：个体评价。计算群体p ( f ) 中各个个体的适应度。 s t e p 3 ：选择运算。将选择算子作用于群体。 s t e p 4 ：交叉运算。将交叉算子作用于群体。 s t e p 5 ：变异运算。将变异算子作用于群体。群体p ( t 1 经过选择、交叉、变 异运算之后得到下一代群体p ( t + 1 1 。 s t e p 6 ：终止条件判断。若ts t ，则：t t + 1 ，转至s t e p 2 ；若t t ，则 以进化过程中所得到的具有最大适应度的个体作为最优解输出，终 止计算。 遗传算法包括了三个基本操作：选择、交叉和变异。 1 ) 选择 武汉理工大学硕士学位论文 选择即从当前群体适应值高的个体以生成交配池的过程。目前，主要有适 应值比例选择、b o l t z m a n n 选择、排序选择、联赛选择等形式。 2 ) 交叉 交叉操作是进化算法中遗传算法具备的原始的独有特征。g a 交叉算子是模 仿自然界有性繁殖的基因重组过程，其作用在于将原有的优良基因遗传给下一 代个体，并生成包含更复杂基因结构的新个体。它通过交换两个染色体部分遗 传信息以产生新的染色体。这一过程类似于自然界中的有性繁殖。在一般情况 下，双亲染色体在一固定点被分割，形成左右两个部分。其中一个双亲染色体 的左部份与另一个双亲染色体的右部份组合在一起，形成一个新的染色体。单 点交叉是最常被使用到的一种交叉操作。 图2 1 单点交叉示意图【5 j 3 ) 变异 变异操作模拟自然界生物进化中染色体上某位基因发生的突变现象从而改 变染色体的结构和物理性状。一方面，变异算予可以使群体进化过程中丢失的 等位基因信息得以恢复，以保持群体的个体差异性，防止发生成熟前收敛；另 一方面，当种群规模较大时，在交叉操作基础上引入适度的变异，也能提高遗 传算法的局部搜索效率。 2 3 模式定理( s c h e m at h e o r e m ) 及其缺陷 模式( s c h e m a ) 是一个描述字符串集的模板，该字符串集中串的某些位置 上存在着相似性。不失一般性，我们考虑二值字符集 0 ，1 ，由此产生通常的0 ， 1 字符串。现在我们增加一个符号“一，称作“无关符”( d o n tc a r e ) 或通配符， 即“t ”既可以被当作“0 ”，又可以被当作“1 ”。这样，二值字符集 o ，1 就扩 展为三值字符集 0 ，1 ，+ ，由此可以产生诸如0 1 1 0 、0 + 1 1 ”、+ + 0 1 + 0 等字符串。 4 武汉理工大学硕士学位论文 以长度为5 的串为例，模式* 0 0 0 1 描述了在位置2 、3 、4 、5 具有形式“0 0 0 1 ” 的所有字符串，目o l o o m ，0 0 0 0 1 由此可以看出，模式的概念为我们提供了一种 简洁的用于描述在某些位置上具有结构相似的0 、1 字符串集合的方法。然而， 模式概念的引入并不是仅仅为了描述上的方便。在引入模式概念前，我们所看 到的遗传算法是：在某一代中，n 个互不相同的串在选择、交叉、变异等遗传 算子作用下产生下一代的n 个互不相同的串。那么，在两代之间究竟保留了什 么性质，破坏了什么性质，我们无从得知，因为我们看到的串是相互独立的， 互不联系的。而引入模式的概念后，我们看到一个串实际上隐含了多个模式( 长 度为l 的串隐含着2 l 各模式) ，一个模式可以隐含在多个串中，不同的串之间 通过模式而相互联系。遗传算法中串的运算实际是就是模式的运算，因此，通 过分析模式在遗传操作下的变化，从而把握遗传算法的实质，这正是模式定理 所要揭示的内容。 在一个模式中确定位置的个数称作为模式的模式阶：模式中第一个确定位 置和最后一个确定位置之间的距离称作模式的定义距。在遗传算子的选择、交 叉和变异作用下，具有低阶、短定义距以及平均适应度高于群体平均适应度的 模式在子代中将得以指数级增长，这就是模式定理。【5 】 基于此定理，遗传算法并非搜寻染色体本身，而是染色体内的模式。实际 决定可能解的适应值的因素在于此解的染色体内所含的模式，某些模式会导致 较佳解，而其它的基因则对适应值无贡献，演化的目的即为筛选出这些模式。 较短且级数较低的模式在交配时有较佳的存活纪律，故将可能解编码进染色体 的方法亦会影响到搜索效果及效率。若产生最佳解的模式在某编码方法中较短 且级数较低，搜索的效果及效率则均会提高。所以遗传算法虽为广义型求解法， 但问题的特性亦会影响到用此法最佳解搜寻，所以编码时必须先了解导致最佳 解的基因组，编成较佳的模式，以避免因编码造成的搜寻困扰，但这样做也失 去了遗传算法作为广义型求解法的精神与其黑箱作业的优点。但是当面多位置 问题的求解时，要在使用遗传算法之前来了解其最佳的基因组是不合时宣的。 6 1 武汉理工大学硕士学位论文 2 4 积木块假设( b u il d i n gb i o c k sh y p o t h e s i s ) 及其与模 式定理的矛盾 遗传算法的交叉可信度不仅仅依赖于模式定理。它还依赖于积木块假设理 论。也就是说遗传算法中低阶、短距、高平均适应度的模式( 积木块) 在遗传 算子作用下，相互结合，能生成高阶、长距、高平均适应度的模式，最终生成 平均最优解。【5 】通过组合积木块来找到越来越好的局部解，这种能力是遗传算 法的搜索能力的主要来源。不幸的是，当我们考虑积木块假设的时候，发现它 和模式定理刚好矛盾。 积木块假设理论假设所有的积木块的适应值受基因型上的其它积木块的影 响。如果不是这样的话，讨论积木块没有任何意义。因此，积木块假设理论假 设了基因的显性作用于适应值，而这点与模式定理中的隐性作用矛盾。 考虑到积木块假设的长度问题，我们发现了迸一步的矛盾之处。在对积木 块的操作之中，在给定的阶段需要处理的模式确实是先前的积木块被放在一起 而得到的。除了在初始阶段之外，这些模式的定义长度和积木块成员的定义长 度有关联。如果我们保守的假设，积木块定义长度至少是成员的定义长度的和， 于是我们可以发现在对积木块的操作中实际的模式长度呈指数增长。我们能够 发现积木块假设( 它依赖于不重要的模式长度) 很可能除了初始阶段之外在其 它所有阶段也起重要作用。它需要增加模式长度，这点上和模式理论中的短距 离假设不同。 2 5 遗传算法的缺陷 如果算法设计适当，再结合操作能保证最合适的遗传结构( 积木块) 被后 代所保留。而关系到整个算法的效率的是对优化问题的解( 种群中的个体) 的 编码方式。也就是说参数的设置能极大程度的影响变异以及交叉操作。 针对特定的问题在编码以及再结合操作中难以找到一个适当的参数设置这 正是传统的遗传算法所具有的最大缺陷。而这正是只需要较少的参数设置、用 跟先进的方法取代再结合操作的分布估计算法相对于传统的遗传算法所具有的 优越之处。 6 武汉理工大学硕士学位论文 第3 章概率图模型 概率推论早已成为人工智能技术的核心，并被，“泛应用于图论方法以用来 表示和处理复杂的概率分布。而图论的框架能被应用于建立e d a 算法，并能 使之在搜索解的过程中得到比传统的遗传算法更高的效率。 3 1 表示法 用盖；来表示一个随机变量，x i 代表个具体的值。那么( x i ：墨) ( 或 0 ；) ) 则表示点x i 的广义概率分布。与之类似，我们可以用x 一( 墨，x 。) 来 表示n 维的随机变量，x - ( 而，x 。) 怎能表示一个可能的值。z 的联合概率分 布表示为( x = d ( 或 ) ) 。由变量x ，对应的值z ，所决定的x ；的条件概率分 布表示为( x f = x i i x f = x f ) ( 或( x i i 石i ) ) 。 如果z ；是离散的，那么( x i 一一) - p ( x i 一工；) ( 或p ( x ；) ) 被称为z 。的质 量概率。如果所有的变量x 都为离散的，那么( x - x ) 一p ( x = x ) ( 或p ( 砷) 被称为联合概率质量，( x i = ti x f - x f ) * p ( x ；= x ii x f = 算f ) ( 或p ( x il 工f ) ) 为由x i ；x i 决定的x i 的条件质量概率。 如果j ；是连续的，( x ；= x i ) n ，( x ；x i ) ( 或( x 。) ) 为x 。的密度函数。 如果z 所有的变量均为连续型，( x 一力一，( x = 力( 或，( 砷) 为联合密函数， ( x f x ij x j = x j ) = ( x f t x ii x j = x j ) ( 或，“l x j ) ) 为由x j x ，决定的置 的条件密度函数。 设x 一僻l 一，x 。) 为任意变量的一个向量，我们用t 表示x ；的值， y = 。) 。代表集合y 膏的一个值。x 的概率图模型是一个联合广义概率分 布的因式分解图( x ；曲( 或( 硝) 。这一表示方式由两部分组成：一个结构和 一个本地广义概率分布的集合。置的结构s 为一个有向无环图( d a g ) ，表示 变量z 条件依赖的集合。 z 的结构s 表明了对于每个变量并；以及 x ，x 。 p a s 不受 p a s ，i = 2 3 1 的约束。其因数分解可表示为； ( z ) = ( x l ，) m ( x 1 ) ( 工2l ) 。( ti 工l ，一一1 ) ( 屯l x , 1 ，工。一1 ) = 武汉理工大学硕士学位论文 ( _ ) 阮ip 口；) ( t i 伊? ) “i 朋：) = 丌( t i 即? ) 在以上的表达式中，我们假定本地广义概率分布依赖手生个参数的有限集 如o ，。于是公式即变为 p ( x i 以) = 兀p ( ti 朋? ，包) 此时以= ( q ，吼) 。将概率分布图模型的两部分组合在一起，它可以被表示 为m = 岱，8 。) 。 图3 1 x = 晖。，x ：，鼍，x 。，x ，戤) 的概率图模型结构图7 1 3 2 贝叶斯网络 自从5 0 6 0 年代贝叶斯学派形成后，关于贝叶斯分析的研究久盛不衰。早在 8 0 年代，贝叶斯网络就成功地应用于专家系统，成为表示不确定性专家知识和推 理的种流行的方法。9 0 年代以来，贝叶斯学习一直是机器学习研究的重要方 向。由于概率统计与数据采掘的天然联系，数据采掘兴起后，贝叶斯网络日益受到 重视，再次成为引人注目的热点。近两年研究者们进一步研究了直接从数据中学 习并生成贝叶斯网络的方法，包括贝叶斯方法、类贝叶斯方法和非贝叶斯方法， 武汉理工大学硕士学位论文 为贝叶斯网络用于数据采掘和知识发现开辟了道路。这些新的方法和技术还在 发展之中，但是已经在一些数据建模问题中显示出令人瞩目的效果。【8 】 3 2 1 贝叶斯网络的基本概念 贝叶斯网络又称为信念网络 s - 1 7 】，是一种图型化的模型，能够图形化地表示 一组变量间的联合概率分布函数。一个贝叶斯网络包括了一个结构模型和与之 相关的一组条件概率分布函数。结构模型是一个有向无环图，其中的节点表示了 随机变量，是对于过程、事件、状态等实体的某特性的描述，边则表示变量间 的概率依赖关系。图中的每个节点都有一个给定其父节点情况下该节点的条件 概率分布函数。这样。一个贝叶斯网络就用图形化的形式表示了如何将与一系列 节点相关的条件概率函数组合成为一个整体的联合概率分布函数。因果贝叶斯 网络是指具有因果含义的贝叶斯网络，其中每个节点的父节点被解释为该节点 相对于模型中其它节点的直接原因。为了与之区别，有时也将没有因果意义的贝 叶斯网络称为概率贝叶斯网络。 贝叶斯网络作为一种图形化的建模工具，具有一系列的优点：( 1 ) 贝叶斯 网络将有向无环图与概率理论有机结合，不但具有了正式的概率理论基础，同 时也具有更加直观的知识表示形式。一方面，它可以将人类所拥有的因果知识 直接用有向图自然直观地表示出来；另方面，也可以将统计数据以条件概率 的形式融入模型。这样贝叶斯网络就能将人类的先验知识和后验的数据无缝地 结合，克服框架、语义网络等模型仅能表达处理定量信息的弱点和神经网络等 方法不够直观的缺点：( 2 ) 贝叶斯网络与一般知识表示方法不同的是对于问题 域的建模。因此当条件或行为等发生变化时，不用对模型进行修正；( 3 ) 贝叶斯 网络可以图形化表示随机变量间的联合概率，因此能够处理各种不确定性信息； ( 4 ) 贝叶斯网络中没有确定的输入或输出节点，节点之间是相互影响的，任何 节点观测值的获得或者对于任何节点的干涉，都会对其他节点造成影响，并可 以利用贝叶斯网络推理来进行估计预测；( 5 ) 贝叶斯网络的推理是以贝叶斯概 率理论为基础的，不需要外界的任何推理机制，不但具有理论依据，而且将知 识表示与知识推理结合起来，形成统一的整体。 由于上述优点，贝叶斯网络很快就成为人工智能领域进行不确定性推理和 建模的一个有效工具。利用贝叶斯网络对于事件或者属性间的带有不确定性的 9 武汉理工大学硕士学位论文 相互关系进行建模和推理在医学诊断、自然语言理解、故障诊断、启发式搜索、 图像解释、目标识别以及不确定推理和预测等方面产生了很多成功的应用，这 些应用大致可分为建立系统模型以辅助决策、实现特征融合以及进行分类的数 据分析三大类。 a。马暑 s a b e p ( s 队e 磅 ll葛s l1o 0 ，9 5 ： lo 。l0 2 0 ioo0 。0 5 夸1l0 0 0 争l00 0 0 0 ：0 l00 0 n oo0 o o 图3 2贝叶斯网络 1 l 罔3 2 是一个简单的贝叶斯网络结构以及相关的条件概率分布，用以表示 s ：1 时的概率值 3 2 2 贝叶斯网络的结构及建立方法 贝叶斯网络是一个带有概率注释的有向无环图。 1 7 “2 7 这种概率型能表示变 量之间的联合概率分布( 物理的或贝叶斯的) 分析变量之间的相互关系，利用贝叶 斯定理揭示的学习和统计推断功能，实现预测、分类、聚类、因果分析等数据采 掘任务。 关于一组变量z = ( x 1 】“，x 。) 的贝叶斯网络由以下两部分组成：一个表 示x 中的变量的条件独立断言的网络结构s ；与每一个变量相联系的局部概 率分布集合p 。两者定义了x 的联合概率分布。s 是一个有向无环图，s 中的 节点一对一地对应于x 中的变量。以并；表示变量以及该交量对应的节点，k ；表 示s 中的z ；的父节点。s 的节点之间缺省弧线则表示条件独立。x 的联合概率 分布表示为： n p ( 砂一兀p ( 置i p a ；) ( 1 ) p 表示( 1 ) 式中的局部概率分布，即乘积中的项p ( tl 艘；) o = 1 2 ，阼) ，则二元组 岱，p ) 表示了联合概率分布p ( x ) 。当仅仅从先验信息出发建立贝叶斯网络时，该 1 0 武汉理工大学硕士学位论文 概率分布是贝叶斯的( 主观的) 。当从数据出发进行学习，进而建立贝叶斯网络时， 该概率是物理的( 客观的) 。 为了建立贝叶斯网络，第一步，必须确定为建立模型有关的变量及其解释。 为此，需要：确定模型的目标，即确定问题相关的解释；确定与问题有 关的许多可能的观测值，并确定其中值得建立模型的子集：将这些观测值组 成互不梢容的而且穷尽所有状态的变量。这样做的结果不是唯一的。 第二步，建立一个表示条件独立断言的有向无环图。根据概率乘法公式有： p ( 砷2 p ( 五h ，h ) ；p ( x 1 ) p ( z 2i 工1 ) p ( 工3l ，x 2 ) p ( x 。i 工i ，工2 ，z 。一1 ) 对于每个变量置，如果有某个子集兀。 z t ，x z ，t t 使得z ；与 似，x ：，x 。) n ：是条件独立的，即对任何x ，有： p ( x 1i f ，上2 ，t - 1 ) - p ( x li 以“一1 2 ，n ) ( 2 ) ( 3 ) 则由( 2 ) 、( 3 ) 两式可得p ( 砷8 珥_ p ( t i 吒) 。变量集合( n t 一，f i t l ) 对应于父结 点( n ”- ，砌n ) ，故又可以写成p ( 砷2 p “i 印一) 。于是，为了决定贝叶斯网 络的结构，需要将变量j 。，石：，x 。那某种次序排序；决定满足( 3 ) 式的 变量集兀f ( f - 1 , 2 ，”) 。 从原理上说，如何从n 个变量中找出适合条件独立的顺序，是一个组合爆炸问 题。因为要比较州种变量顺序。不过，通常可以在现实问题中决定因果关系，而且 因果关系一般都对应于条件独立的断言。因此，可以从原因变量到结果变量划一 个带箭头的弧来直观表示变量之间的因果关系。 第三步，指派局部概率分布p ( tin ；) 。在离散的情形，需要为每一个变量x ； 的各个父节点的状态指派一个分布。 显然，以上各步可能交叉进行，而不是简单的顺序进行可以完成的。因为网络 的结构和参数都是根据背景知识和经验确定的，这样建立的网络又称为先验贝叶 斯网络。 1 1 武汉理工大学硕士学位论文 3 2 3 贝叶斯网络的语义 贝叶斯网络对给定网络结构s 编码了一组变量z = ( z l ，一，x 。) 的联合 概率分布： p ( 砷= 丌p i p a ；) 贝叶斯网络表示条件独立及因果关系。所谓z ；刘于 _ ，工：，z 。 n 条件独立意味着变量x ；只依赖于变量集瞄1 i 一，x 。) 中的某此变量 丌f ( f - 1 ，2 胛) ，而与 x t ，x z 一，工“ l - i , 中的变量无关。前一种情况在贝叶斯 网络表现为变量之间有弧线连接，而后一种情况表现为变量之间无弧线连接。 贝叶斯网络是概率的分类回归模型。假设一组变量x 一( 盖l ，一，x 。) 的物 理联合概率分布可以编码在某个网络结构s 中： p ( x i 以，s “) = 兀p ( 而i p a j ，q ，s6 ) i r 其中0 ；是分布p ( x ；l p a ；，q ，s 6 ) 的参数向量，位是参数组( 日，0 。，吼) 构成 的向量，而s “表示物力联合分布可以依照5 分解的假设。将分布p lp a ；，b ，s “) 看成0 。的函数，并称为局部分布函数。局部分布函数其实只是一个概率分类或 回归函数，在离散变量情形是分类，在连续变量情形是回归。于是，贝叶斯网络可 以看成由条件独立关系组成的概率分类回归模型的集合。如线性回归、扩展的 线性回归、概率神经网络、概率决策树等，都是该集合的例子。在大多数情形， 都可以用贝叶斯方法进行学习。 3 2 4 贝叶斯网络结构学习 一般贝叶斯网络的构建是首先由相关领域的专家根据事物间的关系来确定 出结构模型，即有向无环图，然后再利用其它方法确定每个节点的条件概率，但 这样构建的网络模型无法保证其客观性和可靠性。因此，研究人员尝试引入客 观的观测数据，希望通过将观测数据与专家知识相结合来共同构建贝叶斯网络， 并进一步在没有专家先验知识的情况下，尝试完全从观测数据中学习得到网络 结构和参数。其中网络结构的学习不但是整个学习过程的基础，并且是一个n p 难题，因此更吸引了大量研究人员的注意。 武汉理工大学硕士学位论文 研究人员借鉴统计学领域对多变量联合概率分布近似分解的方法，从多个 角度对该问题进行研究，形成了基于独立性检验和基于评价与搜索的两大类算 法。在一系列假设下，通过将先验信息与观测数据相结合，实现了多种网络结 构模型的学习算法，进而提出了在没有任何先验信息情况下的相应算法。最近 的研究开始减弱甚至放弃某些假设，从更一般意义下研究网络结构的学习。因 果贝叶斯网络结构模型的学习有时也称为因果发现或因果挖掘。这是因为数据 的处理所获得的结构模型反映了事物间因果关系的知识。从广义的角度讲，因 果数据挖掘可以认为是从数据中发现有关因果性知识的过程。 我们把根据用户的先验知识构造的贝叶斯网络称为先验贝叶斯网络，把先 验贝叶斯网络和数据相结合而得到的贝叶斯网络称为后验贝叶斯网络。由先验 贝叶斯网络到后验贝叶斯网络的过程称为贝叶斯网络学习，或者说，把先验贝 叶斯网络和数据相结合而得到后验贝叶斯网络的过程称为贝叶斯网络学习。继 而把先验贝叶斯网络和数据相结合而得到后验贝叶斯网络的过程称为贝叶斯网 络学习。贝叶斯网络学习是用数据对先验知识的修正( 贝叶斯网络是一种知识表 示形式) ，贝叶斯网络能够持续学习，上次学习得到的后验贝叶斯网络变成下 一次学习的先验贝叶斯网络。 + ( 函 + 且叶囊方赡 斗囊膏生 图3 3 贝叶斯网络持续学习图【2 8 】 贝叶斯网络学习包括参数学习、结构学习和概率学习，参数学习是结构学 习和概率学习的基础。对变量集x 一( j 1 ，一，丑。) ，其中置x 的值域( 或状态 集) ( 一，一) ；d = c ，c 。 为数据样本( 数据集或数据库) ，c 1 为一事例 ( 一次实验情况或数据库的一个记录) ；tp ji 朋? ，s ，导) 为先验概率的参 数变量，表示在用户具有知识状态亭，网络为s 的假设，z ；的父结点集朋；具有 第j 个状态的前提下，变量j z 取第七个值的客观概率， o ，薹2 1 ，n ； 武汉理工大学硕士学位论文 的值域为 p 日；，膨产，g f2 肪为脚t 的所有可能状态的个数，记 以= u 碱 ，0 ；一u ，岛- u ，那么 i - 1 ，- l i - i 掣“，亭) 2 兀p “，峨，s “，亭) a 我们提出以下三个假设： ( 1 ) 随机样本d ( 数据库) 是完整的，记在d 中没有丢失的数据。 ( 2 ) 参数矢量相互独立，即 p 慨”亭) 一兀p i s h , 亭) ； p ( b 毒) 2 i = l p ( 日j 亭) 。 鹏妒固知鸭卜刺妒1 3 2 5 贝叶斯推断与预测 贝叶斯推断： 把在贝叶斯网络中计算人们想计算的概率过程称为贝叶斯推断，在理论上 由联合分布可以推断出任何在贝叶斯网络中人们想知道的概率。考虑前面的信 誉卡欺骗问题，根据局部概率分布可以得到联合概率分布，我们就可以计算出 在网络中任何想计算的概率。 例如：计算p ( ，i 口，j ，g ，j ) 1 4 武汉理工大学硕士学位论文 p ( f l a , s , g , j ，2 等岩4 秽舞2 p ( f ) p ( a ) p ( s ) p ( si ，) p ( ，i ，a ，5 ) 罗，e ( f ) p 0 ) 尸( s ) p ( gl ，) p ( ，i ，口，s ) p ( f ) p ( g ，) p ( jif ，a ，j ) ，尸( ，) p ( g i ，) p ( ，i ，口，5 ) 贝叶斯预测： 贝叶斯预测是根据已知数据推测未知情况的过程，设数据集中有c ，c 。 个事例。具有确定结构的预测公式为： 掣。旧趵t 丹叩忱咖一n 冉糟 具有非确定结构的预测公式为： p ( x “+ - i d ，s ) = 一尸( x ”+ ti d ，s ) p p i d ) 具有非确定结构的预测一般很难计算，因为要对所有结构求知，因此，一 般采用选择性的模式平均，即选择合适数量的网络结构，这些网络结构可以代 表所有的网络结构。 贝叶斯网络有着广泛的应用，预测是贝叶斯网络重要的应用之一。把朴素 ( n a i v e ) 贝叶斯网络分类( 单变量预测) 器进行依赖扩展而得到的t a n ( t r e e a u g m e n t e dn a i v eb a y e s ) 分类器，是目前性能最好的分类器之一；用贝叶斯网 络可有效地进行多变量联合预测，并且具有良好的性能：贝叶斯网络聚类( 类变 量生成及预测) 系统( a u t o c l a s s ) 能有效地处理离散与连续混合数据且参考的 是全局上下文，是目前最优秀的聚类系统之一；利用贝叶斯网络能够有效地进 行多因素定性与定量因果分析( 因果预测) 。 3 2 6 具有未知参数的贝叶斯网络的统计推断和问题求解 当贝叶斯网络结构是确定的，并且没有未知参数且数据是完整的情况下可用 上面的方法进行推断和求解。如果贝叶斯网络中含有未知的参数，则可通过学 习获得贝叶斯网络中未知的参数的概率分布，然后再进行推断和求解。此时的 武汉理工大学硕士学位论文 统计推断和求解问题则变为求变量相对于未知参数的条件期望： p ( x + 。id ，s 5 ) =ep ( x + ，| 如，d ，s 6 ，亭) ( 4 ) p ( 以p 矿) 其中x 。+ 。表示某个变量，p 僻。1 8 ，d ，s “，亭) 表示改变量的联合分布， p ( old ，s6 ) 表示参数0 的后验分布。 假定每个变量x 盖。是离散的，有个可能的值一，x i t ，每个局部分布函 数是一组多项分布的集合，一个分布对应于p 吩的一个构成( 即一个分量) 。也就 是说，假定 p ( 露lp a ，q ，s “) 一日社 0 ( i = 1 , 2 ，以；j = 1 ，2 ，吼) ( 5 ) 其中p _ 朋? ，册产表示朋t 的构成，q i 一豇。o i 一( ( ) 2 z ) 知是参数，为 方便起见，定义参数向量： 6 0 一z ，- - 。，b n ( f t l , 2 ，丹；j 1 , 2 ，吼) 给定以上的局部分布函数，在以下两个假设下，可以封闭地计算后验分布 p ( 色i d ，s “) ： 在随机样本d 中没有缺损数据，这时又称d 是完全的； 参数向量嘞是相互独立的，即p ( 吼i s “) 2 i ：! l p 略i s ) 。这就是参数 独立假设。在以上两个假设下，对于给定随机样本d ，参数仍然保持独立： p ( oi s h ) 。i = i i = i p ( l d s ) ( 6 ) 于是可以相互独立地更新每一个参数向量。假设每一个参数向量有先验 d j r i c h l e t 分布d 打( p # lo 口l ，8f2 ，驴。) ，我们得到后验分布为： p ( 岛i s h ) 昌d i r ( 0 0i 口1 + 可l ，a 可2 + f 2 ，a 巍+ 巍) ( 7 ) 其中斑是当盖；工? 且砌。一p a ? 时d 中的案例数目。 于是我们有： 舭一i 邸6 卜，( 缸( n ) 使用参数对给定d 保持独立的事实，可以计算数学期望： 武汉理工大学硕士学位论文 p ( + - 眇“) 2 黔p ( 岛m “) 织 通过计算，最后可得如下的统计推断模型： 熙彬，一1 ) 糟 其中= 艺：。，a 社且- ：。班n 由于无约束多项分布属于指数家族，上丽的 计算将变得简单。 3 2 7 具有不确定网络结构的统计推断和问题求解 如果对网络的结构也不能确定，