Higher-Order Inference for Multi-class Log-Supermodular Models

Jian Zhang, Josip Djolonga, Andreas KrauseICCV 2015 · DOI

TL;DR

Researchers from ETH Zurich have developed the first efficient method for approximate Bayesian marginal inference in high-order, multi-label "attractive" models. By framing the problem as variational inference in log-supermodular models under partition constraints, they achieve state-of-the-art accuracy in semantic segmentation while providing meaningful uncertainty estimates—all without the exponential slowdown typical of traditional high-order inference.

Introduction: The Challenge of High-Order Marginals

In computer vision, modeling complex dependencies between pixels—high-order interactions—is crucial for tasks like semantic segmentation. For instance, pixels within a "superpixel" (a group of similar pixels) should ideally share the same label.

While finding the Maximum A Posteriori (MAP) estimate is tractable for "submodular" energy functions (which exhibit diminishing returns), calculating marginals—the specific probability of a pixel belonging to a class—is notoriously difficult. Traditional algorithms like Belief Propagation or Mean-Field scale exponentially with the size of the interaction group (clique size). This makes them unusable for large-scale high-order models. Without marginals, we cannot quantify uncertainty or properly train complex probabilistic models.

Proposed Method: Multi-label Log-Supermodular Models

The authors introduce a framework for multi-label log-supermodular models that breaks this exponential barrier.

  1. Encoding and Constraints: They represent multi-label problems using a "1-of-L" encoding. To ensure each pixel is assigned exactly one label, they introduce partition constraints.
  2. Variational Inference via the Base Polytope: Instead of calculating the intractable partition function, they seek the best "modular" (fully factorized) lower bound. They utilize the base polytope of the submodular function, a mathematical structure that allows for efficient bound discovery.
  3. Convex Optimization: The resulting problem is convex and solved using the Frank-Wolfe (conditional gradient) algorithm. Crucially, the linear optimization step within Frank-Wolfe is solved in $O(N \log N)$ time using Edmonds’ greedy algorithm, avoiding exponential complexity.
  4. Mathematical Equivalence: They prove that their marginal inference technique is equivalent to solving a "smoothed" version of the MAP inference problem using Shannon entropy.

Experimental Evaluation

The researchers evaluated their approach on the MSRC-21 dataset, specifically a subset of 93 images with fine-grain annotations to measure accuracy at semantic boundaries. They used TextonBoost features as unary potentials.

Semantic segmentation pipeline showing (a) original image, (b) superpixels, (c) cliques, (d) ground truth, (e) entropy/uncertainty, and (f) inference results.

Key Results

  • State-of-the-Art Accuracy: The best model (SUBMOD3-LAYER) achieved a pixel-wise accuracy of 88.61%, outperforming standard pairwise models and competing well with other high-order baselines like ROBUST-PN (86.5%).
  • High-Quality Marginals: Using Area Under the ROC Curve (AUC) for marginal quality, the proposed models significantly outperformed unary and pairwise baselines, particularly near object boundaries.
  • Computational Efficiency: Inference runs in seconds (e.g., ~15 seconds for a 3-layer model), whereas traditional methods would be mathematically impossible on cliques encompassing hundreds of pixels.
  • Meaningful Uncertainty: As shown in the entropy maps (Figure 3e), the model is "aware" of its confusion in difficult regions, such as boundaries between objects. This is vital for safety-critical applications like autonomous driving.

Limitations and Future Work

The method relies on the energy function being submodular (attractive). While excellent for consistency (e.g., "all these pixels are grass"), it cannot model "repulsive" interactions (e.g., "a person cannot be inside a cow"). Additionally, while Frank-Wolfe is efficient per iteration, reaching extremely precise marginals might require many iterations due to its $O(1/k)$ convergence rate. Future work could involve integrating this framework into the training loop of Conditional Random Fields (CRFs) for better parameter learning.

Summary updated

BibTeX
@inproceedings{zhang2015higher,
  author = {Jian Zhang and Josip Djolonga and Andreas Krause},
  title = {{Higher-Order Inference for Multi-class Log-Supermodular Models}},
  booktitle = {IEEE/CVF International Conference on Computer Vision},
  year = {2015},
  doi = {10.1109/iccv.2015.216},
}
Figure