Bi-objective evolutionary Bayesian network structure learning via skeleton constraint

Abstract

Bayesian network is a popular approach to uncertainty knowledge representation and reasoning. Structure learning is the first step to learn a Bayesian network. Score-based methods are one of the most popular ways of learning the structure. In most cases, the score of Bayesian network is defined as adding the log-likelihood score and complexity score by using the penalty function. If the penalty function is set unreasonably, it may hurt the performance of structure search. Thus, Bayesian network structure learning is essentially a bi-objective optimization problem. However, the existing bi-objective structure learning algorithms can only be applied to small-scale networks. To this end, this paper proposes a bi-objective evolutionary Bayesian network structure learning algorithm via skeleton constraint (BBS) for the medium-scale networks. To boost the performance of searching, BBS introduces the random order prior (ROP) initial operator. ROP generates a skeleton to constrain the searching space, which is the key to expanding the scale of structure learning problems. Then, the acyclic structures are guaranteed by adding the orders of variables in the initial skeleton. After that, BBS designs the Pareto rank based crossover and skeleton guided mutation operators. The operators operate on the skeleton obtained in ROP to make the search more targeted. Finally, BBS provides a strategy to choose the final solution. The experimental results show that BBS can always find the structure which is closer to the ground truth compared with the single-objective structure learning methods. Furthermore, compared with the existing bi-objective structure learning methods, BBS is scalable and can be applied to medium-scale Bayesian network datasets. On the educational problem of discovering the influencing factors of students’ academic performance, BBS provides higher quality solutions and is featured with the flexibility of solution selection compared with the widely-used Bayesian network structure learning methods.

Graphical abstract

Keywords

Bayesian network / structure learning / multi-objective optimization / conditional independence test

Ting Wu is currently a postgraduate in the School of Computer Science and Technology, East China Normal University, China. Her current research interests include evolutionary optimization, Bayesian networks, and intelligent education

Hong Qian received the PhD in the Department of Computer Science and Technology from Nanjing University, China in 2020. He is currently an associate researcher in the School of Computer Science and Technology, East China Normal University, China. His research interests include derivative-free optimization, evolutionary machine learning, and intelligent education. He has served as a reviewer of several world-class journals and a (senior) program committee member of several leading international conferences in the field of machine learning and evolutionary computation

Ziqi Liu received the PhD from Xi’an Jiaotong University, China in 2017. During 2014 and 2016, he was a visiting scholar at Machine Learning Department, Carnegie Mellon University, USA. In 2017 he joined the AI Department, Ant Financial Services Group as a research scientist

Jun Zhou is currently a Senior Staff Engineer at Ant Group, China. His research mainly focuses on machine learning and data mining. He has participated in the development of several distributed systems and machine learning platforms in Alibaba and Ant Group, such as Apsaras (Distributed Operating System), MaxCompute (Big Data Platform), and KunPeng (Parameter Server). He has published more than 40 papers in top-tier machine learning and data mining conferences, including VLDB, WWW, NeurIPS, and AAAI

Aimin Zhou received the BS and MS degrees in computer science from Wuhan University, China in 2001 and 2003, respectively, and the PhD in computer science from the University of Essex, Colchester, UK in 2009. He is currently a professor with the School of Computer Science and Technology, and the Shanghai Institute of AI for Education, East China Normal University, China. His current research interests include evolutionary computation, machine learning, and intelligent education. He has published over 80 peer-reviewed papers. Prof. Zhou is an Associate Editor of Swarm and Evolutionary Computation and an Editorial Board Member of Complex and Intelligent Systems

References

[1] Koller D, Friedman N. Probabilistic Graphical Models - Principles and Techniques. Cambridge: MIT Press, 2009

[2] Lee S M, Abbott P A . Bayesian networks for knowledge discovery in large datasets: basics for nurse researchers. Journal of Biomedical Informatics, 2003, 36( 4−5): 389–399

[3] Luo G, Zhao B, Du S . Causal inference and Bayesian network structure learning from nominal data. Applied Intelligence, 2019, 49( 1): 253–264

[4] Heckerman D . Bayesian networks for data mining. Data Mining and Knowledge Discovery, 1997, 1( 1): 79–119

[5] Lv Y, Miao J, Liang J, Chen L, Qian Y . BIC-based node order learning for improving Bayesian network structure learning. Frontiers of Computer Science, 2021, 15( 6): 156337

[6] 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

[7] Wu T, Qian H, Zhou A, Li Z. Bi-objective search method for Bayesian network structure learning. In: Proceedings of the 7th IEEE International Conference on Cloud Computing and Intelligent Systems. 2021, 433−437

[8] Chickering D M, Meek C, Heckerman D. Large-sample learning of Bayesian networks is NP-hard. In: Proceedings of the 19th Conference in Uncertainty in Artificial Intelligence. 2003, 124−133

[9] Robinson R W. Counting unlabeled acyclic digraphs. In: Proceedings of the 5th Australian Conference on Combinatorial Mathematics V. 1976, 28−43

[10] Schwarz G . Estimating the dimension of a model. The Annals of Statistics, 1978, 6( 2): 461–464

[11] Chickering D M. Learning Bayesian networks is NP-complete. In: Fisher D, Lenz H J, eds. Learning from Data: Artificial Intelligence and Statistics V. New York: Springer, 1996, 121−130

[12] Chickering D M, Heckerman D, Meek C. A Bayesian approach to learning Bayesian networks with local structure. In: Proceedings of the 13th Conference on Uncertainty in Artificial Intelligence. 1997, 80−89

[13] Chickering D M. Learning equivalence classes of Bayesian network structures. In: Proceedings of the 12th International Conference on Uncertainty in Artificial Intelligence. 1996, 150−157

[14] Larrañaga P, Kuijpers C M H, Murga R H, Yurramendi Y . Learning Bayesian network structures by searching for the best ordering with genetic algorithms. IEEE Transactions on Systems, Man, and Cybernetics- Part A: Systems and Humans, 1996, 26( 4): 487–493

[15] de Campos L M, Fernández-Luna J M, Gámez J A, Puerta J M . Ant colony optimization for learning Bayesian networks. International Journal of Approximate Reasoning, 2002, 31( 3): 291–311

[16] Yang J, Tong Y, Wang Z, Tan S . Efficient and effective Bayesian network local structure learning. Frontiers of Computer Science, 2014, 8( 4): 527–536

[17] Larrañaga P, Poza M, Yurramendi Y, Murga R H, Kuijpers C M H . Structure learning of Bayesian networks by genetic algorithms: a performance analysis of control parameters. IEEE Transactions on Pattern Analysis and Machine Intelligence, 1996, 18( 9): 912–926

[18] 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, 548−549

[19] Stanley K O, Clune J, Lehman J, Miikkulainen R . Designing neural networks through neuroevolution. Nature Machine Intelligence, 2019, 1( 1): 24–35

[20] Qian H, Yu Y . Derivative-free reinforcement learning: a review. Frontiers of Computer Science, 2021, 15( 6): 156336

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

[22] Singh M, Valtorta M. An algorithm for the construction of Bayesian network structures from data. In: Proceedings of the 9th International Conference on Uncertainty in Artificial Intelligence. 1993, 259−265

[23] Friedman N, Nachman I, Pe’er 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

[24] Tsamardinos I, Aliferis C F, Statnikov A. Time and sample efficient discovery of Markov blankets and direct causal relations. In: Proceedings of the 9th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. 2003, 673−678

[25] Gasse M, Aussem A, Elghazel H . A hybrid algorithm for Bayesian network structure learning with application to multi-label learning. Expert Systems with Applications, 2014, 41( 15): 6755–6772

[26] de Morais S R, Aussem A. An efficient and scalable algorithm for local Bayesian network structure discovery. In: Proceedings of the 14th European Conference on Machine Learning and Knowledge Discovery in Databases. 2010, 164−179

[27] Yu K, Liang J, Qu B, Luo Y, Yue C . Dynamic selection preference-assisted constrained multiobjective differential evolution. IEEE Transactions on Systems, Man, and Cybernetics: Systems, 2022, 52( 5): 2954–2965

[28] Yang P, Yang Q, Tang K, Yao X . Parallel exploration via negatively correlated search. Frontiers of Computer Science, 2021, 15( 5): 155333

[29] Deb K, Pratap A, Agarwal S, Meyarivan T . A fast and elitist multiobjective genetic algorithm: NSGA-II. IEEE Transactions on Evolutionary Computation, 2002, 6( 2): 182–197

[30] Deb K, Sundar J. Reference point based multi-objective optimization using evolutionary algorithms. In: Proceedings of the 8th Annual Conference on Genetic and Evolutionary Computation. 2006, 635−642

[31] Poli R, Langdon W B . Schema theory for genetic programming with one-point crossover and point mutation. Evolutionary Computation, 1998, 6( 3): 231–252

[32] Kora P, Yadlapalli P . Crossover operators in genetic algorithms: a review. International Journal of Computer Applications, 2017, 162( 10): 34–36

[33] Korb K B, Nicholson A E. Bayesian Artificial Intelligence. 2nd ed. Boca Raton: CRC Press, 2010

[34] Lauritzen S L, Spiegelhalter D J . Local computations with probabilities on graphical structures and their application to expert systems. Journal of the Royal Statistical Society: Series B (Methodological), 1988, 50( 2): 157–194

[35] Scutari M, Denis J B. Bayesian Networks: with Examples in R. 2nd ed. New York: Chapman and Hall/CRC, 2021

[36] Sachs K, Perez O, Pe’er D, Lauffenburger D A, Nolan G P . Causal protein-signaling networks derived from multiparameter single-cell data. Science, 2005, 308( 5721): 523–529

[37] Spiegelhalter D J, Lauritzen S L. Techniques for Bayesian analysis in expert systems. Annals of Mathematics and Artificial Intelligence, 1990, 2(1−4): 353−366

[38] Beinlich I A, Suermondt H J, Chavez R M, Cooper G F. The ALARM monitoring system: a case study with two probabilistic inference techniques for belief networks. In: Proceedings of the 2nd European Conference on Artificial Intelligence in Medicine. 1989, 247−256

[39] Oniśko A, Druzdzel M J, Wasyluk H. A probabilistic causal model for diagnosis of liver disorders. In: Proceedings of the Workshop Held in Intelligent Information Systems VII. 1998, 379−388

[40] de Campos L M . A scoring function for learning Bayesian networks based on mutual information and conditional independence tests. The Journal of Machine Learning Research, 2006, 7: 2149–2187

[41] Ankan A, Panda A. pgmpy: probabilistic graphical models using python. In: Proceedings of the 14th Python in Science Conference. 2015, 6−11

[42] Scutari M. Learning Bayesian networks with the bnlearn R package. Journal of Statistical Software, 2010, 35(3): 1−22

[43] Schwartz A E, Rothbart M W . Let them eat lunch: the impact of universal free meals on student performance. Journal of Policy Analysis and Management, 2020, 39( 2): 376–410

[44] Reilly D, Neumann D L, Andrews G . Gender differences in reading and writing achievement: evidence from the national assessment of educational progress (NAEP). American Psychologist, 2019, 74( 4): 445–458

[45] Hyde J S, Fennema E, Lamon S J . Gender differences in mathematics performance: a meta-analysis. Psychological Bulletin, 1990, 107( 2): 139–155

[46] Rodríguez S, Regueiro B, Piñeiro I, Estévez I, Valle A . Gender differences in mathematics motivation: differential effects on performance in primary education. Frontiers in Psychology, 2020, 10: 3050

Acknowledgements

The authors would like to thank the anonymous reviewers for the valuable suggestions. The authors also would like to thank Yi-Bo Zeng for the helpful comments. This work was supported by the Fundamental Research Funds for the Central Universities, the Science and Technology Commission of Shanghai Municipality (No. 19511120601), the Scientific and Technological Innovation 2030 Major Projects (No. 2018AAA0100902), the CCF-AFSG Research Fund (No. CCF-AFSG RF20220205), and the “Chenguang Program” sponsored by Shanghai Education Development Foundation and Shanghai Municipal Education Commission (No. 21CGA32).

Competing interests

The authors declare that they have no competing interests or financial conflicts to disclose.

RIGHTS & PERMISSIONS

2023 Higher Education Press