Introduction to Submodularity Reading Group's Greedy Algorithm
In this reading group, we delve into the concepts of submodularity using various examples such as incidence vectors and fractional vectors. The focus is on understanding the greedy algorithm, maximizing values based on specified criteria, and determining optimal values. Through visual aids, we explore the implications and applications of these mathematical concepts.
Download Presentation
Please find below an Image/Link to download the presentation.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author.If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.
You are allowed to download the files provided on this website for personal or commercial use, subject to the condition that they are used lawfully. All files are the property of their respective owners.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author.
E N D
Presentation Transcript
Submodularity Reading Group Lov sz Extension M. Pawan Kumar http://www.robots.ox.ac.uk/~oval/
Greedy Algorithm max wTx x EPf Order s1,s2, ,sn S such that w(si) w(si+1) Define Ui = {s1,s2,..,si} xGi = f(Ui) f(Ui-1)
Example Incidence Vector Consider S = {1, 2, 3, 4, 5, 6, 7} Define A = {1, 2, 3} Incidence vector vA = [1 1 1 0 0 0 0]T Set w = vA
Greedy Algorithm f({1,2,3}) max wTx Optimal Value? x EPf Order s1,s2, ,sn S such that w(si) w(si+1) Define Ui = {s1,s2,..,si} xGi = f(Ui) f(Ui-1)
Example Incidence Vector Consider S = {1, 2, 3, 4, 5, 6, 7} Define A = {3, 5, 7} Incidence vector vA = [0 0 1 0 1 0 1]T Set w = vA
Greedy Algorithm f({3,5,7}) max wTx Optimal Value? x EPf Order s1,s2, ,sn S such that w(si) w(si+1) Define Ui = {s1,s2,..,si} xGi = f(Ui) f(Ui-1)
Greedy Algorithm max wTx x EPf Order s1,s2, ,sn S such that w(si) w(si+1) Define Ui = {s1,s2,..,si} xGi = f(Ui) f(Ui-1) In general, if w = vA then optimal value = f(A)
Example Fractional Vector Consider S = {1, 2, 3, 4, 5, 6, 7} Define A = {1, 2, 3} Fractional vector wA = [0.9 0.7 0.6 0 0 0 0]T We restrict ourselves to values in [0,1] Set w = wA
Greedy Algorithm max wTx Optimal Value? x EPf Order s1,s2, ,sn S such that w(si) w(si+1) Define Ui = {s1,s2,..,si} xGi = f(Ui) f(Ui-1) 0.2*f({1}) + 0.1*f({1,2})+0.6*f({1,2,3}) Notice that 0.2+0.1+0.6 = 0.9
Example Fractional Vector Consider S = {1, 2, 3, 4, 5, 6, 7} Define A = {3, 5, 7} Fractional vector wA = [0 0 0.8 0 0.7 0 0.5]T We restrict ourselves to values in [0,1] Set w = wA
Greedy Algorithm max wTx Optimal Value? x EPf Order s1,s2, ,sn S such that w(si) w(si+1) Define Ui = {s1,s2,..,si} xGi = f(Ui) f(Ui-1) 0.1*f({3}) + 0.2*f({3,5})+0.5*f({3,5,7}) Notice that 0.1+0.2+0.5 = 0.8
Greedy Algorithm Lov sz Extension L(w) max wTx x EPf Order s1,s2, ,sn S such that w(si) w(si+1) Define Ui = {s1,s2,..,si} xGi = f(Ui) f(Ui-1) In general, convex combination A S aAf(A) Coefficients aA [0,1] and A S aA 1
An Interesting Optimization Problem min L(w) w [0,1]|S| Non-positive optimum value? Yes, f(null) = 0 Convex? Yes, pointwise max of linear functions
An Interesting Optimization Problem min L(w) w [0,1]|S| Integer optimum solution? Proof by contradiction In general, convex combination A S aAf(A) Pick A* = argminA f(A) We want aA* = 1 w = vA* Incidence vector of A*
An Interesting Optimization Problem min L(w) w [0,1]|S| Integer optimum solution In fact, equivalent to submodular minimization SFM via convex programming
