IS = { zkontrolovano 24 Jan 2014 },
  UPDATE  = { 2013-10-07 },
   author =	 {Werner, Tom{\'a}{\v s}},
   title =	 {Marginal Consistency: Unifying Convergent Message Passing
                   and Constraint Propagation},
   institution =	 {Center for Machine Perception, K13133 FEE Czech Technical
   address =	 {Prague, Czech Republic},
   year =	 {2013},
   month =	 {October},
   type =	 {Research Report},
   number =	 {CTU--CMP--2013--26},
   issn =	 {1213-2365},
   pages =	 {12},
   figures =	 {1},
   authorship =	 {100},
   psurl =	 {[Werner-TR-2013-26.pdf]},
   project =	 {GACR P202/12/2071, FP7-ICT-270138 DARWIN},
   annote =	 {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.},
   keywords =	 {graphical model, Markov random field, linear programming
                   relaxation, message passing, max-sum diffusion, soft
                   constraint satisfaction, local consistency, constraint
                   propagation, commutative semiring},