On Approximate Non-submodular Minimization via Tree-Structured Supermodularity

Yoshinobu Kawahara, Rishabh Iyer, Jeffrey Bilmes
Proceedings of the Eighteenth International Conference on Artificial Intelligence and Statistics, PMLR 38:444-452, 2015.

Abstract

We address the problem of minimizing non-submodular functions where the supermodularity is restricted to tree-structured pairwise terms. We are motivated by several real world applications, which require submodularity along with structured supermodularity, and this forms a rich class of expressive models, where the non-submodularity is restricted to a tree. While this problem is NP hard (as we show), we develop several practical algorithms to find approximate and near-optimal solutions for this problem, some of which provide lower and others of which provide upper bounds thereby allowing us to compute a tightness gap. We also show that some of our algorithms can be extended to handle more general forms of supermodularity restricted to arbitrary pairwise terms. We compare our algorithms on synthetic data, and also demonstrate the advantage of the formulation on the real world application of image segmentation, where we incorporate structured supermodularity into higher-order submodular energy minimization.

Cite this Paper

BibTeX
@InProceedings{pmlr-v38-kawahara15, title = {{On Approximate Non-submodular Minimization via Tree-Structured Supermodularity}}, author = {Kawahara, Yoshinobu and Iyer, Rishabh and Bilmes, Jeffrey}, booktitle = {Proceedings of the Eighteenth International Conference on Artificial Intelligence and Statistics}, pages = {444--452}, year = {2015}, editor = {Lebanon, Guy and Vishwanathan, S. V. N.}, volume = {38}, series = {Proceedings of Machine Learning Research}, address = {San Diego, California, USA}, month = {09--12 May}, publisher = {PMLR}, pdf = {http://proceedings.mlr.press/v38/kawahara15.pdf}, url = {https://proceedings.mlr.press/v38/kawahara15.html}, abstract = {We address the problem of minimizing non-submodular functions where the supermodularity is restricted to tree-structured pairwise terms. We are motivated by several real world applications, which require submodularity along with structured supermodularity, and this forms a rich class of expressive models, where the non-submodularity is restricted to a tree. While this problem is NP hard (as we show), we develop several practical algorithms to find approximate and near-optimal solutions for this problem, some of which provide lower and others of which provide upper bounds thereby allowing us to compute a tightness gap. We also show that some of our algorithms can be extended to handle more general forms of supermodularity restricted to arbitrary pairwise terms. We compare our algorithms on synthetic data, and also demonstrate the advantage of the formulation on the real world application of image segmentation, where we incorporate structured supermodularity into higher-order submodular energy minimization.} }
Endnote
%0 Conference Paper %T On Approximate Non-submodular Minimization via Tree-Structured Supermodularity %A Yoshinobu Kawahara %A Rishabh Iyer %A Jeffrey Bilmes %B Proceedings of the Eighteenth International Conference on Artificial Intelligence and Statistics %C Proceedings of Machine Learning Research %D 2015 %E Guy Lebanon %E S. V. N. Vishwanathan %F pmlr-v38-kawahara15 %I PMLR %P 444--452 %U https://proceedings.mlr.press/v38/kawahara15.html %V 38 %X We address the problem of minimizing non-submodular functions where the supermodularity is restricted to tree-structured pairwise terms. We are motivated by several real world applications, which require submodularity along with structured supermodularity, and this forms a rich class of expressive models, where the non-submodularity is restricted to a tree. While this problem is NP hard (as we show), we develop several practical algorithms to find approximate and near-optimal solutions for this problem, some of which provide lower and others of which provide upper bounds thereby allowing us to compute a tightness gap. We also show that some of our algorithms can be extended to handle more general forms of supermodularity restricted to arbitrary pairwise terms. We compare our algorithms on synthetic data, and also demonstrate the advantage of the formulation on the real world application of image segmentation, where we incorporate structured supermodularity into higher-order submodular energy minimization.
RIS
TY - CPAPER TI - On Approximate Non-submodular Minimization via Tree-Structured Supermodularity AU - Yoshinobu Kawahara AU - Rishabh Iyer AU - Jeffrey Bilmes BT - Proceedings of the Eighteenth International Conference on Artificial Intelligence and Statistics DA - 2015/02/21 ED - Guy Lebanon ED - S. V. N. Vishwanathan ID - pmlr-v38-kawahara15 PB - PMLR DP - Proceedings of Machine Learning Research VL - 38 SP - 444 EP - 452 L1 - http://proceedings.mlr.press/v38/kawahara15.pdf UR - https://proceedings.mlr.press/v38/kawahara15.html AB - We address the problem of minimizing non-submodular functions where the supermodularity is restricted to tree-structured pairwise terms. We are motivated by several real world applications, which require submodularity along with structured supermodularity, and this forms a rich class of expressive models, where the non-submodularity is restricted to a tree. While this problem is NP hard (as we show), we develop several practical algorithms to find approximate and near-optimal solutions for this problem, some of which provide lower and others of which provide upper bounds thereby allowing us to compute a tightness gap. We also show that some of our algorithms can be extended to handle more general forms of supermodularity restricted to arbitrary pairwise terms. We compare our algorithms on synthetic data, and also demonstrate the advantage of the formulation on the real world application of image segmentation, where we incorporate structured supermodularity into higher-order submodular energy minimization. ER -
APA
Kawahara, Y., Iyer, R. & Bilmes, J.. (2015). On Approximate Non-submodular Minimization via Tree-Structured Supermodularity. Proceedings of the Eighteenth International Conference on Artificial Intelligence and Statistics, in Proceedings of Machine Learning Research 38:444-452 Available from https://proceedings.mlr.press/v38/kawahara15.html.

Related Material