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.
Thus, most algorithms do not satisfy all the desirable properties listed in the introduction. For example, many works have developed convergent message-passing algorithms for convex free energies [e.g.,][] hazan08, hazan10 . However, by optimizing the dual they do not provide a bound until convergence, and the representation and constraints on the counting numbers do not facilitate optimizing the bound over these parameters. To optimize counting numbers, @cite_14 adopt a more restrictive free energy form requiring positive counting numbers on the entropies; but this cannot represent marginal MAP, whose free energy involves conditional entropies (equivalent to the difference between two entropy terms).
@cite_14
1792445207
We consider computation of the permanent of a positive (N  N) non-negative matrix, P = (Pji|i, j = 1, ..., N), or equivalently the problem of weighted counting of the perfect matchings over the complete bipartite graph KN, N. The problem is known to be of likely exponential complexity. Stated as the partition function Z of a graphical model, the problem allows for exact loop calculus representation (Chertkov M and Chernyak V 2006 Phys. Rev. E 72 065102) in terms of an interior minimum of the Bethe free energy functional over non-integer doubly stochastic matrix of marginal beliefs,  = (ji|i, j = 1, ..., N), also correspondent to a fixed point of the iterative message-passing algorithm of the belief propagation (BP) type. Our main result is an explicit expression of the exact partition function (permanent) in terms of the matrix of BP marginals, , as Z = Perm(P) = ZBP Perm(ji(1  ji)) i, j(1  ji), where ZBP is the BP expression for the permanent stated explicitly in terms of . We give two derivations of the formula, a direct one based on the Bethe free energy and an alternative one combining the Ihara graph- function and the loop calculus approaches. Assuming that the matrix  of the BP marginals is calculated, we provide two lower bounds and one upper bound to estimate the multiplicative term. Two complementary lower bounds are based on the Gurvitsvan der Waerden theorem and on a relation between the modified permanent and determinant, respectively.