File Exchange

image thumbnail

Submodular Function Optimization

version 1.2 (262 KB) by

This toolbox provides functions for maximizing and minimizing submodular set functions.

42 Downloads

Updated

View License

Matlab Toolbox for Submodular Function Optimization (v 2.0)

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)

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(A\cup B)+F(A\cap 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 minimum-norm-point algorithm for minimizing general submodular functions
* sfo_queyranne: Queyranne's algorithm for minimizing symmetric submodular functions
* sfo_ssp: Submodular-supermodular 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_infogain: Information gain about gaussian random variables
* 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: Two-element 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'(V\A)-F(V)
* sfo_fn_lincomb: For defining linear combinations of submodular functions

If you use the toolbox for your research, please cite
A. Krause. "SFO: A Toolbox for Submodular Function Optimization". Journal of Machine Learning Research (2010).

Comments and Ratings (3)

Manuel Osdoba

Nice toolbox, It saved much time.

User-friendly, thanks

Colorado Reed

Very helpful; thanks!

Updates

1.2

* 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, additional documentation and more examples

1.1

Changes in version 1.00:
Added pSPIEL for informative path planning
Added eSPASS for simultaneous placement and scheduling
New convention for submodular functions (incremental computations, etc.) Much faster!

MATLAB Release
MATLAB 7.9 (R2009b)

Download apps, toolboxes, and other File Exchange content using Add-On Explorer in MATLAB.

» Watch video

sfo/@sfo_fn/

sfo/@sfo_fn_cutfun/

sfo/@sfo_fn_detect/

sfo/@sfo_fn_entropy/

sfo/@sfo_fn_example/

sfo/@sfo_fn_infogain/

sfo/@sfo_fn_invert/

sfo/@sfo_fn_ising/

sfo/@sfo_fn_iwata/

sfo/@sfo_fn_lincomb/

sfo/@sfo_fn_mi/

sfo/@sfo_fn_residual/

sfo/@sfo_fn_trunc/

sfo/@sfo_fn_varred/

sfo/@sfo_fn_varred_trunc/

sfo/@sfo_fn_welfare/

sfo/@sfo_fn_wrapper/

sfo/private/

sfo/