Treecost-based Preprocessing for Probabilistic Networks

Abstract

Probabilistic inference is an important problem in probability theory and concerns the process of computing the probability distribution of variables, given the evidence of other variables. An often used algorithm for this problem is the junction-tree propagation algorithm. To minimise the time to process all the probabilities by means of the algorithm, an optimal tree decomposition is required. A good parameter that measures the optimality of a tree decomposition is treecost. Unfortunately, computing the tree decomposition with minimal treecost is NP-hard Nevertheless, it can be simpli?ed by applying reduction rules that shrink the graph. These rules are familiar from treewidth, which is a well-studied parameter compared to treecost. In this thesis, a set of reduction rules are introduced and proven to be valid. This set includes rules that remove vertices and separate the graph by its components. Thereafter, experiments are conducted on input graphs, which are real-life probabilistic networks. Results of the experiment show that the graphs are reduced signi?cantly, due to these reduction rules. This, in turn, decreases the time to solve probabilistic inference. Prior knowledge about graph theory and complexity theory is assumed for this thesis.