Distributed Anytime MAP Inference

Joop van de Ven, Fabio Ramos
Proceedings of the 27th Conference on Uncertainty in Artificial Intelligence, PMLR R9:781-789, 2011.

Abstract

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.

Cite this Paper

BibTeX
@InProceedings{pmlr-vR9-ven11a, title = {Distributed Anytime {MAP} Inference}, author = {de Ven, Joop van and Ramos, Fabio}, booktitle = {Proceedings of the 27th Conference on Uncertainty in Artificial Intelligence}, pages = {781--789}, year = {2011}, editor = {Cozman, Fabio and Pfeffer, Avi}, volume = {R9}, series = {Proceedings of Machine Learning Research}, month = {14--17 Jul}, publisher = {PMLR}, pdf = {https://raw.githubusercontent.com/mlresearch/r9/main/assets/ven11a/ven11a.pdf}, url = {https://proceedings.mlr.press/r9/ven11a.html}, abstract = {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.}, note = {Reissued by PMLR on 04 October 2026.} }
Endnote
%0 Conference Paper %T Distributed Anytime MAP Inference %A Joop van de Ven %A Fabio Ramos %B Proceedings of the 27th Conference on Uncertainty in Artificial Intelligence %C Proceedings of Machine Learning Research %D 2011 %E Fabio Cozman %E Avi Pfeffer %F pmlr-vR9-ven11a %I PMLR %P 781--789 %U https://proceedings.mlr.press/r9/ven11a.html %V R9 %X 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. %Z Reissued by PMLR on 04 October 2026.
APA
de Ven, J.v. & Ramos, F.. (2011). Distributed Anytime MAP Inference. Proceedings of the 27th Conference on Uncertainty in Artificial Intelligence, in Proceedings of Machine Learning Research R9:781-789 Available from https://proceedings.mlr.press/r9/ven11a.html. Reissued by PMLR on 04 October 2026.

Related Material