Marginal Consistency: Unifying Convergent Message Passing and Constraint Propagation

Result code in 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>
Result on the web
<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
—

Result language
angličtina
Original language name
Marginal Consistency: Unifying Convergent Message Passing and Constraint Propagation
Original language description
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
Czech name
—
Czech description
—

Project
Result was created during the realization of more than one project. More information in the Projects tab.
Continuities
P - Projekt vyzkumu a vyvoje financovany z verejnych zdroju (s odkazem do CEP)

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

Similar results(10)