Decomposition Bounds for Marginal MAP
Marginal MAP inference involves making MAP predictions in systems defined with latent variables or missing information. It is significantly more difficult than pure marginalization and MAP tasks, for which a large class of efficient and convergent variational algorithms, such as dual decomposition, exist. In this work, we generalize dual decomposition to a generic power sum inference task, which includes marginal MAP, along with pure marginalization and MAP, as special cases. Our method is based on a block coordinate descent algorithm on a new convex decomposition bound, that is guaranteed to converge monotonically, and can be parallelized efficiently. We demonstrate our approach on marginal MAP queries defined on real-world problems from the UAI approximate inference challenge, showing that our framework is faster and more reliable than previous methods.
The authors present a dual decomposition method for marginal MAP problems that makes use of Holder's inequality.This derivation stands apart from previous work in that it requires a fixed elimination ordering for the bounds to hold - the order of operations is not commutative.Still, the authors show that the resulting optimization problem has a similar form to known results in the literature on approximate variational inference.The paper is well-written and easy to read.General comments:-pg. 2, "the resulting optimization is only guaranteed to be a bound at convergence..." I'm not sure that this is true.I know for a fact it isn't true for TRW max-product despite some published statements to the contrary (though it does require a slightly different reparameterization vantage point).You should take another look at "Convergent message passing algorithms - a unifying view" by Meltzer et al.I think that the argument for the max-product case can be applied to the sum-product case as well.The authors made several comments on this point (which I admittedly didn't fully understand).To clarify, I was thinking of techniques based on reparameterization and pushing max through a product to get an inequality.In these situations (much like yours), you have a bound for any choice of messages even when the consistency conditions are not satisfied.-The reparameterization approach described here is similar to "Message-passing algorithms: reparameterizations and splittings" by Ruozzi et al.You should probably cite it. Typos:-pg. 2, extra space in "Section2" -throughout:"message passing algorithm" -> "message-passing algorithm" -throughout:I don't think, grammatically, that citations should be used as nouns."[8] showed" -> "Hazan et al. [8] showed"