Title

Approximating Probabilistic Inference by Treewidth Minimization in Graphical Models

Abstract

Probabilistic inference depends exponentially on the so called tree width, which is a measure of the worst-case intermediate result during inference that is bounded from below by the maximum number of random variables appearing in any factor of a model. Interchangeability between random variables allows for compactly encoding large factors into smaller representations, which may hopefully then be efficiently used during inference. The goal of this thesis is to investigate exact and approximate interchangeability and its potential to reduce the maximum factor size and as such the lower bound on the tree width as well as the runtime for inference.

Requirements

Probability theory, probabilistic graphical models, (lifted inference)

Person working on it

Sagad Hamid

Category

Master thesis