| Description |
Matlab Toolbox for Submodular Function Optimization (v 1.00)
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).
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_sssp: 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_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: 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
Here is an overview reference:
A. Krause, C. Guestrin. Near-optimal Observation Selection Using Submodular Functions. Survey paper, Proc. of 22nd Conference on Artificial Intelligence (AAAI) 2007 -- Nectar Track
|
| Other Files |
SFO/@sfo_fn/,
SFO/@sfo_fn/dec.m,
SFO/@sfo_fn/get.m,
SFO/@sfo_fn/inc.m,
SFO/@sfo_fn/set.m,
SFO/@sfo_fn/sfo_fn.m,
SFO/@sfo_fn/subsref.m,
SFO/@sfo_fn/trunc.m,
SFO/@sfo_fn_cutfun/,
SFO/@sfo_fn_cutfun/sfo_fn_cutfun.m,
SFO/@sfo_fn_detect/,
SFO/@sfo_fn_detect/inc.m,
SFO/@sfo_fn_detect/init.m,
SFO/@sfo_fn_detect/sfo_fn_detect.m,
SFO/@sfo_fn_entropy/,
SFO/@sfo_fn_entropy/inc.m,
SFO/@sfo_fn_entropy/init.m,
SFO/@sfo_fn_entropy/sfo_fn_entropy.m,
SFO/@sfo_fn_example/,
SFO/@sfo_fn_example/sfo_fn_example.m,
SFO/@sfo_fn_ising/,
SFO/@sfo_fn_ising/sfo_fn_ising.m,
SFO/@sfo_fn_iwata/,
SFO/@sfo_fn_iwata/sfo_fn_iwata.m,
SFO/@sfo_fn_mi/,
SFO/@sfo_fn_mi/inc.m,
SFO/@sfo_fn_mi/init.m,
SFO/@sfo_fn_mi/sfo_fn_mi.m,
SFO/@sfo_fn_residual/,
SFO/@sfo_fn_residual/dec.m,
SFO/@sfo_fn_residual/inc.m,
SFO/@sfo_fn_residual/init.m,
SFO/@sfo_fn_residual/sfo_fn_residual.m,
SFO/@sfo_fn_trunc/,
SFO/@sfo_fn_trunc/dec.m,
SFO/@sfo_fn_trunc/inc.m,
SFO/@sfo_fn_trunc/init.m,
SFO/@sfo_fn_trunc/sfo_fn_trunc.m,
SFO/@sfo_fn_varred/,
SFO/@sfo_fn_varred/inc.m,
SFO/@sfo_fn_varred/init.m,
SFO/@sfo_fn_varred/sfo_fn_varred.m,
SFO/@sfo_fn_varred/trunc.m,
SFO/@sfo_fn_varred_trunc/,
SFO/@sfo_fn_varred_trunc/inc.m,
SFO/@sfo_fn_varred_trunc/init.m,
SFO/@sfo_fn_varred_trunc/sfo_fn_varred_trunc.m,
SFO/@sfo_fn_welfare/,
SFO/@sfo_fn_welfare/inc.m,
SFO/@sfo_fn_welfare/init.m,
SFO/@sfo_fn_welfare/partition.m,
SFO/@sfo_fn_welfare/sfo_fn_welfare.m,
SFO/@sfo_fn_wrapper/,
SFO/@sfo_fn_wrapper/init.m,
SFO/@sfo_fn_wrapper/sfo_fn_wrapper.m,
SFO/html/,
SFO/html/sfo_tutorial_pub.png,
SFO/html/sfo_tutorial_pub_01.png,
SFO/html/sfo_tutorial_pub_02.png,
SFO/html/sfo_tutorial_pub_03.png,
SFO/html/sfo_tutorial_pub_04.png,
SFO/html/sfo_tutorial_pub_05.png,
SFO/html/sfo_tutorial_pub_06.png,
SFO/html/sfo_tutorial_pub_07.png,
SFO/html/sfo_tutorial_pub_08.png,
SFO/html/sfo_tutorial_pub_09.png,
SFO/html/sfo_tutorial_pub_10.png,
SFO/html/sfo_tutorial_pub_11.png,
SFO/html/sfo_tutorial_pub_12.png,
SFO/html/sfo_tutorial_pub_eq129486.png,
SFO/html/sfo_tutorial_pub_eq190777.png,
SFO/html/sfo_tutorial_pub_eq22457.png,
SFO/html/sfo_tutorial_pub_eq22793.png,
SFO/html/sfo_tutorial_pub_eq22919.png,
SFO/html/sfo_tutorial_pub_eq2328.png,
SFO/html/sfo_tutorial_pub_eq2330.png,
SFO/html/sfo_tutorial_pub_eq23872.png,
SFO/html/sfo_tutorial_pub_eq24352.png,
SFO/html/sfo_tutorial_pub_eq25884.png,
SFO/html/sfo_tutorial_pub_eq40729.png,
SFO/html/sfo_tutorial_pub_eq5967.png,
SFO/html/sfo_tutorial_pub_eq66030.png,
SFO/html/sfo_tutorial_pub_eq84272.png,
SFO/merced_data.mat,
SFO/private/,
SFO/private/sfo_pspiel_dijkstra.m,
SFO/private/sfo_pspiel_fixed_r.m,
SFO/private/sfo_pspiel_get_r_range.m,
SFO/private/sfo_pspiel_kmst.m,
SFO/private/sfo_pspiel_mst.m,
SFO/private/sfo_pspiel_pd.m,
SFO/private/sfo_pspiel_sp.m,
SFO/readme.txt,
SFO/sfo_balance.m,
SFO/sfo_celf.m,
SFO/sfo_charvector.m,
SFO/sfo_chol_downdate.m,
SFO/sfo_chol_update.m,
SFO/sfo_cover.m,
SFO/sfo_dist.m,
SFO/sfo_eval_maxvar.m,
SFO/sfo_greedy_lazy.m,
SFO/sfo_greedy_splitting.m,
SFO/sfo_greedy_welfare.m,
SFO/sfo_inv_downdate.m,
SFO/sfo_inv_update.m,
SFO/sfo_logdet.m,
SFO/sfo_lovaszext.m,
SFO/sfo_max_dca_lazy.m,
SFO/sfo_max_delta_lazy.m,
SFO/sfo_maxbound.m,
SFO/sfo_maxbound_welfare.m,
SFO/sfo_mi_cluster.m,
SFO/sfo_min_norm_point.m,
SFO/sfo_minbound.m,
SFO/sfo_plot_subgraph.m,
SFO/sfo_polyhedrongreedy.m,
SFO/sfo_pspiel.m,
SFO/sfo_pspiel_get_cost.m,
SFO/sfo_pspiel_get_path.m,
SFO/sfo_pspiel_orienteering.m,
SFO/sfo_queyranne.m,
SFO/sfo_s_t_mincut.m,
SFO/sfo_saturate.m,
SFO/sfo_setdiff_fast.m,
SFO/sfo_sssp.m,
SFO/sfo_tutorial.m,
SFO/sfo_tutorial_pub.m,
SFO/sfo_unique_fast.m
|
