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.
MSC:
| 62F15 | Bayesian inference |
| 68T05 | Learning and adaptive systems in artificial intelligence |
| 05C90 | Applications of graph theory |
| 65C60 | Computational problems in statistics (MSC2010) |
References:
| [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. · 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. · 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 |
| [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 |
| [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 |
| [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 |
| [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 1470.68192 · 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 |
| [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. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
