Distributed Anytime MAP Inference

Details Distributed Anytime MAP Inference Distributed Anytime MAP Inference

2012-02-14

arxiv.org/abs/1202.3767v1

Computer Science

Artificial Intelligence

Scientific paper

We present a distributed anytime algorithm for performing MAP inference in graphical models. The problem is formulated as a linear programming relaxation over the edges of a graph. The resulting program has a constraint structure that allows application of the Dantzig-Wolfe decomposition principle. Subprograms are defined over individual edges and can be computed in a distributed manner. This accommodates solutions to graphs whose state space does not fit in memory. The decomposition master program is guaranteed to compute the optimal solution in a finite number of iterations, while the solution converges monotonically with each iteration. Formulating the MAP inference problem as a linear program allows additional (global) constraints to be defined; something not possible with message passing algorithms. Experimental results show that our algorithm's solution quality outperforms most current algorithms and it scales well to large problems.

Affiliated with

Also associated with

No associations

Rating

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

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-90709