Variational Algorithms for Marginal MAP
This addresses a critical bottleneck in probabilistic models with hidden variables, offering improved inference methods for applications in machine learning and AI, though it is an incremental advancement over prior variational techniques.
The paper tackles the NP-hard marginal MAP inference problem by deriving a dual representation that integrates marginalization and maximization into a joint variational optimization, enabling extension of variational algorithms to marginal MAP. Empirically, their algorithms, including mixed-product message passing and proximal point methods, significantly outperform existing approaches like local search methods.
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 variables 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 marginalization problems. We derive a general dual representation for marginal MAP that naturally integrates the marginalization and maximization operations into a joint variational optimization problem, 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 updates. We also derive a class of convergent algorithms based on proximal point methods, including 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 locally 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.