基于马尔科夫毯约束的最优贝叶斯网络结构学习算法

doi:10.3969/j.issn.0372-2112.2019.09.012

电子学报 ›› 2019, Vol. 47 ›› Issue (9): 1898-1904.DOI: 10.3969/j.issn.0372-2112.2019.09.012

基于马尔科夫毯约束的最优贝叶斯网络结构学习算法

谭翔元, 高晓光, 贺楚超

西北工业大学电子信息学院, 陕西西安 710129

收稿日期:2018-10-30 修回日期:2019-05-22 出版日期:2019-09-25
- 通讯作者:
- 高晓光
- 作者简介:
- 谭翔元 男,1995年6月出生于四川遂宁.现为西北工业大学博士研究生.主要研究方向为贝叶斯网络结构学习.E-mail:tanxy2017@mail.nwpu.edu.cn;贺楚超 男,1992年3月出生于陕西西安.现为西北工业大学博士研究生.主要研究方向为贝叶斯网络学习与应用.E-mail:xomrssh@163.com
- 基金资助:
- 国家自然科学基金 (No.61573285）

Learning Optimal Bayesian Network Structure Constrained with Markov Blanket

TAN Xiang-yuan, GAO Xiao-guang, HE Chu-chao

School of Electronic and Information, Northwestern Polytechnical University, Xi'an, Shaanxi 710129, China

Received:2018-10-30 Revised:2019-05-22 Online:2019-09-25 Published:2019-09-25

摘要/Abstract

摘要： 本文针对最优贝叶斯网络的结构学习问题，在动态规划算法（Dynamic Programming，DP）的基础上，使用IAMB算法（Incremental Association Markov Blanket，IAMB）计算得到的马尔科夫毯对评分计算过程进行约束，减少了评分的计算次数，提出了基于马尔科夫毯约束的动态规划算法（Dynamic Programming Constrained with Markov Blanket，DPCMB），研究了IAMB算法中重要性阈值对DPCMB算法的各项性能指标的影响，给出了调整阈值的合理建议.实验结果表明，DPCMB算法可以通过调整重要性阈值，使该算法的精度与DP算法相当，极大地减少了算法的运行时间、评分计算次数和所需存储空间.

关键词: 贝叶斯网络结构学习, 动态规划算法, 马尔科夫毯, IAMB算法

Abstract: To solve the problem about structure learning of optimal Bayesian network,this paper proposes dynamic programming constrained with Markov blanket (DPCMB),which uses Markov blanket calculated by incremental association Markov blanket (IAMB) to reduce the number of scoring calculations in dynamic programming.We research on the effect of the significance value in IAMB on the performance indicators of DPCMB algorithm,and give reasonable suggestions for adjusting the significance value.Experimental results show that the DPCMB algorithm can adjust the significance value so that the accuracy of the algorithm is comparable to that of the DP algorithm,and running time,score calculation times,and memory requirements of the algorithm are greatly reduced.

Key words: Bayesian network structure learning, dynamic programming, Markov blanket, IAMB

中图分类号:

TP18

谭翔元, 高晓光, 贺楚超. 基于马尔科夫毯约束的最优贝叶斯网络结构学习算法[J]. 电子学报, 2019, 47(9): 1898-1904.

TAN Xiang-yuan, GAO Xiao-guang, HE Chu-chao. Learning Optimal Bayesian Network Structure Constrained with Markov Blanket[J]. Acta Electronica Sinica, 2019, 47(9): 1898-1904.

参考文献

[1] 邸若海,高晓光,郭志高.小数据集BN建模方法及其在威胁评估中的应用[J].电子学报,2016,44(6):1505-1511. DI Ruo-hai,GAO Xiao-guang,GUO Zhi-gao.The modeling method with Bayesian networks and its application in the threat assessment under small data sets[J].Acta Electronica Sinica,2016,44(6):1505-1511.(in Chinese)
[2] CHICKERING DM,HECKERMAN D,MEEK C.Large-sample learning of Bayesian networks is NP-hard[J].Journal of Machine Learning Research,2004,5(10):1287-1330.
[3] 朱明敏,刘三阳,杨有龙.基于混合方式的贝叶斯网络等价类学习算法[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.(in Chinese)
[4] KOIVISTO M,SOOD K.Exact Bayesian structure discovery in Bayesian networks[J].Journal of Machine Learning Research,2004,5(5):549-573.
[5] SINGH A,MOORE A.Finding optimal Bayesian networks by dynamic programming[R].Pittsburgh:Carnegie Mellon University,2005.
[6] SILANDER T,MYLLYMAKI P.A simple approach for finding the globally optimal Bayesian network structure[A].Proceedings of the 22nd Conference on Uncertainty in Artificial Intelligence[C].Arlington:AUAI Press,2006.445-452.
[7] MALONE B,Yuan C.Memory-efficient dynamic programming for learning optimal Bayesian networks[A].Proceedings of 25th AAAI Conference on Artificial Intelligence[C].Palo Alto:AAAI Press,2011.1057-1062.
[8] YUAN C,MALONE B.Learning optimal Bayesian networks:a shortest path perspective[J].Journal of Artificial Intelligence Research,2013,48(1):23-65.
[9] MALONE B,YUAN C.Evaluating anytime algorithms for learning optimal Bayesian networks[A].Proceedings of the 29th Conference on Uncertainty in Artificial Intelligence[C].Corvallis:AUAI Press,2013.381-390.
[10] BARTLETT M,CUSSENS J.Integer linear programming for the Bayesian network structure learning problem[J].Artificial Intelligence,2017,244(244):258-271.
[11] CHICKERING DM.A transformational characterization of equivalent Bayesian network structures[A].Proceedings of the 11th Conference on Uncertainty in Artificial Intelligence[C].San Francisco:Morgan Kaufmann,1995.87-98.
[12] TSAMARDINOS I,ALIFERIS C F.Algorithms for large scale Markov blanket discovery[A].Proceedings of the 16th International FLAIRS Conference[C].Palo Alto:AAAI Press,2003.376-381.

基于马尔科夫毯约束的最优贝叶斯网络结构学习算法

Learning Optimal Bayesian Network Structure Constrained with Markov Blanket

PDF

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 1

编辑推荐

Metrics