Computer Science ›› 2016, Vol. 43 ›› Issue (2): 263-268.doi: 10.11896/j.issn.1002-137X.2016.02.055

Previous Articles     Next Articles

Accelerating Structure Learning of Bayesian Network

SEIN Minn and FU Shun-kai   

  • Online:2018-12-01 Published:2018-12-01

Abstract: Structure learning is the basis for the application of Bayesian networks (BN).A novel algorithm called APC was proposed to recovery the whole structure via sequential induction of local structures.APC inherits the most feature of PC algorithm,i.e.effectively avoiding high-dimensional conditional independence (CI) tests.Besides,it constructs and sorts candidate sets which possibly d-separate any pair of nodes,X and Y,based on information implied in early conducted CI tests and known features of BN topology.Then,CI tests involving highly ranked candidate set are performed with priority.This strategy is expected to avoid fruitless CI tests,and up to 50% saving is observed on APC over PC in our experimental study.

Key words: Bayesian network,Structure learning,Constraint-based learning,Conditional independence test

[1] Liang Jie,Cai Qi,Chu Zhu-li,et al.Reactor water system diagnostic Bayesian network construction Legislation and application[J].Atomic Energy Science and Technology,2013(10):1840-1844(in Chinese)梁洁,蔡琦,初珠立,等.反应堆补水系统诊断贝叶斯网络的建立和应用[J].原子能科学技术,2013(10):1840-1844
[2] Ren Jia,Du Wen-cai,Bai Yong.Adaptive Bayesian networkbased inference UAV mission decisions [J].Systems Enginee-ring Theory and Practice,2013,3(10):2575-2582(in Chinese) 任佳,杜文才,白勇.基于贝叶斯网络自适应推理的无人机任务决策[J].系统工程理论与实践,2013,3(10):2575-2582
[3] Barbaros Y,Zane B P,Todd E R,et al.Combining data and meta-analysis to build Bayesian networks for clinical decision support[J].Journal of Biomedical Informatics,2014,52:373-385
[4] Liu Jian-wei,Li Hai-en,Luo Xiong-lin.Research progress ofprobabilistic graphical model learning technology [J].Journal of Automatic,2014,40 (6):1025-1044(in Chinese) 刘建伟,黎海恩,罗雄麟.概率图模型学习技术研究进展[J].自动化学报,2014,40(6):1025-1044
[5] Daphne K,Nir F.Probabilistic graphical models:principles and techniques[M].MIT Press,2009
[6] Guo Tong,Lin Feng.Hybrid genetic fish group based Bayesian network structure learning algorithm [J].Journal of Zhejiang University(Engineering Science),2014,8(1):130-135(in Chinese) 郭童,林峰.基于混合遗传鱼群算法的贝叶斯网络结构学习[J].浙江大学学报(工学版),2014,8(1):130-135
[7] Peter S,Clark G,Richard S.Causation,Prediction,and Search[M].A Bradford Book,2001
[8] Judea P,Verma T S.A Theory of Inferred Causation[C]∥Proceedings of 2nd International Conference on Principles of Knowledge Representation and Reasoning.1991
[9] Dimitris M,Thrun S.Bayesian Network Induction via LocalNeighborhoods[C]∥Proceedings of the 12th Neural Information Processing Systems (NIPS).MIT Press,1999
[10] Wermuth N,Lauritzen S.Graphical and recursive models forcontingence tables [J].Biometrika,1983,72:537-552
[11] Jie C,David A B,Weiru L.Learning Belief Networks from Data:An Information Theory Based Approach[C]∥Proceedings of the 6th ACM International Conference on Information and Knowledge Management (CIKM).1997:325-331
[12] Laura B,Ioannis T,Constantin A.A Comparison of Novel and State-of-the-Art Polynomial Bayesian Network Learning Algorithm[C]∥Proceedings of the 20th National Conference on Artificial Intelligence (AAAI).AAAI Press,2005:739-745
[13] David M C,Christopher M.Monotone DAG faithfulness:A bad assumption [R].Microsoft,2003
[14] Shunkai F,Michel C D,Sein M,et al.A survey on advances in Markov blanket induction algorithms[C]∥Proceedings of the 10th ICNC-FSKD.Xiamen,China,2014
[15] Shunkai F,Michel C D.Tradeoff analysis of different Markov blanket local learning approaches[C]∥Proceedings of the 12th Pacific-Asia Conference on Advances in Knowledge Discovery and Data Mining (PAKDD).Osaka,Japan:Springer,2008:562-571
[16] Facundo B,Dimitris M,Vsant H.Efficient Markov networkstructure discovery using independence tests [J].Journal of Artificial Intelligence Research,2009,35(1):449-484

No related articles found!
Viewed
Full text


Abstract

Cited

  Shared   
  Discussed   
No Suggested Reading articles found!