From MAP to Marginals: Variational Inference in Bayesian Submodular Models

Josip Djolonga, Andreas KrauseNeurIPS 2014

Overview

This paper introduces L-FIELD, the first systematic variational inference framework for Bayesian models defined by submodular functions. By approximating complex submodular distributions with simpler modular ones using sub- and supergradients, the authors provide rigorous upper and lower bounds on the log-partition function and marginal probabilities. Remarkably, this is achieved at a computational cost comparable to standard Maximum A Posteriori (MAP) optimization.

The Challenge of Probabilistic Inference

Submodular functions are widely used in machine learning to model "diminishing returns"—for example, in document summarization, where adding a redundant sentence provides less value than the first few. While we have efficient tools to find the single best set (MAP inference), we often lack tools for probabilistic inference.

If we want to know the uncertainty of our model, calculate marginal probabilities (the likelihood of a specific element being in the set), or compute the partition function (the normalization constant), we hit a wall: for submodular models, these tasks are generally #P-hard. Existing variational methods like "mean-field" struggle because submodular functions capture high-order interactions that do not play well with standard approximations.

Methods: The L-FIELD Framework

The authors propose L-FIELD, a variational approach that "sandwiches" the true distribution between tractable bounds.

  1. Modular Approximation: They exploit the fact that submodular functions can be bounded by modular (additive) functions. A modular function is simply a sum of independent weights for each element, making its partition function trivial to compute.
  2. Optimizing over Differentials:
    • Subgradients are used to create lower bounds on the function, which translate to upper bounds on the log-partition function.
  3. Supergradients are used to create upper bounds on the function, translating to lower bounds on the log-partition function.
  4. L for Lovász: The name L-FIELD comes from the Lovász extension. Traditional mean-field inference uses a "multi-linear extension" which is non-convex and hard to evaluate. L-FIELD uses the Lovász extension, which results in a concave objective that is much easier to optimize using standard tools.
Optimization Algorithms
  1. Curvature-Based Guarantees: They provide theoretical proofs showing that the quality of these bounds depends on the "curvature" of the submodular function—essentially, how far it deviates from being a simple additive function.

Experimental Setup

The authors evaluated L-FIELD on three distinct types of submodular models:

  • Pairwise MRFs (Cuts): Evaluated using synthetic data from a 2D Gaussian mixture model with two clusters.
  • Network Outbreak Detection: Evaluated using Watts-Strogatz random graphs to model the spread of a contagious process, where the goal is to identify infected nodes from noisy observations.
  • Sensor Placement: Used a real-world water distribution network dataset to model where to place sensors to detect contamination scenarios.

Key Results and Insights

Moving from point estimates to marginals allows researchers to quantify uncertainty in high-stakes tasks like sensor placement or disease tracking. By choosing the Lovász extension over the multi-linear extension, the authors transform a messy, non-convex inference problem into a well-behaved convex optimization problem.

Experimental Results across Datasets
  • Rigorous Bounds: L-FIELD successfully produced both upper and lower bounds for the log-partition function across all experiments.
  • Accuracy: In the network detection and sensor placement tasks, the estimated marginals were highly accurate, often showing an average error of less than 0.1, even when the theoretical curvature-based bounds were conservative.
  • Robustness: Compared to mean-field, which often got stuck in local optima (even with 20 random restarts), L-FIELD was more robust and consistently provided reliable estimates.
  • Efficiency & Scalability: Obtaining these probabilistic intervals costs roughly the same as performing traditional MAP optimization. While the authors focused on ground sets of size 100 for exhaustive comparison, the underlying optimization can scale to over 270,000 variables.

Limitations and Future Work

While highly effective, the theoretical guarantees based on curvature are quite conservative; the method often performs much better in practice than the theory predicts. Tightening these theoretical bounds remains an open challenge. Additionally, computing tight intervals for every marginal probability requires two MAP-like optimizations per variable, which can be computationally intensive for very large sets. Exploring how these techniques apply to even more complex "deep" submodular architectures could be a promising future direction.

Summary updated

BibTeX
@inproceedings{djolonga2014from,
  author = {Josip Djolonga and Andreas Krause},
  title = {{From MAP to Marginals: Variational Inference in Bayesian Submodular Models}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2014},
}
Figure