Optimal triangulation of Bayesian networks for efficient inference
Chao Li · Institutional Repositories DataBase (IRDB) · 2017
Bayesian networks are widely used probabilistic graphical models that provide a compact representation of joint probability distributions over a set of variables. A common inference task in Bayesian networks is to compute the posterior marginal distributions for the unobserved variables given some evidence variables that we have already observed. However, the inference problem is known to be NP-hard and this complexity of inference limits the usage of Bayesian networks. Many attempts to improve the inference algorithm have been made in the past two decades. Currently, the junction tree algorithm is among the most prominent exact inference algorithms. To perform efficient inference on a Bayesian network using the junction tree algorithm, it is necessary to find a triangulation of the moral graph of the Bayesian network such that the total table size is small. In this context, the total table size is used to measure the computational complexity of the junction tree inference algorithm. This thesis focuses on exact algorithms for finding a triangulation that minimizes the total table size for a given Bayesian network. For optimal triangulation, Ottosen and Vomlel have proposed a depth-first search (DFS) algorithm. They also introduced several techniques to improve the DFS algorithm, including dynamic clique maintenance and coalescing map pruning. Nevertheless, the efficiency and scalability of their algorithm leave much room for improvement. First, the dynamic clique maintenance allows the recomputation of some cliques. Second, for a Bayesian network with n variables, the DFS algorithm runs in O*(n!) time because it explores a search space of all elimination orders. To mitigate these problems, an extended depth-first search (EDFS) algorithm is proposed in this thesis. The new EDFS algorithm introduces two techniques: (1) a new dynamic clique maintenance algorithm that computes only those cliques that contain a new edge, and (2) a new pruning rule, called pivot clique pruning. The new dynamic clique maintenance algorithm explores a smaller search space and runs faster than the Ottosen and Vomlel approach. This improvement can decrease the overhead cost of the DFS algorithm, and the pivot clique pruning reduces the size of the search space by a factor of O(n2). Our empirical results show that our proposed algorithm finds an optimal triangulation markedly faster than the state-of-the-art algorithm does.