How to Compute Primal Solution from Dual One in MAP Inference in MRF?

Kód výsledku v IS VaVaI

<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F68407700%3A21230%2F11%3A00187153" target="_blank" >RIV/68407700:21230/11:00187153 - isvavai.cz</a>

Výsledek na webu

—

DOI - Digital Object Identifier

—

Jazyk výsledku

angličtina

Název v původním jazyce

How to Compute Primal Solution from Dual One in MAP Inference in MRF?

Popis výsledku v původním jazyce

In LP relaxation of MAP inference in Markov random fields (MRF), the primal LP maximizes the MAP objective over relaxed labelings (pseudomarginals) and the dual LP minimizes an upper bound on the true MAP solution by reparameterizations. Having solved the dual~LP, we have no direct access to the corresponding primal solution. We propose a simple way to compute an optimal primal solution from an optimal dual solution. Precisely, we given an algorithm that either shows that the upper bound for a given problem can be further decreased by reparameterizations (i.e., it is not dual-optimal) or computes the corresponding optimal relaxed labeling. This is done by first removing inactive dual constraints and then solving the resulting feasibility problem by a very simple message-passing algorithm, sum-product diffusion.

Název v anglickém jazyce

How to Compute Primal Solution from Dual One in MAP Inference in MRF?

Popis výsledku anglicky

In LP relaxation of MAP inference in Markov random fields (MRF), the primal LP maximizes the MAP objective over relaxed labelings (pseudomarginals) and the dual LP minimizes an upper bound on the true MAP solution by reparameterizations. Having solved the dual~LP, we have no direct access to the corresponding primal solution. We propose a simple way to compute an optimal primal solution from an optimal dual solution. Precisely, we given an algorithm that either shows that the upper bound for a given problem can be further decreased by reparameterizations (i.e., it is not dual-optimal) or computes the corresponding optimal relaxed labeling. This is done by first removing inactive dual constraints and then solving the resulting feasibility problem by a very simple message-passing algorithm, sum-product diffusion.

Druh

J_x - Nezařazeno - Článek v odborném periodiku (Jimp, Jsc a Jost)

CEP obor

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

OECD FORD obor

—

Projekt

—

Návaznosti

Z - Vyzkumny zamer (s odkazem do CEZ)

Rok uplatnění

2011

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 periodika

Control Systems and Computers

ISSN

0130-5395

e-ISSN

—

Svazek periodika

2011

Číslo periodika v rámci svazku

2

Stát vydavatele periodika

UA - Ukrajina

Počet stran výsledku

8

Strana od-do

86-93

Kód UT WoS článku

—

EID výsledku v databázi Scopus

—