Tighter Linear Program Relaxations for High Order Graphical Models

Elad Mezuman, Daniel Tarlow, Amir Globerson, Yair Weiss
Proceedings of the 29th Conference on Uncertainty in Artificial Intelligence, PMLR R11:530-539, 2013.

Abstract

Graphical models with High Order Potentials (HOPs) have received considerable interest in recent years. While there are a variety of approaches to inference in these models, nearly all of them amount to solving a linear program (LP) relaxation with unary consistency constraints between the HOP and the individual variables. In many cases, the resulting relaxations are loose, and in these cases the results of inference can be poor. It is thus desirable to look for more accurate ways of performing inference. In this work, we study the LP relaxations that result from enforcing additional consistency constraints between the HOP and the rest of the model. We address theoretical questions about the strength of the resulting relaxations compared to the relaxations that arise in standard approaches, and we develop practical and efficient message passing algorithms for optimizing the LPs. Empirically, we show that the LPs with additional consistency constraints lead to more accurate inference on some challenging problems that include a combination of low order and high order terms.

Cite this Paper

BibTeX
@InProceedings{pmlr-vR11-mezuman13a, title = {Tighter Linear Program Relaxations for High Order Graphical Models}, author = {Mezuman, Elad and Tarlow, Daniel and Globerson, Amir and Weiss, Yair}, booktitle = {Proceedings of the 29th Conference on Uncertainty in Artificial Intelligence}, pages = {530--539}, year = {2013}, editor = {Nicholson, Ann and Smyth, Padhraic}, volume = {R11}, series = {Proceedings of Machine Learning Research}, month = {12--14 Jul}, publisher = {PMLR}, pdf = {https://raw.githubusercontent.com/mlresearch/r11/main/assets/mezuman13a/mezuman13a.pdf}, url = {https://proceedings.mlr.press/r11/mezuman13a.html}, abstract = {Graphical models with High Order Potentials (HOPs) have received considerable interest in recent years. While there are a variety of approaches to inference in these models, nearly all of them amount to solving a linear program (LP) relaxation with unary consistency constraints between the HOP and the individual variables. In many cases, the resulting relaxations are loose, and in these cases the results of inference can be poor. It is thus desirable to look for more accurate ways of performing inference. In this work, we study the LP relaxations that result from enforcing additional consistency constraints between the HOP and the rest of the model. We address theoretical questions about the strength of the resulting relaxations compared to the relaxations that arise in standard approaches, and we develop practical and efficient message passing algorithms for optimizing the LPs. Empirically, we show that the LPs with additional consistency constraints lead to more accurate inference on some challenging problems that include a combination of low order and high order terms.}, note = {Reissued by PMLR on 04 October 2026.} }
Endnote
%0 Conference Paper %T Tighter Linear Program Relaxations for High Order Graphical Models %A Elad Mezuman %A Daniel Tarlow %A Amir Globerson %A Yair Weiss %B Proceedings of the 29th Conference on Uncertainty in Artificial Intelligence %C Proceedings of Machine Learning Research %D 2013 %E Ann Nicholson %E Padhraic Smyth %F pmlr-vR11-mezuman13a %I PMLR %P 530--539 %U https://proceedings.mlr.press/r11/mezuman13a.html %V R11 %X Graphical models with High Order Potentials (HOPs) have received considerable interest in recent years. While there are a variety of approaches to inference in these models, nearly all of them amount to solving a linear program (LP) relaxation with unary consistency constraints between the HOP and the individual variables. In many cases, the resulting relaxations are loose, and in these cases the results of inference can be poor. It is thus desirable to look for more accurate ways of performing inference. In this work, we study the LP relaxations that result from enforcing additional consistency constraints between the HOP and the rest of the model. We address theoretical questions about the strength of the resulting relaxations compared to the relaxations that arise in standard approaches, and we develop practical and efficient message passing algorithms for optimizing the LPs. Empirically, we show that the LPs with additional consistency constraints lead to more accurate inference on some challenging problems that include a combination of low order and high order terms. %Z Reissued by PMLR on 04 October 2026.
APA
Mezuman, E., Tarlow, D., Globerson, A. & Weiss, Y.. (2013). Tighter Linear Program Relaxations for High Order Graphical Models. Proceedings of the 29th Conference on Uncertainty in Artificial Intelligence, in Proceedings of Machine Learning Research R11:530-539 Available from https://proceedings.mlr.press/r11/mezuman13a.html. Reissued by PMLR on 04 October 2026.

Related Material