Efficient and effective Bayesian network local structure learning

doi:10.1007/s11704-014-3335-z

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 YANG^1,^*(

),Yunhai TONG¹,Zitian WANG²,Shaohua TAN¹

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