Predicting Loss of Inference Accuracy in Bounded Tree-Width Bayesian Networks

A Bayesian network (BN) is a compact way to represent a joint probability distribution graphically. The BN consists of a structure in the form of a directed acyclic graph (DAG) and a set of parameters. The nodes of the DAG correspond to random variables, and the absence of an arc encodes a conditional independence between two variables. Computing conditional probabilities from a Bayesian network is known as inference and is an NP-hard problem. However, the problem is fixed-parameter tractable with respect to a property of the network called tree-width. As a consequence, learning networks of bounded tree-width is of interest. When we bound the tree-width of a BN, we may no longer be able to accurately represent the probability distribution and thus we expect some loss of inference accuracy. However, predicting how much the inference accuracy will decay is no easy task. In this thesis, we propose a solution to this problem by quantifying the strength of arcs in the network. We define a measure called dependency strength that measures how strong the dependencies in our network are. We also report results from an experiment to evaluate how well the measure performs in predicting the loss of accuracy in bounded tree-width BNs. Our findings show indications that the measure can be used to predict loss of inference accuracy, but we conclude that more experiments are needed to confirm this.Masteroppgave i Programutvikling samarbeid med HVLPROG399MAMN-PRO