Combinatorial optimization and graphical models Submodular functions Optimization 10725 Carlos Guestrin Carnegie Mellon University 2008 Carlos Guestrin April 28th 2008 1 Most probable explanation MPE in a Markov network Markov net Most probable explanation In general NP complete problem and hard to approximate 2008 Carlos Guestrin 2 1 MPE for attractive MNs 2 classes Attractive MN E g image classification Finding most probable explanation Can be solved by 2008 Carlos Guestrin 3 MPE Attractive MNs k classes MPE for k classes Multiway cut Graph G edge weights wij Finding minimum cut separate s1 sk Multiway cut problem is 2008 Carlos Guestrin 4 2 Multiway cut combinatorial algorithm Very simple alg For each i 1 k Discard argmaxi w Ci return union of rest Find cut Ci that separates si from rest Algorithm achieves 2 2 k approximation OPT cut A separates graph into k components No advantage in more than k From A form A 1 A k where A i separates si from rest Each edge in A appears in Thus 2008 Carlos Guestrin 5 Multiway cut proof Thus for OPT cut A we have that Each A i separates si from rest thus But can do better because 2008 Carlos Guestrin 6 3 General solutions to combinatorial problems Nonlinear optimization Covex problems Extremely general NP Hard to solve Special problem structure General efficient solution algorithms Applies to many continuous problems Combinatorial optimization Integer programming Convex relaxations Very general but NP hard Approximation guarantees for many problems Usually solution is problem specific Though there are general principles Is there general problem structure in combinatorial problems Analogously to convexity Recognize structure and use general algorithms 7 2008 Carlos Guestrin Water distribution networks Water distribution in a city very complex system Pathogens in water can affect thousands or millions of people Currently Add chlorine to the source and hope for the best Chlorine ATTACK could deliberately introduce pathogen Simulator from EPA 2008 Carlos Guestrin 8 4 Monitoring water networks Krause Leskovec G Faloutsos VanBriesen 08 Contamination of drinking water could affect millions of people Sensors Simulator from EPA Hach Sensor Place sensors to detect contaminations 14K Battle of the Water Sensor Networks competition Where should we place sensors to detect contamina8ons quickly 2008 Carlos Guestrin 9 Model based sensing Model predicts impact of contaminations For water networks Water flow simulator from EPA For lake monitoring Learn probabilistic models from data later For each subset A V compute Model predicts Low impact High impact location Contamination Medium impact location S3 S1S2 S1 S4 Set V of all network junctions High sensing quality F A 0 9 2008 Carlos Guestrin sensing quality F A S3 Sensor reduces impact through early detection S2 S4 S1 Low sensing quality F A 0 01 10 5 Sensor placement Given finite set V of locations sensing quality F Want A V such that Typically NP hard S3 S2 S1 S5 S4 Greedy algorithm Start with A For i 1 to k s argmaxs F A s A A s S6 How well can this simple heuristic do 11 2008 Carlos Guestrin Performance of greedy algorithm Population protected higher is better Optimal Greedy Small subset of Water networks data Number of sensors placed Greedy score empirically close to optimal Why 2008 Carlos Guestrin 12 6 Key property Diminishing returns Placement A S1 S2 Placement B S1 S2 S3 S4 S2 S1 S1 Adding S will help a lot S2 S3 S New sensor S S4 Adding S doesn t help much Theorem Krause Leskovec G Faloutsos VanBriesen 08 Sensing quality F A in water networks is submodular 2008 Carlos Guestrin 13 Submodularity Formalizes notion of diminishing returns Equivalent definition 2008 Carlos Guestrin 14 7 What do we get from submodularity Submodularity is a general property of set functions Submodular function can be minimized in polynomial time But our problem is 2008 Carlos Guestrin 15 Another example Maximum cover Ground elements Set of sets Pick k sets maximize number of covered elements 2008 Carlos Guestrin 16 8 Maximizing submodular functions cardinality constraint Given Submodular function Normalized Non decreasing Greedy algorithm guarantees Can you get better algorithm 2008 Carlos Guestrin 17 Online bounds Submodularity provides bounds on the quality of the solution A obtained by any algorithm For normalized non decreasing functions Advantage of adding elements to A Bound on the quality of any set A Tighter bound 2008 Carlos Guestrin 18 9 Battle of the Water Sensor Networks Competition Real metropolitan area network 12 527 nodes Water flow simulator provided by EPA 3 6 million contamination events Multiple objectives Detection time affected population Place sensors that detect well on average 19 2008 Carlos Guestrin BWSN Competition results 13 participants Performance measured in 30 different criteria G Genetic algorithm D Domain knowledge H Other heuristic E Exact method MIP 30 Total Score Higher is better 2008 Carlos Guestrin G H D D G G G H E G H E 25 20 15 10 5 0 20 10 What was the trick Running 8me minutes Simulated all 3 6M contamina8ons on 2 weeks 40 processors 152 GB data on disk 16 GB in main memory compressed Very accurate sensing quality Very slow evalua8on of F A 30 hours 20 sensors 300 200 Naive Greedy 100 0 6 weeks for all 30 se ngs Exhaustive search All subsets ubmodularity to the rescue Lazy Greedy 1 2 3 4 5 6 7 8 9 10 Number of sensors selected Using lazy evalua8ons 1 hour 20 sensors Done a er 2 days 21 2008 Carlos Guestrin Lazy evaluations Na ve implementation of greedy Advantage of an element never increases Advantage What if you already picked a larger set Set after picking i elements Ai Lazy evaluations Keep a priority queue over elements Pick element on top recompute priority If element remains on top Initialize 2008 Carlos Guestrin with advantage of each element 22 11 Other maximization settings Non monotone submodular functions Non unit costs Complex constraints Paths Spanning trees Worst case optimization 2008 Carlos Guestrin 23 12