Joint M-Best-Diverse Labelings as a Parametric Submodular Minimization

Alexander Kirillov, Alexander Shekhovtsov, Carsten Rother, Bogdan Savchynskyy

TL;DR

This paper establishes a surprising theoretical link between finding diverse, low-energy solutions in graphical models and the field of parametric submodular minimization. By proving that the "joint M-best-diverse" problem can be decomposed into independent sub-problems for a wide class of diversity measures, the authors introduce new algorithms that are not only mathematically exact but also significantly faster than previous approximate, greedy methods.

What Problem Does This Paper Address?

In many machine learning and computer vision tasks—like image segmentation—we use graphical models to find the most likely labeling (MAP inference). However, finding just one "best" solution is often insufficient. We might want $M$ different solutions to express uncertainty, rank results, or provide options for a human-in-the-loop system.

The challenge is finding solutions that are both high-quality (low energy) and significantly different from one another (diverse). There are two main ways to do this:

  1. Sequential (Greedy): Find the best solution, then find the next best that is diverse from the first, and so on. This is fast but often yields sub-optimal sets of solutions.
  2. Joint: Optimize all $M$ solutions simultaneously to minimize a combined energy and diversity objective. This is theoretically superior but has historically been computationally expensive, with runtimes that scale poorly as $M$ increases.

This paper aims to bridge the gap, providing a way to solve the joint problem exactly without the massive computational overhead.

Methods

The authors focus on binary submodular energies, a common class of problems in computer vision (like foreground/background segmentation) that can be solved efficiently using min-cut/max-flow algorithms.

The key technical contribution is a proof that for concave node-wise diversity measures (such as Hamming distance), the joint $M$-best-diverse problem satisfies a "nestedness" property. This means that if you order the $M$ solutions, the set of pixels labeled as "1" in solution $i$ is always a subset of those in solution $i+1$.

This nestedness allows the authors to reduce the complex joint optimization into $M$ independent, non-parametric submodular minimization problems. Crucially:

  • The parameters ($\gamma$) that enforce diversity can be calculated in closed form before any optimization begins.
  • Because the problems are independent, they can be solved in parallel.
  • Because they are nested, a sequential solver can reuse information from the previous step (warm-starting the max-flow) to speed up computation even further.

Datasets

The authors evaluated their approach on two main benchmarks:

  1. Interactive Segmentation: A dataset of 50 super-pixel graphical model instances based on PASCAL VOC 2010, featuring manually added user scribbles.
  2. PASCAL VOC 2012 (Foreground/Background): A new dataset derived by selecting 451 images from the PASCAL VOC 2012 validation set that contain only two labels (background and one object class). Unary potentials were generated using a Fully Convolutional Network (FCN-8s).

Key Insights and Ideas

  • The Power of Concavity: The authors identify that the "secret sauce" for efficient joint diversity is the concavity of the diversity measure. As shown in Figure 1, common measures like Hamming distance are concave when viewed as a function of the number of labels. Hamming distance and linear diversity measures
  • Decomposition is Possible: The most striking finding is that a problem that looks like it must be solved jointly can actually be broken apart. You don't need to look at solution $A$ to find solution $B$ if you know the right diversity parameters $\gamma$ in advance.
  • Exact beats Approximate in Speed: Usually, there is a trade-off between accuracy and speed. Here, by leveraging the mathematical structure of parametric submodular functions, the authors provide an exact solver that outperforms the popular approximate DivMBest method in raw runtime.
Hamming distance and linear diversity measures

Key Results

The proposed methods, Parametric-sequential and Parametric-parallel, were compared against the standard DivMBest [4] and the previous exact Joint-DivMBest [23].

  • Quality: Both parametric methods achieved higher per-pixel accuracy and Intersection-over-Union (IoU) scores than the sequential DivMBest because they solve the joint objective exactly.
  • Speed: In the interactive segmentation task (Table 1), the Parametric-parallel method was the fastest, taking only 6.2ms for $M=10$ solutions, compared to 15.4ms for DivMBest and a staggering 80.3ms for the previous joint solver. Interactive segmentation results table
  • Scalability: As $M$ increases, the runtime of the parametric methods grows much more slowly than DivMBest, especially in the parallel implementation. IoU and Runtime plots
Interactive segmentation results table
IoU and Runtime plots

Limitations and Future Work

  • Binary Labels Only: The current theory and algorithms are strictly limited to binary (0/1) labeling problems. Extending this to multi-label problems remains a significant challenge.
  • Submodularity Requirement: The efficiency relies on the energy function being submodular. While many vision problems fit this, many others (like those with "anti-submodular" components) do not.
  • Diversity Measures: While Hamming distance is covered, the authors note that exploring which other complex multilabel diversity measures can be expressed as a sum with monotone differences is a task for future research.

Summary updated

Abstract

We consider the problem of jointly inferring the M-best diverse labelings for a binary (high-order) submodular energy of a graphical model. Recently, it was shown that this problem can be solved to a global optimum, for many practically interesting diversity measures. It was noted that the labelings are, so-called, nested. This nestedness property also holds for labelings of a class of parametric submodular minimization problems, where different values of the global parameter $γ$ give rise to different solutions. The popular example of the parametric submodular minimization is the monotonic parametric max-flow problem, which is also widely used for computing multiple labelings. As the main contribution of this work we establish a close relationship between diversity with submodular energies and the parametric submodular minimization. In particular, the joint M-best diverse labelings can be obtained by running a non-parametric submodular minimization (in the special case - max-flow) solver for M different values of $γ$ in parallel, for certain diversity measures. Importantly, the values for $γ$ can be computed in a closed form in advance, prior to any optimization. These theoretical results suggest two simple yet efficient algorithms for the joint M-best diverse problem, which outperform competitors in terms of runtime and quality of results. In particular, as we show in the paper, the new methods compute the exact M-best diverse labelings faster than a popular method of Batra et al., which in some sense only obtains approximate solutions.
BibTeX
@inproceedings{kirillov2016joint,
  author = {Alexander Kirillov and Alexander Shekhovtsov and Carsten Rother and Bogdan Savchynskyy},
  title = {{Joint M-Best-Diverse Labelings as a Parametric Submodular Minimization}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2016},
  url = {https://openreview.net/forum?id=rkVE7wZObB},
}
Figure