Please wait a minute...
Frontiers of Computer Science

ISSN 2095-2228

ISSN 2095-2236(Online)

CN 10-1014/TP

Postal Subscription Code 80-970

2018 Impact Factor: 1.129

Front. Comput. Sci.    2014, Vol. 8 Issue (4) : 527-536    https://doi.org/10.1007/s11704-014-3335-z
RESEARCH ARTICLE
Efficient and effective Bayesian network local structure learning
Jianjun YANG1,*(),Yunhai TONG1,Zitian WANG2,Shaohua TAN1
1. Center for Information Science, Peking University, Beijing 100871, China
2. Agricultural Bank of China, Beijing 100871, China
 Download: PDF(442 KB)  
 Export: BibTeX | EndNote | Reference Manager | ProCite | RefWorks
Abstract

In this paper, we propose a more efficient Bayesian network structure learning algorithm under the framework of score based local learning (SLL). Our algorithm significantly improves computational efficiency by restricting the neighbors of each variable to a small subset of candidates and storing necessary information to uncover the spouses, at the same time guaranteeing to find the optimal neighbor set in the same sense as SLL. The algorithm is theoretically sound in the sense that it is optimal in the limit of large sample size. Empirical results testify its improved speed without loss of quality in the learned structures.

Keywords local structure learning      Bayesian network      Markov blanket     
Corresponding Author(s): Jianjun YANG   
Issue Date: 11 August 2014
 Cite this article:   
Jianjun YANG,Yunhai TONG,Zitian WANG, et al. Efficient and effective Bayesian network local structure learning[J]. Front. Comput. Sci., 2014, 8(4): 527-536.
 URL:  
https://academic.hep.com.cn/fcs/EN/10.1007/s11704-014-3335-z
https://academic.hep.com.cn/fcs/EN/Y2014/V8/I4/527
1 Friedman N, Linial M, Nachman I, Pe’er D. Using Bayesian networks to analyze expression data. Journal of Computational Biology, 2000, 7(3-4): 601-620
doi: 10.1089/106652700750050961
2 Wang Z, Wang L, Tan S. Emergent and spontaneous computation of factor relationships from a large factor set. Journal of Economic Dynamics and Control, 2008, 32(12): 3939-3959
doi: 10.1016/j.jedc.2008.04.005
3 Yang J, Wang Z, Liu B, Tan S. Continuous variable based Bayesian network structure learning from financial factors. In: Proceedings of the 2012 IEEE Conference on Computational Intelligence for Financial Engineering & Economics. 2012, 1-6
4 Kuikka S, Varis O. Uncertainties of climatic change impacts in finnish watersheds: a Bayesian network analysis of expert knowledge. Boreal Environment Research, 1997, 2(1): 109-128
5 Spirtes P, Glymour C N, Scheines R. Causation Prediction & Search 2e, Volume 81. MIT press, 2000
6 Pearl J. Causality: models, reasoning and inference, Volume 29. Cambridge University Press, 2000
7 Silander T, Myllymaki P. A simple approach for finding the globally optimal Bayesian network structure. arXiv preprint arXiv:1206.6875, 2012
8 Teyssier M, Koller D. Ordering-based search: a simple and effective algorithm for learning Bayesian networks. arXiv preprint arXiv:1207.1429, 2012
9 Aliferis C, Statnikov A, Tsamardinos I, Mani S, Koutsoukos X. Local causal and Markov blanket induction for causal discovery and feature selection for classification, Part i: Algorithms and empirical evaluation. The Journal of Machine Learning Research, 2010, 11: 171-234
10 Niinimaki T, Parviainen P. Local structure discovery in Bayesian networks. In: Proceedings of the 28th Annual Conference on Uncertainty in Artificial Intelligence (UAI-12). 2012, 634-643
11 Tsamardinos I, Aliferis C, Statnikov A. Time and sample efficient discovery of Markov blankets and direct causal relations. In: Proceedings of the 9th ACMSIGKDD International Conference on Knowledge Discovery and Data Mining. 2003, 673-678
12 Koller D, Sahami M. Toward optimal feature selection. Proceedings of the 13th International Conference on Machine Learning. 1996, 284-292
13 Friedman N, Nachman I, Peér D. Learning Bayesian network structure from massive datasets: the “sparse candidate” algorithm. In: Proceedings of the 15th Conference on Uncertainty in Artificial Intelligence. 1999, 206-215
14 Aliferis C F, Tsamardinos I, Statnikov A. Hiton: a novel Markov blanket algorithm for optimal variable selection. In: Proceedings of the 2003 Association of Moving Image Archivists Annual Symposium. 2003, 21-25
15 Tsamardinos I, Brown L E, Aliferis C F. The max-min hill-climbing Bayesian network structure learning algorithm. Machine learning, 2006, 65(1): 31-78
doi: 10.1007/s10994-006-6889-7
16 Koller D, Friedman N. Probabilistic Graphical Models: Principles and Techniques. <PublisherName Language="chs">MIT p<?Pub Caret?>ress</PublisherName>, 2009
17 Tsamardinos I, Statnikov A, Brown L E, Aliferis C F. Generating realistic large Bayesian networks by tiling. In: Proceedings of the 19th International FLAIRS Conference. 2006, 592-597
[1] Shangfei WANG,Menghua HE,Yachen ZHU,Shan HE,Yue LIU,Qiang JI. Learning with privileged information using Bayesian networks[J]. Front. Comput. Sci., 2015, 9(2): 185-199.
[2] Shangfei WANG,Shan HE,Yue WU,Menghua HE,Qiang JI. Fusion of visible and thermal images for facial expression recognition[J]. Front. Comput. Sci., 2014, 8(2): 232-242.
Viewed
Full text


Abstract

Cited

  Shared   
  Discussed