What Is Decreased by the Max-sum Arc Consistency Algorithm?

Kód výsledku v IS VaVaI

<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F68407700%3A21230%2F07%3A03134582" target="_blank" >RIV/68407700:21230/07:03134582 - isvavai.cz</a>

Výsledek na webu

—

DOI - Digital Object Identifier

—

Jazyk výsledku

angličtina

Název v původním jazyce

What Is Decreased by the Max-sum Arc Consistency Algorithm?

Popis výsledku v původním jazyce

Inference tasks in Markov random fields (MRFs) are closely related to the constraint satisfaction problem (CSP) and its soft generalizations. In particular, MAP inference in MRF is equivalent to the weighted (max-sum) CSP. A well-known tool to tackle CSPs are arc consistency algorithms, a.k.a. relaxation labeling. A promising approach to MAP inference in MRFs is linear programming relaxation solved by sequential tree-reweighted message passing (TRW-S). There is a not widely known algorithm equivalent toTRW-S, max-sum diffusion, which is slower but very simple. We give two theoretical results. First, we show that arc consistency algorithms and max-sum diffusion become the same thing if formulated in an abstract-algebraic way. Thus, we argue that max-sum arc consistency algorithm or max-sum relaxation labeling is a more suitable name for max-sum diffusion. Second, we give a criterion that strictly decreases during these algorithms.

Název v anglickém jazyce

What Is Decreased by the Max-sum Arc Consistency Algorithm?

Popis výsledku anglicky

Inference tasks in Markov random fields (MRFs) are closely related to the constraint satisfaction problem (CSP) and its soft generalizations. In particular, MAP inference in MRF is equivalent to the weighted (max-sum) CSP. A well-known tool to tackle CSPs are arc consistency algorithms, a.k.a. relaxation labeling. A promising approach to MAP inference in MRFs is linear programming relaxation solved by sequential tree-reweighted message passing (TRW-S). There is a not widely known algorithm equivalent toTRW-S, max-sum diffusion, which is slower but very simple. We give two theoretical results. First, we show that arc consistency algorithms and max-sum diffusion become the same thing if formulated in an abstract-algebraic way. Thus, we argue that max-sum arc consistency algorithm or max-sum relaxation labeling is a more suitable name for max-sum diffusion. Second, we give a criterion that strictly decreases during these algorithms.

Druh

D - Stať ve sborníku

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í

2007

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 statě ve sborníku

ICML 2007: Proceedings of the 24th international conference on Machine learning

ISBN

978-1-59593-793-3

ISSN

1053-587X

e-ISSN

—

Počet stran výsledku

8

Strana od-do

—

Název nakladatele

ACM

Místo vydání

New York

Místo konání akce

Corvallis

Datum konání akce

20. 6. 2007

Typ akce podle státní příslušnosti

WRD - Celosvětová akce

Kód UT WoS článku

—