LogisticsReviewMatroid Partition w. FlowsMost Violated Ineq.Towards SFMScratchSummaryLogistics Review Matroid Partition w. Flows Most Violated Ineq. Towards SFM 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 10 - May 4th, 2011Prof. Jeff Bilmes EE595A/Spr 2011/Submodular Functions – Lecture 10 - May 4th, 2011 page 1Logistics Review Matroid Partition w. Flows Most Violated Ineq. Towards SFM Scratch SummaryAnnouncementsOn Final projects. One single page final project proposals (revisionone) are due next Friday (one week from 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 10 - May 4th, 2011 page 2Logistics Review Matroid Partition w. Flows Most Violated Ineq. Towards SFM 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 10 - May 4th, 2011 page 3Logistics Review Matroid Partition w. Flows Most Violated Ineq. Towards SFM 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 10 - May 4th, 2011 page 3Logistics Review Matroid Partition w. Flows Most Violated Ineq. Towards SFM 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 10 - May 4th, 2011 page 3Logistics Review Matroid Partition w. Flows Most Violated Ineq. Towards SFM 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 10 - May 4th, 2011 page 3Logistics Review Matroid Partition w. Flows Most Violated Ineq. Towards SFM 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 10 - May 4th, 2011 page 3Logistics Review Matroid Partition w. Flows Most Violated Ineq. Towards SFM 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 10 - May 4th, 2011 page 3Logistics Review