（计算机软件与理论专业论文）基于k2评分的贝叶斯网结构学习算法的研究.pdf

摘要 摘要 贝叶斯网( b a y e s i a nn e t w o r k ，b n ) 是联合概率分布的一种图形化表示，由于 具有结构清晰，语义明确等特点，因此成为处理不确定性知识表示和推理的一种 重要理论模型。贝叶斯网在机器学习、医疗诊断、金融分析等领域有着广泛的应 用，并已经取得了较大的成功。但仅由专家构建贝叶斯网通常十分困难，有时甚 至是不可能的。因此，从数据中快速、准确地学习贝叶斯网络结构具有重要的理 论意义和应用价值。 本文在研究国内外现有算法的基础上，针对其中的一些贝叶斯网结构学习算 法的不足，以k 2 网络结构评分为测度，提出了几种改进方法。主要工作包括三 个部分： 首先，针对目前学习算法参数较多，结构复杂的不足，将禁忌搜索( t a b u s e a r c h ) 应用到贝叶斯网结构学习当中，提出了一种基于禁忌搜索的贝叶斯网结 构学习算法。新算法首先利用加边、减边、逆向边三个算子产生当前解的邻域， 然后将禁忌表和蔑视准则结合使用来引导和限制搜索过程，两步骤迭代进行，最 后达到全局最优解或近似最优解。与其他算法相比，新算法结构简单、参数少， 易于实现和应用，同时求解质量也有一定的提高。 其次，针对蚁群优化学习贝叶斯网结构算法a c o b 的不足，提出了基于独 立性测试和蚁群优化的结构学习的改进算法i - a c o b 。新算法首先利用0 阶独立 性测试来限制侯选结构的搜索空间，避免了蚁群的一些不必要的搜索，然后融合 解的全局评分增益和节点间局部的互信息，给出了启发能力更强的启发函数来引 导随机搜索，实验结果表明，新算法能更有效地处理大规模数据，且大幅度提升 了学习速度。 最后，针对数据不完备情况下贝叶斯网算法学习精度不高的问题，将e m ( e x p e c t a t i o nm a x i m i z a t i o n ) 算法与i - a c o b 算法相结合，提出了能够直接从不 完备数据中学习贝叶斯网结构的新算法e a c o b 。首先随机初始化未观察到的数 据，得到完整的数据集，并利用蚁群算法学习得到初始网络结构：然后进行迭代 学习，在每次迭代中根据当前最好的贝叶斯网结构，利用e m 估计和随机的采样 插入对数据进行完备化，在完备数据下，利用改进的蚁群优化过程使结构不断进 化，直到获得全局最优的解。实验结果表明，新方法能够有效地从不完备数据中 学习贝叶斯网结构，且与新近的一些方法相比，具有更高的学习精度。 关键词贝叶斯网；结构学习；蚁群算法；禁忌搜索：缺失数据 a b s t r a c t a b s tr a c t b a y e s i a nn e t w o r k ( b n ) i sag r a p h i c a lr e p r e s e n t a t i o nf o rp r o b a b i l i t yd i s t r i b u t i o n s b e c a u s eo fi t sw e l l d e f i n e ds e m a n t i c sa n ds o l i dt h e o r e t i c a lf o u n d a t i o n s ，i tb e c a m ea n i m p o r t a n tt h e o r ym o d e li n t h ec o m m u n i t yo fa r t i f i c i a li n t e l l i g e n c e ，a n da l s oa p o w e r f u lf o r m a l i s mt oe n c o d et h eu n c e r t a i n t yk n o w l e d g e ；b nh a sb e e na p p l i e di nt h e f i e l d ss u c ha sm a c h i n el e a r n i n g ，m e d i c a ld i a g n o s e s ，f i n a n c i a lm a r k e ta n a l y s i s ，a n d a c h i e v eag r e a ts u c c e s s u s u a l l y , i ti sd i f f i c u l tt oc o n s t r u c tab a y e s i a nn e t w o r ko n l yb y t h ed o m a i ne x p e r t 。t h e r e f o r e ，l e a r n i n gab ns t r u c t u r ef r o md a t ai sv e r ym e a n i n g f u lt 0 i t sr e s e a r c ha n da p p l i c a t i o n b yu s i n gk 2n e t w o r ks c o r em e t r i c ，t h i sd i s s e r t a t i o nm a i n l yf o c u s e so nb a y e s i a n n e t w o r ks 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 t of i n das i m p l e rs t r u c t u r ea n da ne a s y i m p l e m e n t a t i o na l g o r i t h m ，w ei n t r o d u c e d t h et a b us e a r c hi n t ob a y e s i a nn e t w o r ks t r u c t u r el e a r n i n gp r o b l e m s ，p r o p o s e da t a b u s e a r c h b a s e db a y e s i a nn e t w o r ks t r u c t u r el e a r n i n ga l g o r i t h m ( t b n ) f i r s t ，t h e n e wa l g o r i t h mg e n e r a t e st h en e i g h b o r h o o d s o l u t i o n sb ya d d ，s u b t r a c ta n dr e v e r s ea r c o p e r a t o r s a n dt h e n ，t h et a b ul i s ta n da s p i r a t i o nc r i t e r i ag u i d et h es e a r c hp r o c e d u r e c o r p o r a t e l y a f t e rt h ei t e r a t i o no ft h et w os t e p sa b o v e ，t h ea l g o r i t h mw i l lf i n a l l yo b t a i n o p t i m a la n dn e a ro p t i m a ls o l u t i o n s c o m p a r e dw i t ho t h e ra l g o r i t h m s ，t b nh a sa s i m p l e rs t r u c t u r ea n df a s t e rs p e e d 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 rl e a r n i n gb a y e s i a n n e t w o r k s ( a c o - b ) ，w ep r o p o s e da ni m p r o v e da l g o r i t h mb a s e do nt h ec o n d i t i o n a l i n d e p e n d e n c et e s ta n da n tc o l o n yo p t i m i z a t i o n ( i a c o b ) f i r s t ，t h ei - a c o - b u s e s o r d e r - 0i n d e p e n d e n c et e s t st oe f f e c t i v e l yr 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 o t h a tm a n yu n n e c e s s a r ys e a r c h e so fa n t sc a nb ea v o i d e d a n dt h e n ，b yc o m b i n i n gt h e g l o b a ls c o r ei n c r e a s eo fas o l u t i o na n dl o c a lm u t u a li n f o r m a t i o nb e t w e e nn o d e s ，an e w h e u r i s t i cf u n c t i o nw i t hb e t t e rh e u r i s t i ca b i l i t yi s g i v e nt o i n d u c tt h ep r o c e s so f s t o c h a s t i cs e a r c h e s t h ee 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 as e t ss h o wt h a tt h e n e wa l g o r i t h mi se f f e c t i v ea n de f f i c i e n ti nl a r g es c a l ed a t a b a s e s ，a n dg r e a t l ye n h a n c e s c o n v e r g e n c es p e e dc o m p a r e dt ot h eo r i g i n a la l g o r i t h m 3 t ol e a r nb a y e s i a nn e t w o r ks t r u c t u r ef r o mi n c o m p l e t ed a t aw i t hh i g h e rp r e c i s i o n ， w ep r o p o s e da na p p r o a c hc o m b i n e dw i t hb o t hp r o c e s s e so fd a t ac o m p l e t i n ga n da c o f i r s t ，u n o b s e r v e dd a t aa r er a n d o m l yi n i t i a l i z e d ，t h u sac o m p l e t ed a t a s e ti sg o t b a s e d o ns u c had a t as e t ，a ni n i t i a l i z a t i o nb ni sl e a r n e db ya n tc o l o n ya l g o r i t h m s e c o n d ， i n l i g h t o ft h ec u r r e n tb e s ts t r u c t u r eo fe v o l u t i o n a r y p r o c e s s ，e x p e c t a t i o n - - i l i 北京工业大学工学硕士学位论文 m a x i m i z a t i o n ( e m ) e s t i m a t i n ga n dr a n d o m l ys a m p l i n ga r ep e r f o r m e dt oc o m p l e t e d a t a t h i r d ，o nt h eb a s i so ft h en e wc o m p l e t ed a t as e t ，t h eb ns t r u c t u r ei se v o l v e db y a ni m p r o v e da c o p r o c e s s f i n a l l y , t h es e c o n da n dt h i r ds t e p sa r ei t e r a t e du n t i lt h e g l o b a lb e s ts t r u c t u r ei so b t a i n e d e x p e r i m e n tr e s u l t ss h o wt h a tt h ea p p r o a c hc a n e f f e c t i v e l yl e a r nb ns t r u c t u r ef r o mi n c o m p l e t ed a t a ，a n di sm o r ea c c u r a t et h a ns o m e r e c e n ta l g o r i t h m s k e y w o r d sb 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 ，a n tc o l o n yo p t i m i z a t i o n ，t a b us e a r c h ， m i s s i n gd a t a i v 独创性声明 本人声明所呈交的论文是我个人在导师指导下进行的研究工作及取得的研 究成果。尽我所知，除了文中特别加以标注和致谢的地方外，论文中不包含其他 人已经发表或撰写过的研究成果，也不包含为获得北京工业大学或其它教育机构 的学位或证书而使用过的材料。与我一同工作的同志对本研究所做的任何贡献均 已在论文中作了明确的说明并表示了谢意。 签名：蜀缒三垒塑日期：趁芝缝髅旦 关于论文使用授权的说明 本人完全了解北京工业大学有关保留、使用学位论文的规定，即：学校有权 保留送交论文的复印件，允许论文被查阅和借阅：学校可以公布论文的全部或部 分内容，可以采用影印、缩印或其他复制手段保存论文。 ( 保密的论文在解密后应遵守此规定) 签名：拯趱塑导师签名：鲎鳖显：日期：逸! 篚地 第1 章绪论 第1 章绪论 1 1 本文的背景和研究意义 1 1 1 背景和研究意义 不确定性问题是人工智能领域中的一个重要的研究问题i lj ，其中以概率论为 基础的贝叶斯网是处理不确定性知识表示和推理的主要模型。贝叶斯网具有理论 基础坚实，结构直观，语义清晰等特点，因此成为处理不确定性知识的主流模型， 已经成功的应用到医疗诊断、金融分析、自动目标识别、军事等很多领域。 贝叶斯网的构造方法有两种，一种是通过咨询专家进行手工构造，一种是利 用计算机从数据集中学习。前者一般不采用，因为当数据量较大时，仅仅依赖于 专家知识构造网络是费时费力，甚至是不可能的 2 1 。因此国内外的学者主要兴趣 集中在如何从数据中学习贝叶斯网，从而使其成为当今的一个热门研究领域。 从数据中学习贝叶斯网的结构，可以概括为：找出与给定的数据集相对应的 后验概率最大的网络模型【3 4 1 。基于完备数据的结构学习方法相对比较成熟，其 中主要分为基于约束满足的方法和基于评分搜索的方法。 然而，现实世界中的数据并不都是完备的，因为某些变量的值不可观测或者 观测代价较大，所以导致数据集通常包含缺失值。另外，贝叶斯网的优势之一就 是可以进行缺失数据下的推理，然而与此同时要求其训练数据集必须是完备的就 难以让人信服。因此对不完备数据下贝叶斯网结构学习的研究更具有实际意义。 综上，全面深入的研究贝叶斯网络结构学习问题，无论在理论上还是在现实生活 的应用中都有着重要的意义和价值。 1 1 2 国内外研究现状 从数据中学习贝叶斯网络结构，是本领域的热点和难点问题。十几年来，国 内外的学者对其进行了积极的探索，并取得了一定的成果，其中数据完备时的算 法相对比较成熟。从实现的机理上，这些算法可概括为两种基本方法： 1 基于约束满足的方法。它将学习视为约束满足问题，即通过测试节点变量 问的条件独立性关系来学习贝叶斯网结构。s p i r t e s 在1 9 9 0 年提出的s g s 算法p j ， 在不给定结点顺序的情况下，利用条件独立性测试确定边的存在性和方向，但需 要指数级的条件独立性检验计算。1 9 9 1 年s p i r t e s 对s g s 算法的搜索策略进行改 进，提出y p c 算法【6 】，使用具有1 0 0 0 0 个样本的数据集进行a l a r m 网学习，产 北京工业大学工学硕士学位论文 生3 个缺失边和2 个冗余边。该算法对于稀疏网络的结构学习表现出较小的计算 量。1 9 9 7 年s e b a s t i a n 和m a r i 提出将b c ( b o u n da n dc o l l a p s e ) 算法应用于结构学习， 算法首先选择一个随机网络结构作为开始状态，然后为网络选择参数和计算网络 的得分，接着添加边，建立新的网络并使用b c 方法估计新网络参数的后验概率， 计算新网络结构的得分，选择得分较高的网络作为最终的网络状态。c h e n g j i e 在 其它约束满足方法的基础上提出基于互信息和独立性测试的算法【7 1 ，该算法分为 画草图、剪薄和增厚三个阶段来学习贝叶斯网络结构，表现出很好的性能和精度。 但是，基于约束满足的方法都需要指数级的条件独立性测试，高阶条件独立性测 试的计算代价很高，对于稀疏贝叶斯网络比较有效，但对复杂一些的贝叶斯网络 效率则很低。 2 基于评分搜索的方法。它将学习视为结构优化的过程，即利用评分函数寻 找与样本数据匹配程度最高的网络结构。1 9 9 2 年，c o o p e r 和h e r s k o v i t s 建立了著 名的基于贝叶斯评分( b a y e s i a ns c o r e ) 和爬山法搜索的l ( 2 算法博j ，该算法在给定 结点顺序这一先验信息的情况下，利用贝叶斯评分来评价模型与数据的符合程 度，通过爬山法来找出最佳网络结构。r e m c o 于1 9 9 4 年提出飚算法1 9 j ，使用最小 描述长度m d l 评分函数代替k 2 算法中贝叶斯评分函数进行贝叶斯网络结构学 习。与此同时，广大学者也尝试在没有任何先验信息的情况下进行贝叶斯网络结 构的学习。l a m 在1 9 9 4 年提出的算法【j o j 用最小描述长度m d l 作为衡量标准，完 全通过搜索与评价来找出正确的网络结构，而不需要知道结点顺序等先验信息。 2 0 0 2 年，l u i sm d ec a m p o s 提出了基于k 2 评分和蚁群算法的学习算法a c o b 【i ， 该算法有着较好的学习精度和效率。虽然基于约束的方法实现简单，但其高阶测 试的计算复杂且不可靠，故模型的学习精度难以保证。因此，基于评分搜索的学 习方法逐渐成为b n 结构学习的主流方法。 另外，一些学者也提出了将上述两种方法进行融合的结构学习算法。s i n g h 和v a l m r t a 提出了一种混合算法【1 2 j ，首先通过对一种基于独立性检验的p c 算法进 行改进来获得结点的顺序，在贝叶斯网络结构学习中，使用改进的k 2 算法确定 结点的顺序，然后使用依赖分析方法建立贝叶斯网络结构。2 0 0 9 年，国内的冀俊 忠等人【i3 】提出了基于独立性测试和蚁群优化的贝叶斯网结构学习算法，该算法 将基于约束的方法和评分搜索的a c o b 算法进行了有效的融合，在算法求解速度 和处理大规模数据的能力上有着较大的改进。 当数据不完备时，情况相对比较复杂。通常先对数据进行相应的修补，然后 在进行完备数据下的结构学习。19 9 7 年，c h i c k e r i n g 介绍了基于g i b b ss a m p l i n g 数据修补方法进行网络结构学习的算法【l4 1 ，其主要问题是计算代价较大，结果 不是很准确。19 9 8 年f r i e d m a n 提出s e m ( s t r u c t u r ee x p e c t a t i o n m a x i m i z a t i o n ) 算 法i i5 | ，f r i e d m a n 证明s e m 可以在算法的每个循环内查找较好的得分网络，但是 第l 章绪论 该算法的主要问题是容易陷入局部最优解。1 9 9 9 年，m y e r s 在p e d r o 工作的基础 上，应用进化算法进行数据缺失时网络结构的学习 1 6 l ，但是进化算法的随机性 较大，且收敛性难以保证。2 0 0 1 年，r a m o n i 等提出基于b c 方法的学习算法i i ， 但该算法仅对特定的数据缺失模式才比较有效果。2 0 0 5 年，r i g g e l s e n 等提出了 基于i m p o r t a n c es a m p l i n g 数据完备化的e m c 4 算法【l 引，该算法的目标在于用较小 的计算代价来获得次优解。与此同时，国内的一些学者也对此问题进行了研究， 主要思路是对国外学者算法进行改进或融合。2 0 0 1 年清华大学田凤占等人提出 基于e m 完备化方法和进化算法的e m e a i l 9 】算法，该算法首先通过e m 算法进 行数据完备化，然后通过进化算法来搜索网络结构。2 0 0 1 年吉林大学刘大有、 王飞等提出e g a ( e x p e c t a t i o n & g e n e t i ca l g o r i t h m ) 算法，该算法也是应用e m 算 法进行数据完备化，然后再用遗传算法来进行结构寻优。2 0 0 3 年田凤占等人又 提出e m i 算法1 2 0 】，应用b c 完备化和基于约束满足的结构学习方法解决数据不 完备下的b n 学习问题。2 0 0 4 年王双成、苑森淼提出b n g s ( b a y e s i a nn e t w o r k & g i b b ss a m p l i n g ) 算法t 2 i 】，该算法应用g i b b ss a m p l i n g 来处理缺失数据，然后应 用约束满足的方法进行结构寻优。2 0 0 6 年，w o n gm a n - l e u n g 等人提出了e m 和 h e a m 算法相结合的混合学习算法【2 2 1 ，该算法首先用e m 进行数据完备化，然 后应用e a 算法的改进算法h e a m 进行结构学习。2 0 0 7 年胡春玲、胡学钢提出 了b c i s o r 2 3 1 结构学习算法，算法首先应用b c 进行变量集联合概率的估计， 然后应用约束满足的思想进行结构学习。 1 2 本文的主要研究内容 本文在研究国内外现有算法的基础上，针对一些贝叶斯网结构学习算法的不 足，以k 2 网络结构评分为测度，提出了相应的改进方法。主要工作包括三个部 分： 1 尽管现有的许多贝叶斯网结构学习算法能够取得较好的结果，但是通常 算法本身太复杂，参数较多，这给算法的调试和应用带来一定的困难。针对这个 问题，本文将禁忌搜索应用到贝叶斯网结构学习当中，提出了一种基于禁忌搜索 的贝叶斯网结构学习算法。新算法首先利用加边、减边、逆向边三个算子产生当 前解的邻域，然后将禁忌表和蔑视准则相结合来引导和限制搜索过程，两个步骤 迭代进行直至达到全局最优解。与其他算法相比，新算法具有结构简单、参数少、 求解时间短且能够找到精度相同甚至更好的解等特点。 2 针对现有网络结构学习算法a c o b 容易陷入局部最优的不足，提出了基 于独立性测试和蚁群优化的结构学习算法i - a c o b 。算法首先利用0 阶独立性测 试米限制候选结构的搜索空l _ i j ，避免了蚁群的一些不必要的搜索；然后融合解的 北京工业大学工学硕士学位论文 全局评分增益和节点间局部的互信息，给出了启发能力更强的启发函数来引导随 机搜索。实验表明，新算法具有更好的处理大规模数据的能力和较快的学习速度。 3 针对现实世界中数据不完备的情况，将e m 算法与i - a c o b 算法相结合， 提出了能够直接从不完备数据中学习贝叶斯网结构的新算法e a c o b 。算法首先 随机初始化未观察到的数据，得到完整的数据集，并利用蚁群算法学习得到初始 网络结构：然后进行迭代学习，在每次迭代中根据当前最好的贝叶斯网结构，利 用e m 估计和随机的采样插入对数据进行完备化，在完备数据下，利用改进的蚁 群优化过程使结构不断进化，直到获得全局最优的解。实验结果表明，新方法能 够有效地从不完备数据中学习贝叶斯网结构，且与新近的一些方法相比，具有更 高的学习精度。 1 3 本文组织结构 第一章：绪论。对课题的研究现状和研究意义进行了介绍，并详细阐述了国 内外学者的研究现状，随后介绍了本课题的研究内容。 第二章：对贝叶斯网概率模型进行了概述，详细的介绍了基于约束满足和评 分搜索的两种基本的结构学习方法，最后介绍了贝叶斯评分及其勉评分。 第三章：提出了基于禁忌搜索的结构学习算法。首先介绍了禁忌搜索的基本 思想和算法核心部分的设计原则：其次，结合贝叶斯网结构学习的特点，详细的 定义了新算法的禁忌表、蔑视准则等核心模块，给出了算法描述：最后给出了实 验结果和分析。 第四章：针对a c o b 的不足，提出了基于独立性测试和蚁群优化的结构学 习算法。首先介绍了蚁群优化算法的基本思想：然后，描述了新的基于独立性测 试和蚁群优化的混合学习算法i - a c o b 的算法思想和改进策略；最后给出了实 验结果和分析。 第五章：针对数据缺失的情况，提出了基于e m 和蚁群算法的不完备学习算 法。首先，介绍了不完备数据的完备化方法，然后给出了新算法的核心思想；详 细的介绍了算法的框架；最后进行了实验结果的比较和分析。 第2 章贝叶斯网概述 2 1 贝叶斯网基础 第2 章贝叶斯网概述 贝叶斯网又被称作贝叶斯信念网【2 4 1 ，它可以表示为一个二元组b n = ( g ，8 ) ， 其中g = ( n ，e ) 为一个有向无环图，用来表示网络结构。n = 五，五，墨，以 为 节点集合，对应随机变量的集合。e 是边的集合，代表随机变量间的依赖关系。 日为网络参数向量，是b n 中节点间依赖程度的一种精确表示。向量p 中包含若 干分量，每一个分量以f | i x i = p ( 置i ( z ”，表示网络结构中节点的条件概率， 为一个网络参数。兀( 五) 为节点置的父母节点的组合。 图2 1 是贝叶斯网的一个实例【2 5 1 。 n e e d s p ( g = t l a p ( g = h a p a t i e n t sa g e 7 5 p ( a - 1 d = 0 1 v i s i o ni m f i r o v e d v i s i o n r e t i n a lr e f l e x b ys q u i n t i n g c o m p l a i n t sd e t e c t a b l e p ( v = t i g 一= t ) = 0 一8 0 p ( s 5 t i g 。t ，c 2 t ) 。0 9 5 p ( r = t l c = d = 0 2 5 p ( v ：t l g _ f ) ：0 0 5 p ( s 5 t i g = t ，c 2 f ) 。0 7 5 p ( r - = t i c = f ) = 0 9 5 。p ( s = t i g = f ，c 2 t ) 。0 4 0 p ( s = 卅g = f ，c = f ) = 0 0 5 图2 1 一个贝叶斯网实例 f i g u r e2 - 1ab a y e s i a nn e t w o r ki n s t a n c e 示例中每个节点的取值都是二元的，其每个节点的意义为：当病人的年龄大 于7 5 岁( a ) ，病人需要一副眼镜( g ) ，病人有白内障( c ) ，病人的视力增强了( v ) ， 病人抱怨视力弱( s ) ，以及病人的视网膜反射是可探测的( r ) 。节点a 和g 之间的 边表示了a 和g 是直接依赖的，相对于其他节点来说。节点a 和s 之间缺少一条 边表示a 和s 之f u j 的依赖关系是通过节点g 和c 来实现的。 北京工业大学工学硕士学位论文 节点间依赖的强度是由每个节点的参数表来表示的。例如，在图2 1 中，当 a 为真时，g 为真的概率是p ( g = tl 口= t ) = 0 7 5 ，可以被解释为，当病人的年龄 大于7 5 岁时，他需要一副眼镜的概率是o 7 5 。值得说明的是，所有的概率中， 当病人a = f 时并没有直接给出，它们是可以由给出的数据推导出来。我们可以输 入一个观测到的节点的取值，来通过贝叶斯网的概率推理，迅速的得到其他节点 事件发生的概率。 当给定了网络结构g ，则表示了一组独立性的断言，在这个前提下，结合参 数d ，一个贝叶斯网可以唯一地确定节点n 的联合概率分布。由于条件独立性的 性质，贝叶斯网比直接的按照传统公式计算联合概率要简单得多。也就是说，条 件独立性极大地的增加了贝叶斯网建模、推理的效率。 2 2 贝叶斯网结构的学习 由贝叶斯网的定义可知，b n 的网络结构是用有向无环图来表示的。对于一 个节点个数为n 的有向无环图，设f ( n ) 是所有由n 个节点组成的有向无环图的 个数。r o b i n s o n 给出了关于( 刀) 的计算公式【2 6 l ： ( 1 ) = 1 ， m ) = 扣) j + 1 志m _ f ) 础 q 。1 从式( 2 1 ) 可见，贝叶斯网结构空间随着节点数n 增大而迅速增大。而且， 贝叶斯网结构学习问题已经被证明是一个n p h a r d 问题【2 7 1 ，所以采用确定性的 精确算法求解最优网络结构通常是不可行的，故一般采用启发式搜索算法来对其 进行求解。 2 2 1 基于约束满足的方法 在基于约束满足的方法中( 也称依赖分析或者基于条件独立性测试的方法) ， b n 被看作是变量间独立性关系的图结构。该方法先通过计算节点间的互信息 ( m u t u a li n f o r m a t i o n ，m i ) 和条件独立性测试( c o n d i t i o n a li n d e p e n d e n c et e s t ，c i ) 来找出数据集d 中各个变量间的条件独立性关系，再寻找和这些条件独立性断 言一致的网络模型。这类算法主要的计算代价在于节点间互信息和条件独立性测 试的计算。随着节点数目的增多，独立性测试的次数成指数级增长。互信息和条 件独立性测试是信息论中的概念，有必要进行一下简单的介绍。 第2 章贝叶斯网概述 在信息论中，两个节点五，x ，的互信息定义为 她圳= 荟p ( ) l o g 篙杀 ( 2 2 ) 给定条件c ，则条件互信息可以定义为： 她州c ) = 互p ( x ，, x j , c ) l o g 揣 ( 2 - 3 ) 其中置，x ，为两个节点，c 是多个节点的集合。通常情况下，应用条件互信 息来进行独立性测试，来测量两个节点的平均信息量。基本上有两种方法：一种 是设定一个阈值s ，如果，( 置，x ，ic ) 小于这个阈值，我们则认为这两个节点在 给定条件集c 时是条件独立的。另外一种方法，令，= 2 xn x ，( 置，x ，ic ) ，其中 n 为实例总数，则当样本总数n 足够大的时候，t 服从以ic i ( 1 置i - 1 ) ( ix jl - 1 ) 为 自由度的z 2 分布。其中ix ，i _ 口7 为变量的值域容量，令检验假设为：给定c 的条件下，x , 和x j 独立，也即给定置信度g 下，通过z 2 检验的可以认为节点 置和x ，之间一定不存在一条边在网络结构中，因此可以在选边的过程中加以排 除。 下面以c h e n gj i e 的三阶段算法【7 1 为例，说明基于约束满足方法的大致流程： 该算法采用互信息和条件互信息进行变量间定量的条件独立性检验，对于给 定的阈值( 一般s = 0 0 1 ) ，如果条件互信息，( 五，x ，lc ) o e m a k = l 问 其由i。7 、 一i 若否 是网络参数 m 咖是充分统计量。 ( 2 8 ) 是指随机变量x 的取值- g l 重l 对于完整的数据集d 来说，所驰可以直接从数据集进行统计得出，进而求出 北京工业大学工学硕士学位论文 p 。当数据集为不完备时，就不能从数据集中直接得出，p 从而无法求出， 也就不能进行结构的评分计算，这是缺失数据下结构学习的难点所在。此问题在 第五章有详细的介绍。 2 。2 3 贝叶斯评分及k 2 评分 对于应用贝叶斯评分进行结构学习的研究，国外的学者做了很多相关的工 作。其中最著名的是c o o p e r 和h e r s k o v i t s 提出的k 2 算法【8 j ，他们应用贝叶斯评 分和爬山法搜索的方法来优化网络模型，其中的评分函数即为贝叶斯评分的一种 简化，又被称为k 2 评分。由于它拥有坚实理论基础，并且也是一种实用的从数 据集中选择统计模型的方法，所以应用十分广泛。本文所有算法均采用k 2 评分 作为评价网络结构的测度。下面对贝叶斯评分进行详细的介绍。 从统计学的观点来看，一个网络结构是一个统计模型，在这种方法中，基本 的思想是应用从观测数据中获得的网络结构的后验概率作为尺度来测量一个网 络结构的质量。要比较两个网络结构g l 和g 2 ，我们可以计算似然比： ! ( g ! 望2 ：! ( g ! 望2 ( 2 9 ) - - - - 一= - ；一 三- 7j 尸( g 2d )尸( g 2 ，d ) 贝叶斯评分是在概率模型下的一系列假设中推导出来的。其中，最重要的一个假 设就是由条件概率( 参数0 ) 所确定的先验概率是均匀分布的。 令n = 五，五，以) ，其中z 的取值范围 薯l ，薯：，) ，2 ，江1 ，刀。令 g 表示一个在n 上的网络结构，我们假设网络参数d 的先验分布满足：( 1 ) 令 = ) 蚓。，则嘭的先验概率分布独立于其他参数b y 。( 2 ) 若吼中的参数满 足= 1 的均匀分布，则可知岛服从狄利克雷分布。现在，令为数据集d 量 中变量墨的值取靠时，其父节点丌取值为第个组合时的个数。最后，令 ：f ，= 。c o o p e r 和h e r s k o v i t s 用p ( g ，d ) 作为评分函数： k = l b ( g ，d ) = p ( g ，d ) = 尸( g ) p ( d ig ) = 尸( g ) n p ( tlg ) 叫g ，购揣觚 q 。1 第2 章贝叶斯网概述 其中尸( g ) 是网络结构g 的先验概率分布。举例子来说，如果一个专家建议 存在一条特定的边或者一个局部结构，则符合给定的网络结构应该被给定一个更 高的先验概率。如果对网络结构没有先验概率，或者没有特殊的优先的网络结构， 那么先验概率p ( g ) 可以被假设服从均匀分布，即p ( g ) = c ，c 是常量。给定一个 网络结构g ，条件概率o o k 可由贝叶斯估计器进行估计： 歌川i d g ) = 筹 ( 2 - 其中e 表示期望，贝叶斯评分可以解释为：如果对于所有的网络结构g ，一 个网络结构g o 有p ( g o ，d ) p ( g ，d ) ，那么对于当前的数据集d 来说，g o 是贝叶 斯评分意义上最符合d 的网络结构。 在算法实现过程中，通常对公式( 2 - 1 0 ) 进行简化，方法是用l o g ( p ( g ，d ) ) 来 代替p ( g ，d ) ，从而得到评分函数的分解形式： 厶：( g ：d ) = 厶：( 五，n ( 五) ：也n ( 而) ) 彬，：如( 揣胁k = lc 剐 q 。1 2 值得说明的是，评分函数的可分解性是贝叶斯网结构学习中最重要的性质。 利用此性质，搜索过程能够重用大部分结构评分，减少了运算代价。 2 3 本章小结 本章首先介绍了贝叶斯网的基本概念，以及基于约束满足和基于评分搜索的 两种基本的贝叶斯网结构学习方法，并介绍了两种方法的优缺点。然后重点介绍 了本文所采用的k 2 评分机制，给出了k 2 评分的分解形式，为后续章节的结构 学习提供了理论基础。 第3 章基于禁忌搜索的贝叶斯网结构学习算法 第3 章基于禁忌搜索的贝叶斯网结构学习算法 禁忌搜索是一种亚启发式搜索算法，能够有效的取得大规模组合优化问题的 全局最优解或近似最优解，且算法思想相对简单。针对现有的一些贝叶斯网结构 学习算法结构复杂、参数较多、不利于调试和应用的不足，本章将禁忌搜索引入