Near-optimal Nonmyopic Value of Information in Graphical Models
arXiv:1207.1394
Abstract
A fundamental issue in real-world systems, such as sensor networks, is the selection of observations which most effectively reduce uncertainty. More specifically, we address the long standing problem of nonmyopically selecting the most informative subset of variables in a graphical model. We present the first efficient randomized algorithm providing a constant factor (1-1/e-epsilon) approximation guarantee for any epsilon > 0 with high confidence. The algorithm leverages the theory of submodular functions, in combination with a polynomial bound on sample complexity. We furthermore prove that no polynomial time algorithm can provide a constant factor approximation better than (1 - 1/e) unless P = NP. Finally, we provide extensive evidence of the effectiveness of our method on two complex real-world datasets.
Appears in Proceedings of the Twenty-First Conference on Uncertainty in Artificial Intelligence (UAI2005)
References in corpus (1)
Cited by in corpus (27)
- Learning Mixtures of Submodular Shells with Application to Document Summarization
- Parallelizing Exploration-Exploitation Tradeoffs with Gaussian Process Bandit Optimization
- Structured sparsity-inducing norms through submodular functions
- Submodular Maximization Beyond Non-negativity: Guarantees, Fast Algorithms, and Applications
- Expectation-Maximization for Learning Determinantal Point Processes
- Convex Analysis and Optimization with Submodular Functions: a Tutorial
- Constrained Submodular Maximization via a Non-symmetric Technique
- Convex Relaxations for Learning Bounded Treewidth Decomposable Graphs
- Active Classification: Theory and Application to Underwater Inspection
- Stochastic Submodular Maximization: The Case of Coverage Functions
- Scalable Variational Inference in Log-supermodular Models
- Observation Subset Selection as Local Compilation of Performance Profiles
- Active Learning for Autonomous Intelligent Agents: Exploration, Curiosity, and Interaction
- Submodular Norms with Applications To Online Facility Location and Stochastic Probing
- Adaptive Sequence Submodularity
- Information Inequalities via Submodularity and a Problem in Extremal Graph Theory
- Weakly Submodular Maximization Beyond Cardinality Constraints: Does Randomization Help Greedy?
- Maximizing Information Gain in Partially Observable Environments via Prediction Reward
- Practical Context Awareness: Measuring and Utilizing the Context Dependency of Mobile Usage
- On the Unreasonable Effectiveness of the Greedy Algorithm: Greedy Adapts to Sharpness
- Feature Cross Search via Submodular Optimization
- Sensor Planning for Large Numbers of Robots
- Expedited Multi-Target Search with Guaranteed Performance via Multi-fidelity Gaussian Processes
- Accelerating Experimental Design by Incorporating Experimenter Hunches
- Variational Optimization for the Submodular Maximum Coverage Problem
- DISCO : efficient unsupervised decoding for discrete natural language problems via convex relaxation
- Online Distributed Sensor Selection