Marginal Consistency: Unifying Convergent Message Passing and Constraint Propagation

Kód výsledku v IS VaVaI

<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F68407700%3A21230%2F13%3A00212553" target="_blank" >RIV/68407700:21230/13:00212553 - isvavai.cz</a>

Výsledek na webu

<a href="http://cmp.felk.cvut.cz/pub/cmp/articles/werner/Werner-TR-2013-26.pdf" target="_blank" >http://cmp.felk.cvut.cz/pub/cmp/articles/werner/Werner-TR-2013-26.pdf</a>

DOI - Digital Object Identifier

—

Jazyk výsledku

angličtina

Název v původním jazyce

Marginal Consistency: Unifying Convergent Message Passing and Constraint Propagation

Popis výsledku v původním jazyce

We propose a unified framework for two classes of algorithms that have been so far studied separately: convergent message passing algorithms in graphical models (in particular, max-sum diffusion) and constraint propagation (or local consistency) algorithms in constraint networks. We show that max-sum diffusion can be naturally generalized to an algorithm defined over the abstract commutative semiring. In a wide class of commutative semirings, this algorithm converges to a fixed point and monotonically decreases an upper bound on the semiring-based partition function. This generalization reveals a deep property of constraint networks over commutative semirings: By locally changing constraint values such that the semiring-based partition function is preserved, any network can be transformed into a state when the overlapping marginals of each constraint pair coincide. We call this state marginal consistency. We further construct a hierarchy of marginal consistencies of increasingly higher

Název v anglickém jazyce

Marginal Consistency: Unifying Convergent Message Passing and Constraint Propagation

Popis výsledku anglicky

We propose a unified framework for two classes of algorithms that have been so far studied separately: convergent message passing algorithms in graphical models (in particular, max-sum diffusion) and constraint propagation (or local consistency) algorithms in constraint networks. We show that max-sum diffusion can be naturally generalized to an algorithm defined over the abstract commutative semiring. In a wide class of commutative semirings, this algorithm converges to a fixed point and monotonically decreases an upper bound on the semiring-based partition function. This generalization reveals a deep property of constraint networks over commutative semirings: By locally changing constraint values such that the semiring-based partition function is preserved, any network can be transformed into a state when the overlapping marginals of each constraint pair coincide. We call this state marginal consistency. We further construct a hierarchy of marginal consistencies of increasingly higher

Druh

O - Ostatní výsledky

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í

2013

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ů