（计算机应用技术专业论文）贝叶斯网络推理算法研究.pdf

贝叶斯网络推理算法研究 摘要 基于概率知识表达的贝叶斯网，己成为人工智能不确定知识表示与推 理领域近几年来研究的热点，目前国内外的许多研究机构都对贝叶斯网进 行了深入的研究。本文对贝叶斯网的国内外研究现状进行了深入分析，对 它的原理、构造方法及其扩展，进行了深入的讨论。论文的主要工作和创 新之处如下： l 、介绍了贝叶斯网原理及其中的条件独立性。讨论了b a y e s i a n 网的 常用推理算法，包括：消息传递推理算法、子团树传播推理算法与基于消 元的推理算法等。此外，还对近似推理算法进行了讨论。 2 、本文从讨论联结树( j u n c t i o nt r e ej t ) 推理算法入手，提出基于 局部联结树( l o c a lj u n c t i o nt r e e ，l j t ) 的近似推理算法。该算法采用相对于 查询节点的节点相关度来搜索影响较大的节点，同时考虑了距离影响和证 据节点的特殊性，使构造的子网比较合理，有利于提高推理计算速度和保 证较高的计算精度。 3 、提出一种基于节点相关度n r 对d b n 进行裁剪的近似推理算法。 一般而言，d b n 推理过程是对网络所有结点的概率的更新，对于一个大 型复杂的d b n ，该推理算法能够显著提高效率，并能保持较高的计算精 度。 关键词：贝叶斯网，概论推理，联结树算法，局部联结树算法，节点相关 度 r e s e a r c ho nt h eb a y e s i a nn e t w o r k si n f e r e n c e a b s t r a c t b a y e s i a nn e t w o r kb a s e do nk n o w l e d g er e p r e s e n t a t i o no fp r o b a b i l i t y t h e o r yh a sb e c o m eah o ts p o ti nt h ed o m a i n so fa iu n c e r t a i nk n o w l e d g e r e p r e s e n t a t i o na n di n f e r e n c ei nr e c e n ty e a r s c u r r e n t l ym a n yo ft h ed o m e s t i c a n df o r e i g nr e s e a r c hi n s t i t u t i o n sc o n d u c t e di n - d e p t hs t u d yo fb a y e s i a n n e t w o r k i nt h i sp a p e r , t h ec u r r e n tt h er e s e a r c hs i t u a t i o no fb a y e s i a n n e t w o r ka th o m ea n da b r o a di sa n a l y z e da n dt h ep r i n c i p l e sa n dc o n s t r u c t i o n m e t h o d sa r ed i s c u s s e d t h em a i nw o r ka n di n n o v a t i o n so ft h ep a p e ra r ea s f o l l o w s ： 1 t h ef u n d a m e n t a lt h e o r yo fb a y e s i a nn e t w o r ka n de o n d i t i o n a l i n d e p e n d e n c ea r ei n t r o d u c e d b o t ht h ea c c u r a t ea n da p p r o x i m a t ei n f e r e n c e a l g o r i t h m s ，s u c h a sm e s s a g ep a s s i n ga l g o r i t h m ，c l i q u et r e ep r o p a g a t i o n a l g o r i t h m ，v a r i a b l ee l i m i n a t i o na l g o r i t h ma n ds oo n ，a r ed i s c u s s e d 2 a f t e rt h ed i s c u s s i o no fj u n c t i o nt r e e ( j t ) i n f e r e n c ea l g o r i t h m ，a n a p p r o x i m a t ea l g o r i t h mb a s e do nl o c a lj u n c t i o nt r e e ( l j t ) i sp r o p o s e df o r i n f e r e n c eo fl a r g ec o m p l e xb n t h er e l e v a n c eb e t w e e nan o d ea n dt h ei n q u i r y n o d eqi sd e f i n e da n di su s e dt oc o n s t r u c tl jt t h ei m p a c to ft h ed i s t a n c e f r o man o d et ot h en o d eqa n dt h es p e c i a l t yo ft h ee v i d e n c en o d ea r e c o n s i d e r e df o rt h ep u r p o s eo fc o n s t r u c t i o no fl jt i nt h i sw a y , t h es p e e do f i n f e r e n c ec a ni n c r e a s e ，c o m p u t i n gp r e c i s i o nc a nb eg u a r a n t e e da n di n f e r e n c e e f f i c i e n c yc a nb ea t t e n d e da tt h es a m et i m e 3 a na p p r o x i m a t ei n f e r e n c ea l g o r i t h mb a s e do nn ri sp r o p o s e df o r c r o p p i n go fd b n g e n e r a l l y ，t h ep r o c e s so fd b ni n f e r e n c ei st ou p d a t et h e p r o b a b i l i t yo fa l ln o d e s t ol a r g ec o m p l e xd b n ，t h ea l g o r i t h mc a ng e tr e s u l t s w i t hg o o da c c u r a c ya n di n c r e a s ec o m p u t i n gs p e e de v i d e n t l y k e y w o r d s ：b a y e s i a nn e t w o r k s ，p r o b a b i l i t yi n f e r e n c e ，j u n c t i o nt r e e ，l o c a l j u n c t i o nt r e e ，n o d er e l e v a n c e 插图清单 图1 1关于草地湿的贝叶斯网络4 图2 1上下文独立的例子1 3 图2 2 简单的贝叶斯网模型1 4 图2 3单连通与多连通贝叶斯网1 6 图2 4贝叶斯网推理模式1 7 图2 5贝叶斯网络推理的已有算法1 8 图2 6 消息和g 消息的传递过程2 0 图2 7 联结树算法流程图2 1 图2 8贝叶斯网转化为联结树2 2 图2 9 一次消息传递过程2 3 图3 1 b o e r l a g e 9 2b n 3 2 图3 2a l a r mb n 模型3 4 图3 3a l a r m b n 1 模型3 4 图3 4a l a r m b n 2 模型3 4 图3 5a l a r m b n 3 模型3 5 图4 1d b n 3 个时间片的基本结构3 8 图4 2 动态贝叶斯网d b n 6 3 9 图4 3 w a t e rd b n 4 3 图4 4 推理过程中的w a t e rd b n 化简4 4 表2 1 表2 2 表3 1 表3 2 表3 3 表4 1 表4 2 表格清单 上下文独立的例子1 3 节点删除顺序表2 2 p = h m ( 叶子节点) 一3 1 口= t f ( 中间节点) 3 2 口= h t ( 根节点) 3 2 节点c 在各个时间片的概率值4 5 节点h 在各个时间片的概率值4 5 独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工作及取得的研 究成果。据我所知，除了文中特别加以标注和致谢的地方外，论文中不包含其他人 已经发表或撰写过的研究成果，也不包含为获得 盒理王些太堂 或其他教 育机构的学位或证书而使用过的材料。与我一同工作的同志对本研究所做的任何贡 献均已在论文中作了明确的说明并表示谢意。 学一磅俨呷柳瓤叫年钿 学位论文版权使用授权书 本学位论文作者完全了解金蟹王些态堂有关保留、使用学位论文的规定，有 权保留并向国家有关部门或机构送交论文的复印件和磁盘，允许论文被查阅和借 阅。本人授权佥壁王些太堂可以将学位论文的全部或部分内容编入有关数据库进 行检索，可以采用影印、缩印或扫描等复制手段保存、汇编学位论文。 ( 保密的学位论文在解密后适用本授权书) 日 学位论文作者毕业后去向； 工作单位： 通讯地址： 导师繇辰 签字日期：刀年月i f 电话： 邮编； 孝 日 佳， 纠钿 一外 致谢 值此论文完成之际，衷心的感谢我的导师张佑生教授! 在这三年多的 学习和研究工作中，张老师给予了我精心的指导和亲切的关怀，使我的研 究工作有了明确的目标，使我对研究工作有了正确的态度，并且论文中的 很多思想都是在张老师引导和启发下产生的。张老师广博的学识、开阔的 学术思维、严谨的治学精神和踏实诚恳的工作作风，为我树立了榜样，时 刻激励着我，并深深地影响了我! 在此对张老师表示衷心的感谢! 同时感谢图形图像研究室的江涛、侯顺风、习雅思、王良燕、洪沛霖 同学以及所有的师弟师妹们，感谢他们给予我的热情支持和帮助! 还要感谢计算机与信息学院的徐静老师、曹航老师、王新生老师以及 其他老师在日常事务中提供的帮助。 最后，由衷地感谢我的父母这些年对我的培养和支持! 感谢弟弟妹妹 给予我的帮助，感谢和祝福所有支持或帮助过我的老师、同学、亲人和朋 友们! 作者：刘俊娜 2 0 0 7 年5 月 第一章绪论 1 1 贝叶斯网络的研究与发展 建立能像人一样思维的计算机系统，是人们梦寐以求的事，人工智能研究 者对此进行了长期不懈的研究。他们在这方面的研究中遇到了很多问题，例如， 如何更好地学习、表达知识以及如何在实际中有效地应用知识就受到普遍的关 注。对于某些知识来说，存在信息不完备、背景不足、模糊以及信息中含有噪 声等问题，即存在不确定性。这种知识被称为不确定知识。传统的不确定知识 表示模型有模糊逻辑、可信度方法和神经网络等等，在实际应用中取得了不错 的效果。但也存在某些局限，如知识处理与推理计算的时间较长，模式单一等 等。 贝叶斯理论是由1 8 世纪数学家和神学家r e v t h o m a sb a y e s 在1 7 6 3 年第一次提出的。数学描述公式如下： 尸f ie 力= 只日1 0 4 只e f e c ) e ( e fc ) ( 1 1 ) 这里，给定背景先验知识c 和证据e ，就可以更新假设日的概率。左边 的p 口i e ，一是后验概率，是在考虑了应加在c 上的效果后日的概率。p 佴l 砂 是只给定c 下，日的后验概率。p 陋j h 称为似然度，是在假设日和背景知识 c 为真情况下证据e 的概率。最后，p 陋i 砂是独立于日的，可以认为是一个 规范化比例因子。 人们很早以前曾经利用过有向无环图( d i r e c t e d a c y c l i e g r a p h ，d a g ) 表示 法。最先，遗传学家s e w a l lw r i g h t t l o 】提出了种叫路径分析的表示因果关系的 图形化方法，这后来成为了经济学、社会学、心理学方面对因果关系的固定的 表示模型。i j g o o d t l l l 曾经用有向无环图来表示有分布式原因的二值变量所组 成的因果关系网。而统计学家为了寻找一种对可能性表有意义且有效的分解， 利用这种网络建立模型，并称之为递归模型。影响图则是为了进行决策分析而 发展的另一类有向无环图的应用，它包括事件节点和决策节点。有向无环图在 这些应用中的主要作用是提供一个对概率函数有效描述。一旦网络配置完成， 随后的所有计算可以通过概率表达式的符号操作来完成。 1 9 8 2 年，p e a r l 开始注意到有向无环图可以作为一种计算结构。并因此可 以作为一种认知行为模型1 5 1 。他通过一个分布式方案示范了树状网络的概率更 新，目的是为了对阅读理解的分布处理进行建模。其中自上而下和自下而上的 推理被结合起来形成一致的解释。这种双重推理模型是贝叶斯网络( b a y e s i a n n e t w o r k s b n ) 更新的核心。这也是贝叶斯理论的中心思想。 后来，贝叶斯网络在逻辑和认知领域没有引起进一步注意，但却在专家系 统上受到了广泛的重视。这种协调双向推理的技术填补了专家系统在7 0 年代 后期的一项空白，并使贝叶斯网络在这一领域真正繁荣起来。8 0 年代以来， b n 以其坚实的理论基础，自然的知识结构表达方式，灵活的推理能力，方便 的决策机制而成为近年来人工智能、专家系统、模式识别、数据挖掘、软件测 试川等领域的研究热点。该模型不仅有着坚实的概率论理论基础，同时又能够 很好地同专家头脑中的知识结构相对应，因此有着重要的应用价值和广阔的应 用空间。在模式识别中，利用最简单的贝叶斯网络一朴素贝叶斯网络( n a i v e b a y e s i a nn e t w o r k ) 构造的分类器，分类能力与经典的c 4 5 分类器【4 j 不相上下。 在数据挖掘中，利用贝叶斯网络的学习算法，既可以脱机对数据进行分析整理， 也可以在线更新数据。贝叶斯网络学习数据中隐含的因果关系为知识的挖掘提 供了更有力的工具。在专家系统领域，最早p a t h f i n d e r 系统【3 】咧就是以贝叶斯 网络为基础建立起来的，该系统主要用于6 0 多种淋巴疾病的诊断，涉及1 0 0 多种症状；后来发展起来的i n t e r n i s t i 系统，可以诊断多达6 0 0 多种常见疾 病。在商业应用领域，以微软为代表的一批公司，已将贝叶斯网络应用到了自 己的产品中。早在1 9 9 5 年，微软就推出了第一个基于贝叶斯网络的专家系统， 即用于幼儿保健的网站m i c r 0 no n p a r e n t t ”，使父母能自行诊断幼儿的疾 病。1 9 9 6 年，微软提供了w i n 9 5 中打印机故障的在线诊o n l i n e t r o u b l e s h o o t e r s t 2 1 系统，其中一个包含5 0 多个节点的贝叶斯网络，涉及打印机出现的四到五种 主要故障，可为每种故障可以提供十多种可能的原因。m i c r o s o f to f f i c e 软件中 的幽灵小助手也是贝叶斯网络在实际中应用的典例，它根据以往的使用经验及 时地为用户提供不同的帮助主题，如当一个用户在对一个表格进行操作时，系 统会相应地给出关于表格格式的提示。此外，贝叶斯网络在决策支持系统、软 件开发过程的软件测试、网站的智能导航、故障诊断、文档筛选、图像解释、 滤波、平滑、预测等方面也有着广泛的应用。 1 2 贝叶斯网络介绍 贝叶斯网( b a y e s i a nn e t w o r k s ，b n ) 也称为信念网( b e l i e fn e t w o r k s ) ，概率网 ( p r o b a b i l i t yn e t w o r k s ) 、因果概率网( c a u s a lp r o b a b i l i t yn e t w o r k s ) 和因果图 ( c a u s a ld i a g r a m ) 等。贝叶斯网络是用来表示变量间连接概率的图形模式，它提 供了一种自然的因果信息表示法，用以发现数据阃的潜在关系。贝叶斯网络作 为一种有向无环图，其中节点表示问题域的随机变量，有向边表示节点间的条 件依赖关系。多连通的贝叶斯网络是指在有向无环图中至少存在这样两个节点， 他们之间的路径不唯一。 贝叶斯网的网络结构揭示了研究领域对象的结构性质，有助于深入理解领 域问题；网络结构蕴涵的条件独立性有助于认识事件之间的序关系。此外，还 可以从网络结构的因果语义中学习到事件间的因果关系，从而预测某些行为的 可能效果。其网络拓扑结构直接由全概率分布函数决定。 贝叶斯网络作为一种图模型，具有图模型的大多数性质。下面先对图模型 进行简单的介绍。 图模型是概率理论和图论的结合，可以用来处理贯穿于应用数学和工程中 的不确定性和复杂性问题，在机器学习算法的设计和分析方面扮演着越来越重 要的角色。模块化的概念对图形模型来说是很重要的一个复杂系统是由多 个简单部分组成。概率理论提供了各个部分联合起来的黏合剂，保证系统作为 整体的一致性，并提供模型到数据的接口。图形模型的图论部分则提供了一个 可以应用于知觉的界面，通过它人们可以将高交互性的变量集和数据结构模型 化，还可以设计出有效的算法。 在统计学、统计力学、系统工程、信息理论和模式识别等领域中，许多经 典的多变量概率系统都是通用图形的特例典型的例子包括：混合模型、因 素分析、隐马尔可夫模型、卡尔曼滤波和i s i n g 模型。图模型提供了一种可以 将所有这些系统看作一个统一的根本实例形式的方法，并且为新系统的设计提 供了一种自然的框架。 图模型中的节点表示随机变量，节点间的弧表示条件依赖关系。两节点之 间若没有弧，则表示该两节点条件独立。图模型分为无向和有向两种。无向图 模型也称为马尔可夫随机域( m a r k o vr a n d o mf i e l d s ，m r f s ) ，它有一个简单的 独立性定义：若节点爿和b 在给定c 下是条件独立的，则a 和占相互独立。 贝叶斯网络由于考虑了弧的方向性，故其独立性定义比较复杂。贝叶斯网络可 用如下定义进行描述： 定义l ( b n ) ：贝叶斯网络是一个二元组b = ( s ，p ) ，其中：s 为贝叶斯网的 结构，是一个有向无环图，图中的每一个节点唯一地对应一个随机变量，节点 的状态对应随机变量的值，有向边表示节点( 变量) 之间的条件( 因果) 依赖关系； p 为贝叶斯网的条件概率集合p = p ( x i 刀曲，每个节点五都有一个条件概率表， 用来表示出对于其父节点集t f x i 的条件概率p 1 t f 。 对于一个有n 个节点的贝叶斯网，可以定义一个联合概率函数： ” p ( x l ，x 2 ，x 。) = r 】p ( x 。i 石。，) ( 1 2 ) ，- l 从定义中可以看出贝叶斯网络具有如下特性： l 、每个节点对应一个变量； 2 、节点之间通过有向边进行连接，由节点x 指向y 的有向边表示z 对】，具有直接影响关系； 3 、每个节点都具有相应的条件概率表，表示其父节点对它的具体概率 3 影响关系，其中结点z 的父节点是指所有通过有向边直接指向它的 节点。若x 为根节点，则其条件概率表为其自身的先验概率； 4 、贝叶斯网的结构是有向图，其中不包括有向环。 贝叶斯网络用贝叶斯理论给出概率函数的计算方法，有良好的数学基础， 同时用图形的方法描述数据间的相互关系，语义清晰、易于理解，这有助于利 用数据间的因果关系进行预测分析在数据挖掘中，贝叶斯网络可以处理不完 整和带有噪声的数据集，它用概率测度的权重来描述数据间的相关性，从而解 决了数据间的不一致性的问题。 贝叶斯网最典型的实例是下雨或洒水而路湿的例子。己知有两种情况可能 导致地面潮湿，下雨和洒水。如果地面潮湿而且天气晴朗，则表明是洒水产生 的结果。图1 1 所示，它包含四个二值结点：厕( 天气为阴天) 、噩( 刚洒过水) 、 为( 刚下过雨) 与凰( 草地湿) ，它们的取值均为：t 或f 。根据条件独立性， 该模型的联合概率分布可表示为： p ( x ) = ，( 蜀) p ( 工2x i ) p ( x 3i 蜀) ，( 墨l 丑2 ，k ) ( l 3 ) 图1 1关于草地湿的贝叶斯网络 图中，每个节点旁给出一个概率表，其中的一行表示一个节点在其父节点 给定取值情况下取t 或f 的概率，概率和为l 。节点蜀没有父亲节点，其概率表 中给出先验概率( 都取为0 5 ) 。图中所有节点的联合概率分布为： p ( x l 。x 2 。x h x 毋= p ( x 1 ) 4 p ( x 蕾x 1 ) p ( x 武x l , x 2 ) * p ( x 4 1 x 锻毋 = p ( x 1 ) p x 2 旺1 ) p g ( 1 ) p 僻4 2 x 移 其中第三个因式可以被简化是因为给定x i 时，x 2 和x 3 条件独立；最后一 个因式的简化是因为给定x 2 与x 3 时，) ( 4 和x l 独立。 4 1 3 贝叶斯网络的特性 由于贝叶斯网络是全概率分布和因果关系表示的完美结合，所以在机器学 习领域得到普遍重视。与许多其它方法相比，贝叶斯网络具备如下特性： l 、易于利用先验知识。先验知识是人们已经认识的自然界的现象和规律， 可用于对现实世界中的问题作进一步研究。当数据稀少时，先验知识尤显珍贵。 事实上，一些商业化系统( 如专家系统等) 的知识库直接来源于先验知识。贝 叶斯网络的直接因果语义使得转化领域专家知识有据可依，建造初始网络结构 的过程正规、自然，并且因果影响的不确定性可以转换成概率表达式。 2 、结果容易理解。与“黑匣子”知识表示方式( 如神经元网络) 相比， 贝叶斯网络可以解释为因果关系，可以用图形化的方式表示出来，不仅容易理 解，而且也有利于进行深入研究。 3 、具有较大的灵活性。没有确定的输入或输出节点，节点之间是相互影 响的，任何节点观测值的获得或者对于任何节点的干涉，都会对其它节点造成 影响，其影响大小可以通过推理计算来进行估计。 4 、知识获取与推理的复杂度较小。由于贝叶斯网络具有条件独立性的特 点，因此可以减少知识获取与推理的复杂程度。也就是说，在知识获取时，只 需要关心与节点相邻的局部网络图，在推理计算时，只要相关节点状态己知， 即可以估计该节点的概率信息。 5 、能有效的处理不完备数据集合。以贝叶斯概率理论为基础进行推理， 可将知识表示与知识推理结合起来，形成统一的整体。多种高效的推理算法使 贝叶斯网络能够处理多种概率查询，包括预言推理和诊断推理。贝叶斯网没有 查询方向的限制，没有输入变量和输出变量的区别。能够应用于不完备数据的 学习。而一般分类法和回归法( 如前向神经元网络和决策树) 只能进行一个方 向的推理计算，且不具备不完备数据的学习功能。 现在，神经元网络和隐藏马尔可夫模型等方法比较成熟，已广泛应用于模 式识别的各个领域。贝叶斯网络可与这些方法竞争高下，例如，神经元网络具 有的局部学习、并行计算及对噪音数据有效处理等优点，贝叶斯网络同样具有。 因此，贝叶斯网络有望成为符号主义和连接主义之间的桥梁。 贝叶斯网络的独特结构隐含着三种独立性：条件独立、上下文独立和因果 影响独立。c o o p e r 已经证明，对于一般问题的贝叶斯网络，其联合概率分布的 计算的复杂性是变量数目的指数关系，故后验概率的计算是n i p 难题1 9 1 。利用这 三种独立关系可把联合概率分布分解成颗粒更小的因式，从而达到节省存储空 间、简化知识获取、简化领域建模过程和降低推理计算复杂性的目的。 虽然贝叶斯网络的研究和应用取得了巨大的成就，但作为一种新的理论和 模型，它仍然存在着许多问题。无论在学习、推理，还是应用都存在一些不足 和缺陷。对贝叶斯网络的研究和应用多见于国外的报道，国内在这一领域与之 有一定的差距，仅就用于贝叶斯网络研究的软件环境来讲，国内研究人员大部 分使用的都是国外一些公司和大学编写的软件，如微软的m s b n ，m u r p h y 的 基于m a t l 曲的b a y e s i a nn e t w o r k st o o l b o x 等。 在贝叶斯网络的推理方面，人们提出了许多的推理算法，也开发出某些实 用软件。但也存在如下一些问题： l 、现有的推理算法都不同程度地存在一些不足，例如：联结树算法的空间 复杂性高、计算效率低；消息传递与汇聚算法对于多连通网络处理困难；桶消 元算法一次只能计算出一个变量的信度，而且寻找最优消元顺序也是一个n p 难题：仿真算法计算复杂性也比较高；等等。 2 、现有的贝叶斯网络的推理软件，其计算精度及计算速度往往达不到实际 应用的要求t 6 l 。 3 、确定先验概率表往往很困难，虽有大量不同的近似方法、折衷方法和敏 感性研究等帮助解决这个问题，但效果不很理想。 因此，如何利用贝叶斯网络的结构特点，设计出精确、高效的推理算法仍 是贝叶斯网络推理研究中的一个重要问题。此外，提供一个用于贝叶斯网络研 究和应用的软件环境也具有重要的意义。 l - 4 贝叶斯网络的主要研究方向 基于概率知识表达的贝叶斯网络，己成为人工智能不确定知识表示与推理 领域近几年来研究的热点，目前国内外的许多研究机构都对贝叶斯网络进行了 深入的研究。这些研究主要集中在贝叶斯网络的推理、基于贝叶斯网络的学习 和贝叶斯网络的应用三个方面。 贝叶斯网络的知识表示一定程度上体现了其推理方式。b n 的推理一般分为： 精确推理( 精确计算概率值) 和近似推理( 近似计算概率值) 两个部分，主要是研究 高效的推理算法。 学习是依据观察数据样本自动构造贝叶斯网络，从数据中自动建造贝叶斯 网络是当前非常活跃的研究领域。基于贝叶斯网络的学习一般分为参数学习和 结构学习两种情况，并且根据样本数据的不同性质又分为实例数据完备和不完 备两个方面。 贝叶斯网络的应用主要包括：基于贝叶斯网络的知识表达、相应的软件工 具开发、基于实例的应用等。目前这些研究都取得了丰硕的成果，并逐步在实 际中得到应用。静态贝叶斯网络的应用已经相当普及，涉及到时间因素的系统 需应用动态贝叶斯网络进行解决。 6 贝叶斯网络的基础理论研究包括算法复杂性、知识工程、知识结构与表达、 学习和推理方法等几方面。 l 、计算复杂性 这方面的研究工作是关于贝叶斯网络学习、推理算法的复杂度，现有研究 认为，贝叶斯网学习、贝叶斯网的精确推理和近似推理都是n p 难题。需要研 究更为有效的学习算法与推理求解算法。 2 、知识工程 此方面的研究涉及推理的性能、灵敏度、网络冲突、概率引导以及故障查 找等。主要研究包括：结合定性和定量信息贝叶斯网络的概率引导，提高贝叶 斯网络模型的推断性能，提高中间状态的诊断推理灵敏度，建造两部分网络作 为假想模型用于贝叶斯网络上冲突检测。 3 、知识结构和表达 在知识结构和表达方面主要研究贝叶斯网络结构、独立性以及短暂性。对 知识结构的研究有：在有连续变量的贝叶斯网络中进行知识获取和推理、扩展 贝叶斯网络结构以计算概率密度函数、定性概率网络的推理以及在不确定性条 件下的决策影响图的表述。 4 、学习 在贝叶斯网络的学习方面主要涉及学习的算法，如归纳、估计、链图等。 有关的研究包括：使用模拟数据集合的贝叶斯网络的归纳学习，关于质量测量 的贝叶斯网络学习算法的特性，用于学习的系列链图，研究参数独立性的贝叶 斯网络学习，在多动因随机域中使用估计方法学习，学习贝叶斯网络的样本复 杂度，采用局部结构学习贝叶斯网络，以及用于神经连接的对数模型的贝叶斯 学习。 5 、推理 推理是根据已有贝叶斯网络和先验概率表数据计算后验概率分布，从而得 到实际问题的解。推理算法包括修正算法和更新算法，有精确推理算法和近似 推理算法。许多方法都是同时适用于修正算法和更新算法的。 1 5 研究内容及安排 在贝叶斯网络上的直接推理是一个n p 难题，多连通贝叶斯网络的推理计 算复杂度更高。而现实生活中的需要解决的问题大多是多连通的，现有的推理 算法的计算速度往往达不到实际应用的要求。如何利用贝叶斯网络的结构特点， 设计出高效的推理算法是贝叶斯网络研究的重要方向。本文在介绍现有贝叶斯 网络推理算法的基础上，分析它们存在的缺点和不足，并针对知名度很高的联 结树算法，提出了改进方案，目的就是要在不明显降低计算精度的前提下最大 7 限度提高计算速度。 以下各章节安排为： 第二章将对贝叶斯网推理的框架及其分类进行介绍，给出贝叶斯网研究中 所涉及的一些基本概念。对贝叶斯网精确推理的基本思想和当前的一些推理算 法进行介绍。 第三章针对贝叶斯网络推理中的联结树算法，提出了自适应联结树算法的 改进方案，在不降低计算精度的条件下最大限度的提高计算速度。本文算法采 用相对于查询节点的节点相关度来搜索影响较大的节点，同时考虑了距离影响 和证据节点的特殊性，使构造的子网比较合理，有利于提高推理计算速度和保 证较高的计算精度。我们将该算法在不同贝叶斯网上进行实验，取得了很好的 效果。 第四章将本文提出的算法应用于动态贝叶斯网络，取得了很好的效果。 第五章总结全文工作，给出进一步的研究打算。 8 第二章贝叶斯网推理 2 1 引言 当采用贝叶斯网模型解决实际问题时，首先要构造出符合问题的贝叶 斯网，然后通过该贝叶斯网进行问题的求解。这种应用b n 进行问题求解 的过程称为贝叶斯网推理。贝叶斯网推理是概率分布的计算过程，即“寻 求给定条件下事件发生的概率”，也称为信念更新。这里的信念指的是后 验概率。简单地说，在给定模型中计算目标变量的后验概率就是贝叶斯网 推理。 贝叶斯网可以进行双向推理，即既可使用诊断知识也可使用预言知识 进行推理。前者称为“诊断推理”，后者称为“预言推理”。以“感冒”和 “发烧”这一因果关系为例，当测量出“发烧”而估计“感冒”为诊断推 理，当诊断出“感冒”而推断可能“发烧”是预言推理。 在推理中处理的是概率，而非空间的状态，因此推理是否合理反应了 所使用的贝叶斯网数据结构是否符合。贝叶斯网的推理就是在给定一组证 据变量值的情况下，计算一个或者一组查询变量的概率分布。近似推理是 进行因果模式、诊断模式、多原因模式和混合模式推理的最优推理机制。 贝叶斯网的推理是在不完全信息条件下决策支持和因果发现的工具。 它以概率分布为基础，并认为所有变量的取值受概率分布的控制。人们结 合观察到的数据，对这些概率进行推算便可做出正确的决策。因为它提供 了一种基于证据支持的定量假设方法，不仅为那些直接操纵概率的算法提 供理论基础，而且也为分析那些没有明确的概率计算公式的算法提供理论 构架，因此，贝叶斯学习中的概率推理在机器学习中占有相当重要的地位。 贝叶斯网推理( 概率推理) 问题的核心是计算( 后验) 条件概率分布。 若设所有变量的集合为x ，证据( e v i d e n c e ) 变量集合为e ，查询( q u e r y ) 变量集合为q ，则贝叶斯网推理的任务就是在给定证据变量集合e - - e 的 前提下计算q e q 的条件概率分布。可形式化描述为： p ( qle ：p ) ：丛堕坚旦 ( 2 1 ) 。 。p ( e = p 1 在此基础上，贝叶斯推理还可以解决以下几种问题： 1 、b uf b e l i e fu p d a t i n g ) 问题：给定证据节点后，计算得到变量的条 件概率，称为变量的信度更新。在实际应用中，可为信度给出明确的解释， 信度更新是贝叶斯网络推理的主要任务。 2 、m p e ( m o s tp r o b a b l ee x p l a n a t i o n ) 问题：给定证据变量集e 求解 o = x 、e 的最大概率指派。形式化描述为：给定e = e ，计算o = 9 a r g m a x ( p ( o = o ie = e ) ) 。o = x 、e 表示变量集x 中除证据变量集e 外 的其余变量集合。 3 、m p h ( m o s tp o s t e r i o rh y p o t h e s i s ) 问题：给定证据变量e 和一组 假设h 求解最大概率后验假设。形式化描述为：给定e = e ，计算h = a r g m a x ( p ( h = h i e = e ) ) 。 4 、m e u ( m a x i m i z et h ee x p e c t e du t i l i t y ) 问题：给定一效用函数u ( q ) ， 求解决策变量集合d 的某一使效用函数最大化的指派。形式化描述为： 给定e = e ，计算d = a r g m a x ( p ( u ( q ) i d = d ) ) 。 2 2 贝叶斯网推理的概率论基础 l 、条件概率 条件概率是概率论中的一个重要概念，它表示事件a 已发生的条件 下，事件b 发生的可能性，用符号记为：p 俾l 砂。 定义2 1 设a 、b 是两个基本事件，且尸口j 0 ，则称 础= 船 ( 2 2 ) 为事件a 已发生的条件下事件b 发生的条件概率。 若q 表示事件的全集，根据条件概率的定义，则得出以下几个性质： 1 ) p 佃1 矽= l ； 2 ) 若a 与b 为互斥的两个事件，则p 口i = o ： 3 ) p ( a 1 9 = p 例。 2 、先验概率 定义2 2 设b l ，b 2 ，b 。为样本空间s 中的事件，若b f 发生的概率 p ( b ，) 可根据已有数据的分析或者根据先验知识估计得到，则称尸陋为先 验概率。 先验概率p ( b ，) 的值以过去的实践经验和认识为依据，在实验之前就 可以得到或确定。 3 、后验概率 定义2 3 设占1 ，历，毋为样本空间s 中的事件，则在事件a 发生的 情况下目发生的概率p ( b ，阻) ，可根据先验概率p ( b 。) 和观测信息通过调整 得到。通常将p 佃f l 刎称为后验概率。随着样本信息的不断变化，后验概 率也不断的更新。前一次的后验概率将作为再次调整时的先验概率使用， 从而得到新的后验概率。这是一个不断更新、反复调整的过程。 1 0 4 、全概率公式 设实验e 的样本空间为s ，其中b l ，b 2 ，b 。为e 的组事件，这些 事件互不相容，且b ，u b 2 u u b 。= s ，p 俾j d ( i = 1 ，2 ，n ) ，则有 全概率公式： p ( 4 ) = p ( alb o p ( b i ) + p ( ai 岛) p ( 岛) + + ，( 4fb ) p ( 峨) = p ( a ie ) p ( e ) ( 2 3 ) i = l 其中，a 为任意事件。 5 、联合概率 设a 、b 为两个事件，则它们的联合概率为： p ( a b ) = p ( bi4 ) p ( 4 )( 2 4 ) 联合概率可以扩展到多个事件( 变量) 的形式。 6 、贝叶斯定理 设实验e 的样本空间为s ，a 为e 的事件，事件口l ，b 2 ，风互不相 容，口，u 历u u 风= s ，且p 俾 d ( i = 1 ，2 ，n ) ，则根据乘法定 理和条件概率有： p ( a b j ) = p ( aj e ) p ( e )( 2 5 ) 粥协a 警 ( 2 6 ) 将全概率公式代入( 2 6 ) 可得： p ( 马j 彳) ：_ ? ! 生_ 里盟f = 1 ，2 ，珂( 2 7 ) p ( a | b j ) p ( b j ) j = l 这就是重要的贝叶斯公式，在式( 2 7 ) 中，p 陋一的值称为先验概率， p ( b i i a ) n 值称为后验概率，从先验概率推导出后验概率就是运用贝叶斯公 式来实现的。 7 、链规则 设随机变量集合x 一，扔，别，用新表示蜀的取值，则变量 局，局，的值分别为x j ，x 2 ，的概率为一个联合概率p ( x l = x l ， x 2 = x 2 ，五。) 。在实际应用中，联合概率都满足一定的条件独立性， 依据条件概率链来表达联合概率，可以得到表达式： 尸( 蜀，也，乃) = 兀p ( x il 五_ i ，x i ) ( 2 8 ) i = 1 式( 2 8 ) 通常称为链规则。 8 、概率公理 1 ) 任意概率值p ，满足p c 0 ，1 】，即 0 p 1 2 ) 恒真命题的概率为l ，恒假命题的概率为0 ，即 p ( t r u e ) = 1 p ( f a l s e ) = 0 3 ) 命题的析取式的概率计算如下： p ( a v b ) = p ( a ) + p ( b ) - p ( a b ) 由这三条公理，就可以推导出概率的所有其他的性质。 2 3 贝叶斯网中的独立关系 贝叶斯网是联合概率分布的简化表示形式，可用于计算变量空间的任 意概率值。当变量数目很大时，运用联合概率分布公式进行计算通常是不 可行的。利用贝叶斯网的独立因果影响关系可解决这个难题。贝叶斯网中 的条件独立、上下文独立及因果影响独立这三种独立关系可把联合概率分 布分解成更小的因式，从而达到节省存储空间、简化知识获取和领域建模 过程、降低推理过程中计算复杂性的目的。因此可以说，独立关系是贝叶 斯网的灵魂。 2 3 1 条件独立关系 贝叶斯网的图形结构表达出变量间的条件独立关系，其中每个节点在 已知其父亲节点取值的条件下独立于所有非子孙节点。利用条件独立关 系，贝叶斯网把联合概率分布分解成若干个条件概率的乘积。由于每个条 件概率涉及的变量数日很少，故可大大简化联合概率分布的计算。 2 3 2 上下文独立关系 贝叶斯网的任一节点x 都带有一张条件概率表，在其父节点集“x 的每种取值情况下给出其每一种取值的概率。p ( 并i 靠x ) 条件概率表中 的条件概率数目与父亲节点数目成指数关系，并且无法捕捉条件概率分布 的某些规律。例如，在表2 1 中，在u = t 时，不需要考虑v ，w 的取 值，这时最多只需要5 个条件概率值，而不是8 个。在一些知名的贝叶斯 网产品中已经注意到这类问题，如微软的贝叶斯网建造工具，其知识获取 接口引入特殊机制，使用户容易给出各节点的条件概率，减少工作量。 在表2 1 中，u = f 时，x 与n 矽相关：u = t 时，x 与n 矽独 立，这是另一种独立关系上下文独立关系，它是某些变量取特定值之 1 2 后，其余变量之间存在的独立关系。贝叶斯网的结构可以表达出条件独立 关系，但对上下文独立关系无能为力。不过，通过条件概率的其它表示形 式，如条件概率树等，也可以表示这种关系。实质上，条件独立关系可以 看作是一种特殊的上下文独立关系，i ( z 明e ) 表示一旦已知e ，无论其 值是什么，兄y 条件独立。 图2 1上下文独立的例子 表2 1 上下文独立的例子 u矿w p t x ) ttt p l ttf p l tft p l t f f p j ftt p 2 ftf p 2 fft p 3 fff p 4 定义2 4 ；上下文独立关系设zj r ，z ，c 是两两互不相交的随机 变量集合，给定z 及上下文c e v a l ( c ) ，如果p 俘lz ，c ，矽= p 俩iz ， c j ，则x ，l ，是上下文独立的，记做c 佃，y lz ，c ) 。 由定义可以看出，当c 为空时，上下文独立变成特殊的条件独立。 2 3 3 因果影响独立关系 贝叶斯网中的有向孤是一种因果关系，表示父节点对子节点的直接影 响，子节点的取值，在最坏的情况下，需要给出的条件概率数目与父节点 数目成指数关系。一些情况下，父节点( 原因) 之间相互合作，对子节点 ( 结果) 共同产生影响。更多情况下，各个父节点独自对子节点起作用， 我们说父节点对子节点的影响是因果独立的。 定义2 5 ：因果影响独立我们说节点x 的各个父亲nx l ，n x 。对于x 是因果影响独立的，如果对应于“x 1 ，耳x m 存在和x 有 相同取值范围的随机变量，s 。，并且下面两个条件成立： 1 ) 对于每个j ，p 。仅仅在概率意义上依赖于”x i ，在“x i 条件下独 立于所有其它的x j 及5 ，( j i ) ，即： ，( q ， 刀墨，万h 。，歹。，7 k ，q ，t l ，岛+ 1 ，) ) 1 3 2 ) 存在一个定义域是x 的取值范围，且具有交换律