# Loop Corrections for Approximate Inference on Factor Graphs

Joris M. Mooij, Hilbert J. Kappen.

Year: 2007, Volume: 8, Issue: 40, Pages: 1113−1143

#### 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 inference
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.