On Cavity Approximations for Graphical Models

Abstract

We reformulate the Cavity Approximation (CA), a class of algorithms recently introduced for improving the Bethe approximation estimates of marginals in graphical models. In our new formulation, which allows for the treatment of multivalued variables, a further generalization to factor graphs with arbitrary order of interaction factors is explicitly carried out, and a message passing algorithm that implements the first order correction to the Bethe approximation is described. Furthermore we investigate an implementation of the CA for pairwise interactions. In all cases considered we could confirm that CA[k] with increasing $k$ provides a sequence of approximations of markedly increasing precision. Furthermore in some cases we could also confirm the general expectation that the approximation of order $k$, whose computational complexity is $O(N^{k+1})$ has an error that scales as $1/N^{k+1}$ with the size of the system. We discuss the relation between this approach and some recent developments in the field.

Extension to factor graphs and comments on related work added

References in corpus (5)

• The Bethe lattice spin glass revisited
• Cluster Variation Method in Statistical Physics and Probabilistic Graphical Models
• Loop Calculus in Statistical Physics and Information Science
• How to Compute Loop Corrections to Bethe Approximation
• Loop expansion around the Bethe-Peierls approximation for lattice models

Cited by in corpus (9)

• Critical phenomena in complex networks
• Region graph partition function expansion and approximate free energy landscapes: Theory and some numerical results
• Partition function loop series for a general graphical model: free energy corrections and message-passing equations
• Loop expansion around the Bethe approximation through the $M$-layer construction
• Finite size corrections to disordered systems on Erdös-Rényi random graphs
• Belief propagation with multipoint correlations and its application to Inverse problem
• Loop corrections in spin models through density consistency
• A Generalized Loop Correction Method for Approximate Inference in Graphical Models
• Decimation flows in constraint satisfaction problems