The Power of LP Relaxation for MAP Inference

Kód výsledku v 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>

Výsledek na webu

<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

—

Jazyk výsledku

angličtina

Název v původním jazyce

The Power of LP Relaxation for MAP Inference

Popis výsledku v původním jazyce

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.

Název v anglickém jazyce

The Power of LP Relaxation for MAP Inference

Popis výsledku anglicky

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.

Druh

C - Kapitola v odborné knize

CEP obor

JD - Využití počítačů, robotika a její aplikace

OECD FORD obor

—

Projekt

Výsledek vznikl pri realizaci vícero projektů. Více informací v záložce Projekty.

Návaznosti

P - Projekt vyzkumu a vyvoje financovany z verejnych zdroju (s odkazem do CEP)

Rok uplatnění

2014

Kód důvěrnosti údajů

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

Název knihy nebo sborníku

Advanced Structured Prediction

ISBN

978-0-262-02837-0

Počet stran výsledku

24

Strana od-do

19-42

Počet stran knihy

456

Název nakladatele

MIT PRESS

Místo vydání

Boston

Kód UT WoS kapitoly

—