BIC-based node order learning for improving Bayesian network structure learning

Abstract

Node order is one of the most important factors in learning the structure of a Bayesian network (BN) for probabilistic reasoning. To improve the BN structure learning, we propose a node order learning algorithmbased on the frequently used Bayesian information criterion (BIC) score function. The algorithm dramatically reduces the space of node order and makes the results of BN learning more stable and effective. Specifically, we first find the most dependent node for each individual node, prove analytically that the dependencies are undirected, and then construct undirected subgraphs U_G. Secondly, the U_G- is examined and connected into a single undirected graph U_GC. The relation between the subgraph number and the node number is analyzed. Thirdly, we provide the rules of orienting directions for all edges in UGC, which converts it into a directed acyclic graph (DAG). Further, we rank the DAG’s topology order and describe the BIC-based node order learning algorithm. Its complexity analysis shows that the algorithm can be conducted in linear time with respect to the number of samples, and in polynomial time with respect to the number of variables. Finally, experimental results demonstrate significant performance improvement by comparing with other methods.

Keywords

probabilistic reasoning / Bayesian networks / node order learning / structure learning / BIC scores / V-structure

References

[1] Judea P. Probabilistic Reasoning in Intelligent Systems: Networks of Plausible Inference. Morgan Kaufmann Publishers, San Mateo, California, 1988

[2] Friedman N. Inferring cellular networks using probabilistic graphical models. Science, 2004, 303(5659): 799–805

[3] Raval A, Ghahramani Z, Wild D L. A Bayesian network model for protein fold and remote homologue recognition. Bioinformatics, 2002, 18(6): 788–801

[4] Chen W, Zhu B, Zhang H. BN-mapping: visual analysis of geospatial data with Bayesian network. Chinese Journal of Computers, 2016, 39(7): 1281–1293

[5] Peng P, Tian Y, Wang Y, Li J, Huang T. Robust multiple cameras pedestrian detection with multi-view Bayesian network. Pattern Recognition, 2015, 48(5): 1760–1772

[6] Liu L,Wang S, Su G, Huang Z, Liu M. Towards complex activity recognition using a Bayesian network-based probabilistic generative framework. Pattern Recognition, 2017, 68: 295–309

[7] Oatley G, Ewart B. Crimes analysis software: ‘pins in maps’ clustering and Bayes net prediction. Expert Systems with Applications, 2003, 25(4): 569–588

[8] Chickering D M, Heckerman D, Meek C. Learning Bayesian networks is NP-hard. Technical Report, MSR-TR-94-17, Microsoft Research, Microsoft Corporation, 1994

[9] Chickering D M, Heckerman D, Meek C. Large-sample learning of Bayesian networks is NP-hard. Journal of Machine Learning Research, 2004, 5: 1287–1330

[10] Bouhamed H, Masmoudi A, Lecroq T, Rebai A. Structure space of Bayesian networks is dramatically reduced by subdividing it in subnetworks. Journal of Computational and Applied Mathematics, 2015, 287: 48–62

[11] Heckerman D, Geiger D, Chickering D M. Learning Bayesian networks: the combination of knowledge and statistical data. Machine Learning, 1995, 20: 197–243

[12] Lam W, Bacchus F. Learning Bayesian belief networks: an approach based on the MDL principle. Computational Intelligence, 1994, 10(3): 269–293

[13] Scanagatta M, Corani G, De Campos C P, Zaffalon M. Approximate structure learning for large Bayesian networks. Machine Learning, 2018, 107: 1209–1227

[14] De Campos C P, Scanagatta M, Corani G, Zaffalon M. Entropy-based pruning for learning Bayesian networks using BIC. Artificial Intelligence, 2018, 260: 42–50

[15] Cooper G F, Herskovits E H. A Bayesian method for the induction of probabilistic networks from data. Machine Learning, 1992, 9: 309–347

[16] Scanagatta M, Corani G, Zaffalon M, Yoo J, Kang U. Efficient learning of bounded-treewidth Bayesian networks from complete and incomplete data sets. International Journal of Approximate Reasoning, 2018, 95: 152–166

[17] Nie S, De Campos C P, Ji Q. Learning Bayesian networks with bounded treewidth via guided search. In: Proceedings of the 30th AAAI Conference on Artificial Intelligence. 2016, 3294–3300

[18] Parviainen P, Farahani H S, Lagergren J. Learning bounded treewidth Bayesian networks using integer linear programming. In: Proceedings of the 17th International Conference on Artificial Intelligence and Statistics. 2014, 751–759

[19] Elidan G, Gould S. Learning bounded treewidth Bayesian networks. Journal of Machine Learning Research, 2008, 9: 2699–2731

[20] Niinimaki T, Parviainen P, Koivisto M. Structure discovery in Bayesian networks by sampling partial orders. Journal of Machine Learning Research, 2016, 17(1): 2002–2048

[21] Teyssier M, Koller D. Ordering-based search: a simple and effective algorithm for learning Bayesian networks. In: Proceedings of the 21st Conference on Uncertainty in Artificial Intelligence. 2005, 584–590

[22] Scanagatta M, De Campos C P, Corani G, Zaffalon M. Learning Bayesian networks with thousands of variables. Neural Information Processing Systems, 2015, 28: 1855–1863

[23] Chen X, Anantha G, Lin X. Improving Bayesian network structure learning with mutual information-based node ordering in the K2 algorithm. IEEE Transactions on Knowledge and Data Engineering, 2008, 20(5): 1–13

[24] Ko S, Kim D. An efficient node ordering method using the conditional frequency for the K2 algorithm. Pattern Recognition Letters, 2014, 40: 80–87

[25] Hsu W H, Guo H, Perry B B, Stilson J A. A permutation genetic algorithm for variable ordering in learning Bayesian networks from data. In: Proceedings of the Genetic and Evolutionary Computation Conference. 2002, 383–390

[26] Park Y W, Klabjan D. Bayesian network learning via topological order. Journal of Machine Learning Research, 2017, 18: 1–32

[27] Zhang L, Guo H. Introduction to Bayesian Networks. Science Press, 2006

[28] Zhang N L, Yan L. Independence of causal influence and clique tree propagation. International Journal of Approximate Reasoning, 1998, 19(3–4): 335–349

[29] Mateescu R, Kask K, Gogate V, Dechter R. Join-graph propagation algorithms. Journal of Artificial Intelligence Research, 2010, 37: 279–328

[30] Goudie R J, Mukherjee S. A Gibbs sampler for learning DAGs. Journal of Machine Learning Research, 2016, 17: 1–39

[31] Benjumeda M, Bielza C, Larranaga P. Learning tractable Bayesian networks in the space of elimination orders. Artificial Intelligence, 2019, 274: 66–90

[32] Benjumeda M, Luengosanchez S, Larranaga P, Bielza C. Tractable learning of Bayesian networks from partially observed data. Pattern Recognition, 2019, 91: 190–199

[33] Tsamardinos I, Brown L E, Aliferis C F. The max-min hill-climbing Bayesian network structure learning algorithm. Machine Learning, 2006, 65: 31–78

[34] Lv Y, Wu J, Liang J, Qian Y. Random search learning algorithm of BN based on super-structure. Journal of Computer Research and Development, 2017, 54(11): 2558–2566

[35] Qi X, Fan X, Gao Y, Liu Y. Learning Bayesian network structures using weakest mutual-information-first strategy. International Journal of Approximate Reasoning, 2019, 114: 84–98

[36] Talvitie T, Eggeling R, Koivisto M. Learning Bayesian networks with local structure, mixed variables, and exact algorithms. International Journal of Approximate Reasoning, 2019, 115: 69–95

[37] Scutari M, Graafland C E, Gutiérrez J M. Who learns better Bayesian network structures: accuracy and speed of structure learning algorithms. International Journal of Approximate Reasoning, 2019, 115: 235–253

[38] Ye Q L, Amini A A, Zhou Q. Optimizing regularized cholesky score for order-based learning of Bayesian networks. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2020,

[39] Lee S, Kim S B. Parallel simulated annealing with a greedy algorithm for Bayesian network structure learning. IEEE Transactions on Knowledge and Data Engineering, 2020, 32(6): 1157–1166

[40] Yao T, Choi A, Darwiche A. Learning Bayesian network parameters under equivalence constraints. Artificial Intelligence, 2017, 244: 239–257

[41] Riggelsen C. Learning parameters of Bayesian networks from incomplete data via importance sampling. International Journal of Approximate Reasoning, 2006, 42: 69–83

[42] Niculescu R S, Mitchell T M, Rao R B. Bayesian network learning with parameter constraints. Journal of Machine Learning Research, 2006, 7: 1357–1383

[43] Yang Y, Gao X, Guo Z, Chen D. Learning Bayesian networks using the constrained maximum a posteriori probability method. Pattern Recognition, 2019, 91: 123–134

[44] Benjumeda M, Bielza C, Larranaga P. Tractability of most probable explanations in multidimensional Bayesian network classifiers. International Journal of Approximate Reasoning, 2018, 93: 74–87

[45] Madsen A L, Jensen F, Salmeron A, Langseth H, Nielsen T D. A parallel algorithm for Bayesian network structure learning from large data sets. Knowledge Based Systems, 2017, 117: 46–55

[46] Arnborg S, Corneil D G, Proskurowski A. Complexity of finding embeddings in a k-tree. SIAM Journal on Algebraic Discrete Methods, 1987, 8(2): 277–284

[47] Nie S, Maua D D, De Campos C P, Ji Q. Advances in learning Bayesian networks of bounded treewidth. Advances in Neural Information Processing Systems, 2014, 27: 2285–2293

[48] Liao W, Ji Q. Learning Bayesian network parameters under incomplete data with domain knowledge. Pattern Recognition, 2009, 42: 3046–3056

[49] Lv Y, Wu J, Jing T. Pqisem: BN’s structure learning based on partial qualitative influences and SEM algorithm from missing data. International Journal of Wireless and Mobile Computing, 2018, 14(4): 348–357

[50] Masegosa A R, Feelders A, Der Gaag L C. Learning from incomplete data in Bayesian networks with qualitative influences. International Journal of Approximate Reasoning, 2016, 69: 18–34

RIGHTS & PERMISSIONS

Higher Education Press