| Attributes | Values |
|---|
| rdf:type
| |
| rdfs:seeAlso
| - ftp://cmp.felk.cvut.cz/pub/cmp/articles/werner/Werner-TR-2013-26.pdf
|
| 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 levels, and show than any such level can be enforced by adding 'dummy' constraints of higher arity. Finally, we discuss in detail instances of the framework for several semirings, including or-and, max-min, max-sum, and sum-product semiring.
- 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 levels, and show than any such level can be enforced by adding 'dummy' constraints of higher arity. Finally, we discuss in detail instances of the framework for several semirings, including or-and, max-min, max-sum, and sum-product semiring. (en)
|
| Title
| - Marginal Consistency: Unifying Convergent Message Passing and Constraint Propagation
- Marginal Consistency: Unifying Convergent Message Passing and Constraint Propagation (en)
|
| skos:prefLabel
| - Marginal Consistency: Unifying Convergent Message Passing and Constraint Propagation
- Marginal Consistency: Unifying Convergent Message Passing and Constraint Propagation (en)
|
| skos:notation
| - RIV/68407700:21230/13:00212553!RIV14-MSM-21230___
|
| http://linked.open...avai/predkladatel
| |
| http://linked.open...avai/riv/aktivita
| |
| http://linked.open...avai/riv/aktivity
| - P(7E11036), P(GAP202/12/2071)
|
| http://linked.open...vai/riv/dodaniDat
| |
| http://linked.open...aciTvurceVysledku
| |
| http://linked.open.../riv/druhVysledku
| |
| http://linked.open...iv/duvernostUdaju
| |
| http://linked.open...titaPredkladatele
| |
| http://linked.open...dnocenehoVysledku
| |
| http://linked.open...ai/riv/idVysledku
| - RIV/68407700:21230/13:00212553
|
| http://linked.open...riv/jazykVysledku
| |
| http://linked.open.../riv/klicovaSlova
| - graphical model; Markov random field; linear programming relaxation; message passing; max-sum diffusion; soft constraint satisfaction; local consistency; constraint propagation; commutative semiring (en)
|
| http://linked.open.../riv/klicoveSlovo
| |
| http://linked.open...ontrolniKodProRIV
| |
| http://linked.open...in/vavai/riv/obor
| |
| http://linked.open...ichTvurcuVysledku
| |
| http://linked.open...cetTvurcuVysledku
| |
| http://linked.open...vavai/riv/projekt
| |
| http://linked.open...UplatneniVysledku
| |
| http://linked.open...iv/tvurceVysledku
| |
| http://localhost/t...ganizacniJednotka
| |
![[RDF Data]](/fct/images/sw-rdf-blue.png)
![[cxml]](/fct/images/cxml_doc.png)
![[csv]](/fct/images/csv_doc.png)
![[text]](/fct/images/ntriples_doc.png)
![[turtle]](/fct/images/n3turtle_doc.png)
![[ld+json]](/fct/images/jsonld_doc.png)
![[rdf+json]](/fct/images/json_doc.png)
![[rdf+xml]](/fct/images/xml_doc.png)
![[atom+xml]](/fct/images/atom_doc.png)
![[html]](/fct/images/html_doc.png)