Heuristic Algorithms for Bayesian Network Triangulation

Bayesian networks (BNs) are popular tools for uncertain reasoning in expert systems. These networks rely on inference algorithms to answer queries in the context of observed evidence. One established algorithm, called join tree propagation (JTP), requires triangulation of the directed acyclic graph (DAG) of a BN to conduct a generalized evidence propagation scheme. Depending on the problem to be solved by triangulation, optimality may be defined differently. Total cost is a optimality criterion which contains the number of fill-in edges, the size of largest clique and the total weight of all the cliques in a triangulation of a BN. The advantage of total cost criterion is that the smaller the total cost is, the more efficiently the join tree propagation algorithm is carried out.;In this thesis, we present a heuristic algorithm named dynamic tree decomposition (DTD) for finding minimal triangulations with small total cost. This is the first algorithm to ever apply total cost criterion in triangulation of BNs. DTD also obtains a tree decomposition satisfying the join tree (JT) property. Moreover, DTD can be extended to decompose a BN into its maximal prime subgraph decomposition (MPD), which is unique and contains several smaller and simpler maximal prime subgraphs. Those maximal prime subgraphs can be triangulated separately and then assembled together to give a triangulation for the entire BN. The improvement offered by DTD is shown by using a series of empirical evaluations conducted on various BNs from Evaluation of Probabilistic Inference Systems at 22nd Conference on Uncertainty in Artificial Intelligence. The experimental results demonstrate three major advantages offered by our algorithm DTD. Firstly, DTD generates triangulations with not only smaller total cost and total weight, but also fewer fill-in edges than the current state-of-the-art triangulation algorithms, namely, maximum cardinality search, minimum degree and LB-Triang. Secondly, DTD takes less time to perform transformation from a BN to a JT. Thirdly, DTD can be exploited as a good approach to divide a complicated BN into its unique MPD, which can be used to generate an even better triangulation with fewer fill-in edges, smaller total weight and total cost.