Near Optimal Bayesian Active Learning for Decision Making

How should we gather information to make effective decisions? We address Bayesian active learning and experimental design problems, where we sequentially select tests to reduce uncertaintyaboutasetofhypotheses. Instead ofminimizinguncertaintyperse,weconsidera set of overlappingdecision regions of these hypotheses. Our goal is to drive uncertainty into a single decision region as quickly as possible. We identify necessary and sucient conditionsforcorrectlyidentifyingadecisionregion that contains all hypotheses consistent with observations. We develop a novel Hyperedge Cutting (HEC) algorithm for this problem, and prove that is competitive with the intractable optimal policy. Our ecient implementation of the algorithm relies on computingsubsetsofthecompletehomogeneoussymmetric polynomials. Finally, we demonstrate its eectiveness on two practical applications: approximate comparison-based learning and activelocalizationusingarobotmanipulator.

• Publication year

  2014

• Venue

  International Conference on Artificial Intelligence and Statistics

• Publication date

  2014-02-24

• Fields of study

  Mathematics, Computer Science

• Identifiers
  arXiv 1402.5886
• External record

  Open on Semantic Scholar

• Source metadata

  Semantic Scholar

• No claims are published for this paper.

• No concepts are published for this paper.

• Comparison-Based Learning with Rank Nets

  2012cited by this paper
• Efficient touch based localization through submodularity

  2012cited by this paper
• Adaptive Submodularity: Theory and Applications in Active Learning and Stochastic Optimization

  2010influential reference
• Near-Optimal Bayesian Active Learning with Noisy Observations

  2010influential reference
• Average-Case Active Learning with Costs

  2009cited by this paper
• Noisy Generalized Binary Search

  2009cited by this paper
• Disorder inequality: a combinatorial approach to nearest neighbor search

  2008cited by this paper
• Efficient Optimization of Information-Theoretic Exploration in SLAM

  2008cited by this paper
• Robust Belief-Based Execution of Manipulation Programs

  2008cited by this paper
• Decision trees for entity identification: approximation algorithms and hardness results

  2007cited by this paper
• Agnostic active learning

  2006cited by this paper
• Analysis of a greedy active learning strategy

  2004influential reference
• Machine learning for medical diagnosis: history, state of the art and perspective

  2001cited by this paper
• Programming for Mathematicians

  2000cited by this paper
• On an Optimal Split Tree Problem

  1999influential reference
• Active Markov localization for mobile robots

  1998cited by this paper
• Bayesian Experimental Design: A Review

  1995cited by this paper
• Symmetric functions and Hall polynomials

  1979cited by this paper
• An Experimental System for Computer Controlled Mechanical Assembly

  1975cited by this paper
• Information Value Theory

  1966cited by this paper
• On a Measure of the Information Provided by an Experiment

  1956cited by this paper

• Enhancing Binary Search via Overlapping Partitions

  2025cites this paper
• Informative Path Planning with Limited Adaptivity

  2023cites this paper
• Efficient Online Decision Tree Learning with Active Feature Acquisition

  2023cites this paper
• Active Cost-aware Labeling of Streaming Data

  2023cites this paper
• Optimal Decision Tree and Adaptive Submodular Ranking with Noisy Outcomes

  2023cites this paper
• Classifier-Aided Maximization of Feasible- Error-Region for Robust Manipulation Learning

  2021cites this paper
• Scalable Batch-Mode Deep Bayesian Active Learning via Equivalence Class Annealing

  2021cites this paper
• Bayesian Active Learning by Disagreements: A Geometric Perspective

  2021cites this paper
• The Power of Adaptivity for Stochastic Submodular Cover

  2021cites this paper
• BALanCe: Deep Bayesian Active Learning via Equivalence Class Annealing

  2021cites this paper
• Optimal Decision Tree and Submodular Ranking with Noisy Outcomes

  2021cites this paper
• Sensor Planning for Large Numbers of Robots

  2021cites this paper
• Exploiting Uncertainties from Ensemble Learners to Improve Decision-Making in Healthcare AI

  2020cites this paper
• Adaptivity in Adaptive Submodularity

  2019cites this paper
• Active sensing for motion planning in uncertain environments via mutual information policies

  2019cites this paper
• Leveraging experience in lazy search

  2019cites this paper
• Active Learning for Improving Decision-Making from Imbalanced Data

  2019cites this paper
• Active Learning for Decision-Making from Imbalanced Observational Data

  2019cites this paper
• Beyond Adaptive Submodularity: Approximation Guarantees of Greedy Policy with Adaptive Submodularity Ratio

  2019cites this paper
• Adaptive Motion Planning

  2018cites this paper
• Discrete State Estimation with Persistent Sensor Faults and Non-Persistent Noise via Noisy Bayesian Active Diagnosis

  2018influential citation
• Active Distribution Learning from Indirect Samples

  2018cites this paper
• Active Learning for Visual Question Answering: An Empirical Study

  2017cites this paper
• Weak adaptive submodularity and group-based active diagnosis with applications to state estimation with persistent sensor faults

  2017cites this paper
• Near-Optimal Edge Evaluation in Explicit Generalized Binomial Graphs

  2017cites this paper
• Touch based localization of parts for high precision manufacturing

  2017cites this paper
• Efficient Online Learning for Optimizing Value of Information: Theory and Application to Interactive Troubleshooting

  2017cites this paper
• Adaptive matching for expert systems with uncertain task types

  2017cites this paper
• Data-driven planning via imitation learning

  2017cites this paper
• Interactive Submodular Bandit

  2017cites this paper
• Bayesian Active Edge Evaluation on Expensive Graphs

  2017cites this paper
• Adaptive Information Gathering via Imitation Learning

  2017cites this paper
• Active-Bayesian learning for cooperation connectivity in dynamic cyber-physical-human systems

  2017cites this paper
• Sur deux problèmes d'apprentissage automatique : la détection de communautés et l'appariement adaptatif. (On two problems in machine learning : community detection and adaptive matching)

  2017cites this paper
• A Bayesian Active Learning Approach to Adaptive Motion Planning

  2017cites this paper
• Leveraging Multimodal Perspectives to Learn Common Sense for Vision and Language Tasks

  2017cites this paper
• Robotic Motion Planning in Uncertain Environments via Active Sensing

  2017cites this paper
• Acting under Uncertainty for Information Gathering and Shared Autonomy

  2017cites this paper
• Robust Manipulation via Contact Sensing

  2016cites this paper
• Adaptive Submodular Ranking

  2016cites this paper
• Combinatorial Optimization Problems with Testing

  2016cites this paper
• Active Learning Methods based on Statistical Leverage Scores

  2016cites this paper
• Reactive Motion Planning in Uncertain Environments via Mutual Information Policies

  2016cites this paper
• Adaptive Maximization of Pointwise Submodular Functions With Budget Constraint

  2016cites this paper
• Which Classifier to apply?: Bayesian Active Learning on ImageNet

  2016cites this paper
• Active Comparison Based Learning Incorporating User Uncertainty and Noise

  2016cites this paper
• Near-Optimal Active Learning of Halfspaces via Query Synthesis in the Noisy Setting

  2016cites this paper
• Learning to gather information via imitation

  2016cites this paper
• Dimension Coupling: Optimal Active Learning of Halfspaces via Query Synthesis

  2016cites this paper
• Scenario Submodular Cover

  2016influential citation
• Bayesian Active Transfer Learning in Smart Homes

  2015cites this paper
• Bayesian Active Transfer Learning in Smart Homes, Advances in Active Learning: Bridging Theory and Practice

  2015cites this paper
• Bayesian Active Learning with Evidence-Based Instance Selection

  2015cites this paper
• Adaptive informative path planning in metric spaces

  2015cites this paper
• Smooth Interactive Submodular Set Cover

  2015cites this paper
• Submodular Surrogates for Value of Information

  2015influential citation
• Decision Region Determination for Touch Based Localization

  2014cites this paper