Partial optimality of dual decomposition for map inference in pairwise MrFs

Alexander Bauer; Shinichi Nakajima; Nico Görnitz; Klaus Robert Müller

Partial optimality of dual decomposition for map inference in pairwise MrFs

Alexander Bauer, Shinichi Nakajima, Nico Görnitz, Klaus Robert Müller

Research output: Contribution to conference › Paper › peer-review

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.

Original language	English
Publication status	Published - 2020
Event	22nd International Conference on Artificial Intelligence and Statistics, AISTATS 2019 - Naha, Japan Duration: 2019 Apr 16 → 2019 Apr 18

Conference

Conference	22nd International Conference on Artificial Intelligence and Statistics, AISTATS 2019
Country/Territory	Japan
City	Naha
Period	19/4/16 → 19/4/18

Bibliographical note

Funding Information:
This research was supported by the Federal Ministry of Education and Research under the Berlin Big Data Center 2 project (FKz 01IS18025A), and by the World Class University Program through the National Research Foundation of Korea funded by the Ministry of Education, Science, and Technology, under Grant R31-10008.

Publisher Copyright:
© 2019 by the author(s).

ASJC Scopus subject areas

Artificial Intelligence
Statistics and Probability

Cite this

@conference{90958a37e5ee42fe9be34361d80bf86f,

title = "Partial optimality of dual decomposition for map inference in pairwise MrFs",

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.",

author = "Alexander Bauer and Shinichi Nakajima and Nico G{\"o}rnitz and M{\"u}ller, {Klaus Robert}",

note = "Funding Information: This research was supported by the Federal Ministry of Education and Research under the Berlin Big Data Center 2 project (FKz 01IS18025A), and by the World Class University Program through the National Research Foundation of Korea funded by the Ministry of Education, Science, and Technology, under Grant R31-10008. Publisher Copyright: {\textcopyright} 2019 by the author(s).; 22nd International Conference on Artificial Intelligence and Statistics, AISTATS 2019 ; Conference date: 16-04-2019 Through 18-04-2019",

year = "2020",

language = "English",

}

TY - CONF

T1 - Partial optimality of dual decomposition for map inference in pairwise MrFs

AU - Bauer, Alexander

AU - Nakajima, Shinichi

AU - Görnitz, Nico

AU - Müller, Klaus Robert

N1 - Funding Information: This research was supported by the Federal Ministry of Education and Research under the Berlin Big Data Center 2 project (FKz 01IS18025A), and by the World Class University Program through the National Research Foundation of Korea funded by the Ministry of Education, Science, and Technology, under Grant R31-10008. Publisher Copyright: © 2019 by the author(s).

PY - 2020

Y1 - 2020

N2 - 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.

AB - 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.

UR - http://www.scopus.com/inward/record.url?scp=85085060088&partnerID=8YFLogxK

M3 - Paper

AN - SCOPUS:85085060088

T2 - 22nd International Conference on Artificial Intelligence and Statistics, AISTATS 2019

Y2 - 16 April 2019 through 18 April 2019

ER -

Partial optimality of dual decomposition for map inference in pairwise MrFs

Abstract

Conference

Bibliographical note

ASJC Scopus subject areas

Other files and links

Fingerprint

Cite this