LogisticsReviewMore Sub FuncsEq DefsSummaryLogistics Review More Sub Funcs Eq Defs SummaryEE595A – Submodular functions, their optimizationand applications – Spring 2011Prof. Jeff BilmesUniversity of Washington, SeattleDepartment of Electrical EngineeringWinter Quarter, 2011http://ee.washington.edu/class/235/2011wtr/index.htmlLecture 2 - April 1st, 2011Prof. Jeff Bilmes EE595A/Spr 2011/Submodular Functions – Lecture 2 - April 1st, 2011 page 1Logistics Review More Sub Funcs Eq Defs SummaryAnnouncementsWeekly Office Hours: Wednesdays, 12:30-1:30pm, 10 minutes afterclass on Wednesdays.Prof. Jeff Bilmes EE595A/Spr 2011/Submodular Functions – Lecture 2 - April 1st, 2011 page 2Logistics Review More Sub Funcs Eq Defs SummaryScratch PaperProf. Jeff Bilmes EE595A/Spr 2011/Submodular Functions – Lecture 2 - April 1st, 2011 page 3Logistics Review More Sub Funcs Eq Defs SummaryScratch PaperProf. Jeff Bilmes EE595A/Spr 2011/Submodular Functions – Lecture 2 - April 1st, 2011 page 4Logistics Review More Sub Funcs Eq Defs SummaryScratch PaperProf. Jeff Bilmes EE595A/Spr 2011/Submodular Functions – Lecture 2 - April 1st, 2011 page 5Logistics Review More Sub Funcs Eq Defs SummarySubmodular DefinitionsDefinition (submodular)A function f : 2V→ R is submodular if for any A, B ⊆ V , we have that:f (A) + f (B) ≥ f (A ∪ B) + f (A ∩ B) (1)An alternate and equivalent definition is:Definition (diminishing returns)A function f : 2V→ R is submodular if for any A ⊆ B ⊂ V , andv ∈ V \ B, we have that:f (A ∪ {v}) − f (A) ≥ f (B ∪ {v }) − f (B) (2)This means that the incremental “value”, “gain”, or “cost” of vdecreases (diminishes) as the context in which v is considered growsfrom A to B.Prof. Jeff Bilmes EE595A/Spr 2011/Submodular Functions – Lecture 2 - April 1st, 2011 page 6Logistics Review More Sub Funcs Eq Defs SummaryGround set: E or V ?Submodular functions are functions defined on subsets of some finite set,called the ground set .It is common in the literature to use either E or V as the ground set.We will follow this inconsistency in the literature and willinconsistently use either E or V as our ground set (hopefully not inthe same equation, if so, please point this out).Prof. Jeff Bilmes EE595A/Spr 2011/Submodular Functions – Lecture 2 - April 1st, 2011 page 7Logistics Review More Sub Funcs Eq Defs SummaryGround set: E or V ?Submodular functions are functions defined on subsets of some finite set,called the ground set .It is common in the literature to use either E or V as the ground set.We will follow this inconsistency in the literature and willinconsistently use either E or V as our ground set (hopefully not inthe same equation, if so, please point this out).Prof. Jeff Bilmes EE595A/Spr 2011/Submodular Functions – Lecture 2 - April 1st, 2011 page 7Logistics Review More Sub Funcs Eq Defs SummaryNotation RERE= {x = (xj∈ R : j ∈ E )} (3)RE+= {x = (xj: j ∈ E ) : x ≥ 0} (4)Any vector x ∈ REcan be treated as a modular function, and vice versa.That isx(A) =Xa∈Axa(5)Prof. Jeff Bilmes EE595A/Spr 2011/Submodular Functions – Lecture 2 - April 1st, 2011 page 8Logistics Review More Sub Funcs Eq Defs SummaryOther Notation: indicator vectors of setsGiven an A ⊆ E, define the vector 1A∈ RE+to be1A(j) =(1 if j ∈ A;0 if j /∈ A(6)Sometimes this will be written as χA≡ 1A.Thus, given modular function x ∈ RE, we can write x(A) in a variety ofways, i.e.,x(A) = x · 1A=Xi∈Ax(A) (7)Prof. Jeff Bilmes EE595A/Spr 2011/Submodular Functions – Lecture 2 - April 1st, 2011 page 9Logistics Review More Sub Funcs Eq Defs SummaryOther Notation: indicator vectors of setsGiven an A ⊆ E, define the vector 1A∈ RE+to be1A(j) =(1 if j ∈ A;0 if j /∈ A(6)Sometimes this will be written as χA≡ 1A.Thus, given modular function x ∈ RE, we can write x(A) in a variety ofways, i.e.,x(A) = x · 1A=Xi∈Ax(A) (7)Prof. Jeff Bilmes EE595A/Spr 2011/Submodular Functions – Lecture 2 - April 1st, 2011 page 9Logistics Review More Sub Funcs Eq Defs SummaryOther Notation: singletons and setsWhen A is a set and k is a singleton (a set with a single item), the unionis properly written as A ∪ {k}, but sometimes I will write just A + k.Prof. Jeff Bilmes EE595A/Spr 2011/Submodular Functions – Lecture 2 - April 1st, 2011 page 10Logistics Review More Sub Funcs Eq Defs SummarySumming Submodular FunctionsGiven E , let f1, f2: 2E→ R be two submodular functions. Thenf : 2E→ R with f (A) = f1(A) + f2(A) (8)is submodular. This follows easily sincef (A) + f (B) = f1(A) + f2(A) + f1(B) + f2(B) (9)≥ f1(A ∪ B) + f2(A ∪ B) + f1(A ∩ B) + f2(A ∩ B) (10)= f (A ∪ B) + f (A ∩ B). (11)I.e., it holds for each component of f in each term in the inequality.Prof. Jeff Bilmes EE595A/Spr 2011/Submodular Functions – Lecture 2 - April 1st, 2011 page 11Logistics Review More Sub Funcs Eq Defs SummarySumming Submodular and Modular FunctionsGiven E , let f1, m : 2E→ R be a submodular and a modular function.Thenf : 2E→ R with f (A) = f1(A) − m(A) (12)is submodular (as is f (A) = f1(A) + m(A)). This follows easily sincef (A) + f (B) = f1(A) − m(A) + f1(B) − m(B) (13)≥ f1(A ∪ B) − m(A ∪ B) + f1(A ∩ B) − m(A ∩ B) (14)= f (A ∪ B) + f (A ∩ B). (15)That is, the modular component withm(A) + m(B) = m(A ∪ B) + m(A ∩ B) never destroys the inequality.Note of course that if m is modular than so is −m.Prof. Jeff Bilmes EE595A/Spr 2011/Submodular Functions – Lecture 2 - April 1st, 2011 page 12Logistics Review More Sub Funcs Eq Defs SummaryRestricting Submodular FunctionsGiven E , let f : 2E→ R be a submodular functions. And let S ⊆ E bean arbitrary set. thenf0: 2E→ R with f (A) = f (A ∩ S) (16)is submodular.Proof.Given A ⊆ B ⊆ E \ v, considerf ((A + v) ∩ S) − f (A ∩ S) ≥ f ((B + v) ∩ S) − f (B ∩ S) (17)If v /∈ S, then both differences on each size are zero. If v ∈ S, then wecan consider thisf (A0+ v) − f (A0) ≥ f (B0+ v) − f (B) (18)with A0= A ∩ S and B0= B ∩ S. Since A0⊆ B0, this holds due tosubmodularity of f .Prof. Jeff Bilmes EE595A/Spr 2011/Submodular Functions – Lecture 2 - April 1st, 2011 page 13Logistics Review More Sub Funcs Eq Defs SummarySumming Restricted Submodular FunctionsGiven E , let f1, f2: 2E→ R be two submodular functions and let S1, S2be two arbitrary fixed sets. Thenf : 2E→ R with f (A) = f1(A ∩ S1) + f2(A ∩ S2) (19)is submodular. This follows easily from the preceding two