The Power of LP Relaxation for MAP Inference

Result code in IS VaVaI
<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F68407700%3A21230%2F14%3A00223600" target="_blank" >RIV/68407700:21230/14:00223600 - isvavai.cz</a>
Result on the web
<a href="http://cmp.felk.cvut.cz/pub/cmp/articles/werner/ZivWerPru-LP-MIT2014.pdf" target="_blank" >http://cmp.felk.cvut.cz/pub/cmp/articles/werner/ZivWerPru-LP-MIT2014.pdf</a>
DOI - Digital Object Identifier
—

Result language
angličtina
Original language name
The Power of LP Relaxation for MAP Inference
Original language description
Minimization of a partially separable function of many discrete variables is ubiquitous in machine learning and computer vision, in tasks like maximum a posteriori (MAP) inference in graphical models, or structured prediction. Among successful approachesto this problem is linear programming (LP) relaxation. We discuss this LP relaxation from two aspects. First, we review recent results which characterize languages (classes of functions permitted to form the objective function) for which the problem issolved by the relaxation exactly. Second, we show that solving the LP relaxation is not easier than solving any linear program, which makes a discovery of an efficient algorithm for the LP relaxation unlikely.
Czech name
—
Czech description
—

Project
Result was created during the realization of more than one project. More information in the Projects tab.
Continuities
P - Projekt vyzkumu a vyvoje financovany z verejnych zdroju (s odkazem do CEP)

Publication year
2014
Confidentiality
S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů

Similar results(10)