zbMATH — the first resource for mathematics

A decomposition algorithm for learning Bayesian networks based on scoring function. (English) Zbl 1263.62046
Summary: Learning Bayesian network (BN) structures from data is a typical NP-hard problem. But almost existing algorithms have very high complexity when the number of variables is large. In order to solve this problem, we present an algorithm that integrates a decomposition-based approach and a scoring-function-based approach for learning BN structures. First, the proposed algorithm decomposes the supporting graph of BNs into its maximal prime subgraphs. Then it orientates the local edges in each subgraph by the K2-scoring greedy searching. The last step is to combine the directed subgraphs to obtain the final BN structure. The theoretical and experimental results show that our algorithm can efficiently and accurately identify complex network structures from small data sets.
62F15 Bayesian inference
68T05 Learning and adaptive systems in artificial intelligence
05C90 Applications of graph theory
65C60 Computational problems in statistics (MSC2010)
BNT; RAIcode
Full Text: DOI
[1] L. Bouchaala, A. Masmoudi, F. Gargouri, and A. Rebai, “Improving algorithms for structure learning in Bayesian Networks using a new implicit score,” Expert Systems with Applications, vol. 37, no. 7, pp. 5470-5475, 2010. · doi:10.1016/j.eswa.2010.02.065
[2] A. Aussem and S. Rodrigues de Morais, “A conservative feature subset selection algorithm with missing data,” Neurocomputing, vol. 73, no. 4-6, pp. 585-590, 2010. · Zbl 05721251 · doi:10.1016/j.neucom.2009.05.019
[3] S. R. de Morais and A. Aussem, “A novel Markov boundary based feature subset selection algorithm,” Neurocomputing, vol. 73, no. 4-6, pp. 578-584, 2010. · Zbl 05721250 · doi:10.1016/j.neucom.2009.05.018
[4] Y. Sun, Y. Tang, S. Ding, S. Lv, and Y. Cui, “Diagnose the mild cognitive impairment by constructing Bayesian network with missing data,” Expert Systems with Applications, vol. 38, no. 1, pp. 442-449, 2011. · doi:10.1016/j.eswa.2010.06.084
[5] V. Aquaro, M. Bardoscia, R. Bellotti, A. Consiglio, F. De Carlo, and G. Ferri, “A Bayesian Networks approach to Operational Risk,” Physica A, vol. 389, no. 8, pp. 1721-1728, 2010. · doi:10.1016/j.physa.2009.12.043
[6] J. Z. Ji, H. X. Zhang, R. B. Hu, and C. N. Liu, “Bayesian Network learning algorithm based on independence test and ant colony optimization,” Acta Automatica Sinica, vol. 35, no. 3, pp. 281-288, 2009. · Zbl 1212.68129 · doi:10.3724/SP.J.1004.2009.00281
[7] Z. Geng, C. Wang, and Q. Zhao, “Decomposition of search for v-structures in DAGs,” Journal of Multivariate Analysis, vol. 96, no. 2, pp. 282-294, 2005. · Zbl 1137.62420 · doi:10.1016/j.jmva.2004.10.012
[8] X. Xie and Z. Geng, “A recursive method for structural learning of directed acyclic graphs,” Journal of Machine Learning Research, vol. 9, pp. 459-483, 2008. · Zbl 1225.68222 · www.jmlr.org
[9] J. Cheng, R. Greiner, J. Kelly, D. Bell, and W. Liu, “Learning Bayesian networks from data: an information-theory based approach,” Artificial Intelligence, vol. 137, no. 1-2, pp. 43-90, 2002. · Zbl 0995.68114 · doi:10.1016/S0004-3702(02)00191-1
[10] J.-P. Pellet and A. Elisseeff, “Using Markov blankets for causal structure learning,” Journal of Machine Learning Research, vol. 9, pp. 1295-1342, 2008. · Zbl 1225.68205 · www.jmlr.org
[11] C. Borgelt, “A conditional independence algorithm for learning undirected graphical models,” Journal of Computer and System Sciences, vol. 76, no. 1, pp. 21-33, 2010. · Zbl 1186.68356 · doi:10.1016/j.jcss.2009.05.003
[12] E. Perrier, S. Imoto, and S. Miyano, “Finding optimal Bayesian network given a super-structure,” Journal of Machine Learning Research, vol. 9, pp. 2251-2286, 2008. · Zbl 1225.68206 · www.jmlr.org
[13] L. M. de Campos, “A scoring function for learning Bayesian networks based on mutual information and conditional independence tests,” Journal of Machine Learning Research, vol. 7, pp. 2149-2187, 2006. · Zbl 1222.62036 · www.jmlr.org
[14] N. Friedman, I. Nachmama, and D. Peér, “Learning bayesian network structure from massive datasets: the “Sparse Candidate” algorithm,” in Proceedings of the 15th Conference on Uncertainty in Artificial Intelligence, pp. 206-215, Stockholm, Sweden, 1999.
[15] G. Cooper and E. Hersovits, “A bayesian method for the induction of probabilistic networks from data,” Machine Learning, vol. 9, pp. 309-347, 1992. · Zbl 0766.68109
[16] R. W. Robinson, “Counting unlabeled acyclic digraphs,” Combinational Mathematics, vol. 622, pp. 28-43, 1977. · Zbl 0376.05031
[17] K. Olesen and A. Madsen, “Maximal prime sub-graph decomposition of Bayesian networks,” IEEE Transactions on Systems, Man, and Cybernetics B, vol. 32, pp. 21-31, 2002.
[18] S. L. Lauritzen and D. J. Spiegelhalter, “Local computations with probabilities on graphical structures and their application to expert systems,” Journal of the Royal Statistical Society B, vol. 50, no. 2, pp. 157-224, 1988, With discussion. · Zbl 0684.68106
[19] X. C. Xie, Z. Geng, and Q. Zhao, “Decomposition of structural learning about directed acyclic graphs,” Artificial Intelligence, vol. 170, no. 4-5, pp. 422-439, 2006. · Zbl 1131.68510 · doi:10.1016/j.artint.2005.12.004
[20] D. J. Rose, R. E. Tarjan, and G. S. Lueker, “Algorithmic aspects of vertex elimination on graphs,” SIAM Journal on Computing, vol. 5, no. 2, pp. 266-283, 1976. · Zbl 0353.65019 · doi:10.1137/0205021
[21] R. E. Tarjan and M. Yannakakis, “Simple linear-time algorithms to test chordality of graphs, test acyclicity of hypergraphs, and selectively reduce acyclic hypergraphs,” SIAM Journal on Computing, vol. 13, no. 3, pp. 566-579, 1984. · Zbl 0545.68062 · doi:10.1137/0213035
[22] I. Tsamardinos, L. E. Brown, and C. F. Aliferis, “The max-min hill-climbing Bayesian network structure learning algorithm,” Machine Learning, vol. 65, no. 1, pp. 31-78, 2006. · Zbl 05075644 · doi:10.1007/s10994-006-6889-7
[23] R. E. Neapolitan, Learning Bayesian Networks, Prentice-Hall, Englewood Cliffs, NJ, USA, 2004.
[24] I. Beinlich, G. Suermondt, R. Chavez, and G. Cooper, “The ALARM Monitoring System: a case study with two probabilistic inference techniques for belief networks,” in Proceedings of the 2nd European Conference Artificial Intelligence in Medicine, 1989.
[25] J. Binder, D. Koller, S. Russell, and K. Kanazawa, “Adaptive Probabilistic Networks with Hidden Variables,” Machine Learning, vol. 29, no. 2-3, pp. 213-244, 1997. · Zbl 0892.68079 · doi:10.1023/A:1007421730016
[26] K. Murphy, “The Bayes net toolbox for Matlab,” Computing Science and Statistics, vol. 33, pp. 331-350, 2001.
[27] C. F. Aliferis, A. R. Statnikov, I. Tsamardinos, and L. E. Brown, “Causal explorer: a causal probabilistic network learning toolkit for biomedical discovery,” in Proceedings of the International Conference on Mathematics and Engineering Techniques in Medicine and Biological Sciences (METMBS’03), pp. 371-376, June 2003.
[28] R. Yehezkel and B. Lerner, “Bayesian network structure learning by recursive autonomy identification,” Journal of Machine Learning Research, vol. 10, pp. 1527-1570, 2009. · Zbl 1235.68214 · doi:10.1007/11815921_16 · www.jmlr.org
[29] S. L. Lauritzen, Graphical Models, vol. 17, Clarendon Press, New York, NY, USA, 1996. · Zbl 0907.62001
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.