Best-first Search Algorithm For Optimal Triangulation Of Bayesian Networks And Its Application

In the scope of artificial intelligence,uncertain reasoning generally refers to all kinds of reasoning problems except precise reasoning.Among many uncertain reasoning methods,Bayesian network is a connotative method based on model.In short,it provides a model representation of specific domain knowledge and several learning and reasoning mechanisms based on this model.It is used to build models and answer questions related to the domain knowledge,and on this basis,it can assist in prediction,decision-making and analysis.Since the emergence of Bayesian network,its reasoning and calculation has been one of the hot spots and difficulties in artificial intelligence.Bayesian network reasoning methods are divided into two categories: accurate and approximate.Connection tree method is a classical Bayesian network precise reasoning method,which plays an important role in Bayesian network reasoning.The connection tree algorithm first triangulates the Bayesian network,then transforms it into a connection tree,and then propagates the belief on the connection tree to complete the reasoning calculation.The key of the algorithm is to triangulate the Bayesian network in the optimal form so as to maximize the efficiency of reasoning and calculation.For a given Bayesian network,we find a triangulation graph to minimize the number of nodes in the largest cluster.This kind of optimal triangulation problem is called treewidth problem.Another kind of optimal triangulation problem is called tree cost problem.Its goal is to minimize the state space of all clusters in the triangulation graph.This kind of problem is similar to that of Bayesian network Precise reasoning algorithm is more closely related.The problem of tree cost is not only of great significance to join tree method,but also to variable elimination method,adjustment method,decomposable negative normal form method and other precise reasoning methods.In the current popular algorithm research of tree cost problem,the main work is based on the depth first search and best first search algorithm proposed by Ottosen and vomlel in 2012.They have proved that the running time of depth first search and best first search is almost the same,while the former uses less memory.After that,Li and Ueno improved depth first search to further improve the operation efficiency of depth first search.One of the work of this paper is based on Li and Ueno's work,further improve Ottosen and vomlel's best first search algorithm,and more carefully study the advantages and disadvantages of best first search compared with depth first search.In order to evaluate the performance of the proposed improved algorithm,we test the performance of the algorithm on a set of standard test cases on Bayesian networks(http://www.cs.huji.ac.il/site/labs/composite/repository/).The experimental results show that our best first search algorithm has obvious advantages in time and number of access nodes compared with Ottosen's and vomlel's best first search algorithm and even the best depth first search algorithm.The second work of this paper is based on the best first search algorithm proposed in this paper,a software which can edit the structure of Bayesian network and carry out reasoning calculation is designed,and a program which can be used for simple print fault diagnosis is further implemented to verify the practicability of the best first search algorithm.Experiments show that our algorithm has certain application value.