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.
arXiv commentAppears in Proceedings of the Twenty-First Conference on Uncertainty in Artificial Intelligence (UAI2005)
References in corpus (1)
Cited by in corpus (64)
- Gaussian Process Optimization in the Bandit Setting: No Regret and Experimental Design
- Adaptive Submodularity: Theory and Applications in Active Learning and Stochastic Optimization
- Learning Mixtures of Submodular Shells with Application to Document Summarization
- Algorithms for Approximate Minimization of the Difference Between Submodular Functions, with Applications
- Parallelizing Exploration-Exploitation Tradeoffs with Gaussian Process Bandit Optimization
- Structured sparsity-inducing norms through submodular functions
- Guaranteed Non-convex Optimization: Submodular Maximization over Continuous Domains
- A Utility-Theoretic Approach to Privacy in Online Services
- Submodular Maximization Beyond Non-negativity: Guarantees, Fast Algorithms, and Applications
- Curvature and Optimal Algorithms for Learning and Minimizing Submodular Functions
- Optimal Value of Information in Graphical Models
- Expectation-Maximization for Learning Determinantal Point Processes
- Data Summarization at Scale: A Two-Stage Submodular Approach
- Actively Learning Gaussian Process Dynamics
- Convex Analysis and Optimization with Submodular Functions: a Tutorial
- Multimodal Hierarchical Dirichlet Process-based Active Perception
- A Marketplace for Data: An Algorithmic Solution
- Constrained Submodular Maximization via a Non-symmetric Technique
- Convex Relaxations for Learning Bounded Treewidth Decomposable Graphs
- Submodular Combinatorial Information Measures with Applications in Machine Learning
- Discrete Signal Processing with Set Functions
- Active Classification: Theory and Application to Underwater Inspection
- Stochastic Submodular Maximization: The Case of Coverage Functions
- Optimal DR-Submodular Maximization and Applications to Provable Mean Field Inference
- Scalable Variational Inference in Log-supermodular Models
- Behavior-Based online Incentive Mechanism for Crowd Sensing with Budget Constraints
- Information-theoretic Feature Selection via Tensor Decomposition and Submodularity
- Sequential Design of Experiments via Linear Programming
- How Do You Want Your Greedy: Simultaneous or Repeated?
- Observation Subset Selection as Local Compilation of Performance Profiles
- Active Learning for Autonomous Intelligent Agents: Exploration, Curiosity, and Interaction
- Near-Optimal Active Learning of Multi-Output Gaussian Processes
- Non-submodular Function Maximization subject to a Matroid Constraint, with Applications
- A Dynamic Programming Algorithm for Finding an Optimal Sequence of Informative Measurements
- Submodular Norms with Applications To Online Facility Location and Stochastic Probing
- Information Inequalities via Submodularity and a Problem in Extremal Graph Theory
- Modeling Human Decision-making in Generalized Gaussian Multi-armed Bandits
- Submodularity on Hypergraphs: From Sets to Sequences
- Adaptive Sequence Submodularity
- Sensor Array Design Through Submodular Optimization
- Maximizing Stochastic Monotone Submodular Functions
- Weakly Submodular Maximization Beyond Cardinality Constraints: Does Randomization Help Greedy?
- Maximizing Information Gain in Partially Observable Environments via Prediction Reward
- Distributed Submodular Maximization
- Practical Context Awareness: Measuring and Utilizing the Context Dependency of Mobile Usage
- On the Unreasonable Effectiveness of the Greedy Algorithm: Greedy Adapts to Sharpness
- Sensor Planning for Large Numbers of Robots
- Feature Cross Search via Submodular Optimization
- Surrogate-based Optimization using Mutual Information for Computer Experiments (optim-MICE)
- Active Learning Methods based on Statistical Leverage Scores
- Real-Time Resource Allocation for Tracking Systems
- Expedited Multi-Target Search with Guaranteed Performance via Multi-fidelity Gaussian Processes
- Maximizing submodular functions using probabilistic graphical models
- Multi-Robot Gaussian Process Estimation and Coverage: A Deterministic Sequencing Algorithm and Regret Analysis
- Submodular Bandit Problem Under Multiple Constraints
- Value of Information in Probabilistic Logic Programs
- Online Distributed Sensor Selection
- DISCO : efficient unsupervised decoding for discrete natural language problems via convex relaxation
- Submodularity in Input Node Selection for Networked Systems
- Probably Approximately Correct Greedy Maximization with Efficient Bounds on Information Gain for Sensor Selection
- Variational Optimization for the Submodular Maximum Coverage Problem
- Accelerating Experimental Design by Incorporating Experimenter Hunches
- Adaptive Uncertainty Resolution in Bayesian Combinatorial Optimization Problems
- On the Approximation Relationship between Optimizing Ratio of Submodular (RS) and Difference of Submodular (DS) Functions