LogisticsReview SFMScratchSummaryLogistics Review → SFM Scratch SummaryEE595A – Submodular functions, their optimization andapplications – Spring 2011Prof. Jeff BilmesUniversity of Washington, SeattleDepartment of Electrical EngineeringSpring Quarter, 2011http://ssli.ee.washington.edu/~bilmes/ee595a_spring_2011/Lecture 18 - June 1st, 2011Prof. Jeff Bilmes EE595A/Spr 2011/Submodular Functions – Lecture 18 - June 1st, 2011 page 1Logistics Review → SFM Scratch SummaryAnnouncementsLast lecture, and final presentations, will take place Thursday, June 9th,from 3-7:30pm. The lecture will be from 3:00-5:00pm, and the finalpresentations will be from 5:00-7:30pm. Please bring dinner.Today: short lecture (due to many deadlines this week).Prof. Jeff Bilmes EE595A/Spr 2011/Submodular Functions – Lecture 18 - June 1st, 2011 page 2Logistics Review → SFM Scratch SummaryClass Road MapWe need to find one makeup lecture 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): Lov´asz ext. + polymatroidprops.L13 (5/13): More polymatroids, startlatticesL14 (5/18): lattices/submodularL15 (5/20): lattices, → SFM.L16 (5/25): → SFML17 (5/27): dep/satL18 (6/1): exchange capacitiesL19 (6/3):L20: (6/9): 3-7:30pm (EEB-303)?Prof. Jeff Bilmes EE595A/Spr 2011/Submodular Functions – Lecture 18 - June 1st, 2011 page 3Logistics Review → SFM Scratch Summarydep and partial orderWe haveTheorem 2.1If x ∈ Pfis an extreme point, then  is a partial order on sat(x) where fora, e ∈ sat(x), the order  is defined by: a  e iff a ∈ dep(x, e).In fact, we have a stronger result that extreme points are characterizedby this construct:Theorem 2.2x ∈ Pfis an extreme point, iff supp(x) ⊆ sat(x) and dep(x, a) 6= dep(x, b)for every pair of distinct points a, b ∈ sat(x).Prof. Jeff Bilmes EE595A/Spr 2011/Submodular Functions – Lecture 18 - June 1st, 2011 page 4Logistics Review → SFM Scratch Summarydep and partial orderWe haveTheorem 2.1If x ∈ Pfis an extreme point, then  is a partial order on sat(x) where fora, e ∈ sat(x), the order  is defined by: a  e iff a ∈ dep(x, e).In fact, we have a stronger result that extreme points are characterizedby this construct:Theorem 2.2x ∈ Pfis an extreme point, iff supp(x) ⊆ sat(x) and dep(x, a) 6= dep(x, b)for every pair of distinct points a, b ∈ sat(x).Prof. Jeff Bilmes EE595A/Spr 2011/Submodular Functions – Lecture 18 - June 1st, 2011 page 4Logistics Review → SFM Scratch Summarydep and partial orderWe haveTheorem 2.1If x ∈ Pfis an extreme point, then  is a partial order on sat(x) where fora, e ∈ sat(x), the order  is defined by: a  e iff a ∈ dep(x, e).In fact, we have a stronger result that extreme points are characterizedby this construct:Theorem 2.2x ∈ Pfis an extreme point, iff supp(x) ⊆ sat(x) and dep(x, a) 6= dep(x, b)for every pair of distinct points a, b ∈ sat(x).Prof. Jeff Bilmes EE595A/Spr 2011/Submodular Functions – Lecture 18 - June 1st, 2011 page 4Logistics Review → SFM Scratch Summarydep and partial orderWe haveTheorem 2.1If x ∈ Pfis an extreme point, then  is a partial order on sat(x) where fora, e ∈ sat(x), the order  is defined by: a  e iff a ∈ dep(x, e).In fact, we have a stronger result that extreme points are characterizedby this construct:Theorem 2.2x ∈ Pfis an extreme point, iff supp(x) ⊆ sat(x) and dep(x, a) 6= dep(x, b)for every pair of distinct points a, b ∈ sat(x).Prof. Jeff Bilmes EE595A/Spr 2011/Submodular Functions – Lecture 18 - June 1st, 2011 page 4Logistics Review → SFM Scratch Summarythe partial order of extreme pointsTheorem 2.3Let x be an extreme point of Pfand  be its partial order. Let B ⊆ E be anordered set. Then B generates x using the greedy algorithm iff we havesupp(x) ⊆ B ⊆ sat(x) and B is compatible with .Corollary 2.4If x is an extreme point of Pfand B ⊆ E is given such thatsupp(x) ⊆ B ⊆ sat(x), then x is generated using greedy by some ordering ofB.Prof. Jeff Bilmes EE595A/Spr 2011/Submodular Functions – Lecture 18 - June 1st, 2011 page 5Logistics Review → SFM Scratch SummaryExtreme point testing and partial order generationinput : Vector x ∈ RE, polymatroid function f on E.output: That x is not extreme point, or if it is, minimal tight sets dep(x, e)for e ∈ sat(x) thus defining . Moreover, dep(x, ej) = Ajfor1 ≤ j ≤ n where n = | sat(x)|.1 j ← 0 ; B ← ∅ ;2 while true do3 j ← j + 1 ;4 if ∃e ∈ E \ B with x(B + e) = f (B + e) then5 B ← B + e; ej← e;6 else7 STOP, if supp(x) ⊆ B then x is extreme, otherwise not.8 Aj← B; k ← j − 1 ;9 while x(Aj− ek) = f (Aj− ek) and k > 0 do10 Aj= Aj− ek; k ← k − 1;Prof. Jeff Bilmes EE595A/Spr 2011/Submodular Functions – Lecture 18 - June 1st, 2011 page 6Logistics Review → SFM Scratch SummaryOn Greedy, and linear programming maxTheorem 2.5Let y ∈ Pfbe an extreme point, and let  be the partial order of y. Letc ∈ RE. Then, y is the solution in:c|y = max {c|x : x ∈ Pf} (1)iff the following three conditions hold:(1) c(e) ≥ 0 for every e ∈ supp(y)(2) c(e) ≤ 0 for every e ∈ E \ sat(y), and(3) For d, e ∈ sat(y) and d  e imply that c(d) ≥ c(e).Prof. Jeff Bilmes EE595A/Spr 2011/Submodular Functions – Lecture 18 - June 1st, 2011 page 7Logistics Review → SFM Scratch SummaryAnother revealing theoremTheorem 2.6Let f be a polymatroid function and suppose that E can be partitioned into(E1, E2, . . . , Ek) such that f (A) =Pki=1f (A ∩ Ei) for all A ⊆ E, and k ismaximum. Then the base polytope Bf= {x ∈ Pf: x(E ) = f (E )} (theE-tight subset of Pf) has dimension |E| − k.Example f with independence between A = {e2, e3} and B = {e1}, i.e.,e1⊥⊥{e2, e3}, with Bfmarked in green.012340123400.511.522.533.54e1e2e3012340123400.511.522.533.54e2e1e3Prof. Jeff Bilmes EE595A/Spr 2011/Submodular Functions – Lecture 18 - June 1st, 2011 page 8Logistics Review → SFM Scratch SummaryBase polytope existence and locationGiven polymatroid function f , the base polytopeBf=x ∈ RE+: x(A) ≤ f (A) ∀A ⊆ E , and x(E ) = f (E)alwaysexists.For any A ⊆ E, we haveBf∩nx ∈ RE+: x(A) = f (A)o6= ∅ (2)In words, Bfintersects all “multi-axis orthogonal” subsets of RE+.Prof. Jeff Bilmes EE595A/Spr 2011/Submodular Functions – Lecture 18 - June 1st, 2011 page 9Logistics Review → SFM Scratch SummaryBase