Research On Learning Bounded Treewidth Bayesian Networks

As a classical interpretable uncertainty processing model in the field of artificial intelligence,Bayesian networks have been widely used in many areas.Machine learning methods for Bayesian networks are the focus of Bayesian networks research.Although existing learning methods of Bayesian networks can learn the optimal Bayesian network that best fits the training data,due to the close correlation between the complexity of Bayesian networks inference algorithms and the structure of Bayesian networks,the inference complexity of the optimal Bayesian network is not necessarily optimal,which may lead to the high inference complexity of Bayesian networks that require a large amount of computational resources to learn and are difficult to apply in practice.Therefore,this thesis studies how to consider the efficiency of inference in the learning process of Bayesian networks,so as to make the learning results both accurate and efficient.The "treewidth" of a Bayesian network is a key indicator of its inference complexity.The smaller the treewidth of a Bayesian network,the lower its inference complexity.This thesis proposes three bounded treewidth Bayesian networks learning methods,which limit the treewidth of Bayesian networks from three aspects during the learning process,thereby limiting the inference complexity of learning results:(1)This thesis proposes a Bayesian networks learning method combining genetic algorithm and particle swarm optimization.This method introduces an elite set strategy to intelligently limit the maximum number of parent nodes for each node in the Bayesian network,reducing the treewidth of the Bayesian network,and thereby reducing the inference complexity of the Bayesian network.(2)This thesis proposes a bounded treewidth Bayesian networks learning method based on Monte Carlo Tree Search(MCTS).MCTS combines the accuracy of tree search with the universality of random sampling,and has achieved significant results in some game and planning problems with large search space.In this thesis,MCTS is introduced into the learning framework of Bayesian networks,and a heuristic function is designed to balance local and global exploration to enhance the search ability of the node ordered space of Bayesian networks.In addition,bounded treewidth learning of Bayesian networks is performed in the node ordered space.Experimental results on multiple datasets show that under the heuristic ability of MCTS,this method is superior to k-G and approximately equivalent to k-MAX.(3)This thesis designs an index,Average Elimination Cost(AEC),that can more accurately measure the inference complexity than treewidth,and proposes a Bayesian networks learning method that limits AEC.In practical applications,the domain size of node in many datasets is not all binary or the same,and in this case,the treewidth cannot accurately characterize the inference complexity of such Bayesian networks.AEC takes into account the domain size of each node in a Bayesian network,allowing nodes to share unused elimination costs with each other.Therefore,AEC has a stronger ability to characterize inference complexity than treewidth.Experimental results on multiple datasets show that this method is superior to similar methods.