Tighter Relaxations for MAP-MRF Inference: A Local Primal-Dual Gap based Separation Algorithm

Dhruv Batra, Sebastian Nowozin, Pushmeet Kohli
Proceedings of the Fourteenth International Conference on Artificial Intelligence and Statistics, PMLR 15:146-154, 2011.

Abstract

We propose an efficient and adaptive method for MAP-MRF inference that provides increasingly tighter upper and lower bounds on the optimal objective. Similar to Sontag et al. (2008b), our method starts by solving the first-order LOCAL(G) linear programming relaxation. This is followed by an adaptive tightening of the relaxation where we incrementally add higher-order interactions to enforce proper marginalization over groups of variables. Computing the best interaction to add is an NP-hard problem. We show good solutions to this problem can be readily obtained from “local primal-dual gaps” given the current primal solution and a dual reparameterization vector. This is not only extremely efficient, but in contrast to previous approaches, also allows us to search over prohibitively large sets of candidate interactions to add. We demonstrate the superiority of our approach on MAP-MRF inference problems encountered in computer vision.

Cite this Paper

BibTeX
@InProceedings{pmlr-v15-batra11a, title = {Tighter Relaxations for MAP-MRF Inference: A Local Primal-Dual Gap based Separation Algorithm}, author = {Batra, Dhruv and Nowozin, Sebastian and Kohli, Pushmeet}, booktitle = {Proceedings of the Fourteenth International Conference on Artificial Intelligence and Statistics}, pages = {146--154}, year = {2011}, editor = {Gordon, Geoffrey and Dunson, David and Dudík, Miroslav}, volume = {15}, series = {Proceedings of Machine Learning Research}, address = {Fort Lauderdale, FL, USA}, month = {11--13 Apr}, publisher = {PMLR}, pdf = {http://proceedings.mlr.press/v15/batra11a/batra11a.pdf}, url = {https://proceedings.mlr.press/v15/batra11a.html}, abstract = {We propose an efficient and adaptive method for MAP-MRF inference that provides increasingly tighter upper and lower bounds on the optimal objective. Similar to Sontag et al. (2008b), our method starts by solving the first-order LOCAL(G) linear programming relaxation. This is followed by an adaptive tightening of the relaxation where we incrementally add higher-order interactions to enforce proper marginalization over groups of variables. Computing the best interaction to add is an NP-hard problem. We show good solutions to this problem can be readily obtained from “local primal-dual gaps” given the current primal solution and a dual reparameterization vector. This is not only extremely efficient, but in contrast to previous approaches, also allows us to search over prohibitively large sets of candidate interactions to add. We demonstrate the superiority of our approach on MAP-MRF inference problems encountered in computer vision.} }
Endnote
%0 Conference Paper %T Tighter Relaxations for MAP-MRF Inference: A Local Primal-Dual Gap based Separation Algorithm %A Dhruv Batra %A Sebastian Nowozin %A Pushmeet Kohli %B Proceedings of the Fourteenth International Conference on Artificial Intelligence and Statistics %C Proceedings of Machine Learning Research %D 2011 %E Geoffrey Gordon %E David Dunson %E Miroslav Dudík %F pmlr-v15-batra11a %I PMLR %P 146--154 %U https://proceedings.mlr.press/v15/batra11a.html %V 15 %X We propose an efficient and adaptive method for MAP-MRF inference that provides increasingly tighter upper and lower bounds on the optimal objective. Similar to Sontag et al. (2008b), our method starts by solving the first-order LOCAL(G) linear programming relaxation. This is followed by an adaptive tightening of the relaxation where we incrementally add higher-order interactions to enforce proper marginalization over groups of variables. Computing the best interaction to add is an NP-hard problem. We show good solutions to this problem can be readily obtained from “local primal-dual gaps” given the current primal solution and a dual reparameterization vector. This is not only extremely efficient, but in contrast to previous approaches, also allows us to search over prohibitively large sets of candidate interactions to add. We demonstrate the superiority of our approach on MAP-MRF inference problems encountered in computer vision.
RIS
TY - CPAPER TI - Tighter Relaxations for MAP-MRF Inference: A Local Primal-Dual Gap based Separation Algorithm AU - Dhruv Batra AU - Sebastian Nowozin AU - Pushmeet Kohli BT - Proceedings of the Fourteenth International Conference on Artificial Intelligence and Statistics DA - 2011/06/14 ED - Geoffrey Gordon ED - David Dunson ED - Miroslav Dudík ID - pmlr-v15-batra11a PB - PMLR DP - Proceedings of Machine Learning Research VL - 15 SP - 146 EP - 154 L1 - http://proceedings.mlr.press/v15/batra11a/batra11a.pdf UR - https://proceedings.mlr.press/v15/batra11a.html AB - We propose an efficient and adaptive method for MAP-MRF inference that provides increasingly tighter upper and lower bounds on the optimal objective. Similar to Sontag et al. (2008b), our method starts by solving the first-order LOCAL(G) linear programming relaxation. This is followed by an adaptive tightening of the relaxation where we incrementally add higher-order interactions to enforce proper marginalization over groups of variables. Computing the best interaction to add is an NP-hard problem. We show good solutions to this problem can be readily obtained from “local primal-dual gaps” given the current primal solution and a dual reparameterization vector. This is not only extremely efficient, but in contrast to previous approaches, also allows us to search over prohibitively large sets of candidate interactions to add. We demonstrate the superiority of our approach on MAP-MRF inference problems encountered in computer vision. ER -
APA
Batra, D., Nowozin, S. & Kohli, P.. (2011). Tighter Relaxations for MAP-MRF Inference: A Local Primal-Dual Gap based Separation Algorithm. Proceedings of the Fourteenth International Conference on Artificial Intelligence and Statistics, in Proceedings of Machine Learning Research 15:146-154 Available from https://proceedings.mlr.press/v15/batra11a.html.

Related Material