Abstract: We introduce novel results for approximateinference on planar graphical models using
the loop calculus framework. The loop cal-
culus (Chertkov and Chernyak, 2006b) allows
to express the exact partition function Z of
a graphical model as a finite sum of terms
that can be evaluated once the belief prop-
agation (BP) solution is known. In general,
full summation over all correction terms is
intractable. We develop an algorithm for
the approach presented in Chertkov et al.
(2008) which represents an efficient trunca-
tion scheme on planar graphs and a new rep-
resentation of the series in terms of Pfaffians
of matrices. We analyze in detail both the
loop series and the Pfaffian series for mod-
els with binary variables and pairwise in-
teractions, and show that the first term of
the Pfaffian series can provide very accurate
approximations. The algorithm outperforms
previous truncation schemes of the loop series
and is competitive with other state-of-the-art
methods for approximateinference.

Abstract: We propose a novel bound on single-variable marginal probability distributions in
factor graphs with discrete variables. The bound is obtained by propagating local
bounds (convex sets of probability distributions) over a subtree of the factor graph,
rooted in the variable of interest. By construction, the method not only bounds
the exact marginal probability distribution of a variable, but also its approximate
Belief Propagation marginal (“belief”). Thus, apart from providing a practical
means to calculate bounds on marginals, our contribution also lies in providing
a better understanding of the error made by Belief Propagation. We show that
our bound outperforms the state-of-the-art on some inference problems arising in
medical diagnosis.

Abstract: libDAI is a free/open source C++ library (licensed under GPL) that provides
implementations of various (deterministic) approximateinference methods for
discrete graphical models. libDAI supports arbitrary factor graphs with
discrete variables (this includes discrete Markov Random Fields and Bayesian
Networks).

Abstract: In this article we consider the issue of optimal control in collaborative multi-agent systems with stochastic dynamics. The agents have a joint task in which they have to reach a number of target states. The dynamics of the agents contains additive control and additive noise, and the autonomous part factorizes over the agents. Full observation of the global state is assumed. The goal is to minimize the accumulated joint cost, which consists of integrated instantaneous costs and a joint end cost. The joint end cost expresses the joint task of the agents. The instantaneous costs are quadratic in the control and factorize over the agents. The optimal control is given as a weighted linear combination of single-agent to single-target controls. The single-agent to single-target controls are expressed in terms of diffusion processes. These controls, when not closed form expressions, are formulated in terms of path integrals, which are calculated approximately by Metropolis-Hastings sampling. The weights in the control are interpreted as marginals of a joint distribution over agent to target assignments. The structure of the latter is represented by a graphical model, and the marginals are obtained by graphical model inference. Exact inference of the graphical model will break down in large systems, and so approximateinference methods are needed. We use naive mean field approximation and belief propagation to approximate the optimal control in systems with linear dynamics. We compare the approximateinference methods with the exact solution, and we show that they can accurately compute the optimal control. Finally, we demonstrate the control method in multi-agent systems with nonlinear dynamics consisting of up to 80 agents that have to reach an equal number of target states.

Abstract: In the current paper, the Promedas model for internal medicine,
developed by our team, is introduced. The model is based on up-to-date
medical knowledge and consists of approximately 2000 diagnoses, 1000
ndings and 8600 connections between diagnoses and ndings, covering
large parts of internal medicine. Promedas is currently being evaluated
informally by specialists in internal medicine at the Utrecht university
hospital and is receiving positive responses.We show that Belief Propagation (BP) can be successfully applied to approximateinference problems
in the Promedas network. BP converges on all patient test cases, which
were generated with the help of the model itself. In some cases, however,
we nd errors that are too large for this application. We apply a recently
developed method that improves the BP results by means of a loop expansion scheme. This method, termed Loop Corrected (LC) BP, is able
to improve the marginal probabilities signicantly, leaving a remaining
error which is acceptable for the purpose of medical diagnosis.

Abstract: We propose a method for improving approximateinference methods that corrects for the influence of loops in the graphical model. The method is applicable to arbitrary factor graphs, provided that the size of the Markov blankets is not too large. It is an alternative implementation of an idea introduced recently by Montanari and Rizzo (2005). In its simplest form, which amounts to the assumption that no loops are present, the method reduces to the minimal Cluster Variation Method approximation (which uses maximal factors as outer clusters). On the other hand, using estimates of the effect of loops (obtained by some approximateinference algorithm) and applying the Loop Correcting (LC) method usually gives significantly better results than applying the approximateinference algorithm directly without loop corrections. Indeed, we often observe that the loop corrected error is approximately the square of the error of the approximateinference method used to estimate the effect of loops. We compare different variants of the Loop Correcting method with other approximateinference methods on a variety of graphical models, including "real world" networks, and conclude that the LC approach generally obtains the most accurate results.

Abstract: We propose a method to improve approximateinference methods by correcting for the influence of
loops in the graphical model. The method is a generalization and alternative implementation of a recent idea from Montanari and Rizzo (2005). It is applicable to arbitrary factor graphs, provided that
the size of the Markov blankets is not too large. It consists of two steps: (i) an approximate infer-
ence method, for example, belief propagation, is used to approximate cavity distributions for each
variable (i.e., probability distributions on the Markov blanket of a variable for a modified graphical
model in which the factors involving that variable have been removed); (ii) all cavity distributions
are improved by a message-passing algorithm that cancels out approximation errors by imposing
certain consistency constraints. This loop correction (LC) method usually gives significantly better
results than the original, uncorrected, approximateinference algorithm that is used to estimate the
effect of loops. Indeed, we often observe that the loop-corrected error is approximately the square
of the error of the uncorrected approximateinference method. In this article, we compare different
variants of the loop correction method with other approximateinference methods on a variety of
graphical models, including “real world” networks, and conclude that the LC method generally
obtains the most accurate results

Abstract: Probabilistic graphical models, and in particular Bayesian networks, are nowadays well established as a modeling tool for domains with
uncertainty. A drawback is that large, complex graphical models are intractable for exact computation. Therefore there is a lot of research interest in approximateinference.
The lack of open source "reference" implementations hampers progress in research on approximateinference. Methods differ widely in terms of quality and performance characteristics, which also depend in different ways on various properties of the graphical models. Finding the best approximateinference method for a particular application therefore often requires empirical comparisons. However, implementing and debugging these methods takes a lot of time which could otherwise be spent on research. Therefore we have developed libDAI. libDAI is a free/open source C++ library (licensed under GPL) that provides implementations of various (deterministic) approximateinference methods for discrete graphical models. libDAI supports arbitrary `factor graphs` with discrete variables (this includes discrete Markov Random Fields and Bayesian Networks).
This release is an additional contribution to the LibDAI library. This code implements the Z2 algorithm, a particular way of correcting the Belief Propagation (BP) solution, developed in the ICIS project SNN1 (see Gomez (2009), Approximateinference on planar graphs using Loop Calculus and Belief Propagation).