Abstract: We introduce novel results for approximate
inference 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 approximate inference.
Abstract: This paper discusses inference problems in probabilistic graphical models that often occur in a machine learning setting. In particular it presents a unified view of several recently proposed approximation schemes. Expectation consistent approximations and expectation propagation are both shown to be related to Bethe free energies with weak consistency constraints, i.e. free energies where local approximations are only required to agree on certain statistics instead of full marginals.
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
Abstract: 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
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 belief propagation 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: Probabilistic graphical models, and in particular Bayesian networks, are nowadays well established as a modeling tool for domains with
uncertainty. In the SHELL outreach project, we have build a Bayesian network model for petrophysical decision support: the system estimates mineral composition based on borehole estimates. The system uses advanced hybrid Monte Carlo methods for inference. Unfortunately, we cannot disclose the system for Shell. Therefore, to demonstrate the method we have built a demonstrator for similar kind of inference in a toy-domain. What is the chemical composition of wine, given taste observations?
Note that this is a toy model for demonstration purposes. The model does not pretend to be realistic in any way.
Abstract: Variational Bayesian inference and (collapsed) Gibbs sampling are the two important classes of inference algorithms for Bayesian networks. Both have their advantages and disadvantages: collapsed Gibbs sampling is unbiased but is also inefficient for large count values and requires averaging over many samples to reduce variance. On the other hand, variational Bayesian inference is efficient and accurate for large count values but suffers from bias for small counts. We propose a hybrid algorithm that combines the best of both worlds: it samples very small counts and applies variational updates to large counts. This hybridization is shown to significantly improve testset perplexity relative to variational inference at no computational cost.
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 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 approximate inference 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 approximate inference algorithm) and applying the Loop Correcting (LC) method usually gives significantly better results than applying the approximate inference algorithm directly without loop corrections. Indeed, we often observe that the loop corrected error is approximately the square of the error of the approximate inference method used to estimate the effect of loops. We compare different variants of the Loop Correcting method with other approximate inference 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 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, 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, 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: 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 Belief Propagation (BP) solution, developed in the ICIS project SNN1 (see Gomez (2009), Approximate inference on planar graphs using Loop Calculus and Belief Propagation).
Abstract: We study optimal control in large stochastic multi-agent systems in continuous space and time. We consider multi-agent systems where agents have independent dynamics with additive noise and control. The goal is to minimize the joint cost, which consists of a state dependent term and a term quadratic in the control. The system is described by a mathematical model, and an explicit solution is given. We focus on large systems where agents have to distribute themselves over a number of targets with minimal cost. In such a setting the optimal control problem is equivalent to a graphical model inference problem. Exact inference will be intractable, and we use the mean field approximation to compute accurate approximations of the optimal controls. We conclude that near to optimal control in large stochastic multi-agent systems is possible with this approach.
Abstract: Optimal control theory is a mathematical description of how to act optimally
to gain future rewards. In this paper I give an introduction to
deterministic and stochastic control theory; partial observability,
learning and the combined problem of inference and control. Subsequently, I
discuss a new class of non-linear stochastic
control problems for which the Bellman equation becomes linear in the
control and that can be efficiently solved using a path integral.
In this control formalism the central concept of cost-to-go becomes a
free energy and methods and concepts from probabilistic graphical
models and statistical physics can be readily applied. I illustrate the
theory with a number of examples.
Abstract: Recently, a theory for stochastic optimal control in non-linear dynamical systems in continuous space-time has been developed (Kappen, 2005). We apply this theory to collaborative multi-agent systems. The agents
evolve according to a given non-linear dynamics with additive Wiener noise. Each
agent can control its own dynamics. The goal
is to minimize the accumulated joint cost,
which consists of a state dependent term and
a term that is quadratic in the control. We focus on systems of non-interacting agents that
have to distribute themselves optimally over
a number of targets, given a set of end-costs
for the different possible agent-target combinations. We show that optimal control is
the combinatorial sum of independent single-
agent single-target optimal controls weighted
by a factor proportional to the end-costs
of the different combinations. Thus, multi-
agent control is related to a standard graphical model inference problem. The additional
computational cost compared to single-agent
control is exponential in the tree-width of the
graph specifying the combinatorial sum times
the number of targets. We illustrate the result by simulations of systems with up to 42
Abstract: We introduce a computationally efﬁcient method to estimate the validity of the BP method as a function of graph topology, the connectivity strength, frustration and network size. We present numerical results
that demonstrate the correctness of our estimates for the uniform random
model and for a real-world network (“C. Elegans”). Although the method
is restricted to pair-wise interactions, no local evidence (zero “biases”)
and binary variables, we believe that its predictions correctly capture the
limitations of BP for inference and MAP estimation on arbitrary graphical models. Using this approach, we ﬁnd that BP always performs better
than MF. Especially for large networks with broad degree distributions
(such as scale-free networks) BP turns out to signiﬁcantly outperform