Partial Optimality of Dual Decomposition for MAP Inference in Pairwise MRFs

Alexander Bauer, Shinichi Nakajima, Nico Goernitz, Klaus-Robert Müller
Proceedings of the Twenty-Second International Conference on Artificial Intelligence and Statistics, PMLR 89:1696-1703, 2019.

Abstract

Markov random fields (MRFs) are a powerful tool for modelling statistical dependencies for a set of random variables using a graphical representation. An important computational problem related to MRFs, called maximum a posteriori (MAP) inference, is finding a joint variable assignment with the maximal probability. It is well known that the two popular optimisation techniques for this task, linear programming (LP) relaxation and dual decomposition (DD), have a strong connection both providing an optimal solution to the MAP problem when a corresponding LP relaxation is tight. However, less is known about their relationship in the opposite and more realistic case. In this paper, we explain how the fully integral assignments obtained via DD partially agree with the optimal fractional assignments via LP relaxation when the latter is not tight. In particular, for binary pairwise MRFs the corresponding result suggests that both methods share the partial optimality property of their solutions.

Cite this Paper

BibTeX
@InProceedings{pmlr-v89-bauer19b, title = {Partial Optimality of Dual Decomposition for MAP Inference in Pairwise MRFs}, author = {Bauer, Alexander and Nakajima, Shinichi and Goernitz, Nico and M\"{u}ller, Klaus-Robert}, booktitle = {Proceedings of the Twenty-Second International Conference on Artificial Intelligence and Statistics}, pages = {1696--1703}, year = {2019}, editor = {Chaudhuri, Kamalika and Sugiyama, Masashi}, volume = {89}, series = {Proceedings of Machine Learning Research}, month = {16--18 Apr}, publisher = {PMLR}, pdf = {http://proceedings.mlr.press/v89/bauer19b/bauer19b.pdf}, url = {https://proceedings.mlr.press/v89/bauer19b.html}, abstract = {Markov random fields (MRFs) are a powerful tool for modelling statistical dependencies for a set of random variables using a graphical representation. An important computational problem related to MRFs, called maximum a posteriori (MAP) inference, is finding a joint variable assignment with the maximal probability. It is well known that the two popular optimisation techniques for this task, linear programming (LP) relaxation and dual decomposition (DD), have a strong connection both providing an optimal solution to the MAP problem when a corresponding LP relaxation is tight. However, less is known about their relationship in the opposite and more realistic case. In this paper, we explain how the fully integral assignments obtained via DD partially agree with the optimal fractional assignments via LP relaxation when the latter is not tight. In particular, for binary pairwise MRFs the corresponding result suggests that both methods share the partial optimality property of their solutions.} }
Endnote
%0 Conference Paper %T Partial Optimality of Dual Decomposition for MAP Inference in Pairwise MRFs %A Alexander Bauer %A Shinichi Nakajima %A Nico Goernitz %A Klaus-Robert Müller %B Proceedings of the Twenty-Second International Conference on Artificial Intelligence and Statistics %C Proceedings of Machine Learning Research %D 2019 %E Kamalika Chaudhuri %E Masashi Sugiyama %F pmlr-v89-bauer19b %I PMLR %P 1696--1703 %U https://proceedings.mlr.press/v89/bauer19b.html %V 89 %X Markov random fields (MRFs) are a powerful tool for modelling statistical dependencies for a set of random variables using a graphical representation. An important computational problem related to MRFs, called maximum a posteriori (MAP) inference, is finding a joint variable assignment with the maximal probability. It is well known that the two popular optimisation techniques for this task, linear programming (LP) relaxation and dual decomposition (DD), have a strong connection both providing an optimal solution to the MAP problem when a corresponding LP relaxation is tight. However, less is known about their relationship in the opposite and more realistic case. In this paper, we explain how the fully integral assignments obtained via DD partially agree with the optimal fractional assignments via LP relaxation when the latter is not tight. In particular, for binary pairwise MRFs the corresponding result suggests that both methods share the partial optimality property of their solutions.
APA
Bauer, A., Nakajima, S., Goernitz, N. & Müller, K.. (2019). Partial Optimality of Dual Decomposition for MAP Inference in Pairwise MRFs. Proceedings of the Twenty-Second International Conference on Artificial Intelligence and Statistics, in Proceedings of Machine Learning Research 89:1696-1703 Available from https://proceedings.mlr.press/v89/bauer19b.html.

Related Material