LogisticsReviewPartial order of extreme points SFMScratchSummaryLogistics Review Partial order of extreme points → 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 17 - May 27th, 2011Prof. Jeff Bilmes EE595A/Spr 2011/Submodular Functions – Lecture 17 - May 27th, 2011 page 1Logistics Review Partial order of extreme points → SFM Scratch SummaryAnnouncementsLast lecture, and final presentations, will take place Thursday, June9th, from 3-7:30pm. The lecture will be from 3:00-5:00pm, and thefinal presentations will be from 5:00-7:30pm. Please bring dinner.Prof. Jeff Bilmes EE595A/Spr 2011/Submodular Functions – Lecture 17 - May 27th, 2011 page 2(5/27/2011: Note: I didn't have my tablet for today's lecture, so I made annotations using the popup tool in acrobat. A few of the figures I drew on the black board were photographed and included in the "scratch" pages at the end of this lecture).Logistics Review Partial order of extreme points → 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. +polymatroid props.L13 (5/13): More polymatroids, startlatticesL14 (5/18): lattices/submodularL15 (5/20): lattices, → SFM.L16 (5/25): → SFML17 (5/27):L18 (6/1):L19 (6/3):L20: (6/9): 3-7:30pm (EEB-303)?Prof. Jeff Bilmes EE595A/Spr 2011/Submodular Functions – Lecture 17 - May 27th, 2011 page 3Logistics Review Partial order of extreme points → SFM Scratch Summarydep and partial orderConsider x ∈ Pf, and consider the following setDEP(x) = {dep(x, e) : e ∈ sat(x)} (1)So DEP(x) is a set of sets, each element of DEP(x) is the dep(x, e)valuation for some e ∈ sat(x).Moreover, define a partial order on DEP(x) as follows: ifA, B ∈ DEP(x), then A  B iff A ⊆ B.We’re going to use this partial order to define a partial order on allelements of sat(x).Now recall D(x) = {A : x(A) = f (A)} forms a distributive lattice.What is the natural partial order?Prof. Jeff Bilmes EE595A/Spr 2011/Submodular Functions – Lecture 17 - May 27th, 2011 page 4Logistics Review Partial order of extreme points → SFM Scratch Summarydep and partial orderConsider x ∈ Pf, and consider the following setDEP(x) = {dep(x, e) : e ∈ sat(x)} (1)So DEP(x) is a set of sets, each element of DEP(x) is the dep(x, e)valuation for some e ∈ sat(x).Moreover, define a partial order on DEP(x) as follows: ifA, B ∈ DEP(x), then A  B iff A ⊆ B.We’re going to use this partial order to define a partial order on allelements of sat(x).Now recall D(x) = {A : x(A) = f (A)} forms a distributive lattice.What is the natural partial order?Prof. Jeff Bilmes EE595A/Spr 2011/Submodular Functions – Lecture 17 - May 27th, 2011 page 4Logistics Review Partial order of extreme points → SFM Scratch Summarydep and partial orderConsider x ∈ Pf, and consider the following setDEP(x) = {dep(x, e) : e ∈ sat(x)} (1)So DEP(x) is a set of sets, each element of DEP(x) is the dep(x, e)valuation for some e ∈ sat(x).Moreover, define a partial order on DEP(x) as follows: ifA, B ∈ DEP(x), then A  B iff A ⊆ B.We’re going to use this partial order to define a partial order on allelements of sat(x).Now recall D(x) = {A : x(A) = f (A)} forms a distributive lattice.What is the natural partial order?Prof. Jeff Bilmes EE595A/Spr 2011/Submodular Functions – Lecture 17 - May 27th, 2011 page 4Logistics Review Partial order of extreme points → SFM Scratch Summarydep and partial orderConsider x ∈ Pf, and consider the following setDEP(x) = {dep(x, e) : e ∈ sat(x)} (1)So DEP(x) is a set of sets, each element of DEP(x) is the dep(x, e)valuation for some e ∈ sat(x).Moreover, define a partial order on DEP(x) as follows: ifA, B ∈ DEP(x), then A  B iff A ⊆ B.We’re going to use this partial order to define a partial order on allelements of sat(x).Now recall D(x) = {A : x(A) = f (A)} forms a distributive lattice.What is the natural partial order?Prof. Jeff Bilmes EE595A/Spr 2011/Submodular Functions – Lecture 17 - May 27th, 2011 page 4Logistics Review Partial order of extreme points → SFM Scratch Summarydep and partial orderConsider x ∈ Pf, and consider the following setDEP(x) = {dep(x, e) : e ∈ sat(x)} (1)So DEP(x) is a set of sets, each element of DEP(x) is the dep(x, e)valuation for some e ∈ sat(x).Moreover, define a partial order on DEP(x) as follows: ifA, B ∈ DEP(x), then A  B iff A ⊆ B.We’re going to use this partial order to define a partial order on allelements of sat(x).Now recall D(x) = {A : x(A) = f (A)} forms a distributive lattice.What is the natural partial order?Prof. Jeff Bilmes EE595A/Spr 2011/Submodular Functions – Lecture 17 - May 27th, 2011 page 4Logistics Review Partial order of extreme points → SFM Scratch Summarydep and partial orderNow in any distributive lattice L, consider its join-irreducibles J(i.e., any element A ∈ J can’t be represented as a join of any othertwo elements in L).We saw that if the lattice has length n, then J will have exactly nelements (in the Boolean case, these are atoms/ground elements),and each element in J is partially ordered by the lattice partialorder.Moreover, we saw any element can be “generated” by joining thejoin-irreducible elements.Prof. Jeff Bilmes EE595A/Spr 2011/Submodular Functions – Lecture 17 - May 27th, 2011 page 5Logistics Review Partial order of extreme points → SFM Scratch Summarydep and partial orderNow any element in DEP(x) (for x extreme) can’t be represented bythe join of two other elements in DEP(x), since the minimal tightsets containing e would not be generated by merging two minimaltight sets containing, say, a, and b, where all of a, b, c are unequal.Thus, considering D(x) as a distributed lattice, then DEP(x) are thejoin-irreducibles.And the order  defined earlier is the natural order w.r.t. this latticeand its join-irreducibles.Prof. Jeff Bilmes EE595A/Spr 2011/Submodular Functions – Lecture 17 - May 27th, 2011 page 6Logistics Review Partial order of extreme points → SFM Scratch Summarydep and partial orderLet x ∈ Pfagain be an extreme point, and let it be generated by anordering