Bayesian Network Structure Learning Using Improved A* with Constraints from Potential Optimal Parent Sets
Open Access
- 30 July 2023
- journal article
- research article
- Published by MDPI AG in Mathematics
- Vol. 11 (15) , 3344
Abstract
Learning the structure of a Bayesian network and considering the efficiency and accuracy of learning has always been a hot topic for researchers. This paper proposes two constraints to solve the problem that the A* algorithm, an exact learning algorithm, is not efficient enough to search larger networks. On the one hand, the parent–child set constraints reduce the number of potential optimal parent sets. On the other hand, the path constraints are obtained from the potential optimal parent sets to constrain the search process of the A* algorithm. Both constraints are proposed based on the potential optimal parent sets. Experiments show that the time efficiency of the A* algorithm can be significantly improved, and the ability of the A* algorithm to search larger Bayesian networks can be improved by the two constraints. In addition, compared with the globally optimal Bayesian network learning using integer linear programming (GOBNILP) algorithm and the max–min hill-climbing (MMHC) algorithm, which are state of the art, the A* algorithm enhanced by constraints still performs well in most cases.Keywords
Funding Information
- National Natural Science Foundation of China (61573285, 62171360, 2022JQ-590)
- Natural Science Foundation of Shaanxi Province of China (61573285, 62171360, 2022JQ-590)
This publication has 22 references indexed in Scilit:
- Integer Linear Programming for the Bayesian network structure learning problemArtificial Intelligence, 2017
- Learning Bayesian networks by hill climbing: efficient methods based on progressive restriction of the neighborhoodData Mining and Knowledge Discovery, 2010
- The max-min hill-climbing Bayesian network structure learning algorithmMachine Learning, 2006
- Learning Bayesian network structures by searching for the best ordering with genetic algorithmsIEEE Transactions on Systems, Man, and Cybernetics - Part A: Systems and Humans, 1996
- Learning Bayesian Networks is NP-Complete1996
- Learning Bayesian networks: The combination of knowledge and statistical dataMachine Learning, 1995
- A theory of inferred causation1995
- A Bayesian method for the induction of probabilistic networks from dataMachine Learning, 1992
- An Algorithm for Fast Recovery of Sparse Causal GraphsSocial Science Computer Review, 1991
- Modeling by shortest data descriptionAutomatica, 1978