nips nips2009 nips2009-239 nips2009-239-reference knowledge-graph by maker-knowledge-mining
Source: pdf
Author: Yoshinobu Kawahara, Kiyohito Nagano, Koji Tsuda, Jeff A. Bilmes
Abstract: Several key problems in machine learning, such as feature selection and active learning, can be formulated as submodular set function maximization. We present herein a novel algorithm for maximizing a submodular set function under a cardinality constraint — the algorithm is based on a cutting-plane method and is implemented as an iterative small-scale binary-integer linear programming procedure. It is well known that this problem is NP-hard, and the approximation factor achieved by the greedy algorithm is the theoretical limit for polynomial time. As for (non-polynomial time) exact algorithms that perform reasonably in practice, there has been very little in the literature although the problem is quite important for many applications. Our algorithm is guaranteed to find the exact solution finitely many iterations, and it converges fast in practice due to the efficiency of the cutting-plane mechanism. Moreover, we also provide a method that produces successively decreasing upper-bounds of the optimal solution, while our algorithm provides successively increasing lower-bounds. Thus, the accuracy of the current solution can be estimated at any point, and the algorithm can be stopped early once a desired degree of tolerance is met. We evaluate our algorithm on sensor placement and feature selection applications showing good performance. 1
[1] A. Das and D. Kempe. Algorithms for subset selection in linear regression. In R. E. Ladner and C. Dwork, editors, Proc. of the 40th Annual ACM Symp. on Theory of Computing (STOC 2008), pages 45–54, 2008.
[2] J. Edmonds. Submodular functions, matroids, and certain polyhedra. In R. Guy, H. Hanani, N. Sauer, and J. Sh¨ nheim, editors, Combinatorial Structures and Their Applications, pages 69–87. Gordon and o Breach, 1970.
[3] U. Feige. A threshold of ln n for approximating set cover. Journal of the ACM, 45:634–652, 1998.
[4] G. Forman. An extensive empirical study of feature selection metrics for text classification. Journal of Machine Learning Research, 3:1289–1305, 2003.
[5] S. Fujishige. Submodular Functions and Optimization. Elsevier, second edition, 2005.
[6] F. Glover. Convexity cuts and cut search. Operations Research, 21:123–134, 1973.
[7] F. Glover. Polyhedral convexity cuts and negative edge extension. Zeitschrift f¨ r Operations Research, u 18:181–186, 1974.
[8] B. Goldengorin. Maximization of submodular functions: Theory and enumeration algorithms. European Journal of Operational Research, 198(1):102–112, 2009.
[9] T. C. Harmon, R. F. Ambrose, R. M. Gilbert, J. C. Fisher, M. Stealey, and W. J. Kaiser. High resolution river hydraulic and water quality characterization using rapidly deployable. Technical report, CENS,, 2006.
[10] S. C. H. Hoi, R. Jin, J. Zhu, and M. R. Lyu. Batch mode active learning and its application to medical image classification. In Proc. of the 23rd int’l conf. on Machine learning (ICML 2006), pages 417–424, 2006.
[11] R. Horst and H. Tuy. Global Optimization (Deterministic Approaches). Springer, 3 edition, 1996.
[12] A. Krause, H. B. McMahan, C. Guestrin, and A. Gupta. Robust submodular observation selection. Journal of Machine Learning Research, 9:2761–2801, 2008.
[13] A. Krause, A. Singh, and C. Guestrin. Near-optimal sensor placements in Gaussian processes: Theory, efficient algorithms and empirical studies. Journal of Machine Learning Research, 9:235–284, 2009.
[14] H. Lee, G. L. Nemhauser, and Y. Wang. Maximizing a submodular function by integer programming: Polyhedral results for the quadratic case. European Journal of Operational Research, 94:154–166, 1996.
[15] L. Lov´ sz. Submodular functions and convexity. In A. Bachem, M. Gr¨ tschel, and B. Korte, editors, a o Mathematical Programming – The State of the Art, pages 235–257. 1983.
[16] K. Murota. Discrete Convex Analysis, volume 10 of Monographs on Discrete Math and Applications. Society for Industrial & Applied, 2000.
[17] G. L. Nemhauser and L. A. Wolsey. Maximizing submodular set functions: formulations and analysis of algorithms. In P. Hansen, editor, Studies on Graphs and Discrete Programming, volume 11 of Annals of Discrete Mathematics. 1981.
[18] G. L. Nemhauser and L. A. Wolsey. Integer and Combinatorial Optimization. Wiley-Interscience, 1988.
[19] G. L. Nemhauser, L. A. Wolsey, and M. L. Fisher. An analysis of approximations for maximizing for submodular set functions – I. Mathematical Programming, 14:265–294, 1978.
[20] M. Porembski. Finitely convergent cutting planes for concave minimization. Journal of Global Optimization, 20(2):109–132, 2001.
[21] M. Sviridenko. A note on maximizing a submodular set function subject to a knapsack constraint. Operations Research Letters, 32(1):41–43, 2004.
[22] M. Thoma, H. Cheng, A. Gretton, J. Han, H. P. Kriegel, A. J. Smola, L. Song, P. S. Yu, X. Yan, and K. M. Borgwardt. Near-optimal supervised feature selection among frequent subgraphs. In Proc. of the 2009 SIAM Conference on Data Mining (SDM 2009), pages 1075–1086, 2009.
[23] H. Tuy. Concave programming under linear constraints. Soviet Mathematics Doklady, 5:1437–1440, 1964. 9