Matlab toolbox for submodular function optimizationhttp://mloss.orgUpdates and additions to Matlab toolbox for submodular function optimizationenWed, 07 Apr 2010 09:53:40 -0000Matlab toolbox for submodular function optimization 2.0<html><p>Matlab Toolbox for Submodular Function Optimization </p> <p>By Andreas Krause (<br /> Slides, videos and detailed references available at<br /> </p> <p>Tested in MATLAB 7.0.1 (R14), 7.2.0 (R2006a), 7.4.0 (R2007a, MAC), 7.9.0 (MAC). </p> <p>A note on Octave compatibility: </p> <p>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 </p> <p>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<br /> </p> <p>$$F(A)+F(B)geq F(Acup B)+F(Acap B)$$<br /> </p> <p>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<br /> </p> <p>Some information on conventions:<br /> </p> <p>All algorithms will use function objects (see sfo_tutorial.m for examples). For example, to measure variance reduction in a Gaussian model, call<br /> F = sfo_fn_varred(sigma,V)<br /> 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.<br /> </p> <p>Implemented algorithms:<br /> </p> <p>1) Minimization:<br /> </p> <ul> <li> sfo_min_norm_point: Fujishige's minimum-norm-point algorithm for minimizing general submodular functions<br /> </li> <li> sfo_queyranne: Queyranne's algorithm for minimizing symmetric submodular functions<br /> </li> <li> sfo_sssp: Submodular-supermodular procedure of Narasimhan &amp; Bilmes for minimizing the difference of two submodular functions<br /> </li> <li> sfo_s_t_min_cut: For solving min F(A) s.t. s in A, t not in A<br /> </li> <li> sfo_minbound: Return an online bound on the minimum solution<br /> </li> <li> sfo_greedy_splitting: Greedy splitting algorithm for clustering of Zhao et al<br /> </li> </ul> <p>2) Maximization:<br /> </p> <ul> <li> sfo_polyhedrongreedy: For solving an LP over the submodular polytope<br /> </li> <li> sfo_greedy_lazy: The greedy algorithm for constrained maximization / coverage using lazy evaluations<br /> </li> <li> sfo_greedy_welfare: The greedy algorithm for solving allocation problems<br /> </li> <li> sfo_cover: Greedy coverage algorithm using lazy evaluations<br /> </li> <li> sfo_celf: The CELF algorithm of Leskovec et al. for budgeted maximization<br /> </li> <li> sfo_ls_lazy: Local search algorithm for maximizing nonnegative submodular functions </li> <li> sfo_saturate: The <em>SATURATE</em> algorithm of Krause et al. for robust optimization of submodular functions<br /> </li> <li> sfo_max_dca_lazy: The Data Correcting algorithm of Goldengorin et al. for maximizing general (not necessarily nondecreasing) submodular functions<br /> </li> <li> sfo_maxbound: Return an online bound on the maximum solution<br /> </li> <li> sfo_pspiel: pSPIEL algorithm for trading off information and communication cost<br /> </li> <li> sfo_pspiel_orienteering: pSPIEL algorithm for submodular orienteering<br /> </li> <li> sfo_balance: eSPASS algorithm for simultaneous placement and balanced scheduling<br /> </li> </ul> <p>3) Miscellaneous<br /> </p> <ul> <li> sfo_lovaszext: Computes the Lovasz extension for a submodular function<br /> </li> <li> sfo_mi_cluster: Example clustering algorithm using both maximization and minimization<br /> </li> <li> sfo_pspiel_get_path: Convert a tree into a path using the MST heuristic algorithm<br /> </li> <li> sfo_pspiel_get_cost: Compute the Steiner cost of a tree / path<br /> </li> </ul> <p>4) Submodular functions:<br /> </p> <ul> <li> sfo_fn_cutfun: Cut function<br /> </li> <li> sfo_fn_detect: Outbreak detection / facility location<br /> </li> <li> sfo_fn_entropy: Entropy of Gaussian random variables<br /> </li> <li> sfo_fn_mi: Gaussian mutual information<br /> </li> <li> sfo_fn_varred: Variance reduction (truncatable, for use in SATURATE)<br /> </li> <li> sfo_fn_example: Two-element submodular function example from tutorial slides<br /> </li> <li> sfo_fn_iwata: Iwata's test function for testing minimization code<br /> </li> <li> sfo_fn_ising: Energy function for Ising model for image denoising<br /> </li> <li> sfo_fn_residual: For defining residual submodular functions<br /> </li> <li> sfo_fn_invert: For defining F(A) = F'(VA)-F(V) </li> <li> sfo_fn_lincomb: For defining linear combinations of submodular functions </li> </ul></html>Andreas KrauseWed, 07 Apr 2010 09:53:40 -0000 learningoptimizationmarkov random fieldsexperimental designsubmodularity