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
BeliefPropagation 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 BeliefPropagation. We show that
our bound outperforms the state-of-the-art on some inference problems arising in
medical diagnosis.

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 approximate inference methods are needed. We use naive mean field approximation and beliefpropagation to approximate the optimal control in systems with linear dynamics. We compare the approximate inference 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 BeliefPropagation (BP) can be successfully applied to approximate inference 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 BeliefPropagation (BP) that takes into account the influence of loops in the graphical model. The method is a variation on and generalization of the method recently introduced by Montanari and Rizzo [2005]. It consists of two steps: (i) standard BP is used to calculate 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 combined by a messagepassing algorithm to obtain consistent single node marginals. The method is exact if the graphical model contains a single loop. The complexity of the method is exponential in the size of the Markov blankets. The results are very accurate in general: the error is often several orders of magnitude smaller than that of standard BP, as illustrated by numerical experiments.

Abstract: We propose a method to improve approximate inference 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, beliefpropagation, 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, approximate inference 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 approximate inference method. In this article, we compare different
variants of the loop correction method with other approximate inference methods on a variety of
graphical models, including “real world” networks, and conclude that the LC method generally
obtains the most accurate results

Abstract: We analyse the local stability of the high-temperature fixed point of the loopy beliefpropagation (LBP) algorithm and how this relates to the properties of the Bethe free energy which LBP tries to minimize. We focus on the case of binary networks with pairwise interactions. In particular, we state sufficient conditions for convergence of LBP to a unique fixed point and show that these are sharp for purely ferromagnetic interactions. In contrast, in the purely antiferromagnetic case, the undamped parallel LBP algorithm is suboptimal in the sense that the stability of the fixed point breaks down much earlier than for damped or sequential LBP; we observe that the onset of instability for the latter algorithms is related to the properties of the Bethe free energy. For spin-glass interactions, damping LBP only helps slightly. We estimate analytically the temperature at which the high-temperature LBP fixed point becomes unstable for random graphs with arbitrary degree distributions and random interactions.

Abstract: We derive sufficient conditions for the uniqueness of loopy beliefpropagation fixed points. These conditions depend on both the structure of the graph and the strength of the potentials and naturally extend those for convexity of the Bethe free energy. We compare them with (a strengthened version of) conditions derived elsewhere for pairwise potentials. We discuss possible implications for convergent algorithms, as well as for other approximate free energies.

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 approximate inference.
The lack of open source "reference" implementations hampers progress in research on approximate inference. 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 approximate inference 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) approximate inference 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 BeliefPropagation (BP) solution, developed in the ICIS project SNN1 (see Gomez (2009), Approximate inference on planar graphs using Loop Calculus and BeliefPropagation).

Abstract: We derive novel suficient conditions for convergence of Loopy BeliefPropagation (also
known as the Sum-Product algorithm) to
a unique xed point. Our results improve
upon previously known conditions. For binary variables with (anti-)ferromagnetic interactions, our conditions seem to be sharp.

Abstract: We derive novel conditions that guarantee convergence of the Sum-Product algorithm (also known as Loopy BeliefPropagation
or simply BeliefPropagation) to a unique fixed point, irrespective of the initial messages. The computational complexity of the
conditions is polynomial in the number of variables. In contrast with previously existing conditions, our results are directly
applicable to arbitrary factor graphs (with discrete variables) and are shown to be valid also in the case of factors containing
zeros, under some additional conditions. We compare our bounds with existing ones, numerically and, if possible, analytically.
For binary variables with pairwise interactions, we derive sufficient conditions that take into account local evidence (i.e. single
variable factors) and the type of pair interactions (attractive or repulsive). It is shown empirically that this bound outperforms
existing bounds.

Abstract: Recently, M. Chertkov and V.Y. Chernyak derived an exact expression for the partition sum (normalization constant) corresponding to a graphical model, which is an expansion around the BeliefPropagation solution. By adding correction terms to the BP free energy, one for each "generalized loop" in the factor graph, the exact partition sum is obtained. However, the usually enormous number of generalized loops generally prohibits summation over all correction terms. In this article we introduce Truncated Loop Series BP (TLSBP), a particular way of truncating the loop series of M. Chertkov and V.Y. Chernyak by considering generalized loops as compositions of simple loops. We analyze the performance of TLSBP in different scenarios, including the Ising model, regular random graphs and on Promedas, a large probabilistic medical diagnostic system. We show that TLSBP often improves upon the accuracy of the BP solution, at the expense of increased computation time. We also show that the performance of TLSBP strongly depends on the degree of interaction between the variables. For weak interactions, truncating the series leads to significant improvements, whereas for strong interactions it can be ineffective, even if a high number of terms is considered.

Abstract: Recently, M. Chertkov and V.Y. Chernyak derived an exact expression for the partition sum (normalization constant) corresponding to a graphical model, which is an expansion around the BeliefPropagation solution. By adding correction terms to the BP free energy, one for each "generalized loop" in the factor graph, the exact partition sum is obtained. However, the usually enormous number of generalized loops generally prohibits summation over all correction terms. In this article we introduce Truncated Loop Series BP (TLSBP), a particular way of truncating the loop series of M. Chertkov and V.Y. Chernyak by considering generalized loops as compositions of simple loops. We analyze the performance of TLSBP in different scenarios, including the Ising model, regular random graphs and on Promedas, a large probabilistic medical diagnostic system. We show that TLSBP often improves upon the accuracy of the BP solution, at the expense of increased computation time. We also show that the performance of TLSBP strongly depends on the degree of interaction between the variables. For weak interactions, truncating the series leads to significant improvements, whereas for strong interactions it can be ineffective, even if a high number of terms is considered.