（计算数学专业论文）基于周期的贝叶斯网络预测模型.pdf

摘要 摘要 动态贝叶斯网络是对动态系统进行建模和状态估计的重要工具之一。其最突出的优点 是：能方便处理不确定性，并且其预测结果也更可靠更合理，因此成为近年国内外研究的热 点。许多统计模型的变量变动具有一定的特性，例如周期性等。股市的“艾略特波浪理论” 就是状态时问序列变化规律的一个特例。然而，现有贝叶斯网络预测模型大多忽视了这些性 质。本文应用时间序列分析的一般方法，通过分析状态变量周期性，分别从三个不同的角度 建立了基于周期数据的贝叶斯网络预测模型。本文的贡献包括以下几个方面： 对于有周期特性的数据，通过增加相应的状态变量提出一种基于周期性数据的动态贝叶 斯网络预测模型。由于充分考虑到原问题的周期特性，因此有效的提高了预测的精确度。特 别的，应用于我国l 乜力增长率问题，该模型取得较好的效果。 对于周期变动明显的数据，通过引入周期状态转移矩阵，提出了一种基于周期的一阶 隐马尔可夫模型，分析并给出了该模型的似然计算、隐状态估计和模型训练的算法。最后， 数据模拟验证该模型能有效提高预测的精确度和模型的似然度，并加快模型训练的收敛速 度。 对丁贝叶斯网络结构有周期特性的数据，通过引入周期性网络结构，提出了一种周期性 动态贝叶斯网络结构学习。最后，数据模拟验证该模型能有效提高预测的精确度。 关键词：周期性，动态贝什i 斯网络，状态转移矩阵，一阶隐马尔可夫模型，k 2 算法 a b s t r a c t a b s t r a c t t h e o r yo fb a y e s i a nl e a r n i n gd e p i c t sa l lf o r m so fu n c e r t a i n t yb yp r o b a b i l i t y , a n d a c h i e v e sl e a r n i n ga n dr e a s o n i n gp r o c e s st h r o u g ht h er u l e so fp r o b a b i l i t y t h er e s u l t so f b a y e s i a nl e a r n i n gs h o wa st h ep r o b a b i l i t yd i s t r i b u t i o no fr a n d o mv a r i a b l e s ，i tc a nb e u n d e r s t o o da so u rt r u s te x t e n ti nd i f f e r e n tp o s s i b i l i t i e s t h ep a p e r n t r o d u c e st h eb a s i c t h e o r yo fb a y e s i a nl e a r n i n g ，i t sc u r r e n tr e s e a r c hs i t u a t i o n ，t h eb a y e s i a nn e t w o r k s l e a r n i n gp r o c e s sa n de x p r e s s i o na b i l i t y i t sr e a s o n i n gm e c h a n i s mw a ss t u d i e da n d d i s c u s s e di nt h ei ) a p e r o nt h i sb a s i s ，t h ep a p e rs t u d i e ss e v e r a lk e yp r o b l e m si nt h e o r yo f b a y e s i a nl e a r n i n g t h ec o n t r i b u t i o n sg oa sf o l l o w t h i sp a p e rp r e s e n t sad y n a m i cb a y e s i a nn e t w o r k sp r e d i c t i o nm o d e ib a s e do n p e r i o d i cd a t a o w i n gt oc o n s i d e r i n gt h ep e r i o d i cc h a r a c t e r i s t i co ft h eo r i g i n a lp r o b l e m ， t h en e wm o d e ii m p r o v e st h ep r e d i c t i o np r e c i s i o ne f f e c t i v e l y i np a r t i c u l a r , t h i sm o d e l a c h i e v e sb e t t e re f f e c ta sa p p l y i n gi ng r o w t hr a t eo fe l e c t r i cp o w e ri nc h i n a b yi n t r o d u c i n rap e r i o d i cs t a t et r a n s f e rm a t r i x af i r s t o r d e rh m mm o d e 【b a s e do n p e r i o d i c i t yi sp r o p o s e df o rt h ed a t aw i t he x p l i c i tp e r i o d i c i t y t h ea l g o r i t h m s ，i n c l u d i n g l i k e l i h o o dc o m p u t a t i o n ，h i d d e ns t a t ee s t i m a t i o na n dm o d e lt r a i n i n g ，a r ea l s op r e s e n t e d a n da n a l y z e d f i n a t y ，n u m e r i c a ls i m u l a t i o ne x p e r i m e n t ss h o wt h a tt h en e wm e t h o d e f f i c i e n t l yi m p r o v e st h ep r e d i c t i n gp r e c i s i o na n dt h em o d e ll i k e l i h o o d m o r e o v e r , i ta | s o i n c r e a s e st h ec o n v e r g e n c er a t eo ft h em o d e lt r a i n i n g b yi n t r o d u c i n gap e r i o d i cn e t w o r ks t r u c t u r e ，ad y n a m i cb a y e s i a nn e t w o r k ss t r u c t u r e l e a r n i n gb a s e do np e r i o d i c i t yi sp u tf o r w a r df o rt h ed a t aw i t he x p l i c i tp e r i o d i c i t y f i n a l l y , t h ep r o p o s e dm o d e ii m p r o v e st h ep r e d i c t i o np r e c i s i o nj ns i m u l a t i o ne x p e r i m e n t k e yw o r d s ：p e r i o d i c i t y , d y n a m i cb a y e s i a nn e t w o r k s ，s t a t et r a n s f e rm a t r i x ，h i d d e n m a r k o vm o d e l ，k 2a l g o r i t h m 学位论文版权使用授权书 本人完全了解同济大学关于收集、保存、使用学位论文的规定， 同意如下各项内容：按照学校要求提交学位论文的印刷本和电子版 本；学校有权保存学位论文的e r j ) 昂l j 本和电子版，并采用影印、缩印、 扫描、数字化或其它手段保存论文；学校有权提供目录检索以及提供 本学位论文全文或者部分的阅览服务；学校有权按有关规定向国家有 关部门或者机构送交论文的复印件和电子版；在不以赢利为目的的前 提下，学校可以适当复制论文的部分或全部内容用于学术活动。 学位论文作者签名：刁每扳豸 伽罗年圳日 同济大学学位论文原创性声明 本人郑重声明：所呈交的学位论文，是本人在导师指导下，进行 研究工作所取得的成果。除文中已经注明引用的内容外，本学位论文 的研究成果不包含任何他人创作的、已公开发表或者没有公开发表的 作品的内容。对本论文所涉及的研究工作做出贡献的其他个人和集 体，均已在文中以明确方式标明。本学位论文原创性声明的法律责任 由本人承担。 学位论文作者签名： 年月日 第一章绪论 1 1 引言 第一章绪论 二十一世纪，各种技术如雨后春笋般出现，令人应接不暇，其中，信息技术尤为引人注 目。随着信息技术的到来，人们越来越意识到信息的重要性，同时如何有效的保存和利用大 量的信息成为我们不得不面临的问题。类似g 0 0 8 t e 和b a i d u 这样方便的网络检索工具【1 】 使得信息的保存和检索问题得以很好的解决，而网络的急速发展带来信息的爆炸式增长，面 对海量信息，人们突然之间感觉有些棘手。作为世界上最大的数据仓库之一的美国零售商系 统w a m a r t ，其数据容量在1 9 9 6 年就高达11 t b 2 ，2 0 0 0 年高达1 0 1 t b ，每天还以2 亿左 右的交易数据剧增。面对如此浩瀚的数据海洋，人们开始觉得很为难，一方面很难及时处理 过剩信息，如何进行信息取舍成为问题；另一方面在超大规模数据中检索有价值的信息成为 难题。很明显，仅靠数据库的查询检索【1 0 】机制和统计等分析方法已经远远不能满足人们的 需要。目前的数据库系统所能做到的只是对数据库中已有的数据进行存取，而人们需要的是 隐藏在这些数据之中的更重要的信息，包括关于这些数据的整体特征的描述及其发展趋势的 预测，因为这些信息在决策生成过程中具有重要的参考价值。这就需要一种新的技术和工具 来帮助我们智能地、自动地分析这些原始数据，把隐藏在大量数据背后的有价值的知识提取 山来，以便更好地为决策支持服务。 1 2 研究意义 信息中包含大量的数据，如何把大量的数据转化为有用的知识是我们面临的一个重要课 题。图形模式具有多功能性、有效性及开放性等特征，能有效地转化数据为知识，并利用这 些知识进行推理，以解决分类、回归、聚类、联合预测、依赖和因果分析等问题。图论模式 因其有效性已在软件智能化、医疗和故障诊断、金融风险分析、气象分析与预测、d n a 功 能分析及w e b 采掘等方面得到验证。作为图形模式的一种，贝叶斯网络具有图形模式的大 多数性质，很快就成为数据挖掘领域进行不确定性知识推理和建模的一个有效工具。自八十 年代开始，贝叶斯网络已经应用于专家系统，表示不确定知识和推理问题。随着数据库规模 的不断扩大，贝叶斯网络开始逐渐应用于大规模数据库的数据挖掘和知识发现，从而为决策 支持提供更强更有力的手段。到现在，贝叶斯网络已经成为数据库知识发现和决策支持系 统的有效方法之一。本文主要研究面向智能信息处理的贝叶斯网络的基础理论与方法研究， 并将其用于解决实际问题。 伴随着数字网络和计算机的普及，数据收集的速度越来越快，对堆积如山的数据的处理 与理解已经成为计算机科学家与工程师所必然面临的挑战。适应这一迫切的任务需求，数据 挖掘作为理论性与应用性结合最为密切的一个研究领域迅速的发展起来。本文研究贝叶斯学 习理论及其应用，具有以下意义： 贝叶斯学习理论将先验知识与样本信息相结合、依赖关系与概率表示相结合，是数据挖 掘和不确定性知识表示的理想模型。与数据挖掘中的其它方法如：规则表示、决策树、人工 神经网络等相比，贝叶斯学习还具有以下优点。 贝叶斯学习能够方便的处理不完全数据。例如考虑具有相关关系的多个输入变量的分类 或回归问题，对标准的监督学习算法而言，变量间的相关性并不是它们处理的关键因素，当 这些变量中有某个缺值时，它们的预测结果就会出现较大的偏差。而贝叶斯学习【s n 提供 第一章绪论 了较为直观的概率关联关系模型。 贝叶斯学习能够学习变量间的因果关系。因果关系是数据挖掘中极为重要的模式。有两 个原因：在数据分析中，因果关系有利于对领域知识的理解，在干扰较多时，便于做出精确 的预测。例如市场销售分析人员想知道增加广告投入是否能提高产品的销量。为回答这个问 题，分析人员必须清楚，在某种程度上广告投入是否是提高销量的原因。即使没有这方面的 实验数据，贝叶斯学习对这类问题的回答也是相当直观简单的，因为这种因果关系已经包含 在贝叶斯网络模型中了。 贝叶斯网络与贝叶斯统计相结合能够充分利用领域知识和样本数据的信息。任何从事过 实际建模任务的人都会知道先验信息或领域知识在建模方面的重要性，尤其是在样本数据稀 疏或数据较难获取的时候，一些商业方面的专家系统完全根据领域专家知识来构建就是一个 很好的例证。贝叶斯网络使用弧线表示变量间的依赖关系，用概率分布表表示依赖关系的强 弱，将先验信息与样本知识有机结合起来。 贝叶斯方法与神经网络模型相结合，有效的避免了数据的过分拟合问题。贝叶斯学习理 论在数据挖掘中获得了成功的应用。贝叶斯学习理论研究最大的动力就是它在实际应用方面 的巨大作用和潜力。目前，贝叶斯学习理论已成功地应用到智能用户接口、信息滤波、车辆 自动导航、武器制导、医疗诊断、经济预测和文本分类【6 】等诸多领域。 1 3 研究背景与现状 贝n t 。斯( r e v e r e n dt h o m a sb a y e s1 7 0 2 - 1 7 6 1 ) 学派奠基性的工作是贝叶斯的论文“关 丁儿率性问题求解的评论”。或许是他自己感觉到他的学说还有不完善的地方，这一论文在 他生前并没有发表，而是在他死后，由他的朋友发表的。著名的数学家拉普拉斯( l a p l a c e ， r s ) 用贝叶斯的方法导出了重要的“相继律”，贝叶斯的方法和理论逐渐被人理解和重视起 来。但是由于贝叶斯方法在理论和实际应用中还存在很多不完善的地方，因而在十九世纪并 朱被普遍接受。二二十世纪初，意人利的菲纳特( b d ef i n e t t i ) 及其英国的杰弗莱( j e f f r e y s ， h ) 都对贝叶斯学派的理论做出重要的贡献。第二次世界人战后，瓦尔德( w a d ，a ) 提出 了统计的决策理论，在这一理论中，贝叶斯解占有重要的地位：信息论的发展也对贝叶斯学 派做出了新的贡献。1 9 5 8 年英国最悠久的统计杂志b i o m e t r i k a 全文重新刊登了贝叶斯的论 文，二十世纪5 0 年代，以罗宾斯( r o b b i n s ，h ) 为代表，提出了经验贝叶斯方法和经典方 法相结合，引起统计界的广泛注意，这一方法很快就显示出了它的优点，成为很活跃的一个 方向。在这里值得一提的是，八十年代以后，人工智能的发展，尤其是机器学习【2 ，8 ，9 】、数 据挖掘的兴起，为贝叶斯理论豹发展和应用提供了更为广阔的空间。 尽管对于贝叶斯学派哲学上的观点还存在很多异议，然而它的思想和方法在社会生活和 生产实践中得到越来越广泛的应用却是不争的事实尤其是近年来，贝叶斯方法以其独特的 不确定性知识表达形式、丰富的概率表达能力、综合先验知识的增量学习特性等成为当前数 据挖掘众多方法中最为引入注目的焦点之一。 1 3 1 贝叶斯学习理论的基本观点 贝叶斯分析方法的特点是使用概率表示所有形式的不确定性，用概率规则实现学习和推 理。贝叶斯学习的结果表示为随机变量的概率分布。它可以理解为我们对不同可能性的信任 程度贝叶斯学派的起点是贝叶斯的两项工作：贝叶斯定理和贝叶斯假设。贝叶斯定理将事 件的先验概率与后验概率联系起来。假定随机向量x ，乡的联合分布密度p ( o ，z ) ，它们的 - 2 第一章绪论 边际密度分别为p ( x ) ，p ( o ) 。一般情况下设x 是观测变量，口是未知参数向量，通过观测 向量获得未知参数向量的估计，贝叶斯定理记作： p ( o i x ) = ( 乡) p ( x l 口)万( 秒) x p ( xi 口) p ( x ) 一p ( 臼) p o io ) d o ( n - ( o ) 是秒的先验分布) ( 1 1 ) 从上式我们可以看出，对未知参数向量的估计综合了它的先验信息和样本信息，而传统 的参数估计方法只从样本数据获取信息如最大似然估计。贝叶斯方法对未知参数向量估计的 一般过程为： 1 将未知参数看成是随机向量。这是贝叶斯方法与传统的参数估计方法的最大区别。 2 根据以往对参数p 的知识，确定先验分布n - ( o ) ，它是贝叶斯方法容易引起争议的 一步，因此受到经典统计界的攻击。 3 计算后验分布密度，做出对未知参数的推断。 在第2 步，如果没有任何以往的知识来帮助确定万( 9 ) ，贝叶斯提出可以采用均匀分布 作为其分布。即参数在它的变化范围内，取到各个值的机会是相同的，称这个假定为贝叶斯 假设。贝n 1 斯假设在直觉上易丁被人们所接受，然而它在处理无信息先验分布，尤其是未知 参数无界的情况却遇到了困难。经验贝叶斯估计e m ( e m p i r i c a lb a y e s i a ne s t i m a t o r ) 把经 典的方法和贝叶斯方法结合在一起，用经典的方法获得样本的边际密度p ( x ) ，然后通过下 式米确定先验分布万( 口) ： ， p ( x ) = i7 ( 口) p ( x lo ) d o 0 0 ( 1 2 ) 贝1 1 i 斯定理的计算学习机制是将先验分布中的期望值与样本均值按各自的精度进行加 权平均，精度越高者其权值越人。在先验分布为共轭分布的前提下，可以将后验信息作为新 一轮计算的先验，用贝i r l + 斯定理与进一步得到的样本信息进行综合。多次重复这个过程后， 样本信息的影响越米越显著。由丁贝叶斯方法可以综合先验信息和后验信息，既可避免只使 用先验信息带来的主观偏见和缺乏样本信息时的火量盲目搜索与计算，也可避免只使用后验 信息带来的噪音影响。因此，适用于具有概率统计特征的数据挖掘和知识发现问题，尤其是 样本难以取得或代价昂贵的领域。合理准确地确定先验，是贝叶斯方法进行有效学习的关键 问题。目前先验分布的确定依据只是一些准则，没有可操作的完整理论。在许多情况下先验 分布的合理性雨i 准确性难以评价。对于这些问题还需要进一步深入研究。 1 3 2 论文研究内容和组织结构 本文主要对运用贝叶斯学习理论的基本观点来发现数据之间潜在的模式进行了一些探 索性的i ：作。贝叫斯网络是表示和处理不确定性知识的理想模型。它的参数学习和结构学习 正在成为当前机器学习【1 1 ，1 2 ，1 3 】的热点。贝叶斯网络分类器作为分类知识发现的一个重要 方法，是贝叶斯学习理论研究的核心问题之一。 发现数据间隐含的、潜在有用的模式需要大量的标注样本。相对于获得未加类别标注的 样本来说，获得带有类别标注的样本则需要更高的代价，本文从尽量节省标注样本的角度提 - 3 - 第一章绪论 出了三种解决方案：主动贝叶斯分类器【1 5 】、贝叶斯潜在语义分析和贝叶斯模型选择。 本文的具体组织结构如下： 第一章、介绍贝叶斯学习理论的基本观点、研究现状及其研究意义 第二章、贝叶斯网的表示、学习和推理。贝叶斯网络是表示和分析不确定性知识的有效 工具，是用节点表示变量，用边来表示变量间概率依赖关系的有向无环图。分析了贝叶斯网 的语义特性，构建过程和推理机制。并着重讨论了贝叶斯网的参数学习、结构学习和网络推 理中的一些典型算法与研究现状。 第三章、本文提出一种基于周期性数据的动态贝叶斯网络预测模型。由于充分考虑到原 问题的周期特性，因此有效的提高了预测的精确度。特别地，应用于我国电力增长率问题， 该模型取得较好的效果。 第四章、对于周期变动明显的数据，通过引入周期状态转移矩阵，提出了一种基于周 期的一阶隐马尔可夫模型，分析并给出了该模型的似然计算、隐状态估计和模型训练的算法 最后，数据模拟验证该模型能有效提高预测的精确度和模型的似然度，并加快模型训练的收 敛速度。 第五章、对于贝叶斯网络结构有周期特性的数据，通过引入周期性网络结构，提出了一 种周期性动态贝叶斯网络结构学习。最后，数据模拟验证该模型能有效提高预测的精确度。 第六章、结论和本文进一步研究的展望。 一4 - 第二章贝叶斯埘络的表示、学习和推理 第二章贝叶斯网络的表示、学习和推理 贝叶斯网络是表示变量间概率依赖关系的有向无环图。贝叶斯统t , i 【1 6 】和图论的发展为 贝叶斯网络理论的引入提供了坚实的理论基础，而人工智能、专家系统和机器学习在实践中 的j 泛应用，成为j q , l 。斯网络产生和发展的催化剂。在贝叶斯网络建模中，两个关键的任务 是网络参数的学习和网络结构学习。从数据中学习贝叶斯网络是当前机器学习的热点问题之 一。贝叶斯网络推理实质上是回答任何给定证据下的查询问题，包括预测和诊断两个方面。 2 1 引言 贝叶斯网络是川米表示变量之间连接概率的图形模型，它提供了一种表示因果信息的方 法，长期以来一直被认为是人j r 智能领域中的一个重要的研究课题。贝叶斯网络综合考虑先 验信息和样本数据，充分地利用专家知识和经验，可以进行定性分析和定量分析。将主观和 客观有机地结合起来，避免了对数据的过度拟合，又避免了主观因素可能造成的偏见。将变 量之间潜在的关联性用简洁的图解模型【仃】表达出来表达的语义直观、清晰，推理的结果 和结论可信度强，便于解释和易于理解。经过近二十年的发展，贝叶斯网络已经形成相对完 整的推理算法和理论体系，目前成为人工智能和专家系统中的一个研究热点。贝叶斯网络由 结构和参数两部分组成，冈此，构建贝叶斯网络的学习主要也是结构学习和参数学习两部分， 本章主要侧重贝叶斯网络结构学习。 2 2 贝叶斯网络的基础理论 贝叫。斯网络是指基于概率分析和图论的一种不确定性知识【1 8 ，1 9 】的表达和推理的模 型，下面介绍一些相关的基本概念及定理、定义。 2 。2 1 概率论的基础知识 概率论由丁具有坚实的数学理论基础，是人工智能领域中处理不确定性问题的基础理论 之一，是目前处理不确定性问题的方法之一。 定义2 1 条件概率：设彳、b 是两个基本事件，且尸( 么) 。，则称p ( b i 爿) = 等 为枣什a 发生的条件下事件b 发生的条件概率。 定义2 2 先验概率：设蜀，岛，最为样本空间s 中的事件，p c b , ) 可根据以前的数据 分析得到，或根据先验知识估计获取，则称尸( e ) 为先验概率。先验概率是根据历史的资料 或主观判断所确定的各种事件发生的概率，该概率没能经过实验证实，属于检验前的概率。 先验概率一般分为两类，一类是客观先验概率，是指利用过去的历史资料计算得到的概率； 另一类是主观先验概率，是指在无历史资料或者历史资料不全的时候，只凭借人们的主观经 验来判断取得的概率。 5 - 第二章贝叶斯网络的表示、学习和推理 定义2 3 后验概率：设b ，岛，色为样本空间s 中的事件，则事件a 发生的情况下， e 发生的概率尸( 最ia ) ，可根据先验概率尸( e ) 和观测信息重新修正和。、一z ，- 1 0 ，通常 将尸( el 彳) 称为后验概率。后验概率一般是指利用贝叶斯公式，。结合调查等方式获取了新 的附加信息，对先验概率加以修正的更符合实际的概率。即得到信息之后再重新修正的概率。 定义2 4 联合概率：设彳、曰为两个事件，且尸( 彳) 0 ，则贝叶斯网络的表示它们的 联合概率为：p ( a ，b ) 二- p ( bi 彳) 尸( 爿) 。联合概率也叫乘法公式，是指两个任意时间的乘 积的概率，或称之为交事件的概率。 定义2 5 全概率公式：如果影响事件彳的所有因素骂，岛，e 满足： e b ，= ( f j ) ，并且p ( 皇) 0 ，= 1 ，2 ，以。则必有： 尸( 彳) = p ( b , ) p ( a ie ) t = l ( 2 1 ) 定义2 6 贝叶斯概率：贝叶斯概率是观测者对某一事件的发生的相信程度 z o 】。观测者 根据先验知识和现有的统计数据，用概率的方法来预测未知事件发生的可能性。贝叶斯概率 不同于事件的客观概率，客观概率是在多次重复实验中事件发生的频率的近似值，而贝叶斯 概率则是利用现有的知识对来知事件的预测。 定义2 7 贝叶斯公式：也叫后验概率公式，还叫逆概率公式，其用途很广。设先验概率 为p ( b ) ，调查所获得的新附加信息为p ( ai 尽) ，其中i = 1 ，2 ，? ，则后验概率为： 咽2 一 亿2 ， 定义2 8 条件独立：对概率模式m ，a ，b 和c 是u 的三个互不相交的变量子集， 如果对v x a ，b 和v z c 都有尸( xy ，z ) = p ( xiz ) ，其中e ( y ，z ) 0 ，称给定c 时a 和最条件独立，记为，( 彳，c ，b ) m 。条件独立性在某些文献中定义为 p ( x ，yiz ) = p ( xiz ) p ( ylz ) ，可以证明两个定义等价 对概率模式m ，随机变量之间的依赖关系如图2 1 所示。 绝对依赖；z ( a ，囝，b ) m 不成立，而且对任意的c ，i ( a ，c ，b ) m 也不成立。 条件依赖：z ( a ，o ，b ) m 成立，但存在c ，使i ( a ，c ，b ) m 不成立。 绝对独立：i ( a ，o ，b ) m 成立，而且对任意的c ，( 彳，c ，b ) m 也成立。 条件独立：z ( a ，a ，b ) m 不成立，但存在c ，使i ( a ，c ，b ) m 成立。 6 - 第二草贝叶斯网络的表示、学习和推理 2 2 2 贝叶斯网络的基础知识 图表2 1 依赖关系 贝叶斯网络是涉及统计学、图论、人工智能、机器学习和数据挖掘等多个领域的交叉学 科。贝叶斯网络的最初应用是从贝叶斯推理开始的。1 9 7 4 年，d ed o m d a t 等人研制了一个 贝叶斯网络推理系统，该系统能够根据已有证据进行诊断和在证据不充分的情况下能够进一 步选择可能存在的问题进行测试，以获得充分的证据。2 0 世纪8 0 年代，随着贝叶斯网络理 论研究的深入，出现了大量的应用贝叶斯网络的实际应用系统，代表性的主要有m u n i n ， h u g i n ，p a t h f i n d e r ，q m r d t ，c o n v i n c e 等。 m u n i n ( m u s c l ea n dn e r v ei n f e r e n c en e t w o r k ) 是第一个使用贝叶斯网络建立的专家 系统。该系统完全按着严格的条件概率方法来计算某一特征出现的概率。然而利用大量的经 验数值来严格估计后验概率是不实际的。针对这样的问题，l a u r i t z e n 等人开发了专家系统 一t ：具h u g i n ，其思想是使用马尔可夫树代替贝叶斯网络。1 9 9 0 年，针对一般的贝叶斯网络， c o o p e r 证明了概率值的传播问题是n p 问题。p a t h f i n d e r 系统是一个淋巴疾病诊断系统， 它涉及1 0 0 多种症状，可诊断6 0 多种疾病。 买过航空航天局使刚基于贝叶斯网络的卫星遥感分析系统( v i s t a ) ，为诊断航天飞机推 进系统发生故障提供合理的建议，并能利用贝叶斯网的决策机制从遥感信息中找出需要的信 息。 在商业领域，以微软为代表的一些公司，已将贝叶斯网应用到自己的产品中。1 9 9 5 年， 微软推出了第一个基于贝叶斯网的幼儿保健专家系统m i c r o s o f t o n p a r e n t 。19 9 6 年，微软提 供了一个基于贝叶斯网的打印机故障在线诊断系统o n t i n et r o u b l e s h o o t e r s 。另外，在微软 的m i c r o s o f to f f i c e 系统中，也使用了基于贝叶斯网的帮助系统。， 从国际学术界的研究动态可以看出贝叶斯网正在成为人工智能研究的热点。1 9 9 5 年， 国际权威杂志c o m m u n i c a t i o no ft h ea c m 上发表了贝叶斯网研究专集，在a r t i f i c i a l i n t e l u g e n c e 和m a c h i n el e a r n i n g 等重要杂志上有很多关于贝叶斯网的文章。1 9 9 8 年的 a r t i f i c i a li n t e l l i g e n c e 上发表了关丁贝d t 斯网的专集。在国际人：工智能联合会议论文集 p r o c e e d i n g so fi j c a i - 9 5 、9 7 、9 9 、0 1 上都有概率推理的专题。在认i 、e c a i 、a c m 、u a i 等重要的国际会议上，贝叶斯网方面的论文数所占的比重逐年上升，从某种意义上说，1 9 9 0 年以来的u a i 会议几乎成为关于贝叶斯网研究的专题会议。 定义2 9 贝叶斯网络：表示变量间概率依赖关系的有向无环图b = ，这里每一 个节点，z n 表示领域变量，每条边口彳表示变量间的概率依赖关系，同时每条边都对应 着一个条件概率分布表( c p t ) ，指明了该变量与父节点之间概率依赖的数量关系。 贝叶斯网络的一个关键特征是它提供了一种把联合概率分布分解为局部分布的方法。它 的图形结构编码了变量间概率依赖关系，具有清晰的语义特征，这种独立性的语义指明如何 组合这些局部分布来计算变量问联合分布的方法。网络的定量部分给出变量间不确定性的数 7 一 第二章贝叶斯网络的表示、学习和推理 值度量。为叙述方便，我们用大写字母x = 五，置，以) 表示领域变量，用小写字母 戈= ( 为，屯，) 表示变量的取值，那么贝叶斯网络的联合概率分布司以用下面的式子表 不： p ( 功= il 尸( 薯ip a r e n t ( x , ) ) t ( 2 3 ) 这样做的好处有：1 、由于在一个由多变量组成的贝叶斯网络中，变量间交互作用的关 系是稀疏的，这种局部概率分布表能指数级的降低联合分布表的容量；2 、存在许多适合于 局部分布表的贝n l 斯推理算法：3 、贝叶斯网络中的定量表示与定性表示的分离有利于知识 程的建模。 贝叶斯网络不同于一般的基于知识的系统，它以强有力的数学工具处理不确定性知识， 以简单直观的方式解释它们。它也不同于一般的概率分析工具，它将图形表示和数值表示有 机结合起来。 构建一个指定领域的贝叶斯网络包括三个任务：1 、标识影响该领域的变量及其它们的 可能值：2 、标识变量间的依赖关系，并以图形化的方式表示出来：3 、学习变量间的分布参 数，获得局部概率分布表。这三个任务之间一般是顺序进行的，然而在构造过程中一般需要 在卜面两个方面做折中：一方面为了达到足够的精度，需要构建一个足够大的、丰富的网络 模型：另一方面，要考虑构建、维护模型的费用和考虑概率推理的复杂性。一般来讲，复杂 的模型结构，它的概率推理的复杂性也较高，而这往往是影响贝叶斯网络效率的个重要方 面。实际上建立一个贝叶斯网络往往是上述三个过程迭代地、反复地交互过程。 第一个任务主要在领域专家的指导下来选取事宜的变量，同时在有些情况下也需要一定 的策略从专家提供的变量中选择重要的因子，如在贝叶斯网络分类中的m a r k o v - b l a n k 的选 择。后面的两个任务在自动构造贝叶斯网络中是比较关键的步骤，也是目前比较活跃的研究 领域：即所谓的贝叶斯网络的结构学习和参数学习。 一般情况下，有三种不同的方式来构造贝叶斯网：由领域专家确定贝叶斯网的变量( 有 时也成为影响因子) ：1 7 点，然后通过专家的知识米确定贝叶斯网络的结构，并指定它的分布 参数。这种方式构造的贝叶斯网完全在专家的指导下进行，由于人类获得知识的有限性，导 致构建的网络与实践中积累下的数据具有很大的偏差；有领域专家确定贝叶斯网络的节 点，通过人量的训练数据，来学习贝叶斯网的结构和参数。这种方式完全是一种数据驱动的 方法，具有很强的适应性。而且随着人工智能、数据挖掘和机器学习的不断发展，使得这种 方法成为可能如何从数据中学习贝叶斯网的结构和参数，已经成为贝叶斯网络研究的热点。 由领域专家确定贝叶斯网络的节点，通过专家的知识来指定网络的结构，然后利用机器学 习的方法从数据中学习网络的参数。这种方式实际上前两种方式的折中，当领域中变量之间 的关系较明显的情况下，这种方法能大大提高学习的效率。 综上我们可以看出，在由领域专家确定贝叶斯网络的节点后，构造贝叶斯网的主要任务 就是学习它的结构和参数。很显然，学习结构和参数不是完全独立的；一方面节点的条件概 率很大程度上依赖于网络的拓扑结构；另一方面，网络的拓扑结构直接由联合概率分布的函 数来决定。然而，一般情况下，我们还是把这两个方面分开来进行。这是因为，带有太多连 接的复杂网络结构所需观测的参数较多，并且复杂的结构需要太多的存储空间及冗长繁琐的 计算过程才能产生预测和解释。因此，为使贝叶斯网作为知识模型是可用的，在学习过程中 致力于寻找一种最简单的网络结构是非常必要的，这种简单的结构模型称之为系数网络，它 含有很少可能的参数及最少可能的依赖关系。下面我们将分别从数据中学习网络的结构和参 数做一概要的介绍。 8 第二章贝叶斯网络的表示、学习和推理 2 3 贝叶斯网络的参数学习 贝叶斯网络的参数学习实质上是已知网络结构的条件下，来学习每个节点的概率分布 表。早期贝叶斯网的概率分布表是由专家知识指定的，然而这种仅凭专家经验指定的方法， 往往与观测数据产生较大的偏差。当前比较流行的方法是从数据中学习这些参数的概率分 布，这种数据驱动的方法具有很强的适应性。数据指的是领域变量的一组观测值： d = ，x ”) ，x = ( 爿，t ，) r 24 、 、， 根据数据的观测状况，可分为完备数据集和不完备数据集。完备数据集中的每个实例， 都具有完整的观测数据，不完备数据集是指对某个实例的观测有部分缺值或观测异常的情 况。对不完备数据的学习，一般要借助于近似的方法，如m o n t e c a r | o 方法，g a u s s i a n 逼 近，以及e m ( 期望- 极大化) 算法求m l ( 极大似然) 或m a p ( 最大后验概率) 等。尽管有 成熟的算法，但其计算开销是比较大的。由于这部分的内容超出了本论文的范围，有兴趣的 读者可以参看。 对完备数据集d 进行概率参数学习的目标是找到能以概率形式p ( x 。ip ) 概括样本d 的参数秒。参数学习一般要首先指定一定的概率分布族，如分布、多项分布、正态分布、 泊松分布，然后利用一定的策略估计这些分布的参数。 由于贝叶斯网络主要处理的是离散变量，对连续变量一般要经过一定的离散化处理，而 离散变量义以分布和多项分布最为常见。如在自然语言处理、图像识别和信息检索【3 】等 应用中，这两种分布形式都受到普遍的青睐。我们首先对这两种分布做一简单的介绍：对于 定义在【o 一1 】之间的变量的概率分布，存在一个离散的样本空间，如果变量具有两个状态， 那么它服从1 3 分布：如果变量具有两个以上的状态，那么它服从多项d i r i c h i e t 分布。对完备 数据集的学习，有两种常用的学习方法：最大似然估计m l e ( m a x i m u ml i k e l i h o o d e s t i m a t i o n ) 方法和贝叶斯方法。这两种方法都是基于下面的独立同分布i i d ( i n d e p e n d e n t i d e n t i f yd i s t r i b u t i o n ) 假设前提： 1 、样本中的数据是完备的； 2 、各实例之间是相互独立的： 3 、各实例服从统一的概率分布。 最大似然估计m l e 是基于传统分析的思想s 它依据样本与参数的似然程度来评判 样本与模型的拟合程度。似然函数的一般形式为： ( 口；d ) = p ( d i 乡) = iip ( x 。i 口) ， ( 2 5 ) 如果知道变量的分布函数，可通过对上式利用拉格朗日乘子法获得最大似然值，从而获 得参数的估计。从传统学的原理我们可以知道，m l e 具有一卜面的优点： 1 、一致性( c o n s i s t e n c e ) ，随着观测值个数的增多，参数收敛于最佳可能值- 实际的物 理概率： 2 、渐进有效性( a s y m p t o t i ce f f i c i e n t ) ，寻找使样本发生可能性最大的参数口，秒尽 可能接近实际的概率值，实例越多，接近程度越好： 3 、表示灵活性( r e p r e s e n t a t i o ni n v a r i a n t ) ，参数的不同分布形式不影响估计出的概率 分布效果。 贝叶斯方法 9 第二章贝叶斯网络的表示、学习和推理 贝叶斯方法与传统的统计方法最大的差别就是两者对不确定性的看法上的区别。后者把 概率简单的看作是频率的无限趋近而前者认为不确定性是人们对事物的一种认知程度，这 种认知程度是由原来的主观知识和观察到的现象共同决定的。因此贝叶斯方法学习网络参数 应该由两部分组成：观测前的先验知识和观测到的数据。在贝叶斯参数学习中，先验知识包 括参数的先验分布的选取和分布参数的选取规则。学习的任务就是找到一定的算法把二者有 机结合起来。f 面的两条规则给出了学习可行性的依据。 1 、共轭分布族 r a i f f a 和s c h a i f e e r 提山先验分布应选取共轭分布，即要求后验分布与先验分布属于统 一分布类型。它的一般描述为： 定义2 1 0 设样本工，五，以对参数目的条件分布为p ( 五，托，以id ，如果先验 分布密度函数7 r ( 口) 决定的后验密度p ( of ) 与万( 口) 同属于一种类型，则称万( 臼) 为 p ( o i ) 的共轭分布。 定义2 1 1 设尸= p ( xi 口) ：p o ) 是以口为参数的密度函数族，h = 万( 口) ) 是p 的 先验分布族，假设对任何p p 和万h ，得到的后验分布p ( o x ) 仍然在月族中，则称 日为p 的共轭分布族。 因为当样本分布与先验分布的密度函数都是目的指数函数时，它们相乘后指数相加，结 果仍是同一类型的指数函数，只相差一个常数比例因子。核为指数函数的分布都属于共轭分 布族。指数函数族包括二项分布、多项分布、正态分布、g a m m a 分布、p o i s s o n 分布和多 变量正态分布等。它们都是共轭分布。常用的共轭分布还有d i h c n e t 分布。 用共轭分布作先验可以将历史上做过的各次实验进行合理综合，也可以为今后的实验结 果分析提供一个合理的前提。由丁非共轭分布的计算实际上是相当困难的，相比之下，共轭 分布计算后验只需要先验做乘法，其计算特别简单。可以说共轭分布族为贝叶斯学习的实际 使j j 铺平了道路。 2 、最大熵原则 定义2 1 2 设随机变量x 是离散的，它取口i ，口2 ，q ，至多可列个值，且 p ( x 。q ) = 只，i = l ，2 ，- ，k ，则h ( x ) = 一p ，i np l 称为x 的熵。对连续型随机变量 z ，它的概率密度函数为p ( x ) ，若积分n ( x ) = 一i p ( x ) l np ( x ) 有意义，称它为连续 型随机变量的熵从定义可以看出，两个随机变量具有相同分布时，它们的熵 z q 就是相等， 可见熵只与分布类型有关。 最大熵原则：无信息先验分布应取参数口的变化范围内熵最大的分布。可以证明，随机 变量( 或随机向量) 的熵为最大的充分必要条件是随机变量( 或随机向量) 为均匀分布。因 此，贝叶斯假设取无信息先验分布为“均匀分布”是符合信息论的最大熵原则的，它使随机 变量( 或随机向量) 的熵为最大在没有任何信息确定先验分布时，采用无信息先验分布是 合理的。 。卜面以共轭d | r i c h | e t 分布为先验分布的选取原则，分三种不同的情况来说明贝叶斯网 络参数学习的过程： 1 、非条件概率p ( xf 伊) 的计算 1 0 第二章贝叶斯网络的表示、学习和推理 首先假定参数的先验分布为d i d c h i e t 分布： 础瑚唧2 尚q 纩1 i ( 2 6 ) 其中称口= ：l 口为分布的精度，区别于分布参数，口，( ，= 【1 ，2 ，刀】) 为超参数( h y p e r p a r a m e t e r s ) ，这些参数可假象为主观上对每个取值出现个数的先验知识。当n = 2 时，为 b e t a 分布。如果对先验知识不确定时，根据最大熵原则，应取为均匀分布= = = 口。 下面给出在不同的超参数下，b e t a 分布的分布函数图像。 图表2 2 不同超参数下b e t a 分布的密度曲线 实线表示均匀分布：( a ) q = ( 2 = 1 ，( b ) 口l = 口2 = 2 ，( c ) q = a 2 = 1 0 ：点线表 示正向的倾斜密度：( a ) 倪l = 1 5 ，口2 = 0 5 ，( b ) 口l = 3 ，口2 = l ，( c ) q = 1 5 ，= 5 ； 虚线表示负向