Efficient and effective Bayesian network local structure learning

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

References

[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

[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

[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

[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

RIGHTS & PERMISSIONS

2014 Higher Education Press and Springer-Verlag Berlin Heidelberg