SFO: A Toolbox for Submodular Function Optimization
- Creators
- Krause, Andreas
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.
Additional Information
© 2010 Andreas Krause. Submitted 6/09; Published 3/10. Editor: Soeren Sonnenburg. This research was supported by ONR grant N00014-09-1-1044, NSF CNS-0932392, a gift from Microsoft Corporation and an Okawa Foundation Research Grant.Attached Files
Published - Krause2010p10074J_Mach_Learn_Res.pdf
Files
Name | Size | Download all |
---|---|---|
md5:d80e0ffa9e347cee28f5ca354ec65af8
|
39.4 kB | Preview Download |
Additional details
- Eprint ID
- 18474
- Resolver ID
- CaltechAUTHORS:20100527-094314461
- N00014-09-1-1044
- Office of Naval Research (ONR)
- CNS-0932392
- NSF
- Okawa Foundation Research
- Microsoft Corporation
- Created
-
2010-06-23Created from EPrint's datestamp field
- Updated
-
2020-03-09Created from EPrint's last_modified field