（计算机软件与理论专业论文）动态贝叶斯网络结构学习的研究.pdf

摘要 摘要 动态贝叶斯网( d b n ) 作为一种特殊的贝叶斯网络( b n ) ，是贝叶斯网 络与时间信息相结合而形成的可处理时序数据的新的随机模型。由于其在描 述非线性、随机演化的不确定关系时具有较强的优势，所以对动态贝叶斯网 的研究及其应用成为人工智能领域中的一个研究热点。为了进一步提高d b n 结构学习算法的效率，本文在研究国内外现有算法的基础上，完成了如下几 方面的工作： 1 ) 扩展了利用粒子群优化学习贝叶斯网络结构的b n p s o 算法，提出了 基于粒子群优化的d b n 结构学习算法i - b n p s o 。新算法首先利用条件独立 性测试( 0 阶) 确定网络候选的连接图，有效地限制了搜索空间，并利用已获 得的互信息作为启发性知识来初始化粒子群；其次，设计了基于m d l 评分增 益的粒子位置减法算子，使粒子的“飞行”更有效；最后，引入了随机扰动 策略，避免了粒子群的“聚集”现象。在标准数据集上的实验表明，新算法 大大提高了学习的精度和速度。 2 ) 针对基于蚁群优化的贝叶斯网络结构学习算法i - a c o b 的不足，融合 阈值自调整的可变搜索空间和模拟退火的优化策略，提出了v s m i 。a c o b 贝 叶斯网络结构学习算法。新算法将约束满足的方法和m d l 评分搜索的基本思 想相融合，在学习过程中利用阈值自调整的0 阶条件独立性测试来动态压缩 搜索空间，在保证求解质量的同时，加速了搜索过程；然后通过引入基于模 拟退火的优化机制，改进了算法的求解质量，提高了局部优化的效率。实验 结果验证了两种策略的有效性，+ 与最新的同类算法相比，新算法在保持较快 收敛速度的前提下，具有更好的求解质量。 3 ) 结合动态贝叶斯转移网络的特点，将v s m i a c o b 扩展到动态贝叶斯 网络，提出了基于蚁群优化的分步构建转移网络的结构学习算法。算法将转 移网络的结构学习分为时间片之间的结构学习和时间片内的结构学习两个步 骤进行，并再次改进优化策略，减少了无效优化的次数。标准数据集下大量 实验结果表明：新算法能够更有效地处理大规模数据，且学习精度和速度有 较大改进。 关键词贝叶斯网络；动态贝叶斯网络：结构学习；粒子群优化；蚁群优化 a b s t r a c t a b s t r a c t d y n a m i cb a y e s i a nn e t w o r k s ( d b n ) i sas p e c i e so fb a y e s i a nn e t w o r k s 删) d e s i g n e dt om o d e ls t o c h a s t i ct e m p o r a lp r o c e s s e s ，w h i c hm o d e l st h es t o c h a s t i c e v o l u t i o no fas e to fr a n d o mv a r i a b l e so v e rt i m e o w i n gt od b n ss i g n i f i c a n t a d v a n t a g e si nd e s c r i b i n gn o n l i n e a r , t e m p o r a l ，e v o l v i n ga n du n c e r t a i nr e l a t i o n s h i p s a n ds t r o n ga b i l i t yo fp r o b a b i l i s t i ci n f e r e n c e ，s t u d i e so nd b na n di t sa p p l i c a t i o n a r ea l lt h et i m eh o tt o p i c so f 趾t m st h e s i sm a i n l yf o c u s e so nd y n a m i cb a y e s i a n n e t w o r k ss t r u c t u r el e a r n i n gp r o b l e mi nt h ef o l l o w i n gt h r e ed i r e c t i o n s ： 1 ) a n e wa l g o r i t h mf o r l e a r n i n gd b n ss t r u c t u r eu s i n gp a r t i c l es w a r mo p t i m i z a t i o n ( i b n p s o ) i sp r o p o s e db ye x t e n d i n gt h ea l g o r i t h mb n p s o f i r s t ，t h en e w a l g o r i t h mu s e s o r d e r - 0 i n d e p e n d e n c et e s t s t o e f f e c t i v e l yr e s t r i c tt h es p a c eo f c a n d i d a t es o l u t i o n s ，m o r e o v e r , t h em u t u a li n f o r m a t i o no b t a i n e di ni n d e p e n d e n c e t e s t sp h a s ei su s e da sh e u r i s t i ck n o w l e d g et oi n i t i a l i z et h ep a r t i c l es w a r m a n dt h e n , an e w p a r t i c l ep o s i t i o n ss u b t r a c t i o no p e r a t o ri sd e s i g n e db a s e do nt h ei n c r e a s eo f m d ls c o r e ，w h i c hm a k e st h e p a r t i c l ef l y i n ge f f e c t i v e l y a tl a s t , ad i s t u r b e d s t r a t e g yi sa p p l i e dt oa c c e l e r a t et h ep a r t i c l e st oo v e r s t 印t h el o c a le x t r e m u m 1 1 1 e e x p e r i m e n tr e s u l t so nt h eb e n c h m a r kd a t a b a s e ss h o wt h a tt h e s es t r a t e g i e sa r e e 伍c i e n t ，a n dt h es o l u t i o nq u a l i t yo ft h en e wa l g o r i t h mi sb e a e r 2 ) t os o l v et h ed r a w b a c k so ft h ea n tc o l o n yo p t i m i z a t i o nf o r1 e a r n i n gb a y e s i a n n e t w o r k s ( i a c o b ) ，an e wa l g o r i t h mb a s e do nv a r i a b l es e a r c hs p a c ea n ds i m u l a t e d a n n e a l i n gs t r a t e g y ( v s m i a c o b ) i sp r o p o s e d ，w h i c hc o m b i n e dt w ob a s i ci d e a so f c o n s t r a i n ts a t i s f a c t i o na n ds c o r e a n d s e a r c ht o g e t h e r f i r s t ，t h en e wa l g o r i t h m u s e so r d e r - 0i n d e p e n d e n c et e s t sw i t ha s e l f - a d j u s t i n gt h r e s h o l dv a l u et oe f f e c t i v e l y r e s t r i c tt h es p a c eo fc a n d i d a t es o l u t i o n s ，s ot h a tt h es e a r c hp r o c e s sf o ra n t sc a nb e i m p r o v e dw h i l ek e e p i n gb e a e rs o l u t i o nq u a l i t y t h e n ，a l lo p t i m i z a t i o ns c h e m e b a s e do ns i m u l a t e da n n e a l i n gi si n t r o d u c e dt oi m p r o v et h es o l u t i o nq u a l i t y , a n da k n o w l e d g e g u i d e ds t r a t e g yi se m p l o y e dt oe n h a n c et h eo p t i m i z i n ge f f i c i e n c yi nt h e l o c a lo p t i m i z a t i o n p r o c e s s f i n a l l y , t h ea l g o r i t h mi st e s t e do nd i f f e r e n ts c a l e b e n c h m a r k sa n dc o m p a r e dw i t ht h er e c e n t l yp r o p o s e ds t o c h a s t i ca l g o r i t h m s n l e r e s u l t ss h o wt h a tt h e s es t r a t e g i e sa r ee f f i c i e n t ，a n dt h es o l u t i o nq u a l i t yo ft h en e w a l g o r i t h mp r e c e d e st h eo t h e ra l g o r i t h m sw h i l et h ec o n v e r g e n c es p e e di sf a s t e r 3 ) a i m i n ga tt h ec h a r a c t e ro fd y n a m i cb a y e s i a nt r a n s i t i o nn e t w o r k s ，t h ep a p e r p r o p o s e san e wt r a n s i t i o nn e t w o r k sl e a r n i n ga l g o r i t h mb a s e do na n tc o l o n y o p t i m i z a t i o nb ye x t e n d i n gt h es t a t i cb a y e s i a nn e t w o r k ss t r u c t u r el e a n i n ga l g o r i t h m v s m i - a c o b i nt h en e wa l g o r i t h m ，a n t ss e l e c ta r c sf r o mt h ei n t e r - a r c sb e t w e e n t i m es l i c e sb e f o r ef r o mt h ei n t r a a r c si no n es l i c e ，a n dt h e nt h ei n t e r v a l 1 1 i 北京工业大学工学硕士学位论文 o p t i m i z a t i o ns t r a t e g yi si m p r o v e db yd e c r e a s i n g t h et i m e so fo p t i m i z a t i o n o p e r m i o n an u m b e ro fe x p e r i m e n t s a n dc o m p a r i s o n sd e m o n s t r a t et h en e w a l g o r i t h mi se f f i c i e n ta n dc a l lh a n d l el a r g ed a t a s e t s k e y w o r d sb a y e s i a nn e t w o r k ；d y n a m i cb a y e s i a nn e t w o r k ；s t r u c t u r el e a r n i n g ； p a r t i c l es w a r mo p t i m i z a t i o n ；a n tc o l o n yo p t i m i z a t i o n ； i v 独创性声明 本人声明所呈交的论文是我个人在导师指导下进行的研究工作及取得的研 究成果。尽我所知，除了文中特别加以标注和致谢的地方外，论文中不包含其他 人已经发表或撰写过的研究成果，也不包含为获得北京工业大学或其它教育机构 的学位或证书而使用过的材料。与我一同工作的同志对本研究所做的任何贡献均 已在论文中作了明确的说明并表示了谢意。 关于论文使用授权的说明 本人完全了解北京工业大学有关保留、使用学位论文的规定，即：学校有权 保留送交论文的复印件，允许论文被查阅和借阅；学校可以公布论文的全部或部 分内容，可以采用影印、缩印或其他复制手段保存论文。 ( 保密的论文在解密后应遵守此规定) 签名：槛导师签名：璧! 垒坠日期w 罕- 6 - 5 第1 章绪论 第1 章绪论 1 1 课题背景与研究意义 贝叶斯网络( b a y e s i a nn e t w o r k s ，b n ) 的源头可以追溯到1 7 6 3 年英国数 学家贝叶斯撰写的一篇名为“a ne s s a yt o w a r d ss o l v i n gap r o b l e mi nt h e d o c t f i r l ec h a n c e ”的论文，从此贝叶斯方法和理论开始逐渐地被学者所认识和 重视。1 9 8 2 年，p e a r l 在人工智能领域用贝叶斯网络进行概率推理，分别对树 型网络和多树型网络提出了消息传递算法，此后，贝叶斯网络被越来越多地 用在专家系统的不确定性知识表示和推理中。1 9 8 8 年，p e a r l 建立了贝叶斯网 络基础理论体系。1 9 9 6 年，h e c k e r m a n 等一些学者把贝叶斯网络用于数据挖 掘l l j 。随着研究的深入，贝叶斯网逐渐成为人工智能，模式识别，机器学习和 数据挖掘等领域处理不确定问题的重要方法之一【2 】。 贝叶斯网络是一个有向无环图【3 】，它用节点表示变量，有向边表示变量间 的依赖关系。贝叶斯网络作为一种图形模型，具有图形模型的大多数性质， 是概率理论和图论相结合的产物。它把图形理论的表达和计算能力与概率理 论有机地结合在一起，在处理不确定性问题上具有许多优势，如灵活的相互 依赖的拓扑结构，易于理解和解释的语义，强大的处理能力等。 动态贝叶斯网络( d y n a m i cb a y e s i a n n e t w o r k s ，d b n ) 是贝叶斯网络在时 间领域的扩展【4 】，即在原来网络结构的基础上加上时间属性的约束而形成的具 有处理时序数据能力的新的随机模型。它在描述非线性、随机演化的不确定 关系时具有较强的优势。d b n 已经应用于语音识别【5 】、股票市场指数反应、 生物进化过程、病人健康状况监控以及经济预测【6 】等很多方面。 对于随时间变化的动态系统，贝叶斯网络的结构学习和推理算法在动态系 统中不能直接适用。主要的困难在于动态系统的复杂性，使得静态系统中的 一些成熟方法无法处理复杂的随机过程，因此，需要针对复杂动态系统的特 点研究全新或改进的方法【7 j 。 要成功应用d b n ，必须构建合理的d b n 网络，一般来说可以利用常识 和专家知识来构建模型，然而对于复杂的动态系统，这几乎是不可能的。因 此如何从大量样本数据中学习动态贝叶斯网络结构成为当前人工智能领域的 一个研究热点和难点。全面深入地研究此问题，无论在理论上还是在现实生 活中都有着重要的意义和价值。 北京工业大学工学硕士学位论文 1 2d b n 结构学习的研究现状 d b n 的学习是b n 学习技术的延伸，目前主要的研究方法是将静态贝叶 斯网的学习方法和研究成果推广到动态领域。十几年来，国内外一些学者进 行了积极的研究和探索，取得了一定的成果。 1 9 9 8 年，f r i e d m a nn 等人把静态贝叶斯网评分函数扩展到动态的情测4 】， 分别讨论了完全数据和不完全数据下的动态贝叶斯网络结构学习的一般方 法，并提出不完全数据下学习动态贝叶斯网络结构的算法d p n s e m 。其基本 思想是在候选空间中搜索具有最优评分的网络结构。 2 0 0 2 年，m u r p h yk 研究了动态贝叶斯网络并在其博士论文【8 】中详细阐述 了d b n 的知识表示，推理和学习等内容。该文拓展了s e m 算法，并阐述了 d b n 的一系列应用。 2 0 0 3 年，a s h u t o s hg 等人提出了基于a d a b o o s t 框架的d b n 学习算法剀， 并将算法应用于基于语音的人机交互界面。 2 0 0 5 年，j o s em 等人研究了动态贝叶斯网络的评分标准，指出 c r o s s v a l i d a t i o n 较b d e 和b i c 评分更有效，并用大量实验证明了其结论。 国内对d b n 结构学习的研究相对较晚，主要的工作集中在基于评分搜索 的方法研究上。 2 0 0 3 年，复旦大学王飞等人提出了基于遗传算法的d b n 结构学习算法 e g a d b n 1 0 1 ，给出了网络结构的编码方案，并设计了相应的遗传算子，并对 数据不完备情况下的结构学习做了初步尝试。 2 0 0 5 年，吉林大学贾海洋等人改进了e g a d b n 算法，把免疫算法应用 到动态贝叶斯网络结构学习中【l l 】，取得了较好的收敛效果。 2 0 0 6 年，中国科技大学王浩等人结合进化算法，改进了m a r k o vc h a i n m o n t ec a r l o ( m c m c ) 学习d b n 框架【1 2 】，提高了m c m c 的收敛速度。 2 0 0 7 年，西安交大衡星辰等人把粒子群算法应用到动态贝叶斯网络结构 学习中，设计了网络结构编码方案和粒子位置、速度变化的算子【1 3 。同年， 西北工业大学肖秦琨等人提出了基于贝叶斯优化的d b n 结构学习算法，其实 质是一种基于概率模型的进化算法【1 4 】。 综上所述，动态贝叶斯网络结构学习的研究已经取得了一定的成果，然而， 在节点变量较多的情况下，如何提高d b n 结构学习算法的精度和效率，仍然 是一个值得深入探究的问题。 第1 章绪论 1 3 本课题的主要研究内容 针勋i ) d i n 绢俐子刊f f j 咫，年文主要进行了以下几方面的工作： ( 1 ) 、基于粒子群优化的d b n 结构学习算法的研究 通过对基于粒子群优化的b n 结构学习算法b n - p s o 的扩展，提出了动态 贝叶斯网络的结构学习算法i - b n p s o 。新算法首先利用条件独立性测试有效 地限制了搜索空间，并利用已获得的互信息作为启发性知识来初始化粒子群； 其次，设计了基于m d l 评分增益的粒子位置减法算子；最后，引入了随机扰 动策略。实验表明，i - b n p s o 的学习精度和速度都有较大提高。 ( 2 ) 、基于蚁群优化的d b n 结构学习算法的研究 首先，改进了基于蚁群优化的b n 结构学习算法i - a c o b 。改进的算法 v s m i a c o b 使用了两个新策略：阂值自调整的可变搜索空间压缩和基于模拟 退火的优化选择策略。实验结果表明，与算法i - a c o b 以及其他一些最新的同 类算法相比，v s m i a c o b 在学习速度和求解质量上都有优势。 其次，将v s m i a c o b 扩展到d b n 的学习。首先，针对d b n 转移网络 的特点，提出了蚁群的两步选边策略，然后根据实验统计数据，提出了新的 解优化策略。实验表明两个策略是有效的。 1 4 本文的组织结构 本文后面的章节组织如下： 第二章：简单介绍了贝叶斯网络、动态贝叶斯网络及其结构学习、动态贝 叶斯网络的评分标准。 第三章：首先介绍了粒子群优化算法和基于粒子群优化的贝叶斯网络结构 学习算法b n p s o 。然后介绍扩展的i - b n p s o 算法，重点阐述了搜索空间压 缩和新设计的粒子位置减法算子。最后给出实验以及结果分析。 第四章：首先介绍了基于蚁群优化的b n 结构学习算法a c o b 及其改进算 法i - a c o b 。然后阐述了改进的v s m i a c o b 算法及其主要的改进策略，并给 出了实验和结果分析。最后，扩展v s m i a c o b 到d b n 的学习，重点阐述了 蚁群在学习d b n 转移网络时的两步选边策略，并给出实验以及结果分析。 第五章：结论，对全文作一个简单总结，并提出下一步的工作展望。 第2 章动态贝叶斯网络及其结构学习 第2 章动态贝叶斯网络及其结构学习 2 1 贝叶斯网络及其结构学习 贝叶斯网络是采用有向无环图来描述概率关系的理论模型，它提供了一种 表示因果信息的方法，长期以来一直被认为是人工智能领域中的一个重要的 研究课题。 一个贝叶斯网络可以定义为一个二元组b = ( g0 ) ，其中g = ，a ) 为一个有 向无环图，x = 五，五，五 表示领域变量，而a 为节点间的有向弧集合， 每条弧a i j a 表示相应变量五和x 间直接的依赖关系x 。jz ； o = q ，幺，或) 表示网络的条件概率参数集合，q = p ( 五i 万( 五) ) 为节点置在 给定其父母节点集合石( 五) 状态下的条件概率分布。g 是模型中的定性知识表 示部分，用于描述变量间的概率依赖关系，弧的方向具有因果语义，可进行 因果推理：o 是模型中的定量知识表示部分，包括网络中每个节点相对于其 父节点集的条件概率分布表，用于定量描述节点和其父节点的概率依赖程度。 可见，一个贝叶斯网b = ( g0 ) 用图形结构和网络参数唯一地确定了在随机变 量集合x = ，五，z ) 上的一个联合概率分布： j l p ( 五，鼍) = il 尸( 五i 万( 五) ) ( 2 - 1 ) 百 这样表达的好处有：由于在一个由多变量组成的贝叶斯网络中，变量间 相互作用的关系是稀疏的，这种局部概率分布表能指数级地降低联合概率分 布表的容量；存在许多适合于局部分布表的贝叶斯推理算法；贝叶斯网 络中的定量表示与定性表示的分离有利于知识工程的建模【1 5 1 。 网络结构学习的目标是找到和样本数据d 匹配度最好的贝叶斯网络结构。 根据贝叶斯网络研究的不同视角，可以把贝叶斯网络结构学习的方法分成两 类：基于约束满足的方法和基于评分搜索的方法。基于约束满足的方法【1 6 通 过从数据中获得的依赖信息来识别节点变量间的条件独立性关系，并构造贝 叶斯网结构。基于评分搜索的方法【1 7 d 9 将结构学习视为各节点局部连接( 子 结构) 的组合优化过程，即利用所定义的评分函数寻找与样本数据匹配程度 最高的网络结构，于是，结构的学习就被转化为在结构空间中的启发式搜索 问题。 尽管基于约束满足的方法实现简单有效，但其高阶测试的计算复杂且不 可靠，算法的学习质量难以保证。近几年搜索技术的不断发展和进步，为大 北京工业大学工学硕士学位论文 规模的空间搜索提供了有效的解决方法，其中蚁群算法【1 9 】、遗传算法【2 0 】以及 粒子群算法【2 1 1 等已经成功应用到贝叶斯网络结构学习中。然而由于搜索空间 巨大，搜索效率有待提高。针对两种方法的特点，一些学者提出了将两种方 法相融合的结构学习算法，如m a nl e u n gw o n g 等人提出的h e a 算法【2 2 1 和冀 俊忠等人提出的f i b & b m d l 2 3 1 ，i - a c o b 2 4 1 ，v s m i a c o b t 2 5 】等算法在求解 速度和处理大规模数据的能力上都有了较大提高。 2 2 动态贝叶斯网络 d b n 是以静态贝叶斯网络为基础，把原来的网络结构与时间信息相结合， 而形成的具有处理时序数据能力的新的随机模型。随着时间因素的引入，在 不同时刻上系统状态所形成的数据，反映了所代表的变量的变化发展规律。 要分析这种动态数据，就要建立相应的动态模型。 由于动态系统的复杂性，现有的研究成果大多是在一些假设的基础上，对 动态系统进行简化处理，并将适用于静态贝叶斯网络的原理和成熟的方法做 一些改进，推广到动态系统。这些假设包括： ( 1 ) 马尔可夫假设：假设动态概率过程是马氏的( m a r k o v i a n ) ，即满足： p ( x t i 彳【1 ，彳【2 】，x t 一1 】) = p ( x t ix t 一1 】) ( 2 - 2 ) 其中：x 是随时间演变的随机变量集合，x t 1 是x 演化到f 时刻的集合， 系统是离散时间的随机过程。 ( 2 ) 平稳假设：假设在一个有限的时间内条件概率变化过程对所有t 是 一致平稳的。 基于上述假设，建立在随机过程时间轨迹上的d b n 可作如下定义： 一个动态贝叶斯网络可以定义为b ( b o ，b 一) ，其中b o 为初始网络，指 定时态过程初始状态的概率分布尸( 彳 o 】) ；b 一为转移网络，对所有时间点1 ， 2 ，f 指定从卜1 时间点到t 时间点变量集状态的转换概率 p ( x t fx t 一1 】) 。转移网络b 一不能包含时间片f 指向时间片卜1 的弧。 因此，若给定一个d b n 模型，则在( 1 】，2 ，oo 1 p 研t 】) 上d b n 的联合 概率分布为： = l 尸( x o ，x 1 】，x 吲) = 吃( x 【o 】) ii 气( x t + 1 lx 嘲) ( 2 - 3 ) t - 0 也就是说，一个d b n 定义了在动态随机过程中无穷变化轨迹上的概率分 布。图2 1 给出了一个动态贝叶斯网络的例子。一般我们只在有穷的时间o ， 1 ，2 ，t 上推理，由b o 和b 一可以将一个d b n 展开成一个“长 的贝叶 斯网络【4 ，1 0 1 。 第2 章动态贝叶斯网络及其结构学习 a ) ap r i o rn e t w o r k0 1 1b ) at r a n s i t i o nn e t w o r kc ) t h ec o r r e s p o n d i n g v a r i a b l ex l ，x 2 ，x 3 o nv a r i a b l ex l ，x 2 ，x 3“u n r o l l e d ”n e t w o r k 图2 1 动态贝叶斯网的例子 f i g u r e2 1 a ne x a m p l eo f d b n 2 - 3 动态贝叶斯网络学习 通常，几乎没有专家能够给出动态随机过程的模型，从数据中学习模型是 一种可行的建模方法。动态贝叶斯网的学习就是在给定一个样本数据集合d 下，寻找与数据集d 匹配度f 最高的网络。完整的表述如下： 输入：样本数据集合d ，d 中包含n 潮个完全观察序列，第k 个序列的长 度是n k ，其对应变量的值为x k o ，) ( 1 【 1 ，x k n k 】。 输出：输出与数据集d 匹配度最高的d b n 。 d b n 的学习技术是b n 学习技术的延伸。d b n 网络和b n 网络有着非常 密切的联系：一个d b n 网络由两个b n 网络定义( b o ，b ) ，所以可以考虑 扩展b n 网络结构学习算法到动态贝叶斯网络，即从训练数据中分别学习初始 网络b o 和转移网络b 一。 d b n 的学习可以从不同的方面来进行分类：从学习的主要任务来看， 可以分为：参数学习和结构学习。参数学习，顾名思义就是学习模型里面的 参数，即网络的条件概率参数集合o ，很多模型仅仅涉及参数学习。结构学 习是指对网络拓扑结构进行学习，即获得有向无环图g ，该过程也被称为模 型选择。从样本数据的完整性来看，可以分为数据完备和不完备两种情况。 数据完备时，样本数据中的每个实例都具有完整的观测数据。数据不完备是 指样本数据中某些实例的观测有部分缺值或观测异常的情况，有些数据可能 丢了，或者可能根本没有观测数据，这类问题相对较难。h e c k e r m a nd 给出了 贝叶斯网络学习的一般方法，这些方法同样适用于d b n 学习，如表2 1 所示。 北京工业大学工学硕士学位论文 表2 1d b n 学习的一般方法 t a b l e2 一lg e n e r a lm e t h o do fd b nl e a r n i n g ( 1 ) 、参数学习 参数学习实质上是在已知网络结构的条件下，来学习每个节点的概率分布 表。早期的贝叶斯网的概率分布表是用专家知识指定的，然而这种仅凭专家 经验指定的方法，往往会产生较大的偏差。当前比较流行的方法是从数据中 学习这些参数的概率分布，这种数据驱动的学习方法具有很高的适应性。 对完备数据集d 进行概率参数学习的目标是找到能以概率形式概括样本 d 的参数 。常用的学习方法有：最大似然估计方法和贝叶斯方法。这两种 方法都是基于独立同分布的假设前提下提出的。 对于数据不完备的情况，常采用e m 算法( e x p e c t a t i o nm a x i m i z a t i o n ) 进 行估计。其基本思想是：首先给整个网络的条件概率参数随机初始化p o ，并 将其作为当前假设。然后按照如下方式进行迭代，设已经进行了t 次迭代，得 到参数p 。则第什1 次迭代由两步组成：e 步和m 步。e 步基于p 。对数据 进行修补，使之完整；m 步基于修补后的完整数据重新计算参数p 的最大似 然估计，得到p 什l 。重复上述过程，该过程伴随着对隐藏变量的似然估计，收 敛于一个最大可能的假设，即具有最大可能的条件概率表。 ( 2 ) 、结构学习 与b n 结构学习一样，d b n 结构学习方法也可分为两类，一类是是基于 约束满足的学习方法；另一类是基于评分搜索的学习法。 基于约束满足的方法，把贝叶斯网结构视为节点变量间一组条件独立关系 的编码，通过识别节点间条件独立性关系来构造贝叶斯网结构。这种方法的 思想是努力估计代表节点变量的数据属性间条件独立的性质，然后使用这些 局部约束关系来构造网络结构以展现所观察到的依赖和独立关系。这种依赖 关系常用条件独立性( c o n d i t i o n a li n d e p e n d e n c e ，c i ) 测试来度量，常用的测 度有基于阈值的度量【2 6 】和z 2 测试【2 7 】两种方法。 基于评分搜索的方法将学习视为结构优化的过程，即利用评分函数寻找与 样本数据匹配程度最高的网络结构【2 3 1 。该方法主要由两部分组成：评分函数 和相应的搜索算法。学习算法需要解决好以下两个问题： 如何评分? 必须选择合适的网络度量机制，对搜索到的网络进行度量，确 第2 章动态贝叶斯网络及其结构学习 定网络的评分，使其与样本数据集匹配度最高。 如何搜索? 已证明贝叶斯网络结构学习是n p 难题【2 引，因此，采用启发式 搜索算法，提高搜索效率，是解决结构学习问题的关键所在。 对于数据不完备时的d b n 结构学习，文献h 1 中介绍了d p n s e m 算法， 算法框架如下： 彳l g o r i t h md p n - s e m b e g i np ro c e d u r e c h o o s e ( b ? ，硅) ( p o s s i b l yr a n d o m l y ) ； l o o pf o rn = 0 ，1 ，u n t i lc o n v e r g e n c e i m p r o v et h ep a r a m e t e r so f ( 掰，贮) u s i n ge m s e a r c ho v e rd p ns t r u c t u r e s ( u s i n ge x p e c t e dc o u n 捃c o m p u t e dw i t h ( 霹，雎) ) l e tt h eb e s ts c o r i n gd p ns e e nb e ( 掰“，霹1 ) 圹b ：1 磷1 ) = ( 掰，必) r e t u r n ( 霹“，霹1 ) 砌dp ro c e d u r e 图2 - 2d p n s e m 算法 f i g u r e2 - 2a l g o r i t h md p n - s e m d p n s e m 算法的思想仍然是先修补数据，然后基于修补后的完全数据进 行学习。其内层循环包括完全数据下的d b n 结构学习，可见，在完备数据集 下d b n 结构学习效率的提高，也将提高d p n s e m 算法的效率。 2 4 网络的评分标准 贝叶斯网络结构的评分度量，最常见的有b i c ，b d e ，k 2 和最小描述长 度( m i n i m u md e s c r i p t i o nl e n g t h ，m d l ) 等嘲。m d l 评分度量在大样本情况 下，是与b i c 评分等价的嘲1 。 m d l 度量源于信息理论的编码原理，假如我们想在某种介质上存储样本 d ，为节省存储空间，自然希望存储它的压缩版本。并且，为了能够恢复d ， 还必须存储这个压缩模型。因此样本总的描述长度定义为d 的压缩版本总长 度与压缩模型的描述长度之和，m d l 原理认为最优的模型是总描述长度最短 的模型。m d l 原理用于贝叶斯网学习，就是寻找具有最小m d l 评分的网络 结构，该网络结构描述了样本反映的联合概率分布。 令g 表示贝叶斯网所有可能的结构空间，任一结构g g ，则样本集d 的 m d l 描述长度f ( g ：d ) 包含两部分：网络结构的描述长度m ( g ：d ) 和在给定 结构下样本数据集的描述长度h ( g ：d ) 。 北京工业大学工学硕士学位论文 设节点变量x = 五，置，以) ，完备的样本数据集d ，万( 五) 表示节点五 的父节点集合，v 。代表节点变量五的可能的状态数。m ( g ：d ) 分量可定义为乜别： m ( g ：d ) = 【l il o g ：( ”) + d ( _ 一1 ) 兀_ 】 ( 2 4 ) f = 1 x j 局 其中d 为一个常数，代表存储一个数字值所需要的位数。该分量代表了网 络结构的复杂度，并用编码图形结构和存储节点条件概率表的位数来评价。 而分量h ( g ：d ) 的计算公司可定义为： 地d ) = 喜( 磊c ( 五州1 0 9 ：( 高为) ) ( 2 _ 5 ) f l 置。尸r 。o “j ，“z ， 式中“) 表示数据集中对应实例数目的统计。h ( g ：d ) 评价由数据和侯选 网络各自蕴涵的联合概率分布的近似程度，它是对侯选网络精度的一种度量。 所以，一个贝叶斯网的m d l 评分可形式化为： f ( g ：d ) = m ( g ：d ) + h ( g ：d ) ( 2 6 ) 从m d l 评分的定义可见，一个贝叶斯网的m d l 评分能够分解为网络中 所有节点局部结构( 仅与其父母节点相关) 的m d l 评分之和。按照m d l 原 理，我们选择的网络结构要使得网络的描述长度和样本的编码长度之和最小， 这意味着学习过程必须在网络结构的复杂性与网络结构表示样本的准确性之 间选择一个平衡点。 由此扩展到动态贝叶斯网络，得到d b n 的m d l 评分即为初始网络与转 移网络的m d l 评分之和，其形式化表述为： f ( b ：d ) = ，( b o ：d o ) + f ( 疋：以) ( 2 7 ) 其中d o 表示由d 的各个观察序列中关于初始状态的事例组成的数据集， d 一表示由d 的各个观察序列中关于动态随机过程状态转换的事例组成的数 据集。 2 5 本章小结 本章从静态贝叶斯网络的概念出发，引出了d b n 的基本概念，详细介绍 了d b n 结构学习的定义，结构学习的基本方法以及网络评分的标准，为后续 d b n 结构学习的算法研究奠定了基础。 第3 章基于粒子群优化的d b n 结构学习算法 第3 章基于粒子群优化的d b n 结构学习算法 粒子群优化( p a r t i c l es w a r mo p t i m i z a t i o n ，p s o ) 算法【3 0 】是一种全局优化 进化算法，它具有计算简单、收敛速度快、鲁棒性好等优点，因此，算法一 经提出，立刻引起演化计算领域学者们的广泛关注，涌现了大量的研究成果， 并在一些应用领域中得到了很好的应用。 2 0 0 5 年，t a od u 等人首次将p s o 算法应用到贝叶斯网络结构学习中，提 出了b n p s o 算法【2 l 】。文章定义了粒子的移动、位置的加法，减法算子，并 将其与遗传算法做了比较。然而该算法迭代次数较多，收敛速度较慢。本章 对其进行改进并扩展到d b n 学习，提出了d b n 结构学习算法i - b n - p s o 。具 体安排如下： 首先介绍了基本的粒子群优化算法和贝叶斯网络结构学习算法b n p s o ； 然后描述扩展的新算法，重点阐述了基于条件独立性测试的搜索空间压缩和 基于m d l 评分增益的粒子位置减法算子；最后给出了实验结果和分析。 3 1 粒子群优化算法p s o 粒子群算法是在1 9 9 5 年由美国的社会心理学家k e n n e d yj 和电器工程师 e b e r h a r tr 共同提出的，其思想来源于人工生命和演化计算理论。生物学家对 鸟群飞行的研究发现，鸟仅仅是追踪它有限数量的邻居，但最终的整体结果 是整个鸟群好像在一个中心的控制之下，即复杂的全局行为是由简单规则的 相互作用引起的。p s o 即源于对鸟群捕食行为的研究，一群鸟在随机搜寻食 物，如果这个区域里只有一块食物，那么找到食物的最简单有效的策略就是 搜寻目前离食物最近的鸟的周围区域。p s o 算法就是从这种模型中得到启示 而产生的。 粒子群优化算法首先初始化一群随机粒子，然后通过迭代找到最优解。在 每一次迭代中，粒子通过跟踪两个“极值”来更新自己：第一个是粒子本身 所找到的最优解，这个解叫做个体极值p b e s t ；另一个是整个种群目前找到的 最优解，这个极值是全局极值g b e s t 。图3 1 给出了粒子群算法的基本流程。 北京工业大学工学硕士学位论文 开始 粒子群初始化 计算每个粒子适应度 更新个体极值和全局极值 更新粒子位置和速度 是否达到终止条件 、一一 是 否 图3 1粒子群算法的基本框架 f i g u r e3 1f r a m e w o r ko f p s oa l g o r i t h m 在找到这两个最优值g b e s t ，p b e s t 后，粒子根据如下两个公式来更新自己 的速度和位置： k + l = w 圪+ q r l ( p b e s t - 也) + c 2 r 2 ( g b e s t 一五)( 3 1 ) 五+ l = j + 圪+ 1( 3 2 ) 其中k 表示迭代次数，攻是粒子的当前速度，氘是粒子的当前位置，r l 、 1 2 是介于( 0 ，1 ) 之间的随机数，c 1 ，c 2 是学习因子，w 为惯性权重，用来控 制上次迭代的速度对当前速度的影响，较大的w 可以加强p s o 的全局搜索 能力，而较小的w 能加强局部搜索能力，w 相当于遗传算法中的变异算子， 它保证了群体的多样性。在式( 3 1 ) 所描述的速度进化方程中，第一部分为粒子 先前的速度；第二部分为“认知”部分，它考虑了粒子自身的经验，表示粒 子本身的思考；第三部分为“社会部分 ，表示粒子间的社会信息共享。 针对基本的粒子群算法已有很多改进策略【3 1 3 3 1 ，胡旺等人在文献【3 2 1 中证明 了基本粒子群算法的进化过程与粒子速度无关，并提出了简化粒子群优化算 法s p s o 。s p s o 算法中不含速度项，粒子群优化方程简化为： 五+ l = w x k + q r l ( p b e s t 一五) + c 2 r 2 ( g b e s t 一也) ( 3 7 ) 式中右边的第1 项为“历史( h i s t o r y ) 部分，表示过去对现在的影响，通 过w 调节影响程度。 基本的p s o 算法主要应用于连续型的函数优化问题求解，即适用于描述 粒子状态及其