基于混合方式的贝叶斯网络等价类学习算法

doi:10.3969/j.issn.0372-2112.2013.01.018

电子学报 ›› 2013, Vol. 41 ›› Issue (1): 98-104.DOI: 10.3969/j.issn.0372-2112.2013.01.018

基于混合方式的贝叶斯网络等价类学习算法

朱明敏¹, 刘三阳^1,2, 杨有龙¹

1. 西安电子科技大学理学院数学系,陕西西安 710071;
2. 西安电子科技大学综合业务网国家重点实验室,陕西西安 710071

收稿日期:2011-03-16 修回日期:2012-08-30 出版日期:2013-01-25
- 作者简介:
- 朱明敏 女,1985年生于陕西咸阳.西安电子科技大学数学系博士研究生.研究方向:最优化理论、算法及其在贝叶斯网络学习中的应用. E-mail:zmmzhu2010@126.com 杨有龙 男,1967生于陕西西安.西安电子科技大学数学系教授、博士生导师.研究方向:图模型学习及其应用. E-mail:ylyang@mail.xidian.edu.cn
- 基金资助:
- 国家自然科学基金 (No.60974082,No.61075055); 国家杰出青年科学基金 (No.11001214); 西安电子科技大学基本科研业务基金 (No.K5051270013)

Structural Learning Bayesian Network Equivalence Classes Based on a Hybrid Method

ZHU Ming-min¹, LIU San-yang^1,2, YANG You-long¹

1. Department of Mathematics, Xidian University, Xi'an, Shaanxi 710071, China;
2. State Key Laboratory of Integrated Service Networks, Xidian University, Xi'an, Shaanxi 710071, China

Received:2011-03-16 Revised:2012-08-30 Online:2013-01-25 Published:2013-01-25
- Supported by:
- National Natural Science Foundation of China (No.60974082, No.61075055); National Natural Science Foundation of China for Distinguished Young Schoolars (No.11001214); Fundamental Research Funds for Xidian University (No.K5051270013)

摘要/Abstract

摘要： 贝叶斯网络(BN)是不确定知识表示和推理的主要方法之一,是人工智能中重要的理论模型.针对现有混合方法学习BN结构不稳定、容易陷入局部最优等问题,本文将图论中的最大主子图分解理论与条件独立(CI)测试相结合,同时引入少量的局部评分搜索,提出一种新的基于混合方式的BN等价类学习算法.新算法通过确定所有变量的Markov边界构造网络的无向独立图,并对无向图进行最大主子图分解,从而将高维的结构学习问题转化为低维问题,然后利用低阶CI测试和局部评分搜索识别子图中的V结构.理论证明以及实验分析显示了新算法的正确性和有效性.

关键词: 贝叶斯网络, 最大主分解, Markov边界, 有向无环图, 条件独立

Abstract: Bayesian Network (BN) is one of the most important methods for representing and inferring with uncertainty knowledge,and also a powerful theory model within the community of artificial intelligence.To solve the drawbacks of hybrid methods for learning BNs which are easy to fall into local optimum and unreliable for learning large data set,we propose a novel hybrid algorithm for learning BN equivalence classes which combines ideas from maximal prime decomposition (MPD) of graph theory,conditional independence (CI) tests,and local search-and-score techniques in an effective way.It first reconstructs the undirected independence graph of a BN and then performs MPD to transform the undirected graph into its subgraphs.Finally,the new algorithm uses only lower-order CI tests and local BDeu score to check the v-structure of each subgraph.Theoretical and experimental results show that the proposed algorithm is correctness and effective.

Key words: Bayesian network, maximal prime decomposition, Markov boundary, directed acyclic graph, conditional independence

中图分类号:

TP18

朱明敏, 刘三阳, 杨有龙. 基于混合方式的贝叶斯网络等价类学习算法[J]. 电子学报, 2013, 41(1): 98-104.

ZHU Ming-min, LIU San-yang, YANG You-long . Structural Learning Bayesian Network Equivalence Classes Based on a Hybrid Method[J]. Acta Electronica Sinica, 2013, 41(1): 98-104.

参考文献

[1] A Aussem,S R de Morais.A conservative feature subset selection algorithm with missing data[J].Neurocomputing,2010,73(4-6):585-590.
[2] 王洪泊,涂序彦.一种面向最经济服务流的可视化动态贝叶斯网络模型.电子学报,2011,39(6):1331-1335.Hongbo WANG,Xuyan TU.A visual dynamic bayesian network model oriented most economical service-flows,Acta Electronica Sinica,2011,39(6):1331-1335.(in Chinese).
[3] S R de Morais,A Aussem.A novel Markov boundary based feature subset selection algorithm[J].Neurocomputing, 2010,73(4-6):578-584.
[4] J P Pellet,A Elisseef.Using Markov blankets for causal structure learning[J].Journal of Machine Learning Research,2008,9:1295-1342.
[5] C Borgelt.A conditional independence algorithm for learning undirected graphical models[J].Journal of Computer and System Sciences,2010,76(1):21-33.
[6] Xianchao Xie,Zhi Geng.A recursive method for structural learning of directed acyclic graphs[J].Journal of Machine Learning Research,2008,9:459-483.
[7] Xuewen Chen,G.Anantha,Xiaotong Lin.Improving Bayesian network structure learning with mutual information-based node ordering in the K2 algorithm[J].IEEE transactions on knowledge and data engineering,2008,20(5):1-13.
[8] L Bouchaala,A Masmoudi,F Gargouri,A Rebai.Improving algorithms for structure learning in Bayesian networks using a new implicit score[J].Expert Systems with Applications,2010,37(7):5470-5475.
[9] E Perrier,S Imoto,S Miyano.Finding optimal Bayesian network given a super-structure[J].Journal of Machine Learning Research,2008,9:2251-2286.
[10] 冀俊忠,张鸿勋,胡仁兵,刘椿年.一种基于独立性测试和蚁群优化的贝叶斯网学习算法[J].自动化学报,2009,35(3):281-288.Junzhong Ji,Hongxun Zhang,Renbing Hu,Chunnian Liu.A Bayesian network learning algorithm based on independence test and ant colony optimization[J].Acta Automatica Sinica,2009,35(3):281-288.(in Chinese).
[11] 贾海洋,陈娟,等.基于混合方式的贝叶斯网弧定向算法[J].电子学报,2009,37(8):1842-1847.Haiyang JIA,Juan CHEN,et al.A Hybrid method for orienting edges of Bayesian network[J].Acta Electronica Sinica,2009,37(8):1842-1847.(in Chinese).
[12] I Tsamardinos,L F Brown,C F Aliferis.The max-min hillclimbing BN structure learning algorithm[J].Machine Learning,2006,65(1):31-78.
[13] K Olesen,A Madsen.Maximal prime subgraph decomposition of Bayesian networks[J].IEEE Trans Syst Man Cybern B,2002,32:21-31.
[14] R W Robinson.Counting unlabeled acyclic digraphs[J],Combinational Mathematics,1977,622:28-43.
[15] D Heckerman,D Geiger,D M Chickering.Learning BNs:The combination of knowledge and statistical data[J].Machine Learning,1995,20:197-243.
[16] R E Neapolitan.Learning Bayesian Networks[M].Prentice-Hall,Englewood Cliffs,NJ,2004.
[17] S Kullback.Information Theory and Statistics[M].Dover Publication,1968.
[18] S L Lauritzen. Graphical Models[M].Clarendon Press,Oxford,1996.
[19] S Lauritzen,D Spiegelhalter.Local computations with probabilities on graphical structures and their application on expert systems[J].J Royal Statistical Soc,1988,50:157-224.
[20] I Beinlich,G Suermondt,R Chavez,G Cooper.The ALARM monitoring mystem:a case study with two probabilistic inference techniques for belief networks[A].Proc Second European Conf Artificial Intelligence in Medicine[C].NK USA,1989.247-256.

基于混合方式的贝叶斯网络等价类学习算法

Structural Learning Bayesian Network Equivalence Classes Based on a Hybrid Method

PDF

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 15

编辑推荐

Metrics

[1]	吕阳, 钱斌, 胡蓉, 张梓琪. 增强人工蜂群算法求解半导体最终测试调度问题[J]. 电子学报, 2021, 49(9): 1708-1715.
[2]	李海, 尚金雷, 孙婷逸, 冯青, 庄子波. 一种基于离散属性BNT的双偏振气象雷达降水粒子分类方法[J]. 电子学报, 2021, 49(3): 619-624.
[3]	尤殿龙, 郭松, 赵春慧, 原福永, 申利民, 陈真. 面向分类的流特征在线特征选择算法[J]. 电子学报, 2020, 48(2): 321-332.
[4]	谭翔元, 高晓光, 贺楚超. 基于马尔科夫毯约束的最优贝叶斯网络结构学习算法[J]. 电子学报, 2019, 47(9): 1898-1904.
[5]	房丙午, 黄志球, 王勇, 李勇. 基于混合贝叶斯网络的混合系统安全性分析方法[J]. 电子学报, 2017, 45(12): 2896-2902.
[6]	王静云, 刘三阳, 朱明敏. 基于条件独立测试的链图结构学习算法[J]. 电子学报, 2017, 45(10): 2443-2448.
[7]	邱玉, 赵杰煜, 汪燕芳. 结合运动时序性的人脸表情识别方法[J]. 电子学报, 2016, 44(6): 1307-1313.
[8]	邸若海, 高晓光, 郭志高. 小数据集BN建模方法及其在威胁评估中的应用[J]. 电子学报, 2016, 44(6): 1504-1511.
[9]	房丙午, 黄志球, 李勇, 王勇. 基于贝叶斯网络的复杂系统动态故障树定量分析方法[J]. 电子学报, 2016, 44(5): 1234-1239.
[10]	刘钰, 韩峰, 陆希成, 王建国. 电子系统电磁脉冲易损性评估的分层贝叶斯网络模型[J]. 电子学报, 2016, 44(11): 2695-2703.
[11]	王洪泊;涂序彦. 一种面向最经济服务流的可视化动态贝叶斯网络模型[J]. 电子学报, 2011, 39(6): 1331-1335.
[12]	王桢珍;姜欣;武小悦;谭旭. 信息安全风险概率计算的贝叶斯网络模型[J]. 电子学报, 2010, 38(2A): 18-22.
[13]	陈雁翔;刘鸣. 基于发音特征的音视频说话人识别鲁棒性的研究[J]. 电子学报, 2010, 38(12): 2920-2924.
[14]	苑迎春;李小平;王茜;张晓东;. 基于优先级规则的网格工作流调度[J]. 电子学报, 2009, 37(7): 1457-1464.
[15]	刘琪;李承恕. 多模可重构终端的无线接入管理[J]. 电子学报, 2007, 35(10): 1833-1837.