LogisticsReviewTowards Submodular Function Minimization (SFM)On PolymatroidsLovász extensionScratchSummaryLogistics Review Towards Submodular Function Minimization (SFM) On Polymatroids Lov´asz extension Scratch SummaryEE595A – Submodular functions, their optimizationand applications – Spring 2011Prof. Jeff BilmesUniversity of Washington, SeattleDepartment of Electrical EngineeringSpring Quarter, 2011http://ssli.ee.washington.edu/~bilmes/ee595a_spring_2011/Lecture 11 - May 6th, 2011Prof. Jeff Bilmes EE595A/Spr 2011/Submodular Functions – Lecture 11 - May 6th, 2011 page 1Logistics Review Towards Submodular Function Minimization (SFM) On Polymatroids Lov´asz extension Scratch SummaryAnnouncementsOn Final projects. One single page final project proposals (revisionone) are due today at 6:00pm.Again, all submissions must be done electronically, via our drop box.See the linkhttps://catalyst.uw.edu/collectit/dropbox/bilmes/14888,or look at the homework on the web page.Email me and/or stop by office hours for ideas. The proposals nextFriday are non-binding (you can change your mind later) but youshould start thinking about project proposals now.Ideal proposal would, say, lead to a NIPS paper in June and berelated to submodularity.Prof. Jeff Bilmes EE595A/Spr 2011/Submodular Functions – Lecture 11 - May 6th, 2011 page 2Logistics Review Towards Submodular Function Minimization (SFM) On Polymatroids Lov´asz extension Scratch SummaryClass Road MapWe need to find one makeup lectures this term.L1 (3/30):L2 (4/1):L3 (4/6):L4 (4/8):L5 (4/13):L6 (4/15):L7 (4/20):L8 (4/27):L9 (4/29):L10 (5/4):L11 (5/6): On SFM, polymatroidmember & greedy, Lov´asz ext.L12 (5/11):L13 (5/13):L14 (5/18):L15 (5/20):L16 (5/25):L17 (5/27):L18 (6/1):L19 (6/3):L20: (6/?): (need to findtime/date/place).Prof. Jeff Bilmes EE595A/Spr 2011/Submodular Functions – Lecture 11 - May 6th, 2011 page 3Logistics Review Towards Submodular Function Minimization (SFM) On Polymatroids Lov´asz extension Scratch SummaryMost violated inequality problemConsiderPr=nx ∈ RE: x ≥ 0, x(A) ≤ rM(A), ∀A ⊆ Eo(1)We saw before that Pr= Pind. set.Suppose we have any x ∈ RE+such that x 6∈ Pr.The most violated inequality when x is considered w.r.t. Prcorresponds to the set A that maximizes x(A) − rM(A), i.e.,max {x(A) − rM(A) : A ⊆ E}.This corresponds to min {rM(A) + x(E \ A) : A ⊆ E} since x ismodular and x(E \ A) = x(E ) − x(A).More importantly, min {rM(A) + x(E \ A) : A ⊆ E} a form ofsubmodular function minimization, namelymin {rM(A) − x(A) : A ⊆ E } for a submodular function consisting ofa difference of matroid rank and modular (so no longer nec.monotone, nor positive).Prof. Jeff Bilmes EE595A/Spr 2011/Submodular Functions – Lecture 11 - May 6th, 2011 page 4Logistics Review Towards Submodular Function Minimization (SFM) On Polymatroids Lov´asz extension Scratch SummaryAugmenting path theoremThus, we consider x ∈ R+.We’ve constructed the auxiliary s, t graph G as previouslymentioned, where for each e ∈ E, we’ve got a node in G, along withadditional nodes (and edges) s, t.We maintain y =Pi∈Jλi1Ii≤ x and thus y ∈ Pind. set.From this, we can obtain the following theorem (most violatedinequality, then, is given by {e ∈ E : x(e) > y(e)}).Theorem 2.1If there is a directed path from s to t in G , then there exists y0∈ P withy < y0≤ x, with y0(E) > y(E ). If there is no such path, then thereexists a set A ⊆ E s.t. y (A) = r(A) and y(E \ A) = x(E \ A).Prof. Jeff Bilmes EE595A/Spr 2011/Submodular Functions – Lecture 11 - May 6th, 2011 page 5Logistics Review Towards Submodular Function Minimization (SFM) On Polymatroids Lov´asz extension Scratch SummaryAugmenting path theoremThus, we consider x ∈ R+.We’ve constructed the auxiliary s, t graph G as previouslymentioned, where for each e ∈ E, we’ve got a node in G, along withadditional nodes (and edges) s, t.We maintain y =Pi∈Jλi1Ii≤ x and thus y ∈ Pind. set.From this, we can obtain the following theorem (most violatedinequality, then, is given by {e ∈ E : x(e) > y(e)}).Theorem 2.1If there is a directed path from s to t in G , then there exists y0∈ P withy < y0≤ x, with y0(E) > y(E ). If there is no such path, then thereexists a set A ⊆ E s.t. y (A) = r(A) and y(E \ A) = x(E \ A).Prof. Jeff Bilmes EE595A/Spr 2011/Submodular Functions – Lecture 11 - May 6th, 2011 page 5Logistics Review Towards Submodular Function Minimization (SFM) On Polymatroids Lov´asz extension Scratch SummaryAugmenting path theoremThus, we consider x ∈ R+.We’ve constructed the auxiliary s, t graph G as previouslymentioned, where for each e ∈ E, we’ve got a node in G, along withadditional nodes (and edges) s, t.We maintain y =Pi∈Jλi1Ii≤ x and thus y ∈ Pind. set.From this, we can obtain the following theorem (most violatedinequality, then, is given by {e ∈ E : x(e) > y(e)}).Theorem 2.1If there is a directed path from s to t in G , then there exists y0∈ P withy < y0≤ x, with y0(E) > y(E ). If there is no such path, then thereexists a set A ⊆ E s.t. y (A) = r(A) and y(E \ A) = x(E \ A).Prof. Jeff Bilmes EE595A/Spr 2011/Submodular Functions – Lecture 11 - May 6th, 2011 page 5Logistics Review Towards Submodular Function Minimization (SFM) On Polymatroids Lov´asz extension Scratch SummaryAugmenting path theoremThus, we consider x ∈ R+.We’ve constructed the auxiliary s, t graph G as previouslymentioned, where for each e ∈ E, we’ve got a node in G, along withadditional nodes (and edges) s, t.We maintain y =Pi∈Jλi1Ii≤ x and thus y ∈ Pind. set.From this, we can obtain the following theorem (most violatedinequality, then, is given by {e ∈ E : x(e) > y(e)}).Theorem 2.1If there is a directed path from s to t in G , then there exists y0∈ P withy < y0≤ x, with y0(E) > y(E ). If there is no such path, then thereexists a set A ⊆ E s.t. y (A) = r(A) and y(E \ A) = x(E \ A).Prof. Jeff Bilmes EE595A/Spr 2011/Submodular Functions – Lecture 11 - May 6th, 2011 page 5Logistics Review Towards Submodular Function Minimization (SFM) On Polymatroids Lov´asz extension Scratch SummaryAugmenting path theoremThus, we consider x ∈ R+.We’ve constructed the auxiliary s, t graph G as previouslymentioned, where for each e ∈ E, we’ve got a node in G, along withadditional nodes (and edges) s, t.We maintain y =Pi∈Jλi1Ii≤ x and thus y ∈ Pind. set.From this, we can obtain the following theorem (most violatedinequality,