（计算机应用技术专业论文）基于贝叶斯网络的试卷分析.pdf

摘要 考试是一个完整的教学过程中不可缺少的组成部分，是对教和学的质量的检 验。对考试结果进行研究，促进我们对教学过程的反思，进而找到下一步工作的 方向和改进的措施。 贝叶斯网络( b a y e s i a nn e t w o r k ) 是p e a r l 提出的一种基于概率论和图论的不 确定知识表示模型，具有清晰语义的网络结构，揭示领域对象的内在结构，是复 杂全概率分布的紧凑表示方式。其坚实的理论基础、知识结构的自然表达方式、 灵活的推理能力、方便的决策机制及有效的学习能力使其成为一种主要的不确定 知识的处理方法。 本文的主要工作是进行基于贝叶斯网络的试卷分析实验，试验主要用到的工 具是基于m a t l a b 语言编写的b n t 软件包，该软件包提供了许多贝叶斯网络学 习的底层基础函数库，支持多种类型节点的精确推理和近似推理，以及参数学习 和结构学习等功能。通过实验研究，分析了平时出勤率、作业提交率等五方面因 素对试卷成绩的影响。 关键词：试卷分析贝叶斯网络概率推理b n t 工具包 a b s t r a c t t e s ti san e c e s s a r yc o m p o n e n to ft h ew h o l et e a c h i n gc o u r s e i ts e r v e sa sac h e c k o nt h ee f f e c to fb o t ht h et e a c h i n ga n dt h el e a r n i n g t h ei n v e s t i g a t i o no nt h er e s u l to f t h et e s tw i l lh e l pu sr e f l e c to nt h et e a c h i n gc o u r s e ，a n df i n dw h a tt od on e x ta n dh o w t om a k ei m p r o v e m e n t s t h eb a y e s i a nn e t w o r k ( b n ) p r o p o s e db yp e a r li san e wm e c h a n i s mf o r u n c e r t a i nk n o w l e d g er e p r e s e n t a t i o na n dm a n i p u l a t i o nb a s e do np r o b a b i l i t yt h e o r ya n d g r a p ht h e o r y b ni sn e t w o r ks t r u c t u r ew i t hc l a r i t ys e m a n t i c s i te x p l o i t st h es t r u c t u r e 0 ft h ed o m a i nt oa l l o wac o m p a c tr e p r e s e n t a t i o no fc o m p l e xj o i n t p r o b a b i l i t y d i s t r i b u t i o n i t ss o u n d p r o b a b i l i s t i c s e m a n t i c s e x p l i c i te n c o d i n g o fr e l e v a n c e r e l a t i o n s h i p s ，i n f e r e n c ea l g o r i t h m sa n dl e a r n i n ga l g o r i t h m st h a ta r ef a i r l ye f f i c i e n ta n d e f f e c t i v ei np r a c t i c e ，a n dd e c i s i o n - m a k i n gm e c h a n i s mo f f a c i l i t y , h a v el e db nt oe n t e r t h ea r t i f i c i a li n t e l l i g e n c e ( a i ) m a i n s t r e a m t h ep r e s e n tt h e s i si st om a k ea ne x p e r i m e n t a la n a l y s i so ft h et e s tp a p e rb a s e do n b a y e s i a nn e t w o r k t h em a i nt o o l k i tu s e di nt h i se x p e r i m e n ti sb n ts o f t w a r es u i t e c o m p i l e dw i t hm a t l a b t h i ss o f t w a r es u i t ep r o v i d e su sw i t hal o to fb a s i cf u n c t i o n s e t sf o rb a y e sn e t w o r kl e a r n i n g i ti ss u i t a b l ef o rt h ea c c u r a t ea n da p p r o p r i a t el o g i c s o fv a r i o u st y p e so fj o i n t s ，a n di ta l s oh a st h ef u n c t i o no fp a r a m e t e rl e a r n i n ga n d s t r u c t u r el e a r n i n g f r o mt h ee x p e r i m e n tw ec o m et ot h ec o n c l u s i o nt h a tf i v ef a c t o r s i n c l u d i n gs t u d e n t a t t e n d a n c ea n df u l f i l l m e n t o f - h o m e w o r kh a v eg r e a ti n f l u e n c eo n t h e i rs c o r e s k e yw o r d s ：t e s tp a p e ra n a l y s i s ，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 ci n f e r e n c e ，b n t 独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工作和取得的 研究成果，除了文中特别加以标注和致谢之处外，论文中不包含其他人已经发表 或撰写过的研究成果，也不包含为获得苤盗盘堂或其他教育机构的学位或证 书而使用过的材料。与我一同工作的同志对本研究所做的任何贡献均已在论文中 作了明确的说明并表示了谢意。 学位论文作者签名： 御亭 签字同期： 功印年驴月 学位论文版权使用授权书 本学位论文作者完全了解丞盗盘鲎有关保留、使用学位论文的规定。 特授权苤鲞盘堂可以将学位论文的全部或部分内容编入有关数据库进行检 索，并采用影印、缩印或扫描等复制手段保存、汇编以供查阅和借阅。同意学校 向国家有关部门或机构送交论文的复印件和磁盘。 ( 保密的学位论文在解密后适用本授权说明) 学位论文作者签名： 签字同期：矽口7 年多月乡l 同 导师签名： 辩嗍：哆锡月衫同 第一章绪论 1 1 试卷分析的意义 第一章绪论 考试是一个完整的教学过程中不可缺少的组成部分，是对教和学的质量的检 验。考试对教学有巨大的指挥作用。社会对考试有强烈的反响。对于考试的结果， 有必要进行认真地研究和分析。在试卷分析工作中，要运用考试理论和教学理论， 对考试结果进行研究，促进我们对教学过程的反思，进而找到下一步工作的方向， 和改进的措施。考试结果可以反馈出大量的信息，可以反映出整个教学过程的得 失。例如反映出各个教学环节的一些情况，反映出学生的基础和能力的状况、反 映出学生的学习特点和规律。我们在命题的时候，有多方面的设计。考试结果可 以反映命题和考试本身的一些情况，也就是测量工具、测量方法和测量过程的情 况。分析这些信息，能引起我们很多思考，可以形成一些认识，提出一些观点和 建议。可以供领导决策时参考，供自己做为制定工作策略的依据，对学校老师和 学生提供指导。可见，试卷分析是一件很重要的工作。 1 2 试卷分析的原则 第一要看对象，有针对性。不同对象例如：局长、区长、学校领导来了，要 听汇报。这是一种。面向本学科的任课老师，这又是一种。对学生，又是一种。 这三种试卷分析，对象不同，内容和各方面的要求就有所不同。 第二是不搞走过场的表面文章。目的是不断地提高我们工作的科学性，有效 地指导工作。 第三是要有科学的统计，定性与定量结合。光定性说一些看法、观点，没有 数量的分析不行。要有科学统计的数据，定性与定量结合。 第四要深入思考有关的问题，形成观点和见解。不就事论事，不列流水帐， 不上习题课。观点和见解是来自于对一些问题的思考。对考试和试卷演变的轨迹， 对学生的情况，教学的规律，都可以做一些研究，得出分析和判断。另外，结合 对工作过程的回顾，对工作经验的回顾，对于工作得失的思考，在试卷分析里也 可以得出一些认识。 第五是要有理论的指导。所谓理论不外乎考试理论和教学理论。这两方面的 理论，都说来话长。现在这方面的书挺多的。咱们由浅入深、由易到难，要掌握 第一章绪论 一点这个东西。再做试卷分析的时候，有理论指导，就可以站得高一点，也能更 深入一点。如同检验产品质量，工人检验，技术员检验，工程师检验，想法的深 度、广度是不一样的。 1 3 贝叶斯网络的综述 1 3 1 贝叶斯网络简介 贝叶斯网络有时叫做因果网( c a u s a ln e t w o r k ) ，是一个有向无环图。该网络 的节点用随机变量标识，连接节点的弧认为是表达了直接的因果关系。近几年来， 人工智能和统计界已经开始研究学习贝叶斯网络的各种方法，以使其应用于其他 的领域。因为贝叶斯网络对知识的表达是隐含的，既以结构和概率蕴含知识，只 有通过推理才能最终获得感兴趣的结论、概念或原因，而且这种推理是非常灵活 的。 贝叶斯网络表示了世界中客体的条件概率分布与因果联系，其所蕴含的不确 定性知识及规则是进行不精确推理的主要工具。贝叶斯网络的结构就蕴含了规 则，而伴随节点的条件概率则表达了某种知识。贝叶斯网络在统计学、决策分析、 人工智能等领域已有越来越多的应用。 1 3 2 贝叶斯网络的应用现状 贝叶斯网络主要应用在以下几方面【l 】： ( 1 ) 应用于专家系统 贝叶斯网络提供专家水平的推理，模拟人的智能，解决专业领域内的实际 问题。例如贝叶斯网络在医学上的应用，其中典型的一个例子是p a t h f i n d e r ，用来帮助进行“淋巴节点”症状的诊断分析，另一个例子是c p c s b n 远程医 疗系统，该系统有4 4 8 个节点和9 0 8 条弧，优于世界主要的远程医疗诊断分析方 法。 ( 2 ) 应用于数据挖掘 使用贝叶斯网络帮助聚类分析。近些年来人们发现用贝叶斯网络进行数据挖 掘能从数据库中挖掘多层、多点的因果概念关系，这是客观世界普遍存在的一种 关系。由于数据挖掘在本质上具有很强地统计色彩，且贝叶斯网络又起源于贝叶 斯统计学，因此数据挖掘与贝叶斯网络的结合自然是顺理成章。 ( 3 ) 应用于故障诊断 根据发生的故障特征，找出发生故障的原因，根据经常发生的故障或系统现 2 第一章绪论 有的状态，进行实时监控和故障预防。例如，微软视窗软件中的疑难解答，可以 帮助用户解决所遇到的软硬件问题。 ( 4 ) 应用于学习 掌握贝叶斯推理原理，对学习有很大帮助，可以帮助初学者快速掌握事件发 生的因果关系和事件之间存在的规律。 1 4 试卷分析的工作过程 作者进行试卷分析的工作流程如下： 第一步：就刚刚考过的期末考试，抽取2 0 0 名学生的信息，包括：期末考试 总成绩、客观题得分、主观题得分、平时出勤率、作业提交率和是否是留级生。 第二步：将这2 0 0 名学生的信息汇总成一个e x c e l 文件。 第三步：将学生信息进行离散化处理。主要操作是将影响试卷成绩的五个因 素按照平时教学的实际情况进行分段，分成两段的用0 和l 表示，分成三 段的用1 、2 、3 来表示。 第四步：将处理好的数据先拷贝到一个文本文件，目的是为了向m a t l a b 软件导入数据。也可以直接向m a t l a b 导入，用到的命令是x l s r e a d ( ) ，但只有 在m a t l a b 6 5 以后的版本才有这个命令。 第五步：为了根据这些数据之间的关系建立贝叶斯网络，做一些初始化的工 作，例如：指定节点个数，指定节点次序以及指定节点的最大父节点个数等。 第六步：利用b n t 软件包编程建立贝叶斯网络。 第七步：对建立起来的贝叶斯网络进行参数学习。 第八步：把建好的贝叶斯网络和学习得到的参数以图形的形式显示出来。 1 5 论文结构 第一章绪论，主要阐述试卷分析的意义和原则，以及作者进行试卷分析的 工作过程。 第二章试卷分析的工作基础，主要阐述了试卷分析的现状，贝叶斯网络的 推理基础，以及对试卷分析所用到的主要工具b n t 软件包的介绍。 第三章贝叶斯网络，主要介绍了贝叶斯网络的结构，贝叶斯网络的三种推 理方法以及贝叶斯网络的参数学习。 第四章试卷分析，主要应用e x c e l 软件和b n t 软件包实现了试卷分析的 试验，得出了贝叶斯网络和相应的参数。验证了“作业提交率”等五大因素对试 第一章绪论 卷成绩的影响。 第五章结束语，给出了全文的研究结论与下一步的工作计划。 4 第二章试卷分析的工作基础 第二章试卷分析的工作基础 本章着重介绍一下试卷分析的现状，贝叶斯网络的一些基础知识【l 】【2 1 ，包括 贝叶斯理论的起源，贝叶斯公式，贝叶斯假设，贝叶斯网络的性质以及贝叶斯网 络存在的问题。最后介绍了试卷分析的主要工具b n t 软件包。 2 1 试卷分析的现状 目前，大多数的试卷分析是做试题分析。为了说明检测的结果有效，要对检 测工具试题和检测过程做科学的说明。这就是试题分析。实际上每年高考以后， 我们都做试题分析。每年高考试题评价会，那就是评价试题，分析试题的设计、 试题的特色、试题对教学的导向，评判命题的质量。此外，教育科研中，对测试 还有的特殊的要求。要研究测试的设计、测试结果或统计结果的分析，对于有效 性的检验等等，单有一套理论和方法。 2 2 贝叶斯推理基础 2 2 1 贝叶斯理论的起源 贝叶斯统计源于英国数学家贝叶斯撰写的一篇具有哲学性的论文：a ne s s a y t o w a r d ss o l v i n gap r o b l e mi nt h ed o c t r i n eo f c h a n c e ( 解决几率学说中某问题的短 文) 。后来的学者在此基础上发展了一整套的统计推断的原理和方法，这些就是 贝叶斯统计。一些学者更是极力主张将贝叶斯的方法作为全部统计推断的合理基 础，这些学者所形成的学派被称之为贝叶斯学派。贝叶斯学派在2 0 世纪形成， 当时人们认识到客观概率( 频率的稳定性) 与主观概率( 人的信念) 之间既有共 性又有个性。2 0 世纪数学的公理化倾向影响了统计界，对概率的公理化经过许 多人的努力，最终由科尔莫戈洛夫( a n k o l m o g o r o v ) 完成，且得到了普遍的认 同；概率是正则化的测度。但是，对主观概率应该用什么样的公理来描述，还没 有比较一致的看法。 1 9 5 8 年英国历史最长的统计杂志b i o m e t r i k a 全文重刊贝叶斯的论文，表明 第二章试卷分析的工作基础 贝叶斯学派已经成为一支不可忽视的队伍。贝叶斯学派的工作对决策理论的发展 是重要的，对经典学派的理论和方法也提供了许多有益的思路，出现了相互批评 又相互支持、共同发展的局面。当前，贝叶斯统计获得了广泛的应用，贝叶斯学 派已经成为统计学中一个有广泛影响的学派，该学派的一些思想已渗入到自然、 社会科学的不少领域，并产生了新的分支。 2 2 2 贝叶斯公式 定理 设4 ，4 ，4 为样本空问q 的一个划分，_ ep ( 4 ) 0 ( i = 1 ，2 ，开) 。则对 于任何一件事情b ( p ( b ) 0 ) ，有 p ( 4i b ) ：# 皿业洁1 2 ，” e e ( a - ) p ( ba a ) i = 1 有条件概率和全概率公式： 1 ) 条件酶p ( 41 驴等2 掣 2 ) 全概率公式：p ( b ) = p ( a i ) p ( b i a ；) 把全概率公式代入条件概率，得到： 2 2 3 贝叶斯假设 p ( 4i 口) ：筝型：盟盟，( f - 1 知) 。 p ( 彳，) p ( b 1 4 ) 。 j = 1 众所周知，应用贝叶斯公式时，需要知道参数分的分布一先验分布，然后 才能导出后验分布。贝叶斯认为当人们对参数0 没有任何信息时j 乡在其可能变 化的范围内机会是均等的，即0 的先验分布是其值域上的均匀分布，这一假设就 是贝叶斯假设。 对贝叶斯假设存在很多争议。其一是均匀分布的存在性：均匀分布在有限区 域内是存在的，但在无限区域内还存在吗? 其二是贝叶斯假设认为乡没有任何先 验信息，既然没有先验信息，又哪儿来的先验分布呢? 这些都是经典学派怀疑贝 叶斯学派的原因所在。解决无信息先验分布就成了贝叶斯学派面临的一个难题。 尽管如此，贝叶斯假设却有其合理性。对某些应用，以贝叶斯公式导出的结 果似乎更符合实际。例如一个试验做了7 次，7 次都成功，另一种试验做了4 次， 4 次都成功，按经典概率这两个试验做成功的概率都是1 ，这好像不太容易被人 6 第二章试卷分析的工作基础 们所接受，人们对7 次试验成功的信心肯定要比4 次试验成功的信心足，但是都 不能认为成功率是1 。若用贝叶斯假设，采用目的后验期望作为秒的统计，可导 出口的估计量秒= 三竺，因此有下列结果： n + 2 7 次试验，7 次成功，则口= ! ； 9 “ c 4 次试验，4 次成功，则护= 二： 6 从这里可以看出两者之间的明显差别，而且成功率永远小于1 。这个例子说 明了贝叶斯假设的合理性。 2 2 4 贝叶斯网络的性质 贝叶斯网络主要有以下性质【3 】： ( 1 ) 条件独立性( c o n d i t i o ni n d e p e n d e n c e ) 假设贝叶斯网络中任一节点，在给定其父节点的情况下，条件独立于任何 k 的非子孙节点集合，该独立性记为：，( k ，彳( k ) f 尸( ) ) ，也就是说， p ( kl 彳( k ) ，p ( ) ) = p ( l 尸( k ) ) 。其中符号的含义为： 彳( k ) ：任- - v i 的非子孙点集合； 尸( ) ：v i 的父亲集合； p ( i ) ：条件概率。 给定一个集合v ，如果一个变量v i 是条件独立于另一个变量v i ，则有 p ( 形il ，v ) = p ( v jv ) 。根据条件概率的定义，有p ( 杉l 巧，v ) p ( v ji 功= p ( k ，iv ) 。 对于上式的证明如下： p ( v i f v j 胪帮5 篇端 融础州鹏i v ) 眢吲巧，i v ) 又有i ( v i ，v j l v ) ，则p ( v “v j ，v ) = p ( v “v ) ，综合上式，有以下结论成立： p ( k ，巧iv ) 2 p ( v ji ，) p ( k1 ，) 注意到杉和k 是对称出现的，因此，给定v ，说条件独立于巧，也就是说 巧条件独立于杉这足以说明给定v ，k 和巧是条件独立的。 不失一般性，给定集合1 ，如果每个变量条件独立于所有其他的变量，那么 变量k ，k 是相互条件独立的。由于 7 第二章试卷分析的工作基础 k p ( k ，圪i v ) - = n p ( 所l 所一- ，y ，) f 1 且每个v j 是条件独立与其他给定的变量，于是有 膏 p ( k ，屹，kv ) = h p ( ev ) i = 1 当v 为空时，有 p ( k ，圪i v ) = p ( k ) p ( 屹) p ( 圪) 所以说变量是元条件独立的。 ( 2 ) 基于概率的严格推理 贝叶斯网络是一种不确定性知识表达和推理的模型，其推理原理基于贝叶斯 概率理论，推理过程实质上就是概率计算。 ( 3 ) 知识表示为定性知识和定量知识 定性知识是指网络的结构关系，表达事件之间的因果联系。定性关系( 也就 是因果关系，贝叶斯网络结构图) 主要来源于专家经验，专业文献和统计学习。 定量知识包括边缘概率和条件概率，表达原因对结构的影响程度。定量关系( 概 率) 主要来源于统计计算、专业文献和专家经验。当数据不丰富时，可以使用专 家估计加统计修正的方法进行定量。当数据丰富时，使用期望极大化算法 ( e x p e c t a t i o nm a x i m i z a t i o n ，e m ) 进行定量。使用该算法，贝叶斯网络还可以 用于对数据缺失的情况进行处理。 ( 4 ) 知识获取与推理的复杂度较小 由于贝叶斯网络具有条件独立性，因此可以减少知识获取与推理的复杂程 度。也就是说，在知识获取时，只需要关心与节点相邻的局部网络图，而在推理 计算时，只要知道已知节点的相关节点的状态，即可估计该节点的发生概率。 2 3b n t 软件包简介 m a r l a b 作为一种拥有高速性能数值计算能力的通用科技计算语言，简单易 用且功能强大，程序移植性比较好。它集中了数值分析、符号计算、图视能力、 文字处理、可视化建模和实时控制能力，适合多学科、多部门的发展需求。基于 m a t l a b 的贝叶斯网络工具箱b n t 是k e v i ne m u r p h y 基于m a t l a b 语言开发的 关于贝叶斯网络学习的软件包，提供了许多贝叶斯网络学习的底层基础函数库， 支持多种类型的结点( 概率分布) 、精确推理和动态模型。b n t 是个完全免费的软 8 第二章试卷分析的工作基础 件包，其代码完全公开，系统的可扩展性良好h 1 。 2 3 1 贝叶斯软件包b n t 中贝叶斯网络的表示方式 由于m a t l a b 的基本数据单元是维数不加限制的矩阵，用户无需考虑大量的有 关矩阵的运算该采用何种算法等低层总是，更不必深入了解相应算法的具体细 节，因而对用户算法语言方面的要求十分宽松。因此，在贝叶斯软件包b n t 中， 采用的贝叶斯网络的表示方式为矩阵方式。即用矩阵的形式表示贝叶斯网络的结 构，若结点i 到结点j 有一条弧，则对应矩阵中( i ，j ) 值为1 ，否则为0 。如图1 所示的贝叶斯网络，其结构的矩阵表示形式如图2 - 1 所示晦】。 图2 - 1 一个贝叶斯网络和其矩阵 2 3 2 贝叶斯软件包b n t 中贝叶斯网络结构学习算法函数 贝叶斯软件包b n t 为人伙提供了较为丰富的结构学习函数，它们是口1 ： ( 1 ) 学习树扩展贝叶斯网络结构的t a n c 算法l e a ns t r u c tt a n ( o ( 2 ) 数据完整条件下学习一般贝叶斯网络结构的k 2 算法l e a r ns t a r c tk 2 ( ) 、 贪婪搜索g s ( g r e e d ys e r a c h ) 算法l e a m _ s t r u c t _ _ g s ( ) 和爬山h c ( h i l lc l i m b i n g ) 算法l e a r ns t r c th c ( ) 等。 ( 3 ) 缺失数据条件下学习一般贝叶斯网络结构的最大期望e m ( e x p e c t a t i o n m a x i m i z a t i o n ) 算法l e a r ns t m c te m ( ) 和马尔可夫链蒙特卡罗h c m c ( m a r k o v c h a i nm o n t ec a r l o ) l e a r ns t r e e tm e m o ( ) 算法。 2 3 3 贝叶斯软件包b n t 中贝叶斯网络参数学习算法函数 贝叶斯软件包b n t 同时还提供了较为丰富的参数学习函数，它们是陷1 ： ( 1 ) 完整数据时，学习参数的方法主要有两种：最大似然性估计 l e a m _ _ p a r a m s ( ) 和贝叶斯方法b a y e s _ u p d a t e _ p a r a m s ( ) ； ( 2 ) 数据缺失时，如果已知网络拓扑结构，用e m 算法来计算参数，倘若未 知网络拓扑结构，贝叶斯软件包b n t 提供的方法是结构最大期望s e m ( s t r u c t u r a l 9 、llf_ij o l o l o l l i o 0 l d o o o o o o o o o o o 第二章试卷分析的工作基础 2 3 4 贝叶斯软件包b n t 中贝叶斯网络的推理机制及推理引擎 为了提高运算速度，使各种推理算法能够有效应用，b n t - i - 具箱采用了引擎 机制，不同的引擎根据不同的算法来完成模型转换、经化和求解瞄1 。整个推理过 程如图2 - 2 所示。 l 确定贝叶新同! l i 遁挣推艘习l 簟 l l 输入摧瑕证裾 i l 糸* 后验饭辜 b 喇嚏一m k j i 嘲( c l a n s ) 自t g l n e m j w e ei n fa a l l i a e ( 1 l n e t ) i | 川i 知l c 哪；嘲嘲眇p 唁一k 叫簟_ 瞄_ 啪啊出锄 m - m m s i 1n o d c s ( e n s l n e , c h s s ) 图2 2b n t 软件包的推理过程 贝叶斯软件包b n t 提供了多种推理引擎，主要的有： ( 1 ) 联合树推理引擎j t r e e i n f e n g i n e ( ) ； ( 2 ) 全局联合树推理引擎g l o b a l j o i n ti n fe n g i n e ( ) ； ( 3 ) 信念传播推理引擎b e l p r o p _ i n f _ e n g i n e ( ) ； ( 4 ) 变量消除推理引擎v a r _ e l i mi n fe n g i n e ( ) ； l o 第三章贝叶斯网络 第三章贝叶斯网络 贝叶斯网络有时叫做因果网、( c a u s a ln e t w o r k ) ，是一个有向无环图。该网络 的节点用随机变量标识，连接节点的弧认为是表达了直接的因果关系。近几年来， 人工智能和统计界已经开始研究学习贝叶斯网络的各种方法，以使其应用于其他 的领域。因为贝叶斯网络对知识的表达是隐含的，既以结构和概率蕴含知识，只 有通过推理才能最终获得感兴趣的结论、概念或原因，而且这种推理是非常灵活 的。本章就将讨论贝叶斯网络的各种推理方式。 3 1 贝叶斯网络的结构 一个典型的贝叶斯网络由两部分组成口1 ： ( 1 ) 有向无环的图形结构s ，其中每一个节点代表一个变量、属性、状态、 客体、命题或其他的实体，节点之间的弧反映了变量间的依赖关系，指向节点x 的所有节点称为x 的父节点。一个贝叶斯网络规定图中的每个节点r 条件独立 于由杉的父节点给定的k 的非后代节点构成的任何节点子集。也就是说，假设 彳( k ) 是图中非_ 后代节点的任何节点集合，设p ( k ) 是图中k 的直接双亲。图仅 仅是陈述对图中的所有k ，( k ，彳( 杉) l 尸( k ) ) 的一种方式。除了被称为贝叶斯网 络之外，还有另外一些术语：因果网( c a u s a ln e t w o r k ) ，信任网( b e l i e fn e t w o r k ) 。 图3 一l 显示了一个贝叶斯网络的结构。其中匕，k 是k 的父节点，而k 又是，k 的 父节点。 图3 一l 一个贝叶斯网络 ( 2 ) 与每个节点相联系的条件概率表( c p t ，c o n d i t i o n a lp r o b a b i l i t yt a b l e ) ， 该表列出了此节点相对于其父节点所有可能的条件概率。贝叶斯网络约定以节点 第三章贝叶斯网络 形的父节点为条件，k 与任意非杉子节点条件独立。按此约定，则有刀个节点的 贝叶斯网络联合概率分布为： p ( k ，k ) = 兀p ( ip a o ，；l 其中，p a i 表示节点k 的父节点集合。 3 2 贝叶斯网络的推理模式 贝叶斯网络的推理通常是从先验知识入手，按贝叶斯规则沿网络弧线层层演 进计算出需要的概率。按贝叶斯学派的观点，概率推理本质上就是信任的传播哺1 。 按推理方向来说，贝叶斯网络有三种基本的推理模式。 3 2 1 因果推理 这种模式推理又叫做自上而下的推理，是从先验概率开始的正向推理过程。 之所以称为因果推理，是因为贝叶斯网络中相连的两个节点表达式一种直接的因 果关系脚。以图3 - 1 为例，求概率p ( 9 5ly ，) 。 p ( v sl 矿3 ) = p ( v sv 2 , v 3 ) p ( v 2y 3 ) ，其中， r 2 p ( v 5 ，v 2y 3 ) 2 p ( v 5 ，v 2i 矿3 ) + p ( v 5 ，- - , v 2v 3 ) ， v 2 p ( v 5i 矿2 ，矿3 ) p ( y 2i 矿3 ) 2 p ( v 5v 2 ，v 3 ) p ( v 2i 矿3 ) + p ( v 5i - - , v 2 ，v 3 ) p ( - a v 2iy 3 ) 所以，p ( v 5 iv 2 ，v 3 ) p ( 矿2v 3 ) = p ( v 5 iv 2 , v 3 ) p ( 矿2 ) + p ( 矿5 l y 2 ，9 3 ) p ( - - ，v 2 ) y 2 因果推理的过程可总结如下： ， ( 1 ) 按照给定证据的v 和其所有双亲的联合概率，重新表达给定证据的询问节 点v 的所求条件概率，即将询问节点的其他父节点加入到询问节点，条件 不变，对新节点的所有状态求和。 ( 2 ) 回到以所有双亲为条件的v 的概率，利用贝叶斯规则将和式中的每一项展 开，重新表达这个联合概率。 3 2 2 诊断推理 这种推理又叫做自下而上的推理，在这种模式下，事先已经知道了结论，推 断出可能引发该结论的原因，好像医生通过病人的状况查出病因一样。例如：求 1 2 第三章贝叶斯网络 概率p ( y ：i y s ) ：由贝叶斯公式得：p ( y 2i 儿) 2 型紫，其中，p ( 儿l 如) 要利用因果推理求得。所以，诊断推理的主要一步是将所求概率转换成因果推理 的形式。 3 2 3 辩解推理 这种推理方式又叫做解释推理。当问题中已经包含了原因和结果，这时如果 要推断其它的导致该结果的原因，就需要运用辩解推理。辩解推理可概括为：在 诊断推理中运用因果推理。例如，在举积木的例子中， “圳= 趔筹高掣 一p ( - 、mi 坷，也) p ( 埘i1 l ) p ( 也) p ( 坷，卅) 一p ( _ 1 mi 扭，也) p ( 侣) p ( 正) p ( 馏，m ) 辩解推理从本质上来讲，是因果推理和诊断推理的混合口1 。 3 3 在p o l y t r e e 网中的概率推理 一个p o l y t r e e 网是一个有向无环图( d a g ) ，在该d a g 的任何两个节点之 间，顺着弧的每一个方向之间只有一条路径。所以，p o l y t r e e 网也叫作单路径 贝叶斯网。图3 2 的网络就是一个p o l y t r e e 。 再给出一个典型的单路径贝叶斯网。如图3 2 。 p 5 图3 - 2 一个单路径贝叶斯网络 第三章贝叶斯网络 可以看到，有些节点仅通过q 的双亲节点连接至：i j q ，就说这些节点在q 的上 方，其他的节点仅通过q 的直接后继连接至_ i j q ，就说这些节点在q 的下方，而且 没有一条路径可以连接q 上方的节点和q 下方的节点。这就是单路径贝叶斯网络 的特点i 引。 单路径贝叶斯网的推理方式有三种，分别是： ( 1 ) 所有的证据节点在询问节点的上方，例如求p ( qlp 5 ，p 4 ) 。 ( 2 ) 所有的证据节点在询问节点的下方，例如求p ( qf 尸1 l ，p 1 2 ，p 1 3 ，p 1 4 ) 。 ( 3 ) 在询问节点的上下方都有证据节点。例如求 p ( ql p 5 ，p 4 ， 尸1 1 ，p 1 2 ，p 1 3 ，e 1 4 ) 。 在此对这三种推理方式不再进行具体的阐述。 3 4 学习贝叶斯网络 学习是人工智能各研究领域的特征之一，贝叶斯网络也不例外。学习贝叶斯 网络就是要寻找一种网络，能按某种测度最好地匹配一个数据训练集( t r a i n i n g s e t ) 互，e 是所有( 至少有一些) 变量值的实例集合。一般而言，寻找一种网络 包括寻找一种有向无环图( d a g ) 结构和获得与d a g 中每个节点相关的条件概 率表( c p t ) 。前者称为网络结构学习，后者称为网络参数学习乜1 。 3 4 1 无丢失数据的c p t 学习样本统计法 如果有充足的训练样本，只要计算每个节点和其双亲的采样统计信息。假如 给定双亲p ( k ) ，想得到某个节点k 的c p t ，可以用v ，指称k 的值。k 的表和其 具有的不同值( 小于1 ) 一样多。作如下假定：在布尔表达式中，对每个节点仅 有一个c p t 。 设k 有t 个父节点，因为每个双亲有两个可能值，则在表中有2 ；项。用向 量变量p 指称与k 的双亲有关的变量，用向量值p i 指称这些变量的值。采样统计 结果p ( 杉= m1 只= 易) ，由互中有k = 和p = b 的采样数除以有p = 易的采样数 得到。为了学习c p t ，仅仅将实际的这些采样统计结果用于网中的所有节点。 3 4 2 无丢失数据的c p t 学习贝叶斯方法 样本统计法属于经典学派的思想：概率表现为频率的稳定值【9 1 。然而，多数 研究者更倾向于用贝叶斯方法来学习贝叶斯网络。按贝叶斯学派的观点：当参数 目一无所知时，人们对其有一个先验概率的认识，然后通过贝叶斯规则求出该参 数的后验概率。 1 4 第三章贝叶斯网络 已知一个离散变量y 有r 个状态，现有少的所个观察值序列 y l ，y 2 ，) ， 如果交换序列中任意两个值的顺序都不改变变量取值的联合概率，则该序列称为 可交换的。序列可交换假设保证了产生数据的过程是不随时间的改变而变化的。 当序列可交换是，d ef i n e t t i 于1 9 3 7 年证明了：存在参数集 ，= 铭，钻：，：，) ，满足下面三个条件u 0 1 ： g ：。) 0 ，k = - i ，r ；= l ；p ( 乃= ko ，善) = 嘭；。 公式( 3 1 ) 七= 1 善是一种抽象的符号，代表对论域的先验知识或信息。公式( 3 1 ) 表明，参数 。 使得序列中各观察值彼此条件独立，而且无论是哪一次观察，y = k 的概率都是 艮。按博雷尔强大数律，可以把1 9 1 ，：。看作是y = k 观察数的最终比率。 满足上面条件的序列可以看作是特殊形式的随机样本具有参数o 。的r 维多元样本。当，= 1 时，序列称为二元样本，像抛硬币的统计结果就是一个典型 的例子。而且每一次抛硬币的结果都是相互独立的。 3 4 3 有缺失数据情况下的参数学习 从不完整的数据中学习贝叶斯网络的参数，如果想得到精确的计算是很网难 的，目前主要采取一些近似的算法，如：( 1 ) m o n t o c a r l o 方法( 或采样法) ，( 2 ) e m 算法，( 3 ) 概率推理法，( 4 ) g a u s s i a n 近似。 3 4 3 1m o n t e c a r l o 方法或采样法 这类算法能够获得比较精确的结果，但得需要和长时间才能够收敛。其中有 代表性的是g i b b s 采样法。用g i b b s 采样法获得近似后验参数的方法分以下几 步进行： ( 1 ) 随机的初始化每个事例中的丢失数据的值，从而得到一个完整的数据集 d c ； ( 2 ) 选择一个在原数据集中没有观察值的数据嘞( 变量x i 在事例，中，为是随 机初始化的值) ，去掉其初始的状态并利用下面的概率分布对其进行重新 的赋值【11 】： 碱 ，= 最箍高 z j 表示z 的某一种状态的值，表示置的所有的状态值。 1 5 第三章贝叶斯网络 ( 3 ) 按上式选择具有最大概率的作为置的新的填充值，反复重复这一过程， 直到把所有的丢失数据都填充完，得到新的完整数据集砭。 ( 4 ) 利用前面的公式和数据集砭计算后验参数和概率分布p ( o 。i4 ，m ) 。 ( 5 ) 迭代前四步，用p ( o 。i 砭，m ) 的平均值作为最后的近似值。 3 4 3 2e m 算法 e m 算法最初i 扫d e m p s t e r ，l a i r d 和r u b i n 于1 9 7 7 年提出，用于不完整数据模 式下计算最大似然估计【1 2 】，是一种非常简单，具有广泛使用性的算法。e m 算法 是“求期望一最大化”的循环迭代过程，其中期望步骤是根据已有的参数发现所 期望的完整数据，最大化步骤则重新估计参数。每次“求期望一最大化”迭代都 改进了参数的似然性，当达到局部极值时，算法收敛。 为了描述方便，用x = x 1 ，x 表示n 个事例的完整变量集合， 、， y = y l ，】， 表示有观察值的变量集。 、j e m 算法的具体步骤如下所示【1 3 】： ( 1 ) n = 0 ，初始化o ( o ) ； ( 2 ) 根据当前的数据和参数o ( m ，计算牙的联合分布；n = p ( x i y = y ，o m ，聊) ； ( 3 ) 针对p ”，计算充分统计量吆的期望值& ( ) ； ( 4 ) 如果进行的是最大似然计算，则选择o 佃+ 1 。使得p ( 砬io ，m ) 最大，每个参 数满足： 加+ 1 )夸，( ) 嗷“k 下止_ l ( 吆) k = l 。 如果进行的是最大后验计算计算，则选择o ”1 使其后验密度最大，因此每个参 数按下式选择 钞一 若n q i ( 铝州一雏) z 孝( 善是一小正数) ，则n - - n + l ，转2 ：否则得结果o c 州) i = l j = l k = l 退出。 其中前三步是求期望的过程，第四步是最大化的过程。 1 6 第三章贝叶斯网络 3 4 3 3g a u s s i a n 近似 这种方法一般用来计算大样本的近似，其基本思想是：随着样本数量的增加， 有下面的关系成立：p ( o 。i v ，掰) p i o ，历) p ( o 。i 历) 【1 4 】，所以，后验被近似 为变量的高斯分布，可以令： g ( o 。) = l o g ( p ( do ，脚) p ( o ，i 聊) ) 公式( 3 2 ) 并定义 。是使g ( o 。) 取得最大值的o ，同时也使p ( o 。i d ，m ) 取得最大值( 这 就是参数最大后验概率值) 。应用向量形式的泰勒公式，并取基本项和二阶项， 可得： g ( o 。) g ( 孬。) 一丢( o 。一面。) 么( 。一面。) 7 公式( 3 3 ) 其中，a 是g ( o 。) 在o 。取值石。时的海森( h e s s i 锄) 矩阵，( o 。一面。) 7 是( 0 。一舀。) 的转置。综合公式( 3 2 ) 和公式( 3 3 ) ，可得后验参数的近似高斯分布： p ( o 。ld ，聊) o cp ( d0 ，聊) p ( o 。l 聊) 只要找到o 。和矩阵a ，计算就可以完成。 3 4 4 贝叶斯网络的结构学习 公式( 3 - 4 ) 近些年来，人们对从数据中直接学习贝叶斯网络结构的兴趣越来越浓，也出 现了很多学习方法，综合来说，结构学习的方法可分为以下两类【1 5 】： ( 1 ) 渐进正确的学习，这类方法将学习视为约束条件的满足问题。这种方法是 努力估计数据属性间条件独立的性质，然后建立网络来展现所观察到的依赖或独 立的关系。当然，这种依赖关系要用某些条件独立性测试来度量。这种方法试图 通过分解节点之间的依赖关系来获取最优的网络结构。这些算法的优点是计算效 率比较高。 c h e n g e ta l 1 6 】提出的信息论的方法其算法的复杂度为o ( n 2 ) 。这和 其它一些算法如启发式搜索相比更有效率。 ( 2 ) 将学习视为最优化问题，使用启发搜索的方法建造模型并用得分方法来评 价该模型。首先要定义一个评分函数，该评分函数描述了每个可能结构对观察到 的数据的拟合。评分函数有许多，如贝叶斯评分、基于熵的评分以及最小描述长 度的评分。对一个b n 结构评分通常有两个相对立的目标，首先，希望b n 的结 构尽可能简单，即网络进可能的稀疏。其次，希望网络有关节点状态的概率尽可 能的精确，以利于精确的推导。精确度的增加一般会导致网络更稠密同时算法复 1 7 第三章贝叶斯网络 杂度变大。 3 4 4 1 评分函数 在这里着重讨论一下基于描述长度的m d l 评分函数。该评分方法的原理是 r i s s a n c n 1 7 j 在研究通用编码时提出的。问题是这样提出的：存在一个训练集三， 把训练集中的变量值编码成一个位串，如果把互发送给某个人，考虑需要多少位。 有效的编码利用要发送数据的统计属性，这些统计属性正是作者企图在贝叶斯网 络中创建的。根据信息理论，一组数据三，按照一个给定贝叶斯