Submodular Function Optimization

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

Matlab Toolbox for Submodular Function Optimization (v 2.0)

By Andreas Krause ([e-mail]).
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).