nips nips2013 nips2013-319 nips2013-319-reference knowledge-graph by maker-knowledge-mining
Source: pdf
Author: Rishabh K. Iyer, Jeff A. Bilmes
Abstract: We investigate two new optimization problems — minimizing a submodular function subject to a submodular lower bound constraint (submodular cover) and maximizing a submodular function subject to a submodular upper bound constraint (submodular knapsack). We are motivated by a number of real-world applications in machine learning including sensor placement and data subset selection, which require maximizing a certain submodular function (like coverage or diversity) while simultaneously minimizing another (like cooperative cost). These problems are often posed as minimizing the difference between submodular functions [9, 25] which is in the worst case inapproximable. We show, however, that by phrasing these problems as constrained optimization, which is more natural for many applications, we achieve a number of bounded approximation guarantees. We also show that both these problems are closely related and an approximation algorithm solving one can be used to obtain an approximation guarantee for the other. We provide hardness results for both problems thus showing that our approximation factors are tight up to log-factors. Finally, we empirically demonstrate the performance and good scalability properties of our algorithms. 1
[1] A. Atamt¨ rk and V. Narayanan. The submodular knapsack polytope. Discrete Optimization, 2009. u
[2] M. Conforti and G. Cornuejols. Submodular set functions, matroids and the greedy algorithm: tight worstcase bounds and some generalizations of the Rado-Edmonds theorem. Discrete Applied Mathematics, 7(3):251–274, 1984.
[3] U. Feige. A threshold of ln n for approximating set cover. Journal of the ACM (JACM), 1998.
[4] S. Fujishige. Submodular functions and optimization, volume 58. Elsevier Science, 2005.
[5] J. Garofolo, F. Lamel, L., J. W., Fiscus, D. Pallet, and N. Dahlgren. Timit, acoustic-phonetic continuous speech corpus. In DARPA, 1993.
[6] M. Goemans, N. Harvey, S. Iwata, and V. Mirrokni. Approximating submodular functions everywhere. In SODA, pages 535–544, 2009.
[7] A. Guillory and J. Bilmes. Interactive submodular set cover. In ICML, 2010.
[8] A. Guillory and J. Bilmes. Simultaneous learning and covering with adversarial noise. In ICML, 2011.
[9] R. Iyer and J. Bilmes. Algorithms for approximate minimization of the difference between submodular functions, with applications. In UAI, 2012.
[10] R. Iyer and J. Bilmes. The submodular Bregman and Lov´ sz-Bregman divergences with applications. In a NIPS, 2012.
[11] R. Iyer and J. Bilmes. Submodular Optimization with Submodular Cover and Submodular Knapsack Constraints: Extended arxiv version, 2013.
[12] R. Iyer, S. Jegelka, and J. Bilmes. Curvature and Optimal Algorithms for Learning and Minimizing Submodular Functions . In NIPS, 2013.
[13] R. Iyer, S. Jegelka, and J. Bilmes. Fast semidifferential based submodular function optimization. In ICML, 2013.
[14] S. Jegelka and J. A. Bilmes. Submodularity beyond submodular energies: coupling edges in graph cuts. In CVPR, 2011.
[15] Y. Kawahara and T. Washio. Prismatic algorithm for discrete dc programming problems. In NIPS, 2011.
[16] H. Kellerer, U. Pferschy, and D. Pisinger. Knapsack problems. Springer Verlag, 2004.
[17] A. Krause and C. Guestrin. A note on the budgeted maximization on submodular functions. Technical Report CMU-CALD-05-103, Carnegie Mellon University, 2005.
[18] A. Krause, B. McMahan, C. Guestrin, and A. Gupta. Robust submodular observation selection. Journal of Machine Learning Research (JMLR), 9:2761–2801, 2008.
[19] A. Krause, A. Singh, and C. Guestrin. Near-optimal sensor placements in Gaussian processes: Theory, efficient algorithms and empirical studies. JMLR, 9:235–284, 2008.
[20] H. Lin and J. Bilmes. How to select a good training-data subset for transcription: Submodular active selection for sequences. In Interspeech, 2009.
[21] H. Lin and J. Bilmes. Multi-document summarization via budgeted maximization of submodular functions. In NAACL, 2010.
[22] H. Lin and J. Bilmes. A class of submodular functions for document summarization. In The 49th Annual Meeting of the Association for Computational Linguistics: Human Language Technologies (ACL/HLT2011), Portland, OR, June 2011.
[23] H. Lin and J. Bilmes. Optimal selection of limited vocabulary speech corpora. In Interspeech, 2011.
[24] R. C. Moore and W. Lewis. Intelligent selection of language model training data. In Proceedings of the ACL 2010 Conference Short Papers, pages 220–224. Association for Computational Linguistics, 2010.
[25] M. Narasimhan and J. Bilmes. A submodular-supermodular procedure with applications to discriminative structure learning. In UAI, 2005.
[26] E. Nikolova. Approximation algorithms for offline risk-averse combinatorial optimization, 2010.
[27] J. Rousu and J. Shawe-Taylor. Efficient computation of gapped substring kernels on large alphabets. Journal of Machine Learning Research, 6(2):1323, 2006.
[28] M. Sviridenko. A note on maximizing a submodular set function subject to a knapsack constraint. Operations Research Letters, 32(1):41–43, 2004.
[29] L. A. Wolsey. An analysis of the greedy algorithm for the submodular set covering problem. Combinatorica, 2(4):385–393, 1982. 9