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.
- 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.
- Submodular Formulation: By explicitly enforcing this ordering constraint within the energy function, the authors prove that the joint inference problem remains submodular.
- 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.
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.
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