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

Alexander Kirillov, Alexander Shekhovtsov, Carsten Rother, Bogdan Savchynskyy

Research output: Chapter in Book/Report/Conference proceedingOther chapter contributionpeer-review


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 submodu- lar 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.
Original languageEnglish
Title of host publicationAdvances in Neural Information Processing Systems 29
EditorsD. D. Lee, M. Sugiyama, U. V. Luxburg, I. Guyon, R. Garnett
PublisherCurran Associates, Inc
Number of pages9
Publication statusPublished - 2016


Dive into the research topics of 'Joint M-Best-Diverse Labelings as a Parametric Submodular Minimization'. Together they form a unique fingerprint.

Cite this