Variational Algorithms for Marginal MAP
This work addresses a challenging inference problem for researchers in probabilistic graphical models, offering incremental improvements through new algorithms and theoretical bounds.
The paper tackles the difficult problem of marginal MAP inference in graphical models by developing a general variational framework and deriving message-passing algorithms, demonstrating experimentally that these algorithms outperform related approaches.
Marginal MAP problems are notoriously difficult tasks for graphical models. We derive a general variational framework for solving marginal MAP problems, in which we apply analogues of the Bethe, tree-reweighted, and mean field approximations. We then derive a "mixed" message passing algorithm and a convergent alternative using CCCP to solve the BP-type approximations. Theoretically, we give conditions under which the decoded solution is a global or local optimum, and obtain novel upper bounds on solutions. Experimentally we demonstrate that our algorithms outperform related approaches. We also show that EM and variational EM comprise a special case of our framework.