Research On Learning Bayesian Network With Positive And Negative Ancestral Constraints Based On A* Search

Bayesian network is a mathematical model based on graph theory and probability theory.With its clear semantics and strong interpretability,it has become one of the most important models in the field of uncertain knowledge representation and reasoning.And it is widely used in artificial intelligence,fault diagnosis,medical treatment and other fields.The modeling of the Bayesian network includes two parts: structure learning and parameter learning.The structure learning is the learning of the structure of a directed graph,which is the basis of parameter learning.However,the learning of the optimal Bayesian network is an NP-hard problem.Therefore,how to narrow the search space with the guidance of prior knowledge of experts and realize efficient and accurate network search has become a hot research direction for scholars.Ancestral constraints are used to represent the causal relationship between two variables,and it can also be regarded as the path relationship between different nodes in the directed graph structure of the Bayesian network.The ancestral constraint is the important prior knowledge for Bayesian network learning.If X is the ancestor of Y,then in the directed graph structure of the Bayesian network,there must be a directed path from X to Y.If X is not the ancestor of Y,then there is no such path.This paper proposes a Bayesian network learning method based on the A* algorithm,designs two heuristic functions that support ancestral constraints,and proves their admissibility and consistency.The experimental results show that compared with the original heuristic functions,the new heuristic functions can guide the A* algorithm to find the optimal solution faster while occupying less memory.The work of this paper includes:(1)Based on the Bayesian Network Graph(BNG)search space,the A* algorithm is used for Bayesian network learning when ancestral constraints exist,and a new heuristic function that supports ancestral constraints is designed.The new heuristic function restricts the set of candidate parents of each variable basing on the current network structure and ancestral constraints,so as to obtain a more accurate heuristic value,and at the same time it is proved that the new heuristic function satisfies admissibility and consistency.(2)In the process of heuristic function calculation,in order to obtain the ancestordescendant relationship between variables,it is necessary to frequently visit the topology of the network,resulting in high time consumption.To solve this problem,this paper proposes to maintain a descendant matrix during the search process,which is used to cache the ancestor-descendant relationship between variables and speed up the calculation of heuristic values.(3)A new static k-cycle conflict heuristic function that can support the ancestral constraint is designed.The heuristic function restricts the set of candidate parents of each variable in the score cache generation stage,so as to obtain a more accurate heuristic value,and at the same time it is proved that the new heuristic function satisfies admissibility and consistency.In this paper,two new heuristic functions are compared with the original heuristic functions,and comparative experiments are carried out on the classic Bayesian network,ALARM and CHILD.The experimental results verify that the new heuristic functions in this paper can support positive ancestral constraints,negative ancestral constraints,and the hybrid constraints,and compared with the original heuristic functions,the new heuristic functions have better performance in terms of search time and memory usage.