Decomposition Bounds for Marginal MAP
This work addresses a specific bottleneck in probabilistic inference for researchers and practitioners, offering incremental improvements over existing methods.
The paper tackles the challenging problem of marginal MAP inference by generalizing dual decomposition to a generic power sum inference task, resulting in a faster and more reliable framework that demonstrated improved performance on real-world UAI challenge problems.
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.