Variational algorithms for marginal MAP.

Qiang Liu, Alexander T. IhlerJMLR 2013 · OpenReview

TL;DR

This paper introduces a novel variational framework for solving the challenging "marginal MAP" problem, which aims to find the most probable configuration of a subset of variables while marginalizing out others. They achieve this by deriving a unified dual representation and developing "mixed-product" message passing algorithms that efficiently integrate marginalization and maximization steps, outperforming existing methods.

What Problem Does This Paper Address?

Many real-world problems involve inferring the most likely state of a system, often represented by graphical models. While finding the most probable joint configuration (joint MAP) or summing probabilities (marginalization) are well-studied, the "marginal MAP" problem is significantly harder. This problem arises when we're interested in the most likely configuration of a subset of variables (e.g., observable parameters) while others (e.g., hidden variables or uncertain parameters) are marginalized out. This is crucial in scenarios where some variables are of secondary interest or are unobserved. The difficulty stems from the fact that marginal MAP is NP-hard even on simple tree structures, and the standard max and sum operations don't commute, making existing algorithms struggle.

Methods

The authors propose a general variational framework by deriving a novel dual representation for the marginal MAP problem. This representation unifies marginalization and maximization into a single optimization problem, allowing existing variational algorithms to be extended.

Key algorithmic contributions include:

  • "Mixed-Product" Message Passing: A novel message passing algorithm that combines standard sum-product and max-product updates with a new "argmax-product" update. This update synchronizes the marginalization and maximization steps, allowing for more efficient parallel computation.
  • Convergent Proximal Point Algorithms: A class of algorithms based on proximal point methods that transform the marginal MAP problem into a sequence of standard marginalization (sum-inference) tasks, providing theoretical convergence guarantees.
  • TRW and Bethe Approximations: They adapt existing approximation techniques like Tree-Reweighted (TRW) and Bethe free energies to the marginal MAP setting, providing convex upper bounds and efficient optimization strategies.

Datasets

Not discussed in the paper. The experiments are conducted on simulated models (hidden Markov chains, latent tree models, Ising grids) and diagnostic Bayesian networks from the UAI08 inference challenge.

Key Insights and Ideas

  • Unified Dual Representation: The core insight is a dual representation that elegantly integrates marginalization and maximization, providing a unified framework for marginal MAP. This is a significant theoretical contribution.
  • "Argmax-Product" for Synchronization: The introduction of the "argmax-product" message update is crucial for synchronizing the sum and max operations, enabling efficient parallel processing and leading to stronger optimality guarantees.
  • Marginal MAP vs. Joint MAP: The paper highlights that using joint MAP when marginal MAP is appropriate can lead to incorrect or misleading results, as demonstrated by their "Weather Dilemma" example.
  • Trade-off between Convexity and Integrality: The paper discusses a trade-off in approximations, where prioritizing convexity (like in TRW) can lead to less integral solutions, while prioritizing integrality (like in EM) can lead to non-convexity and local optima.

Key Results

  • Theoretical Guarantees: The proposed algorithms offer theoretical guarantees for global or local optimality under certain conditions, particularly for tree-structured graphs.
  • Empirical Performance: Experiments show that their "mix-product (Bethe)" and "proximal (Bethe)" algorithms significantly outperform existing methods, including state-of-the-art local search algorithms, on various simulated and real-world problems.
  • High Success Rate: For challenging problems like hidden Markov chains, their algorithms achieve >99% probability of finding globally optimal solutions.
  • TRW as Upper Bound: The TRW approximation provides a valid upper bound on the optimal energy, even if its accuracy is lower than other methods.

Limitations and Future Work

  • Convergence Guarantees: While proximal point methods offer convergence guarantees, the mixed-product BP algorithm itself lacks guaranteed convergence in all cases, especially for non-tree structures.
  • Intractability of Approximations: Even with approximations, calculating terms like conditional entropy can remain intractable for general graphs.
  • Future Directions: The authors suggest improving TRW approximation performance, developing optimality conditions for non-tree sum components, studying the convergence of mixed-product BP, and applying these methods to learn hidden variable models from data.

Summary updated

Abstract

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.
BibTeX
@article{liu2013variational,
  author = {Qiang Liu and Alexander T. Ihler},
  title = {{Variational algorithms for marginal MAP.}},
  journal = {J. Mach. Learn. Res.},
  year = {2013},
  url = {https://openreview.net/forum?id=_6Avbzk8xB2K},
}
Figure