An efficient Bayesian network structure learning algorithm based on structural information

Bayesian networks (BNs) are probabilistic graphical models regarded as some of the most compelling theoretical models in the field of representation and reasoning under uncertainty. The search space of the model structure grows super-exponentially as the number of variables increases, which makes BN structure learning an NP-hard problem. Evolutionary algorithm-based BN structure learning algorithms perform better than traditional methods. This paper proposes a structural information-based genetic algorithm for BN structure learning (SIGA-BN) by employing the concepts of Markov blankets (MBs) and v-structures in BNs. In SIGA-BN, an elite learning strategy based on an MB is designed, allowing elite individuals' structural information to be learned more effectively and improving the convergence speed with high accuracy. Then, a v-structure -based adaptive preference mutation operator is introduced in SIGA-BN to reduce the redundancy of the search process by identifying changes in the v-structure. Furthermore, an adaptive mutation probability mechanism based on stagnation iterations is adopted and used to balance exploration and exploitation. Experimental results on eight widely used benchmark networks show that the proposed algorithm outperforms other GA -based and traditional BN structure learning algorithms regarding structural accuracy, convergence speed, and computational time.

Automated summary

Bayesian networks (BNs) are powerful models for representation and reasoning under uncertainty. This paper presents a genetic algorithm-based approach called SIGA-BN for learning the structure of BNs. SIGA-BN utilizes the concepts of Markov blankets and v-structures to improve the learning process. The experimental results on benchmark networks demonstrate that SIGA-BN outperforms other GA-based and traditional BN structure learning algorithms in terms of structural accuracy, convergence speed, and computational time.