ANYTIME EXACT BELIEF PROPAGATION FOR PROBABILISTIC GRAPHICAL MODELS AND APPLICATIONS

Abstract

Probabilistic Graphical Models (PGM's) are an elegant and powerful framework that combines uncertainty and a logical structure to represent, in a compact way, complex real world problems.

This framework is quite general, and many common statistical models (Kalman filters, hidden Markov models, mixture models) are actually instances of the PGM formalism. PGM's are also largely used in Decision Making Under Uncertainty.

Inference over PGM's is a major class of problems and is known to be NP-Hard. The present work is a novel approach to thi problem. Traditional algorithms either provide an exact solution for this problem at a high computational cost or provide imprecise information. Anytime Exact Belief Propagation accomplishes both exactness of information (under the form of lower and upper bounds) and relatively fast computation. Besides, the output can be refined as many times as the user finds it necessary, according to the requirements of each particular application.