Abstract

Max-product (max-sum) message passing ha algorithms are widely used for MAP inference as in MRFs. It has many variants sharing MR a common flavor of passing “messages” over some graph-object. Recent advances Re revealed that its convergent versions (such th as MPLP, MSD, TRW-S) can be viewed as co performing block coordinate descent (BCD) 20 in a dual objective. That is, each BCD step op achieves dual-optimal w.r.t. a block of dual (G variables (messages), thereby decreases the (S dual objective monotonically. However, most (W existing algorithms are limited to updating Gi blocks selected in rather restricted ways. In al this paper, we show a “unified” message st passing algorithm that: (a) subsumes MPLP, w. MSD, and TRW-S as special cases when no applied to their respective choices of dual la objective and blocks, and (b) is able to co perform BCD under much more flexible (t choices of blocks (including very large blocks) sp as well as the dual objective itself (that arise ap from an arbitrary dual decomposition).