论文研究-基于互信息的贝叶斯网络结构学习算法.pdf

所需积分/C币:10 2019-09-08 11:16:42 530KB .PDF
收藏 收藏
举报

结构学习是贝叶斯网络的重要分支之一,而由数据学习贝叶斯网络是NP-完全问题,提出了一个由数据学习贝叶斯网络的改进算法。该算法基于互信息知识构造初始无向图,并通过条件独立测试对无向边添加方向;同时提出了一个针对4节点环和5节点环的局部优化方法来构造初始框架,最后利用贪婪搜索算法得到最优网络结构。数值实验结果表明,改进的算法无论是在BIC评分值,还是在结构的误差上都有一定的改善,并且在迭代次数、运行时间上均有明显降低,能较快地确定出与数据匹配程度最高的网络结构。
陈一虎:基于互信息的贝叶斯网络结构学习算法 2012,48(13) 41 若S=d 其复杂度为O(n);向空图添加无向边构造初始无向 则E=E{X-Z,Y-Z}∪{X→Z,Y→Z}; 图的复杂度为On),故步15的复杂度为On);步 1.9确定P0屮所有形如X→Y-Z的子结构; 16需要处理所有的三角环,寻找所有三角环的复杂 1.10对于每个子结构X→Y-Z 度为O(m),假设最多有n个三角环,而实际上三角 若P(ZY)=P(Zy,X) 环的个数小于n,对于每个三角环,最坏情况下是对 则令E=E{Y-2}U{→Z} 三角环中的三条边都进行条件独立性测试,其复杂 否则,令S=φ; 对每个节点W∈{X,F,Z} 度为O(m),对n个三角环进行条件独立性测试的复 计算H与其他各节点(不包含Y)的互信息并降序排杂度为O(m),从而步1.6的复杂度为Om)+O(); 列没前三个与W的互信息最大的节点集为T,若X∈Tnp且 确定形如Ⅹ-Z-Y和X→Y-Z的子结构的复杂度 Z∈Tn,则令S=SUW}; 为O(n),而最多有n个这样的子结构,对每个子结 若S-g,则令E-E∪{z→H}; 构进行条件独立测试的复杂度为O(m),从而步1.7 111付于P0中每个含有无向边的4节点环和5节点环,1.10的复杂度为O(mn)+O(n3);确定所有4节点环和 构造所有可能的非循环有向子图,然后利用得分函数确定出5节点环的复杂度为O(n),对于每个环,所有可能的 具有最高得分的子图S,令P=PUS0,如果多个子图具有非循环有向圈的个数是固定的(4节点圈是14,5节点 最高得分,则则任选一个作为S0 圈是30),计算BC得分的复杂度为O(m)2;而最多 112对P0中尚未确定方向的无向边添加任意方向,使之存在n个圈,那么步111的复杂度为On)+Om); 变为非循环环有向图。 另外,步1.12的复杂度为OE)。由此可知,阶段1的 2 Search phase 调用算法 Find-Compelled确定P的本质图Pb; 复杂度为O(m2)+O(n)。 令P=P 对于阶段2,算法Find- Compelled的复杂度为 while ( true)d On2),由于在实际生活中算法搜索时遇到的网络结 令M是由P开始所有可能的操作算子O的集合 构都是相当稀疏的,从而整个算法的复杂度为 ifM=0或 O(n2)+O(mn2)。也就是说, -GREEDY-E算法的复杂 maxscore increment(m, P)sO 度在最坏情况下,是节点个数的多项式函数和样本 return p 个数的线性函数 7=arg maxm c M score_increment(m, P); 5数值实验 P=apply l to P: 在标准贝叶斯网络Aarm上测试此 - GreedY-e end while 算法,其中 Alarm网络如图1所示。将测试结果与原 其中,函数 core increment(m,P)表示将算子m始贪婪算法进行比较分析。 应用于P后所引起的得分增量 Matlab中利用工具包 FulIbnt-1.0.4,由真实网络 随机生成10000个数据样本,对信息-贪婪算法进行 4复杂度分析 测试。数值实验屮用于比较分析的参数如下。 下面分析本文提出的 I-GREEDY-E算法的复杂 (1)Sco:最优本质图G的BC得分值; 度。设m和n分别表示样本个数和变量个数,第1阶 (2)CEs:与真实网络相比,信息-贪婪算法正确 段Drat的复杂度如下:步1.1需要计算所有节点对之确定出的边条数; 间的互信息,因为互信息是对称的,故只需要计算 (3)MEs:与真实网络相比,信息-贪婪算法没有 m(n-D2次互信息计算每对节点互信息的复杂度为确定出的边条数; O(m),故步1.1的复杂度为O(m);步12是确定所 (4)WOs:与真实网络相比,信息-贪婪算法确定 有n个节点的最大互信息,此时可利用复杂度为出的具有相反方向的有向边条数; O(n2)的冒泡方法对每个节点的互信息进行排序,故 (5)WCs:信息-贪婪算法确定出的不存在于真 42 2012,48(13) Computer Engineering and Applications计算机工程与应用 16 15 (19}(9)-(14 6)(33 图1 Alarm网络图 18 431 2)+5 34 20)(22}(17 图2由I- GREEDY-E算法所得的最优结构图 表1不同容量下两种算法的实验结果 算法 算法 样本容量结果 GREEDY-E 样本容量结果 I-GREEDY-E I-GREEDY-E GREEDY-E C-4.4715E+004-59053E+004 8.5825E+004 1.1737E+005 31 10 12 MES 12 4000 wOs 8000 WOs 4 WCs 17 19 GES 0 19 12 10 12 64895E+00488311E+004 -1.0572E+005-1.4705E+005 31 MES 12 MES 2 12 6000 wOs 100000s wCs wCS GES 19 N 10 12 NI 10 18 实网络的边条数 算法在10000个样本数据下得到的最优网络结构。 (6 GEs: GEs=MEs+WOs+WCs 由实验可知:与原始贪婪算法 GREEDY-E相比 (7)M:信息-贪婪算法的迭代次数。 I-GREEDY-E不仅具有较高的BC得分和相对较多 表1给出了原始贪婪算法和本文的改进算法在的真实边,而且随着抽样规模的扩大,缺失边和冗余 不同样本容量数据集合上的实验结果;图2是由改进边明显减少,迭代次数也相对降低。由此可知,改进 陈一虎:基于互信息的贝叶斯网络结构学习算法 2012,48(13) 算法能够获得更好的求解质量,并且对于构造大规 faults in electrical power systems of spacecraft and air- 模网络结构是可行和高效的 craft[C]/Proceedings of the 20th Innovative Applica tions of artificial Intelligence Conference california 6结语 AAAI Press,2008:1699-1705 8 Julio C r, guillermina M, Ludivina GFault diagnosis 基于变量间的互信息和条件独立测试以及得分 in an industrial process using Bayesian networks: appli- 贪婪搜索方法,提出了一种由数据构造贝叶斯网络 cation of the junction tree algorithm[ C]/Proccedings of 结构的改进算法 I-GREEDY-E。本文算法从空图开 Electronics. Robotics and Automotive Mechanics Confer 始,先由给定数据计算变量间的互信息,然后根据互 ence,2009:30l-306 信息和条件,独立性测试构造一个关于真实网络的[9] Juan M F, Juan F H, Benjamin P. Introduction to the spe 初始框架;同时提岀了一个针对4节点环和5节点环 cial issue on graphical models and information retrieval[JI 的局部优化方法构造初始框架,不仅有效地缩小了 Journal of Approximate Reasoning, 2009, 50(7): 929-931 搜索空间,而且也大大节省了搜索时间。最后利用 110 Dominik S Degrees of conditional in dependence: a 贪婪算法进行穷举搜索,确定最优贝叶斯网络结构。 framework for approximate Bayesian networks and examples related to the rough set-based feature selec- 文中提出的 I-GREEDY-E算法是在标准网络 tion[J].Information Sciences, 2009, 179(3): 197-209 Alarm网络上进行测试的,数值实验结果表明改进算 l11 Kim DC, Wang X, Yang C, et al. l earning biological 法能更高效、准确地确定出大规模的网络结构;与 network using mutual information and conditional inde GREEDY-E算法相比,Ⅰ GREEDY-E算法大大节省 pendence[J]. BMC Bioinformatics, 2010, 11(3): 59-72 了搜索时间,并能相对较快地确定出具有最高得分[12] Verma t, Pearl J Equivalence and synthesis of causal 的最优结构。大多元启发式方法如蚁群优化P可与 models[C)/pRoceedings of the 6th Conference on Uncer 本文的 GREEDY-E算法结合起来使用,以避免陷入 tainty in Artificial Intelligence. New York: Elsevier Sci- 局部最优结构,这也是将来的研究方向。 ence,1990:220-227 [13 Chen Xuewen, Anantha G, Lin Xiaotong. Improving Bayesian network structure learning with mutual infor- 参考文献: mation-based node ordering in the k2 algorithm[J] [1 Fernbach M P, Sloman A S Causal learning with local IEEE Transactions on Knowledge and Data Engineering computations[j]Journal of Experimental Psychology: 2008,20(5):1-13. Learning, Memory, and Cognition, 2009, 35(3): 678-693 [14 Pinto P C, Nagele A, Dejori M. Using a local discov [2] Langseth H, Nielsen T D, Rumi R Inference in hybrid ery ant algorithm for Bayesian network structure Bayesian networks[J]. Reliability Engineering System learning[J].IEEE Trans on Evolutionary Computation Safety,2009,94(10):1499-1509 209,13(4):767-779 3 de Melo A C v, Sanchez A J Soflware maintenance [15 Koivisto M. Advances in exact Bayesian structure dis project delays prediction using Bayesian networks [J.Ex covery in Bayesian networks[C]//Proceedings of the pert Systems with Applications, 2008, 34(2): 908-919 22nd Conference on Uncertainty in Artificial Intelli- [4] Honari B, Donovan J, Murphy E Using Bayesian net- gence. Arlington, Virginia: AUAI Press, 2006: 241-248 yorks in reliability evaluation for an (r,s)-out-of-(m, n): [16] Silander T, Myllymaki P A simple approach for finding F distributed communication system[J]Journal of Statis- the globally optimal Bayesian network structure[C/? tical Planning and Inference, 2009, 139(5): 1756-1765 Proceedings of the 22nd Conference on Uncertainty 5 Daniel S, Kiureghian A D Bayesian network enhanced in Artificial Intelligence. Arlington, Virginia: AUAI Press with structural reliability methods: methodology [] Jour- 2006:445-452 nal of Engineering Mechanics, 2010, 92(10): 1413-1420 [17 de Cassio C, Zeng Z, Ji QStructure learning of Bayesian [6 Huang Yingping, McMurran R, Dhadyalla G Probabilit networks using constraint[C]/Proceedings of the 26th based vehicle fault diagnosis: Bayesian network method[J] International Conference on Machine Learning. Corvallis Journal of Intelligent Manufacturing, 2008, 19(3): 301-311 Oregon: AUAI Press, 2009: 213-221 [7 Mengshoel O J, Darwiche A, Cascio K Diagnosing (下转52页)

...展开详情
试读 5P 论文研究-基于互信息的贝叶斯网络结构学习算法.pdf
立即下载 低至0.43元/次 身份认证VIP会员低至7折
抢沙发
一个资源只可评论一次,评论内容不能少于5个字
weixin_38743506 欢迎大家使用并留下宝贵意见
2019-09-08
  • 至尊王者

    成功上传501个资源即可获取
关注 私信 TA的资源
上传资源赚积分,得勋章
最新推荐
论文研究-基于互信息的贝叶斯网络结构学习算法.pdf 10积分/C币 立即下载
1/5
论文研究-基于互信息的贝叶斯网络结构学习算法.pdf第1页

试读结束, 可继续读1页

10积分/C币 立即下载 >