Source-linked AI summary
Near-Optimal Bayesian Active Learning with Noisy Observations
Daniel Golovin, Andreas Krause, Debajyoti Ray
TL;DR
Bayesian active learning with noisy, expensive tests is poorly understood, and common greedy strategies can perform poorly. The paper introduces EC2, proves near-optimal expected cost, and develops the faster EFFECXTIVE approximation for experimental design.
Problem
Noisy Bayesian active learning lacks broadly applicable algorithms provably competitive with the optimal sequential policy, despite its use in selecting expensive observations for scientific, medical, and classification decisions.
Method
The paper formulates noisy active learning as Equivalence Class Determination, introduces the greedy EC2 algorithm, and proposes EFFECXTIVE as a faster approximation.
Results
EC2 is guaranteed to choose the same hypothesis as observing all tests while incurring near-minimal expected cost, and EFFECXTIVE outperforms InfoGain and Random in the reported noisy experiment.
Takeaways & Limitations
Equivalence-class-based edge cutting provides competitiveness guarantees for noisy Bayesian active learning, including settings with non-uniform test costs and correlated noise.
Takeaways & Limitations
The technical guarantee assumes self-certifying instances, although the paper states that its considered instances satisfy this requirement.
Abstract
from arXiv · showhide
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.
1 Introduction
Bayesian active learning selects costly, noisy observations sequentially to identify the best hypothesis under a prior, but the noisy case lacks broadly competitive algorithms. The paper introduces a formulation and greedy method designed to address this gap.
- Motivation: Bayesian experimental design models hypotheses with a prior and test outcomes probabilistically, seeking the correct hypothesis while minimizing experimentation cost.Finding the optimal policy is NP-hard and hard to approximate.
- Motivation: Noisy observations, which occur in most applications, remain much less understood than noise-free active learning.The introduction states that provable competitiveness with the optimal sequential policy was previously unavailable except in restricted settings.
- Contribution: The Equivalence Class Determination formulation targets decisions that cannot be resolved by simply identifying a hypothesis from noisy outcomes.In the cited setup, generalized binary search, information gain, and decision-theoretic value of information can perform poorly.
- Contribution: EC2 greedily optimizes a novel criterion whose objective satisfies adaptive submodularity, yielding expected cost competitive with the optimal policy.The framework also permits non-uniform test costs and correlated test noise.
2 Bayesian Active Learning in the Noiseless Case
The noiseless Bayesian active learning problem seeks a minimum-expected-cost policy that distinguishes hypotheses through tests. Classical greedy heuristics exploit version-space reduction or information gain, while adaptive-submodularity results provide near-optimality guarantees under stated conditions.
- Problem formulation: The noiseless problem distinguishes hypotheses by selecting tests with finite outcomes and incurs each test's specified cost.A prior specifies the joint distribution of the true hypothesis and test outcomes, which are deterministic given the hypothesis in the noiseless case.
- Problem formulation: A feasible policy can be represented as a decision tree, and the objective is to minimize its expected cost.This formulation is also called the Optimal Decision Tree problem.
- Computational difficulty: Obtaining an approximation with cost c(π) ≤ c(π∗) · o(log(n)) is NP-hard, motivating heuristic approaches to the Optimal Decision Tree problem.The cited hardness concerns improving on the optimal policy by more than a logarithmic factor.
- Greedy heuristics: Information gain and generalized binary search greedily maximize benefit-cost ratios based on their respective benefit functions until one hypothesis remains.In the noiseless setting, the two heuristics are equivalent.
- Guarantees: Adaptive submodularity means expected marginal benefits decrease as observations accumulate, while strong adaptive monotonicity formalizes that observations do not reduce expected reward.These properties support a general greedy performance guarantee when the objective reaches a common maximum and the instance meets the stated threshold condition.
- Guarantees: The self-certifying requirement ensures that a policy knows immediately when it has attained the maximum objective value.The paper states that the instances it considers satisfy this requirement.
- Transition to noisy observations: The paper uses adaptive submodularity to provide the first approximation guarantees for Bayesian active learning with noisy observations.
3 The Equivalence Class Determination Problem and the EC2 Algorithm
The paper formulates Equivalence Class Determination (ECD) as identifying the true hypothesis class while minimizing expected test cost, and introduces EC2 to address failures of existing greedy heuristics. EC2 maximizes weighted edges cut between classes, enabling approximation guarantees and a faster implementation.
- Equivalence Class Determination: ECD partitions hypotheses into equivalence classes and seeks the true class using tests while minimizing expected cost.Termination requires the version space to lie within one class.
- Limitations of Existing Heuristics: GBS can require n/2 tests in expectation, paying n/2 times the optimal expected cost on a uniform-prior instance.The optimal policy selects only the test identifying the singleton class.
- Limitations of Existing Heuristics: The class-aware information-gain policy can cost Ω(n/ log(n)) times the optimum because test complementarities undermine myopic selection.Its entropy is measured over equivalence classes rather than hypotheses.
- The EC2 Algorithm: EC2 defines edges between hypotheses in different classes and greedily maximizes the prior-weighted total weight of edges cut by tests.An edge is cut when a test rules out at least one endpoint from the version space.
- The EC2 Algorithm: The edge-cutting objective is strongly adaptively monotone and adaptively submodular, supporting greedy approximation guarantees.These properties provide the basis for applying the adaptive-greedy theorem.
- Guarantees and Implementation: EC2 obtains a ln(Q/η) + 1 approximation for ECD, with an O(log n) guarantee available for unit-cost tests using a modified prior.The general bound uses Q as total edge weight and η as a lower bound on minimum edge weight.
- Guarantees and Implementation: A fast implementation reduces each EC2 round from O(Nn^2ℓ) naively to O(Nn) by incrementally computing class-weight terms.The intermediate computation evaluates each marginal benefit in O(n + mℓ), then can be reduced further to O(n).
4 Bayesian Active Learning with Noise and the EFFECXTIVE Algorithm
The paper reduces noisy Bayesian active learning to Equivalence Class Determination, where tests need only distinguish outcomes leading to different decisions. It develops EC2 with approximation guarantees and EFFECXTIVE as a faster approximation for large noise supports.
- EC2: When complete test outcomes uniquely identify the hypothesis, EC2 has approximation factor at most 2 ln(1/min_{h,θ} P(h,θ)) + 1.The reduction uses hypotheses indexed by (h, θ) and equivalence classes induced by each original hypothesis.
- Bayesian Active Learning with Noise: Noisy observations may leave multiple hypotheses plausible even after all tests, so the goal becomes selecting the minimum-risk decision rather than identifying one hypothesis.Equivalence classes group complete test-outcome vectors that yield the same optimal decision.
- Bayesian Active Learning with Noise: EC2 reduces noisy active learning to Equivalence Class Determination by distinguishing outcome classes associated with different decisions.The reduction defines one class for each decision that minimizes posterior expected loss, with arbitrary tie-breaking.
- Bayesian Active Learning with Noise: GBS, class-based information gain, and value-of-information heuristics can be far from optimal, with some policies paying Ω(n/log(n)) times the optimal cost.The stated lower bound applies even under a uniform prior on (h, θ) with |supp(Θ)| = 2.
- EC2: EC2 obtains an O(log n) approximation to the optimal policy for identifying the relevant equivalence class.Theorem 4 formalizes this guarantee for hypotheses, tests with costs, outcomes, decisions, losses, and a prior noise model.
- EFFECXTIVE: EFFECXTIVE approximates EC2 using an efficient edge-cutting objective, avoiding explicit representation of exponentially large equivalence classes.Its objective is interpreted as information gain based on exponentiated Rényi entropy and requires inference for each possible test outcome.
5 Experiments
Experiments compare EFFECXTIVE with established test-selection heuristics for identifying economic decision theories. EFFECXTIVE performs strongly under fixed parameters and remains competitive when parameter uncertainty introduces identifiability challenges.
- Figure 2: Figure 2 reports model-recovery accuracy with fixed parameters, accuracy over parameter grids, and the probability of classified theory type across subjects.The figure’s three panels correspond to simulated fixed-parameter results, uncertain-parameter results, and human-subject results.
- Simulated experiments: Six algorithms were compared: EFFECXTIVE, IG, VOI, uncertainty sampling, GBS, and random selection, using simulated responses from four economic theories.The simulations evaluated recovery of the true model under canonical parameter values.
- Simulated experiments: Under noisy fixed-parameter simulations, uncertainty sampling, GBS, and VOI performed significantly worse than random, while EFFECXTIVE significantly outperformed information gain.The comparison measured accuracy of recovering the true model as the number of tests increased.
- Parameter uncertainty: With parameter uncertainty, EFFECXTIVE and information gain significantly outperformed random, although information gain performed marginally better than EFFECXTIVE.The increased parameter range potentially created model-identifiability issues and violated assumptions behind EFFECXTIVE.
- Human-subject experiment: The human-subject experiment tested 11 subjects with dynamically optimized lottery-comparison tests to identify which of four theories best described their behavior.The study used EFFECXTIVE and required fewer tests than prior laboratory approaches.
- Human-subject experiment: Seven of 10 classified subjects were best described by expected value, while the remaining classifications showed MVS, prospect-theory, CRRA, and population heterogeneity.The authors characterize these findings as preliminary and state that a larger sample is needed for significant claims about theory validity.
6 Conclusions
The paper frames EC2 as a near-optimal solution for noisy Bayesian active learning and presents EFFECXTIVE as a practical approximation. Its guarantees follow from adaptive submodularity, and experiments demonstrate an application to Bayesian experimental design.
- Conclusions: EC2 adaptively selects noisy tests to achieve the same decision or hypothesis as observing all tests while incurring near-minimal expected cost.The guarantee is contrasted with the potentially far-from-optimal behavior of version-space, information-gain, and value-of-information heuristics.
- Conclusions: EC2 optimizes an objective tailored to separating observation sets that imply different decisions, rather than directly maximizing generic information or version-space reduction.The analysis relies on adaptive submodularity of this objective.
- Conclusions: EFFECXTIVE provides a practical approximation of EC2 for probabilistic models with efficient exact inference and was applied to Bayesian experimental design with human subjects.The reported results indicate that subject types can be identified and that the population is heterogeneous.
A Additional Proofs
The appendix proves adaptive monotonicity and adaptive submodularity for EC2’s objective, first under a uniform prior and then for rational priors via hypothesis replication.
- Adaptive monotonicity: The objective function f is strongly adaptive monotone: additional observations cannot decrease its conditional expected value.The proof uses nonnegative edge weights and the monotonicity of the corresponding function g over refined realizations.
- Adaptive submodularity: For a uniform prior, the proof represents each test’s conditional gain as a function θ of class-outcome counts n_{i,a}.The version space shrinks under additional observations, making each count n_{i,a} nonincreasing along the proof’s parameterized path.
- Proof decomposition: The proof decomposes edge-cutting gains into terms involving hypotheses that disagree at the selected test and terms conditioned on each possible outcome.The quantities e_a count edges whose endpoints agree at the selected test but disagree with the realized hypothesis.
- Adaptive submodularity: The marginal gain decreases as observations accumulate, establishing adaptive submodularity under a uniform prior.The argument shows the relevant partial derivatives are nonnegative and concludes ∆(t|xB) ≤ ∆(t|xA) whenever xB extends xA.
- General priors: The same adaptive-submodularity result extends to rational priors by replacing each hypothesis with a number of identical copies proportional to its prior probability.All copies share the original conditional test-outcome distribution and equivalence class.
B A Bad Example for the Info-Gain and Value of Information Criteria
The paper constructs equivalence-class determination instances where posterior-based greedy heuristics, including information gain and value of information, can be much worse than an optimal policy. The construction makes useful tests appear uninformative until a particular test is performed, causing greedy policies to waste tests or loop indefinitely.
- Information gain and value-of-information heuristics can each require Ω(n/log(n)) times the cost of an optimal policy.The lower bound holds for a family of instances with uniform priors, where n is the number of hypotheses.
- The bad-policy family includes all greedy policies that choose tests using only the posterior distribution over equivalence classes.Such policies are modeled through potential functions over posterior class distributions.
- The hard instance has 2^q classes, each containing two hypotheses, with a uniform prior and four types of unit-cost binary tests.The test types include a test revealing the within-class bit, binary-search tests, sequential-search tests, and dummy tests.
- Before the within-class bit is observed, binary-search tests provide no information gain, while a sequential-search test can identify the realized class comparatively slowly.After the bit is found, the binary-search tests can quickly discover the class index.
- Because dummy tests leave the posterior unchanged, a posterior-based policy may repeatedly select them and enter an infinite loop.If a sequential-search test is selected but does not identify the realized class, the same residual structure recurs with one fewer class; expected cost is at least 1 before a test outcome of 1.