Optimizing Queries in Bayesian Networks

This thesis explores and compares different methods of optimizing queries in Bayesian networks. Bayesian networks are graph-structured models that model probabilistic variables and their influences on each other; a query poses the question of what probabilities certain variables assume, given observed values on certain other variables. Bayesian inference (calculating these probabilities) is known to be NP-hard in general, but good algorithms exist in practice. Inference optimization traditionally concerns itself with finding and tweaking efficient algorithms, and leaves the choice of algorithms' parameters, as well as the construction of inference-friendly Bayesian network models, as an exercise to the end user. This thesis aims towards a more systematic approach to these topics: We try to optimize the structure of a given Bayesian network for inference, also taking into consideration what is known about the kind of queries that are posed. First, we implement several automatic model modifications that should help to make a model more suitable for inference. Examples of these are the conversion of definitions of conditional probability distributions from table form to noisy gates, and divorcing parents in the graph. Second, we introduce the concepts of usage profiles and query interfaces on Bayesian networks and try to take advantage of them. Finally, we conduct performance measurements of the different options available in the used library for Bayesian networks, to compare the effects of different options on speedup and stability, and to answer the question of which options and parameters represent the optimal choice to perform fast queries in the end product. The thesis gives an overview of what issues are important to consider when trying to optimize an application's query performance in Bayesian networks, and when trying to optimize Bayesian networks for queries. The project uses the SMILE library for Bayesian networks by the University of Pittsburgh, and includes a case study on script-generated Bayesian networks for troubleshooting by Scania AB