Local approximate inference algorithms

Details Local approximate inference algorithms Local approximate inference algorithms

2006-10-18

arxiv.org/abs/cs/0610111v3

Computer Science

Artificial Intelligence

21 pages, 10 figures

Scientific paper

We present a new local approximation algorithm for computing Maximum a Posteriori (MAP) and log-partition function for arbitrary exponential family distribution represented by a finite-valued pair-wise Markov random field (MRF), say $G$. Our algorithm is based on decomposition of $G$ into {\em appropriately} chosen small components; then computing estimates locally in each of these components and then producing a {\em good} global solution. We show that if the underlying graph $G$ either excludes some finite-sized graph as its minor (e.g. Planar graph) or has low doubling dimension (e.g. any graph with {\em geometry}), then our algorithm will produce solution for both questions within {\em arbitrary accuracy}. We present a message-passing implementation of our algorithm for MAP computation using self-avoiding walk of graph. In order to evaluate the computational cost of this implementation, we derive novel tight bounds on the size of self-avoiding walk tree for arbitrary graph. As a consequence of our algorithmic result, we show that the normalized log-partition function (also known as free-energy) for a class of {\em regular} MRFs will converge to a limit, that is computable to an arbitrary accuracy.

Affiliated with

Also associated with

No associations

Rating

Local approximate inference algorithms 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 Local approximate inference algorithms, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Local approximate inference algorithms will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-12596