Exact MAP-inference by confining combinatorial search with LP relaxation
Haller, Stefan
Swoboda, Paul
Savchynskyy, Bogdan
We consider the MAP-inference problem for graphical models,which is a valued constraint satisfaction problem defined onreal numbers with a natural summation operation. We proposea family of relaxations (different from the famous Sherali-Adams hierarchy), which naturally define lower bounds for itsoptimum. This family always contains a tight relaxation andwe give an algorithm able to find it and therefore, solve theinitial non-relaxed NP-hard problem.The relaxations we consider decompose the original probleminto two non-overlapping parts: an easy LP-tight part and adifficult one. For the latter part a combinatorial solver must beused. As we show in our experiments, in a number of applica-tions the second, difficult part constitutes only a small fractionof the whole problem. This property allows to significantlyreduce the computational time of the combinatorial solver andtherefore solve problems which were out of reach before.
AAAI
2018
info:eu-repo/semantics/conferenceObject
doc-type:conferenceObject
text
https://research-explorer.app.ist.ac.at/record/5978
Haller S, Swoboda P, Savchynskyy B. Exact MAP-inference by confining combinatorial search with LP relaxation. In: <i>Proceedings of the 32st AAAI Conference on Artificial Intelligence</i>. AAAI; 2018:6581-6588.
eng
info:eu-repo/semantics/closedAccess