Variational algorithms for marginal MAP

The marginal maximum a posteriori probability (MAP) estimation problem, which calculates the mode of the marginal posterior distribution of a subset of variables with the remaining variables marginalized, is an important inference problem in many models, such as those with hidden vari-ables or uncertain parameters. Unfortunately, marginal MAP can be NP-hard even on trees, and has attracted less attention in the literature compared to the joint MAP (maximization) and marginal-ization problems. We derive a general dual representation for marginal MAP that naturally inte-grates the marginalization and maximization operations into a joint variational optimization prob-lem, making it possible to easily extend most or all variational-based algorithms to marginal MAP. In particular, we derive a set of “mixed-product ” message passing algorithms for marginal MAP, whose form is a hybrid of max-product, sum-product and a novel “argmax-product ” message up-dates. We also derive a class of convergent algorithms based on proximal point methods, includ-ing one that transforms the marginal MAP problem into a sequence of standard marginalization problems. Theoretically, we provide guarantees under which our algorithms give globally or lo-cally optimal solutions, and provide novel upper bounds on the optimal objectives. Empirically, we demonstrate that our algorithms significantly outperform the existing approaches, including a state-of-the-art algorithm based on local search methods