Near-Optimal Bayesian Active Learning with Noisy Observations

Abstract

We tackle the fundamental problem of Bayesian active learning with noise, where we need to adaptively select from a number of expensive tests in order to identify an unknown hypothesis sampled from a known prior distribution. In the case of noise-free observations, a greedy algorithm called generalized binary search (GBS) is known to perform near-optimally. We show that if the observations are noisy, perhaps surprisingly, GBS can perform very poorly. We develop EC2, a novel, greedy active learning algorithm and prove that it is competitive with the optimal policy, thus obtaining the first competitiveness guarantees for Bayesian active learning with noisy observations. Our bounds rely on a recently discovered diminishing returns property called adaptive submodularity, generalizing the classical notion of submodular set functions to adaptive policies. Our results hold even if the tests have non-uniform cost and their noise is correlated. We also propose EffECXtive, a particularly fast approximation of EC2, and evaluate it on a Bayesian experimental design problem involving human subjects, intended to tease apart competing economic theories of how people make decisions under uncertainty.

15 pages. Version 2 contains only one major change, namely an amended proof of Lemma 6

References in corpus (2)

• Adaptive Submodularity: Theory and Applications in Active Learning and Stochastic Optimization
• Group-based Query Learning for rapid diagnosis in time-critical situations

Cited by in corpus (15)

• Asking Easy Questions: A User-Friendly Approach to Active Reward Learning
• Active Classification for POMDPs: a Kalman-like State Estimator
• Beyond Pointwise Submodularity: Non-Monotone Adaptive Submodular Maximization in Linear Time
• Mathematical Notions vs. Human Perception of Fairness: A Descriptive Approach to Fairness for Machine Learning
• Adaptive Submodular Optimization under Matroid Constraints
• Noisy Bayesian Active Learning
• Adaptivity in Adaptive Submodularity
• On-the-Job Learning with Bayesian Decision Theory
• Stopping Criterion Design for Recursive Bayesian Classification: Analysis and Decision Geometry
• Learning to search efficiently for causally near-optimal treatments
• Bayesian Active Learning by Disagreements: A Geometric Perspective
• Sensor Planning for Large Numbers of Robots
• Near-Optimal Data Source Selection for Bayesian Learning
• Max-Cost Discrete Function Evaluation Problem under a Budget
• Efficient Online Decision Tree Learning with Active Feature Acquisition