nips nips2011 nips2011-199 nips2011-199-reference knowledge-graph by maker-knowledge-mining
Source: pdf
Author: Stefanie Jegelka, Hui Lin, Jeff A. Bilmes
Abstract: We are motivated by an application to extract a representative subset of machine learning training data and by the poor empirical performance we observe of the popular minimum norm algorithm. In fact, for our application, minimum norm can have a running time of about O(n7 ) (O(n5 ) oracle calls). We therefore propose a fast approximate method to minimize arbitrary submodular functions. For a large sub-class of submodular functions, the algorithm is exact. Other submodular functions are iteratively approximated by tight submodular upper bounds, and then repeatedly optimized. We show theoretical properties, and empirical results suggest significant speedups over minimum norm while retaining higher accuracies. 1
[1] R. K. Ahuja, T. L. Magnanti, and J. B. Orlin. Network Flows. Prentice Hall, 1993.
[2] Y. Boykov and M.-P. Jolly. Interactive graph cuts for optimal boundary and region segmentation of objects in n-d images. In ICCV, 2001. 1 http://riot.ieor.berkeley.edu/riot/Applications/Pseudoflow/parametric.html 8
[3] Y. Boykov and V. Kolmogorov. An experimental comparison of min-cut/max-flow algorithms for energy minimization in vision. IEEE TPAMI, 26(9):1124–1137, 2004.
[4] W. H. Cunningham. Decomposition of submodular functions. Combinatorica, 3(1):53–68, 1983.
[5] W. H. Cunningham. Testing membership in matroid polyhedra. J Combinatorial Theory B, 36:161–188, 1984.
[6] D. Freedman and P. Drineas. Energy minimization via graph cuts: Settling what is possible. In CVPR, 2005.
[7] S. Fujishige and S. Isotani. A submodular function minimization algorithm based on the minimum-norm base. Pacific Journal of Optimization, 7:3–17, 2011.
[8] S. Fujishige and S. Iwata. Minimizing a submodular function arising from a concave function. Discrete Applied Mathematics, 92, 1999.
[9] S. Fujishige and S. B. Patkar. Realization of set functions as cut functions of graphs and hypergraphs. Discrete Mathematics, 226:199–210, 2001.
[10] G. Gallo, M.D. Grigoriadis, and R.E. Tarjan. A fast parametric maximum flow algorithm and applications. SIAM J Computing, 18(1), 1989.
[11] J.J. Godfrey, E.C. Holliman, and J. McDaniel. Switchboard: Telephone speech corpus for research and development. In Proc. ICASSP, volume 1, pages 517–520, 1992.
[12] D. M. Greig, B. T. Porteous, and A. H. Seheult. Exact maximum a posteriori estimation for binary images. Journal of the Royal Statistical Society, 51(2), 1989.
[13] M. Gr¨ tschel, L. Lov´ sz, and A. Schrijver. The ellipsoid algorithm and its consequences in combinatorial o a optimization. Combinatorica, 1:499–513, 1981.
[14] D. Hochbaum. The pseudoflow algorithm: a new algorithm for the maximum flow problem. Operations Research, 58(4), 2008.
[15] S. Iwata, L. Fleischer, and S. Fujishige. A combinatorial strongly polynomial algorithm for minimizing submodular functions. J. ACM, 48:761–777, 2001.
[16] S. Jegelka and J. Bilmes. Submodularity beyond submodular energies: coupling edges in graph cuts. In CVPR, 2011.
[17] S. Jegelka and J. Bilmes. Approximation bounds for inference using cooperative cuts. In ICML, 2011.
[18] S. Jegelka, H. Lin, and J. Bilmes. Fast approximate submodular minimization: Extended version, 2011.
[19] P. Kohli, L. Ladick´ , and P. Torr. Robust higher order potentials for enforcing label consistency. Int. J. y Computer Vision, 82, 2009.
[20] H. Lin and J. Bilmes. An application of the submodular principal partition to training data subset selection. In NIPS workshop on Discrete Optimization in Machine Learning, 2010.
[21] H. Lin and J. Bilmes. Optimal selection of limited vocabulary speech corpora. In Proc. Interspeech, 2011.
[22] S. T. McCormick. Submodular function minimization. In K. Aardal, G. Nemhauser, and R. Weismantel, editors, Handbook on Discrete Optimization, pages 321–391. Elsevier, 2006. updated version 3a (2008).
[23] M. Narasimhan, N. Jojic, and J. Bilmes. Q-clustering. In NIPS, 2005.
[24] J. B. Orlin. A faster strongly polynomial time algorithm for submodular function minimization. Mathematical Programming, 118(2):237–251, 2009.
[25] M. Preissmann and A. Seb˝ . Research Trends in Combinatorial Optimization, chapter Graphic Submodular o Function Minimization: A Graphic Approach and Applications, pages 365–385. Springer, 2009.
[26] M. Queyranne. Minimizing symmetric submodular functions. Mathematical Programming, 82:3–12, 1998.
[27] A. Schrijver. A combinatorial algorithm minimizing submodular functions in strongly polynomial time. J. Combin. Theory Ser. B, 80:346–355, 2000.
[28] A. Schrijver. Combinatorial Optimization. Springer, 2004.
[29] P. Stobbe and A. Krause. Efficient minimization of decomposable submodular functions. In NIPS, 2010.
[30] J. Vondr´ k. personal communication, 2011. a ˘ y
[31] S. Zivn´ and P.G. Jeavons. Classes of submodular constraints expressible by graph cuts. Constraints, 15: 430–452, 2010. ISSN 1383-7133. ˘ y
[32] S. Zivn´ , D. A. Cohen, and P. G. Jeavons. The expressive power of binary submodular functions. Discrete Applied Mathematics, 157(15):3347–3358, 2009. 9