Approximate Inference by Intersecting Semidefinite Bound and Local Polytope

Jian Peng, Tamir Hazan, Nathan Srebro, Jinbo Xu
Proceedings of the Fifteenth International Conference on Artificial Intelligence and Statistics, PMLR 22:868-876, 2012.

Abstract

Inference in probabilistic graphical models can be represented as a constrained optimization problem of a free-energy functional. Substantial research has been focused on the approximation of the constraint set, also known as the marginal polytope. This paper presents a novel inference algorithm that tightens and solves the optimization problem by intersecting the popular local polytope and the semidefinite outer bound of the marginal polytope. Using dual decomposition, our method separates the optimization problem into two subproblems: a semidefinite program (SDP), which is solved by a low-rank SDP algorithm, and a free-energy based optimization problem, which is solved by convex belief propagation. Our method has a very reasonable computational complexity and its actual running time is typically within a small factor (=10) of convex belief propagation. Tested on both synthetic data and a real-world protein side-chain packing benchmark, our method significantly outperforms tree-reweighted belief propagation in both marginal probability inference and MAP inference. Our method is competitive with the state-of-the-art in MRF inference, solving all protein tasks solved by the recently presented MPLP method, and beating MPLP on lattices with strong edge potentials.

Cite this Paper

BibTeX
@InProceedings{pmlr-v22-peng12, title = {Approximate Inference by Intersecting Semidefinite Bound and Local Polytope}, author = {Peng, Jian and Hazan, Tamir and Srebro, Nathan and Xu, Jinbo}, booktitle = {Proceedings of the Fifteenth International Conference on Artificial Intelligence and Statistics}, pages = {868--876}, year = {2012}, editor = {Lawrence, Neil D. and Girolami, Mark}, volume = {22}, series = {Proceedings of Machine Learning Research}, address = {La Palma, Canary Islands}, month = {21--23 Apr}, publisher = {PMLR}, pdf = {http://proceedings.mlr.press/v22/peng12/peng12.pdf}, url = {https://proceedings.mlr.press/v22/peng12.html}, abstract = {Inference in probabilistic graphical models can be represented as a constrained optimization problem of a free-energy functional. Substantial research has been focused on the approximation of the constraint set, also known as the marginal polytope. This paper presents a novel inference algorithm that tightens and solves the optimization problem by intersecting the popular local polytope and the semidefinite outer bound of the marginal polytope. Using dual decomposition, our method separates the optimization problem into two subproblems: a semidefinite program (SDP), which is solved by a low-rank SDP algorithm, and a free-energy based optimization problem, which is solved by convex belief propagation. Our method has a very reasonable computational complexity and its actual running time is typically within a small factor (=10) of convex belief propagation. Tested on both synthetic data and a real-world protein side-chain packing benchmark, our method significantly outperforms tree-reweighted belief propagation in both marginal probability inference and MAP inference. Our method is competitive with the state-of-the-art in MRF inference, solving all protein tasks solved by the recently presented MPLP method, and beating MPLP on lattices with strong edge potentials.} }
Endnote
%0 Conference Paper %T Approximate Inference by Intersecting Semidefinite Bound and Local Polytope %A Jian Peng %A Tamir Hazan %A Nathan Srebro %A Jinbo Xu %B Proceedings of the Fifteenth International Conference on Artificial Intelligence and Statistics %C Proceedings of Machine Learning Research %D 2012 %E Neil D. Lawrence %E Mark Girolami %F pmlr-v22-peng12 %I PMLR %P 868--876 %U https://proceedings.mlr.press/v22/peng12.html %V 22 %X Inference in probabilistic graphical models can be represented as a constrained optimization problem of a free-energy functional. Substantial research has been focused on the approximation of the constraint set, also known as the marginal polytope. This paper presents a novel inference algorithm that tightens and solves the optimization problem by intersecting the popular local polytope and the semidefinite outer bound of the marginal polytope. Using dual decomposition, our method separates the optimization problem into two subproblems: a semidefinite program (SDP), which is solved by a low-rank SDP algorithm, and a free-energy based optimization problem, which is solved by convex belief propagation. Our method has a very reasonable computational complexity and its actual running time is typically within a small factor (=10) of convex belief propagation. Tested on both synthetic data and a real-world protein side-chain packing benchmark, our method significantly outperforms tree-reweighted belief propagation in both marginal probability inference and MAP inference. Our method is competitive with the state-of-the-art in MRF inference, solving all protein tasks solved by the recently presented MPLP method, and beating MPLP on lattices with strong edge potentials.
RIS
TY - CPAPER TI - Approximate Inference by Intersecting Semidefinite Bound and Local Polytope AU - Jian Peng AU - Tamir Hazan AU - Nathan Srebro AU - Jinbo Xu BT - Proceedings of the Fifteenth International Conference on Artificial Intelligence and Statistics DA - 2012/03/21 ED - Neil D. Lawrence ED - Mark Girolami ID - pmlr-v22-peng12 PB - PMLR DP - Proceedings of Machine Learning Research VL - 22 SP - 868 EP - 876 L1 - http://proceedings.mlr.press/v22/peng12/peng12.pdf UR - https://proceedings.mlr.press/v22/peng12.html AB - Inference in probabilistic graphical models can be represented as a constrained optimization problem of a free-energy functional. Substantial research has been focused on the approximation of the constraint set, also known as the marginal polytope. This paper presents a novel inference algorithm that tightens and solves the optimization problem by intersecting the popular local polytope and the semidefinite outer bound of the marginal polytope. Using dual decomposition, our method separates the optimization problem into two subproblems: a semidefinite program (SDP), which is solved by a low-rank SDP algorithm, and a free-energy based optimization problem, which is solved by convex belief propagation. Our method has a very reasonable computational complexity and its actual running time is typically within a small factor (=10) of convex belief propagation. Tested on both synthetic data and a real-world protein side-chain packing benchmark, our method significantly outperforms tree-reweighted belief propagation in both marginal probability inference and MAP inference. Our method is competitive with the state-of-the-art in MRF inference, solving all protein tasks solved by the recently presented MPLP method, and beating MPLP on lattices with strong edge potentials. ER -
APA
Peng, J., Hazan, T., Srebro, N. & Xu, J.. (2012). Approximate Inference by Intersecting Semidefinite Bound and Local Polytope. Proceedings of the Fifteenth International Conference on Artificial Intelligence and Statistics, in Proceedings of Machine Learning Research 22:868-876 Available from https://proceedings.mlr.press/v22/peng12.html.

Related Material