nips nips2010 nips2010-69 nips2010-69-reference knowledge-graph by maker-knowledge-mining
Source: pdf
Author: Peter Stobbe, Andreas Krause
Abstract: Many combinatorial problems arising in machine learning can be reduced to the problem of minimizing a submodular function. Submodular functions are a natural discrete analog of convex functions, and can be minimized in strongly polynomial time. Unfortunately, state-of-the-art algorithms for general submodular minimization are intractable for larger problems. In this paper, we introduce a novel subclass of submodular minimization problems that we call decomposable. Decomposable submodular functions are those that can be represented as sums of concave functions applied to modular functions. We develop an algorithm, SLG, that can efÄ?Ĺš ciently minimize decomposable submodular functions with tens of thousands of variables. Our algorithm exploits recent results in smoothed convex minimization. We apply SLG to synthetic benchmarks and a joint classiÄ?Ĺš cation-and-segmentation task, and show that it outperforms the state-of-the-art general purpose submodular minimization algorithms by several orders of magnitude. 1
[1] Dimacs, The First international algorithm implementation challenge: The core experiments, 1990.
[2] F. Bach, Structured sparsity-inducing norms through submodular functions, Advances in Neural Information Processing Systems (2010).
[3] S. Becker, J. Bobin, and E.J. Candes, Nesta: A fast and accurate Ä?Ĺš rst-order method for sparse recovery, Arxiv preprint arXiv 904 (2009), 1–37.
[4] F.A. Chudak and K. Nagano, EfÄ?Ĺš cient solutions to relaxations of combinatorial problems with submodular penalties via the Lov´ sz extension and non-smooth convex optimization, Proceeda ings of the eighteenth annual ACM-SIAM symposium on Discrete algorithms, Society for Industrial and Applied Mathematics, 2007, pp. 79–88.
[5] M. Everingham, L. Van Gool, C. K. I. Williams, J. Winn, and A. Zisserman, The PASCAL Visual Object Classes Challenge 2009 (VOC2009) Results, http://www.pascalnetwork.org/challenges/VOC/voc2009/workshop/index.html.
[6] L. Fleischer and S. Iwata, A push-relabel framework for submodular function minimization and applications to parametric optimization, Discrete Applied Mathematics 131 (2003), no. 2, 311–322.
[7] D. Freedman and P. Drineas, Energy minimization via graph cuts: Settling what is possible, IEEE Computer Society Conference on Computer Vision and Pattern Recognition, 2005. CVPR 2005, vol. 2, 2005.
[8] Satoru Fujishige, Takumi Hayashi, and Shigueo Isotani, The Minimum-Norm-Point Algorithm Applied to Submodular Function Minimization and Linear Programming, (2006), 1–19.
[9] E. Hazan and S. Kale, Beyond convexity: Online submodular minimization, Advances in Neural Information Processing Systems 22 (Y. Bengio, D. Schuurmans, J. Lafferty, C. K. I. Williams, and A. Culotta, eds.), 2009, pp. 700–708.
[10] T. Itoko and S. Iwata, Computational geometric approach to submodular function minimization for multiclass queueing systems, Integer Programming and Combinatorial Optimization (2007), 267–279.
[11] S. Iwata, L. Fleischer, and S. Fujishige, A combinatorial strongly polynomial algorithm for minimizing submodular functions, Journal of the ACM (JACM) 48 (2001), no. 4, 777.
[12] S. Iwata and J.B. Orlin, A simple combinatorial algorithm for submodular function minimization, Proceedings of the Nineteenth Annual ACM-SIAM Symposium on Discrete Algorithms, Society for Industrial and Applied Mathematics, 2009, pp. 1230–1237.
[13] P. Kohli, M.P. Kumar, and P.H.S. Torr, P3 & Beyond: Solving Energies with Higher Order Cliques, 2007 IEEE Conference on Computer Vision and Pattern Recognition (2007), 1–8.
[14] P. Kohli, L. Ladick´ , and P.H.S. Torr, Robust Higher Order Potentials for Enforcing Label y Consistency, International Journal of Computer Vision 82 (2009), no. 3, 302–324.
[15] A. Krause, SFO: A Toolbox for Submodular Function Optimization, The Journal of Machine Learning Research 11 (2010), 1141–1144.
[16] L. Lov´ sz, Submodular functions and convexity, Mathematical programming: the state of the a art, Bonn (1982), 235–257.
[17] G. Nemhauser, L. Wolsey, and M. Fisher, An analysis of the approximations for maximizing submodular set functions, Mathematical Programming 14 (1978), 265–294.
[18] Yu. Nesterov, Smooth minimization of non-smooth functions, Mathematical Programming 103 (2004), no. 1, 127–152.
[19] M. Queyranne, Minimizing symmetric submodular functions, Mathematical Programming 82 (1998), no. 1-2, 3–12.
[20] J. Shotton, J. Winn, C. Rother, and A. Criminisi, TextonBoost for Image Understanding: MultiClass Object Recognition and Segmentation by Jointly Modeling Texture, Layout, and Context, Int. J. Comput. Vision 81 (2009), no. 1, 2–23.
[21] P. Stobbe and A. Krause, EfÄ?Ĺš cient minimization of decomposable submodular functions, arXiv:1010.5511 (2010). 9