jmlr jmlr2010 jmlr2010-100 jmlr2010-100-reference knowledge-graph by maker-knowledge-mining
Source: pdf
Author: Andreas Krause
Abstract: In recent years, a fundamental problem structure has emerged as very useful in a variety of machine learning applications: Submodularity is an intuitive diminishing returns property, stating that adding an element to a smaller set helps more than adding it to a larger set. Similarly to convexity, submodularity allows one to efficiently find provably (near-) optimal solutions for large problems. We present SFO, a toolbox for use in MATLAB or Octave that implements algorithms for minimization and maximization of submodular functions. A tutorial script illustrates the application of submodularity to machine learning and AI problems such as feature selection, clustering, inference and optimized information gathering.
U. Feige, V. Mirrokni, and J. Vondrak. Maximizing non-monotone submodular functions. In FOCS, 2007. S. Fujishige. Submodular Functions and Optimization. Elsevier, 2nd edition, 2005. B. Goldengorin, G. Sierksma, G. A. Tijssen, and M. Tso. The data-correcting algorithm for the minimization of supermodular functions. Mgmt Science, 45(11):1539–1551, 1999. V. Kolmogorov and R. Zabih. What energy functions can be minimized via graph cuts? IEEE Trans Patt An Mach Int (PAMI), 26(2):147–159, February 2004. A. Krause, C. Guestrin, A. Gupta, and J. Kleinberg. Near-optimal sensor placements: Maximizing information while minimizing communication cost. In IPSN, 2006. A. Krause, A. Singh, and C. Guestrin. Near-optimal sensor placements in Gaussian processes: Theory, efficient algorithms and empirical studies. In JMLR, volume 9, 2008. A. Krause, R. Rajagopal, A. Gupta, and C. Guestrin. Simultaneous placement and scheduling of sensors. In Information Processing in Sensor Networks, 2009. J. Leskovec, A. Krause, C. Guestrin, C. Faloutsos, J. VanBriesen, and N. Glance. Cost-effective outbreak detection in networks. In KDD, 2007. M. Minoux. Accelerated greedy algorithms for maximizing submodular set functions. Optimization Techniques, LNCS, pages 234–243, 1978. M. Narasimhan and J. Bilmes. Pac-learning bounded tree-width graphical models. In Uncertainty in Artificial Intelligence, 2004. M. Narasimhan and J. Bilmes. A submodular-supermodular procedure with applications to discriminative structure learning. In NIPS 19, 2006. M. Narasimhan, N. Jojic, and J. Bilmes. Q-clustering. In NIPS, 2005. G. Nemhauser, L. Wolsey, and M. Fisher. An analysis of the approximations for maximizing submodular set functions. Mathematical Programming, 14:265–294, 1978. M. Queyranne. A combinatorial algorithm for minimizing symmetric submodular functions. In SODA, 1995. L. Zhao, H. Nagamochi, and T. Ibaraki. Greedy splitting algorithms for approximating multiway partition problems. Mathematical Programming, 102(1):167–183, 2005. 1144