LogisticsReviewPartial order of extreme pointsScratchSummaryLogistics Review Partial order of extreme points 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 16 - May 25th, 2011Prof. Jeff Bilmes EE595A/Spr 2011/Submodular Functions – Lecture 16 - May 25th, 2011 page 1Logistics Review Partial order of extreme points 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 16 - May 25th, 2011 page 2Logistics Review Partial order of extreme points 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):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 16 - May 25th, 2011 page 3Logistics Review Partial order of extreme points Scratch SummaryDistributive LatticesA lattice is distributive if the aforementioned distributive inequalityis an equality. Note that as mentioned above, the distributiveinequality holds for all lattices, but not with equality.Some lattices are such that the distributive inequality is an equalityeverywhere, and these are called distributive lattices. Only onequality is necessary since:Theorem 2.1In any lattice, the following are equivalent:x ∧ (y ∨ z) = (x ∧ y) ∨ (x ∧ z) ∀x, y , z (1a)x ∨ (y ∧ z) = (x ∨ y) ∧ (x ∨ z) ∀x, y, z (1b)It is important to note the ∀x, y, z since this is not true only forindividual elements. Note moreover that this means that the operators∨ = + and ∧ = · do not form a lattice over R.Prof. Jeff Bilmes EE595A/Spr 2011/Submodular Functions – Lecture 16 - May 25th, 2011 page 4Logistics Review Partial order of extreme points Scratch SummaryDistributive LatticesA lattice is distributive if the aforementioned distributive inequalityis an equality. Note that as mentioned above, the distributiveinequality holds for all lattices, but not with equality.Some lattices are such that the distributive inequality is an equalityeverywhere, and these are called distributive lattices. Only onequality is necessary since:Theorem 2.1In any lattice, the following are equivalent:x ∧ (y ∨ z) = (x ∧ y) ∨ (x ∧ z) ∀x, y, z (1a)x ∨ (y ∧ z) = (x ∨ y) ∧ (x ∨ z) ∀x, y, z (1b)It is important to note the ∀x, y, z since this is not true only forindividual elements. Note moreover that this means that the operators∨ = + and ∧ = · do not form a lattice over R.Prof. Jeff Bilmes EE595A/Spr 2011/Submodular Functions – Lecture 16 - May 25th, 2011 page 4Logistics Review Partial order of extreme points Scratch SummaryDistributive LatticesA lattice is distributive if the aforementioned distributive inequalityis an equality. Note that as mentioned above, the distributiveinequality holds for all lattices, but not with equality.Some lattices are such that the distributive inequality is an equalityeverywhere, and these are called distributive lattices. Only onequality is necessary since:Theorem 2.1In any lattice, the following are equivalent:x ∧ (y ∨ z) = (x ∧ y) ∨ (x ∧ z) ∀x, y, z (1a)x ∨ (y ∧ z) = (x ∨ y) ∧ (x ∨ z) ∀x, y, z (1b)It is important to note the ∀x, y, z since this is not true only forindividual elements. Note moreover that this means that the operators∨ = + and ∧ = · do not form a lattice over R.Prof. Jeff Bilmes EE595A/Spr 2011/Submodular Functions – Lecture 16 - May 25th, 2011 page 4Logistics Review Partial order of extreme points Scratch SummaryDistributive LatticesA lattice is distributive if the aforementioned distributive inequalityis an equality. Note that as mentioned above, the distributiveinequality holds for all lattices, but not with equality.Some lattices are such that the distributive inequality is an equalityeverywhere, and these are called distributive lattices. Only onequality is necessary since:Theorem 2.1In any lattice, the following are equivalent:x ∧ (y ∨ z) = (x ∧ y) ∨ (x ∧ z) ∀x, y, z (1a)x ∨ (y ∧ z) = (x ∨ y) ∧ (x ∨ z) ∀x, y, z (1b)It is important to note the ∀x, y, z since this is not true only forindividual elements. Note moreover that this means that the operators∨ = + and ∧ = · do not form a lattice over R.Prof. Jeff Bilmes EE595A/Spr 2011/Submodular Functions – Lecture 16 - May 25th, 2011 page 4Logistics Review Partial order of extreme points Scratch SummaryModular LatticesWe can strengthen the modular inequality to get what is known asthe modular identity.Definition 2.2 (modular identity)∀x, y , z, If x  z, then x ∨ (y ∧ z) = (x ∨ y) ∧ z. (L5)Clearly any distributive lattice satisfies the modular identity sincewhen x  z we have that x ∨ z = z and from the 2nd of thedistributive lattice equalities (i.e., x ∨ (y ∧ z) = (x ∨ y) ∧ (x ∨ z))we get the modular identity.Easy way to remember. x,y ,z and x ∨y ∧ z=x ∨ y∧ zThe term “modular” comes from abstract algebra, where aR-module is an abstract system that generalizes (R, Rn) (i.e., avector field with scalar multiplication). An R-module ends up beinga lattice that satisfies this identity.Prof. Jeff Bilmes EE595A/Spr 2011/Submodular Functions – Lecture 16 - May 25th, 2011 page 5Logistics Review Partial order of extreme points Scratch SummaryModular LatticesWe can strengthen the modular inequality to get what is known asthe modular identity.Definition 2.2 (modular identity)∀x, y , z, If x  z, then x ∨ (y ∧ z) = (x ∨ y) ∧ z. (L5)Clearly any distributive lattice satisfies the modular identity sincewhen x  z we have that x ∨ z = z and from the 2nd of thedistributive lattice equalities (i.e., x ∨ (y ∧ z) = (x ∨ y) ∧ (x ∨ z))we get the modular identity.Easy way to remember. x,y ,z and x ∨y ∧ z=x ∨ y∧ zThe term