On Cavity Approximations for Graphical Models

Details On Cavity Approximations for Graphical Models On Cavity Approximations for Graphical Models

2006-08-14

arxiv.org/abs/cond-mat/0608312v2

Physics

Condensed Matter

Statistical Mechanics

Extension to factor graphs and comments on related work added

Scientific paper

10.1103/PhysRevE.76.011102

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.

Affiliated with

Also associated with

No associations

Rating

On Cavity Approximations for Graphical Models does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with On Cavity Approximations for Graphical Models, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and On Cavity Approximations for Graphical Models will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-242598