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

Result code in 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>

Result on the web

—

DOI - Digital Object Identifier

—

Result language

angličtina

Original language name

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

Original language description

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.

Czech name

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

Czech description

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.

Type

D - Article in proceedings

CEP classification

JD - Use of computers, robotics and its application

OECD FORD branch

—

Project

—

Continuities

Z - Vyzkumny zamer (s odkazem do CEZ)

Publication year

2007

Confidentiality

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

Article name in the collection

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

ISBN

978-1-59593-793-3

ISSN

1053-587X

e-ISSN

—

Number of pages

8

Pages from-to

—

Publisher name

ACM

Place of publication

New York

Event location

Corvallis

Event date

Jun 20, 2007

Type of event by nationality

WRD - Celosvětová akce

UT code for WoS article

—