
 Description:
Matlab Toolbox for Submodular Function Optimization
By Andreas Krause (krausea@gmail.com).
Slides, videos and detailed references available at http://www.submodularity.org
Tested in MATLAB 7.0.1 (R14), 7.2.0 (R2006a), 7.4.0 (R2007a, MAC), 7.9.0 (MAC).
A note on Octave compatibility:
This toolbox also works under Octave; however, since Octave handles function objects differently from Matlab. Use the function sfo_octavize to make a submodular function object Octave ready; type 'help sfo_octavize' for more information. The script sfo_tutorial_octave has been tested under Octave 3.2.3
This toolbox provides functions for optimizing submodular set functions, i.e., functions that take a subset A of a finite ground set V to the real numbers, satisfying
$$F(A)+F(B)geq F(Acup B)+F(Acap B)$$
It also presents several examples of applying submodular function optimization to important machine learning problems, such as clustering, inference in probabilistic models and experimental design. There is a demo script: sfo_tutorial.m
Some information on conventions:
All algorithms will use function objects (see sfo_tutorial.m for examples). For example, to measure variance reduction in a Gaussian model, call
F = sfo_fn_varred(sigma,V)
where sigma is the covariance matrix and V is the ground set, e.g., 1:size(sigma,1) They will also take an index set V, and A must be a subset of V.
Implemented algorithms:
1) Minimization:

sfo_min_norm_point: Fujishige's minimumnormpoint algorithm for minimizing general submodular functions

sfo_queyranne: Queyranne's algorithm for minimizing symmetric submodular functions

sfo_sssp: Submodularsupermodular procedure of Narasimhan & Bilmes for minimizing the difference of two submodular functions

sfo_s_t_min_cut: For solving min F(A) s.t. s in A, t not in A

sfo_minbound: Return an online bound on the minimum solution

sfo_greedy_splitting: Greedy splitting algorithm for clustering of Zhao et al
2) Maximization:

sfo_polyhedrongreedy: For solving an LP over the submodular polytope

sfo_greedy_lazy: The greedy algorithm for constrained maximization / coverage using lazy evaluations

sfo_greedy_welfare: The greedy algorithm for solving allocation problems

sfo_cover: Greedy coverage algorithm using lazy evaluations

sfo_celf: The CELF algorithm of Leskovec et al. for budgeted maximization
 sfo_ls_lazy: Local search algorithm for maximizing nonnegative submodular functions

sfo_saturate: The SATURATE algorithm of Krause et al. for robust optimization of submodular functions

sfo_max_dca_lazy: The Data Correcting algorithm of Goldengorin et al. for maximizing general (not necessarily nondecreasing) submodular functions

sfo_maxbound: Return an online bound on the maximum solution

sfo_pspiel: pSPIEL algorithm for trading off information and communication cost

sfo_pspiel_orienteering: pSPIEL algorithm for submodular orienteering

sfo_balance: eSPASS algorithm for simultaneous placement and balanced scheduling
3) Miscellaneous

sfo_lovaszext: Computes the Lovasz extension for a submodular function

sfo_mi_cluster: Example clustering algorithm using both maximization and minimization

sfo_pspiel_get_path: Convert a tree into a path using the MST heuristic algorithm

sfo_pspiel_get_cost: Compute the Steiner cost of a tree / path
4) Submodular functions:

sfo_fn_cutfun: Cut function

sfo_fn_detect: Outbreak detection / facility location

sfo_fn_entropy: Entropy of Gaussian random variables

sfo_fn_mi: Gaussian mutual information

sfo_fn_varred: Variance reduction (truncatable, for use in SATURATE)

sfo_fn_example: Twoelement submodular function example from tutorial slides

sfo_fn_iwata: Iwata's test function for testing minimization code

sfo_fn_ising: Energy function for Ising model for image denoising

sfo_fn_residual: For defining residual submodular functions
 sfo_fn_invert: For defining F(A) = F'(VA)F(V)
 sfo_fn_lincomb: For defining linear combinations of submodular functions

sfo_min_norm_point: Fujishige's minimumnormpoint algorithm for minimizing general submodular functions
 Changes to previous version:
 Modified specification of optional parameters (using sfo_opt)
 Added sfo_ls_lazy for maximizing nonnegative submodular functions
 Added sfo_fn_infogain, sfo_fn_lincomb, sfo_fn_invert, ...
 Added additional documentation and more examples
 Now Octave ready
 BibTeX Entry: Download
 Corresponding Paper BibTeX Entry: Download
 Supported Operating Systems: Linux, Macosx, Windows
 Data Formats: Matlab, Octave
 Tags: Matlab, Active Learning, Optimization, Markov Random Fields, Experimental Design, Submodularity
 Archive: download here
Other available revisons

Version Changelog Date 2.0  Modified specification of optional parameters (using sfo_opt)
 Added sfo_ls_lazy for maximizing nonnegative submodular functions
 Added sfo_fn_infogain, sfo_fn_lincomb, sfo_fn_invert, ...
 Added additional documentation and more examples
 Now Octave ready
March 24, 2010, 05:58:23 1.0 Initial Announcement on mloss.org.
July 3, 2009, 20:02:01
Comments
No one has posted any comments yet. Perhaps you'd like to be the first?
Leave a comment
You must be logged in to post comments.