Title :
Marginal Consistency: Upper-Bounding Partition Functions over Commutative Semirings
Author_Institution :
Dept. of Cybern., Czech Tech. Univ., Prague, Czech Republic
Abstract :
Many inference tasks in pattern recognition and artificial intelligence lead to partition functions in which addition and multiplication are abstract binary operations forming a commutative semiring. By generalizing max-sum diffusion (one of convergent message passing algorithms for approximate MAP inference in graphical models), we propose an iterative algorithm to upper bound such partition functions over commutative semirings. The iteration of the algorithm is remarkably simple: change any two factors of the partition function such that their product remains the same and their overlapping marginals become equal. In many commutative semirings, repeating this iteration for different pairs of factors converges to a fixed point when the overlapping marginals of every pair of factors coincide. We call this state marginal consistency. During that, an upper bound on the partition function monotonically decreases. This abstract algorithm unifies several existing algorithms, including max-sum diffusion and basic constraint propagation (or local consistency) algorithms in constraint programming. We further construct a hierarchy of marginal consistencies of increasingly higher levels and show than any such level can be enforced by adding identity factors of higher arity (order). Finally, we discuss instances of the framework for several semirings, including the distributive lattice and the max-sum and sum-product semirings.
Keywords :
constraint handling; inference mechanisms; iterative methods; message passing; abstract binary operations; approximate MAP inference; artificial intelligence; commutative semirings; constraint programming; distributive lattice; graphical models; identity factors; inference task; iterative algorithm; max-sum diffusion message passing algorithm generalization; pattern recognition; state marginal consistency; sum-product semirings; upper-bounding partition function; Abstracts; Commutation; Partitioning algorithms; Pattern recognition; Programming; Upper bound; Xenon; Markov random field; Partition function; commutative semiring; constraint propagation; graphical model; linear programming relaxation; local consistency; max-sum diffusion; message passing; partition function; soft constraint satisfaction;
Journal_Title :
Pattern Analysis and Machine Intelligence, IEEE Transactions on
DOI :
10.1109/TPAMI.2014.2363833