Title

Parallelising Probabilistic Inference in Bayesian Networks

Description

Probabilistic Graphical Models (PGMs) are a popular way of portraying condi- tional dependencies between random variables (randvars) of a complex proba- bility distribution. One of the main purposes of PGMs is performing inference, mostly in the form of answering a stated query. Because PGMs only contain variables and values necessary for answering these queries, the total amount of calculations for performing inference is reduced to a minimum in comparison to taking the whole model into account.

In a PGM, each randvar is represented as a node in the graph and edges between randvars depict dependencies. A belief network (BN), also called a Bayesian Network, is a directed acyclic graph (DAG). It factorizes the joint probability distribution into smaller parts for every randvar. This way, instead of answering an inference query with the whole joint probability distribution of the model, it is possible to only consider the values of randvars we know to be dependent on each other.

Cooper has shown that exact inference on BNs is NP-hard, therefore finding an algorithm that efficiently performs on all BNs is not feasible. Still, some researchers have designed algorithms that perform exact inference in cer- tain belief networks. Popular exact inference algorithms include Variable Elim- ination (Zhang and Poole), Sum-Up Message Passing (Belief Propagation) (Kim and Pearl) and Junction Tree algorithm (Lauritzen and Spiegelhalter). To handle the computational complexity, using parallelised algorithms potentially results in a reduction of runtime. Since variable elimination is not only the main part of the Variable Elimination algorithm, but also part of the Sum-Up Message Passing algorithm, parallelising this process offers great potential.

The bigger the network, the greater the runtime becomes. Minimising the calculation time is therefore desirable. The challenge lies in accelerating exact inference without compromising on the correctness or accuracy of the results. Parallelising the variable elimination process and using the results in the Belief Propagation algorithm can yield a significant speedup compared to a sequential implementation while still guaranteeing correctness. It should therefore be examined further.

The goal of this bachelor thesis is to implement a parallel version of the Variable Elimination algorithm and examine its effect on the runtime in comparison to a sequential version of the algorithm. The goal is to achieve a significant speedup in comparison to the sequential implementation.

Requirements

Probabilistic inference

Person working on it

Lisa Angold

Category

Bachelor thesis