M.Sc. Teppo Niinimäki will defend his doctoral thesis Approximation Strategies for Structure Learning in Bayesian Networks on Friday the 21st of August 2015 at noon in the University of Helsinki Exactum Building, Auditorium CK112 (Gustaf Hällströmin katu 2b).  His opponent is Professor Timo Koski (Royal Institute of Technology, Sweden) and custos Professor Jyrki Kivinen (University of Helsinki). The defense will be held in Finnish.

Approximation Strategies for Structure Learning in Bayesian Networks

Bayesian networks are probabilistic graphical models, which can compactly represent complex probabilistic dependencies between a set of variables. Once learned from data or constructed by some other means, they can both give insight into the modeled domain and be used for probabilistic reasoning tasks, such as prediction of future data points.

Learning a Bayesian network consists of two tasks: discovering a graphical dependency structure on variables, and finding the numerical parameters of a conditional distribution for each variable. Structure discovery has attracted considerable interest in the recent decades. Attention has mostly been paid to finding a structure that best fits the data under certain criterion. The optimization approach can lead to noisy and partly arbitrary results due to the uncertainty caused by a small amount of data. The so-called full Bayesian approach addresses this shortcoming by learning the posterior distribution of structures. In practice, the posterior distribution is summarized by constructing a representative sample of structures, or by computing marginal posterior probabilities of individual arcs or other substructures.

This thesis presents algorithms for the full Bayesian approach to structure learning in Bayesian networks. Because the existing exact algorithms only scale to small networks of up to about 25 variables, we investigate sampling based, Monte Carlo methods. The state-of-the-art sampling algorithms draw orderings of variables along a Markov chain. We propose several improvements to this algorithm. First, we show that sampling partial orders instead of linear orders can lead to radically improved mixing of the Markov chain and consequently better estimates. Second, we suggest replacing Markov chain Monte Carlo by annealed importance sampling. This can further improve the accuracy of estimates and has also other advantages such as independent samples and easy parallelization. Third, we propose a way to correct the bias that is caused by sampling orderings of variables instead of structures. Fourth, we present an algorithm that can significantly speed up per-sample computations via approximation.

In addition, the thesis proposes a new algorithm for so-called local learning of the Bayesian network structure. In local learning the task is to discover the neighborhood of a given target variable. In contrast to previous algorithms that are based on conditional independence tests between variables, our algorithm gives scores to larger substructures. This approach often leads to more accurate results.

Availability of the dissertation

An electronic version of the doctoral dissertation is available on the e-thesis site of the University of Helsinki at http://urn.fi/URN:ISBN:978-951-51-1446-4.

Printed copies are available on request from Teppo Niinimäki: tel. +358 2941 51236 or teppo.niinimaki@cs.helsinki.fi.