LogisticsBasic DefsExamplesGraphsOther ExsEq DefsSummaryLogistics Basic Defs Examples Graphs Other Exs 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 1 - March 30th, 2011Prof. Jeff Bilmes EE595A – Spring 2011 – Submodular Functions – Lecture 1 - March 30th, 2011 page 1Logistics Basic Defs Examples Graphs Other Exs Eq Defs SummaryAnnouncementsWelcome to the class!Weekly Office Hours: Wednesdays, 12:30-1:30pm, 10 minutes afterclass on Wednesdays.Prof. Jeff Bilmes EE595A – Spring 2011 – Submodular Functions – Lecture 1 - March 30th, 2011 page 2Logistics Basic Defs Examples Graphs Other Exs Eq Defs SummaryAboutThis course will serve as an introduction to submodular functionsincluding methods for their optimization, and how they have been (andcan be) applied in many application domains.Prof. Jeff Bilmes EE595A – Spring 2011 – Submodular Functions – Lecture 1 - March 30th, 2011 page 3Logistics Basic Defs Examples Graphs Other Exs Eq Defs SummaryRough OutlineIntroduction to submodular functions, including definitions,real-world and contrived examples of submodular functions,properties, operations that preserve submodularity, submodularvariants and special submodular functions, and computationalproperties.Background on submodular functions, including a brief overview ofthe theory of matroids and lattices.Polyhedral properties of submodular functionsThe Lov´asz extension of submodular functions. The Choquetintegral.Submodular maximization algorithms under simple constraints,submodular cover problems, greedy algorithms, approximationguaranteesProf. Jeff Bilmes EE595A – Spring 2011 – Submodular Functions – Lecture 1 - March 30th, 2011 page 4Logistics Basic Defs Examples Graphs Other Exs Eq Defs SummaryRough Outline (cont. II)Submodular minimization algorithms, a history of submodularminimization, including both numerical and combinatorialalgorithms, computational properties of these algorithms, anddescriptions of both known results and currently open problems inthis area.Submodular flow problems, the principle partition of a submodularfunction and its variants.Constrained optimization problems with submodular functions,including maximization and minimization problems with variousconstraints. An overview of recent problems addressed in thecommunity.Applications of submodularity in computer vision, constraintsatisfaction, game theory, information theory, norms, naturallanguage processing, graphical models, and machine learningProf. Jeff Bilmes EE595A – Spring 2011 – Submodular Functions – Lecture 1 - March 30th, 2011 page 5Logistics Basic Defs Examples Graphs Other Exs Eq Defs SummaryFacts about the classPrerequisites: ideally knowledge in probability, statistics, convexoptimization, and combinatorial optimization these will be reviewedas necessary. The course is open to students in all UW departments.Any questions, please contact me.Text: We will be drawing from the book by Satoru Fujishige entitled”Submodular Functions and Optimization” 2nd Edition, 2005, butwe will also be reading research papers that will be posted here onthis web page, especially for some of the application areas.Grades and Assignments: Grades will be based on a combination ofa final project (35%), homeworks (35%), and the take homemidterm exam (30%). There will be between 3-4 homeworks duringthe quarter.Final project: The final project will consist of a 4-page paper(conference style) and a final project presentation. The project mustinvolve using/dealing mathematically with submodularity in someway or another.Prof. Jeff Bilmes EE595A – Spring 2011 – Submodular Functions – Lecture 1 - March 30th, 2011 page 6Logistics Basic Defs Examples Graphs Other Exs Eq Defs SummaryFacts about the classHomework/midterm must be submitted electronically using our webpage (see http://ssli.ee.washington.edu/~bilmes/ee595a_spring_2011/).PDF submissions only please.Lecture slides - are being prepared as we speak. I will try to havethem up on the web page the night before each class. I will not onlydraw from the book but other sources which will be listed at the endof each set of slides.Our currently scheduled final presentation is Monday, June 06, 2011,830-1020, MUE 155. Perhaps this is a bit early on a Monday. Finalsweek is June 6-10th, so we’ll find a time later this week to do it.Prof. Jeff Bilmes EE595A – Spring 2011 – Submodular Functions – Lecture 1 - March 30th, 2011 page 7Logistics Basic Defs Examples Graphs Other Exs Eq Defs SummaryScratch PaperProf. Jeff Bilmes EE595A – Spring 2011 – Submodular Functions – Lecture 1 - March 30th, 2011 page 8Logistics Basic Defs Examples Graphs Other Exs Eq Defs SummaryScratch PaperProf. Jeff Bilmes EE595A – Spring 2011 – Submodular Functions – Lecture 1 - March 30th, 2011 page 9Logistics Basic Defs Examples Graphs Other Exs Eq Defs SummaryScratch PaperProf. Jeff Bilmes EE595A – Spring 2011 – Submodular Functions – Lecture 1 - March 30th, 2011 page 10Logistics Basic Defs Examples Graphs Other Exs Eq Defs SummarySubmodular MotivationGiven a set of objects V = {v1, . . . , vn} and a function f : 2V→ Rthat returns a real value for any subset S ⊆ V .Suppose we are interested in finding the subset that eithermaximizes or minimizes the function, e.g., argmaxS⊆Vf (S), possiblysubject to some constraints.In general, this problem has exponential time complexity.Example: f might correspond to the value (e.g., information gain)of a set of sensor locations in an environment, and we wish to findthe best set S ⊆ V of sensors locations given a fixed upper limit onthe number of sensors |S|.In many cases (such as above) f has properties that make itsoptimization tractable to either exactly or approximately compute.One such property is submodularity.Prof. Jeff Bilmes EE595A – Spring 2011 – Submodular Functions – Lecture 1 - March 30th, 2011 page 11Logistics Basic Defs Examples Graphs Other Exs 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 \