Near-optimal Observation Selection using Submodular Functions

By Andreas Krause, Carlos Guestrin. AAAI Conference on Artificial Intelligence, 2007

384 citations recorded by the source corpus.

View Paper: https://www.semanticscholar.org/paper/1883ed384896a799cedf8b02633a09b8259fe985

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

Citations in the corpus

Bayesian optimisation for Intelligent Environmental Monitoring (2012, background): “For example, the spatial-temporal distribution of air-pollutant concentration in a city depends on traffic, temperature, humidity, wind speed, air pressure and building configuration among many others.”
Online Submodular Maximization with Preemption (2015, methodology): “In machine learning, submodular maximization has been used for document summarization [46, 47], sensor placement [41, 42, 44], and information gathering [43].”
Resource Constrained Neural Network Architecture Search: Will a Submodularity Assumption Help? (2019, background): “Results in [22] show that for a nonnegative monotone submodular function, the greedy algorithm can find a set Sr such that F (Sr) ≥ (1 − 1/e)max|S|r F (S).”
Who2com: Collaborative Perception via Learnable Handshake Communication (2020, background): “, that adding more observation agents achieves diminishing returns [20].”
Submodular Maximization with Cardinality Constraints (2014, methodology): “In machine learning, maximization of submodular functions has been used for document summarization [41, 42], sensor placement [36, 38, 35], and information gathering [37] (consult the references therein for additional applications in AI).”
Batched Stochastic Bayesian Optimization via Combinatorial Constraints Design (2019, background): “…number of previously studied problems can be expressed as submodular minimization (Jegelka & Bilmes, 2011) or maximization (Kempe et al., 2003; Krause & Guestrin, 2007) problems, standard maximization and minimization formulations only capture a small subset of discrete optimization problems.”
Learning to Look Around: Intelligently Exploring Unseen Environments for Unknown Tasks (2017, background): “Optimal sensor placement: The sensor placement literature studies how to place sensors in a distributed network to provide maximum coverage [14, 36, 64].”
Efficient Informative Sensing using Multiple Robots (2014, methodology): “…which will allow us to obtain such an algorithm is that the mutual information (and several other notions of informativeness (as discussed in Krause and Guestrin, 2007) satisfies submodularity, an intuitive diminishing returns property - making a new observation helps more if we have made…”
Adaptive Information Gathering via Imitation Learning (2017, background): “However, the utility function F is a monotone submodular function. it For such functions, has been shown that greedy strategies achieve near-optimality (Krause et al. [25], Krause and Guestrin [24]).”
Click Carving: Segmenting Objects in Video with Point Clicks (2016, background): “This resembles the sub-modular subset selection problem (Krause and Guestrin 2007), where one tries to maximize the set coverage while choosing a subset.”
Adaptive Submodularity: Theory and Applications in Active Learning and Stochastic Optimization (2010, methodology): “Krause and Guestrin (2007) show that many more realistic utility functions in sensor placement (such as the improvement in prediction accuracy w.r.t. some probabilistic model) are submodular as well.”
Greedy sensor selection: Leveraging submodularity (2010, background): “INTRODUCTION Sensor networks have attracted much attention in recent years [1], [2], [3].”
Bounded approximate decentralised coordination via the max-sum algorithm (2009, methodology): “20This measure was chosen because it has been often used in related work to ascertain the accuracy of sensor predictions [37, 38].”