LogisticsReviewDistributive LatticesModular LatticesSubmodular LatticesLatticeExtremeScratchSummaryLogistics Review Distributive Lattices Modular Lattices Submodular Lattices Lattice Extreme 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 15 - May 19th, 2011Prof. Jeff Bilmes EE595A/Spr 2011/Submodular Functions – Lecture 15 - May 19th, 2011 page 1Logistics Review Distributive Lattices Modular Lattices Submodular Lattices Lattice Extreme Scratch SummaryAnnouncementsHomework 2 is due tonight at 11:45pm. All things in lecturesmarked “exercise”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.Last lecture, all annotations apparently lost (unless you are a PDFexpert). Please email me any typos you discover in lecture 14!!Prof. Jeff Bilmes EE595A/Spr 2011/Submodular Functions – Lecture 15 - May 19th, 2011 page 2Logistics Review Distributive Lattices Modular Lattices Submodular Lattices Lattice Extreme 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, → SVML16 (5/25):L17 (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 15 - May 19th, 2011 page 3Logistics Review Distributive Lattices Modular Lattices Submodular Lattices Lattice Extreme Scratch SummaryPolymatroidsTheorem 2.1For a given ordering E = (e1, . . . , em) of E and a given Eiand xgenerated by Eiusing the greedy procedure, then x is an extreme pointof PfTheorem 2.2If x is an extreme point of Pfand B ⊆ E is given such thatsupp(x) ⊆ B ⊆ sat(x), then x is generated using greedy by someordering of B.Prof. Jeff Bilmes EE595A/Spr 2011/Submodular Functions – Lecture 15 - May 19th, 2011 page 4Logistics Review Distributive Lattices Modular Lattices Submodular Lattices Lattice Extreme Scratch SummaryPartially ordered setA partially ordered set (poset) is a set of objects with an order.In a poset, for any x, y, z ∈ V the following conditions hold (bydefinition):For all x, x  x. (Reflexive) (P1.)If x  y and y  x, then x = y (Antisymmetriy) (P2.)If x  y and y  z, then x  z. (Transitivity) (P3.)The order n(P) of a poset P is meant the (cardinal) number of itselements.Prof. Jeff Bilmes EE595A/Spr 2011/Submodular Functions – Lecture 15 - May 19th, 2011 page 5Logistics Review Distributive Lattices Modular Lattices Submodular Lattices Lattice Extreme Scratch SummaryPartially ordered setA partially ordered set (poset) is a set of objects with an order.In a poset, for any x, y, z ∈ V the following conditions hold (bydefinition):For all x, x  x. (Reflexive) (P1.)If x  y and y  x, then x = y (Antisymmetriy) (P2.)If x  y and y  z, then x  z. (Transitivity) (P3.)The order n(P) of a poset P is meant the (cardinal) number of itselements.Prof. Jeff Bilmes EE595A/Spr 2011/Submodular Functions – Lecture 15 - May 19th, 2011 page 5Logistics Review Distributive Lattices Modular Lattices Submodular Lattices Lattice Extreme Scratch SummaryPartially ordered setA partially ordered set (poset) is a set of objects with an order.In a poset, for any x, y, z ∈ V the following conditions hold (bydefinition):For all x, x  x. (Reflexive) (P1.)If x  y and y  x, then x = y (Antisymmetriy) (P2.)If x  y and y  z, then x  z. (Transitivity) (P3.)The order n(P) of a poset P is meant the (cardinal) number of itselements.Prof. Jeff Bilmes EE595A/Spr 2011/Submodular Functions – Lecture 15 - May 19th, 2011 page 5Logistics Review Distributive Lattices Modular Lattices Submodular Lattices Lattice Extreme Scratch SummaryPartially ordered setxy1243612∅{a,b,c}{a,b}{a}{b}{c}{a,c}{b,c}(A)(B)(C)(D) (E)(F)(G) (H)000 0 01 11 11a aaaabb bbbcccccd ddeef∅{a,b,c} {a,b,d} {a,c,d} {b,c,d}{a,b,c,d}{a} {b} {c} {d}{a,b} {a,c} {a,d} {b,c} {b,d} {c,d}(C2)(C3)123414/231/234124/313/24123/4134/212/341/23/414/2/31/24/313/2/412/3/41/2/341/2/3/4Hasse-diagram: We can draw a poset using a graph where eachx ∈ V is a node, and if x @ y we draw y directly above x with aconnecting edge, but no other edges.Theorem 2.3Every non-empty finite subset X ⊆ V has a minimal (and maximal)element.Prof. Jeff Bilmes EE595A/Spr 2011/Submodular Functions – Lecture 15 - May 19th, 2011 page 6Logistics Review Distributive Lattices Modular Lattices Submodular Lattices Lattice Extreme Scratch SummaryPartially ordered setxy1243612∅{a,b,c}{a,b}{a}{b}{c}{a,c}{b,c}(A)(B)(C)(D) (E)(F)(G) (H)000 0 01 11 11a aaaabb bbbcccccd ddeef∅{a,b,c} {a,b,d} {a,c,d} {b,c,d}{a,b,c,d}{a} {b} {c} {d}{a,b} {a,c} {a,d} {b,c} {b,d} {c,d}(C2)(C3)123414/231/234124/313/24123/4134/212/341/23/414/2/31/24/313/2/412/3/41/2/341/2/3/4Hasse-diagram: We can draw a poset using a graph where eachx ∈ V is a node, and if x @ y we draw y directly above x with aconnecting edge, but no other edges.Theorem 2.3Every non-empty finite subset X ⊆ V has a minimal (and maximal)element.Prof. Jeff Bilmes EE595A/Spr 2011/Submodular Functions – Lecture 15 - May 19th, 2011 page 6Logistics Review Distributive Lattices Modular Lattices Submodular Lattices Lattice Extreme Scratch SummaryPartially ordered setxy1243612∅{a,b,c}{a,b}{a}{b}{c}{a,c}{b,c}(A)(B)(C)(D) (E)(F)(G) (H)000 0 01 11 11a aaaabb bbbcccccd ddeef∅{a,b,c} {a,b,d} {a,c,d} {b,c,d}{a,b,c,d}{a} {b} {c} {d}{a,b} {a,c} {a,d} {b,c} {b,d} {c,d}(C2)(C3)123414/231/234124/313/24123/4134/212/341/23/414/2/31/24/313/2/412/3/41/2/341/2/3/4Hasse-diagram: We can draw a poset using a graph where eachx ∈ V is a node, and if x @ y we draw y directly above x with aconnecting edge, but no other edges.Theorem 2.3Every non-empty finite subset X ⊆ V has a minimal (and maximal)element.Prof. Jeff Bilmes EE595A/Spr 2011/Submodular Functions – Lecture 15 - May 19th, 2011 page 6Logistics Review Distributive Lattices Modular Lattices Submodular Lattices Lattice Extreme Scratch SummaryPartially ordered setTheorem