M-Best-Diverse Labelings for Submodular Energies and Beyond

Alexander Kirillov, Dmytro Shlezinger, Dmitry P. Vetrov, Carsten Rother, Bogdan SavchynskyyNeurIPS 2015 · OpenReview

Introduction

In many machine learning tasks—such as image segmentation or protein folding—finding a single "best" (Maximum A Posteriori, or MAP) solution is often insufficient. Real-world applications frequently require a set of $M$ solutions that are both high-quality (low energy) and significantly different from one another (diverse). This diversity is crucial for expressing uncertainty, ranking results, or providing meaningful options for human-in-the-loop systems.

The traditional approach, DivMBest, finds these solutions greedily: it identifies the best solution, then the next best that differs from the first, and so on. While computationally fast, this sequential approach is inherently suboptimal. Recent advancements have demonstrated that finding all $M$ solutions jointly yields qualitatively superior results. However, this comes at a massive computational cost: the complexity typically grows exponentially with $M$, rendering it impractical for real-world use.

This paper bridges that gap, introducing a method to achieve the high quality of joint inference with the speed of sequential methods. By proving that optimal diverse solutions are naturally ordered in submodular problems, the authors transform a computationally expensive joint optimization into a fast, solvable submodular energy minimization.

Methods: The Joint-DivMBest Framework

The authors focus on submodular energy minimization, a class of problems efficiently solvable using graph cuts (min-cut/max-flow algorithms). Their core theoretical contribution is the Joint-DivMBest framework.

  1. The Ordering Constraint: The foundational insight of the paper is a mathematical proof regarding submodular functions. If the original energy function is submodular and the diversity measure is "permutation invariant" (such as Hamming distance), the optimal $M$ diverse solutions exhibit a natural partial order (they are nested). This means solution $i$ is always "less than or equal to" solution $j$, drastically reducing the search space.
  2. Submodular Formulation: By explicitly enforcing this ordering constraint within the energy function, the authors prove that the joint inference problem remains submodular.
  3. Efficient Solvers: Because the problem retains its submodularity, the method avoids the exponential "clique encoding" required by previous joint methods. Instead, it leverages standard, highly optimized min-cut/max-flow solvers, moving from a label space that grows exponentially ($L^M$) to one that grows linearly.
Graphical representations of joint inference models for different diversity measures.

For problems that are not naturally submodular (like complex multi-label segmentation), the authors propose practical heuristics: either explicitly enforcing the ordering constraint regardless, or "learning" submodular potentials that approximate the original non-submodular problem.

Datasets and Evaluation

The approach was evaluated on two primary computer vision tasks:

  • Interactive Foreground/Background Segmentation: Utilizing 50 graphical model instances based on a subset of PASCAL VOC 2010. This task featured manually added user "scribbles" to guide the segmentation and represents a naturally submodular problem.
  • Category-Level Segmentation: Utilizing the PASCAL VOC 2012 validation set (1,449 images). This is a more complex, multi-label problem (21 categories) that is not naturally submodular, testing the proposed heuristics.

Key Results

The empirical results strongly validate the theoretical claims, showing massive improvements in inference time without sacrificing the quality of joint optimization.

  • Speed: In interactive segmentation, Joint-DivMBest was roughly 60 times faster than the previous state-of-the-art joint method (CE) for $M=10$ (20.4ms compared to 1247ms). Its runtime is comparable to the much simpler sequential greedy method.
  • Quality: Joint-DivMBest consistently matched the accuracy of exact joint methods and exceeded sequential methods. On the non-submodular PASCAL VOC 2012 dataset, it achieved an Intersection-over-Union (IoU) of 56.31% (for $M=16$), outperforming the sequential DivMBest's 53.07%.
  • Exactness: For submodular cases, Joint-DivMBest provides an exact solution to the joint diversity problem, whereas previous fast methods were often only approximate.
Performance comparison showing Joint-DivMBest matching CE quality while drastically reducing inference time.

Limitations and Future Work

While highly effective, the current submodular formulation relies heavily on "node-wise" diversity measures like Hamming distance. Incorporating more complex, higher-order diversity measures—which evaluate relationships between pixels rather than just individual pixel differences—while maintaining submodularity remains an open challenge.

Furthermore, while the "ordered" heuristic performs admirably for non-submodular problems (like the 21-label PASCAL task), it is no longer mathematically guaranteed to find the exact global optimum. Future work may explore extending this framework to other types of discrete optimization problems beyond computer vision, provided they exhibit similar submodular properties.

Summary updated

Abstract

We consider the problem of finding M best diverse solutions of energy minimization problems for graphical models. Contrary to the sequential method of Batra et al., which greedily finds one solution after another, we infer all $M$ solutions jointly. It was shown recently that such jointly inferred labelings not only have smaller total energy but also qualitatively outperform the sequentially obtained ones. The only obstacle for using this new technique is the complexity of the corresponding inference problem, since it is considerably slower algorithm than the method of Batra et al. In this work we show that the joint inference of $M$ best diverse solutions can be formulated as a submodular energy minimization if the original MAP-inference problem is submodular, hence fast inference techniques can be used. In addition to the theoretical results we provide practical algorithms that outperform the current state-of-the art and can be used in both submodular and non-submodular case.
BibTeX
@inproceedings{kirillov2015m,
  author = {Alexander Kirillov and Dmytro Shlezinger and Dmitry P. Vetrov and Carsten Rother and Bogdan Savchynskyy},
  title = {{M-Best-Diverse Labelings for Submodular Energies and Beyond}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2015},
  url = {https://openreview.net/forum?id=r1VEc_ZdbS},
}
Figure