# Bayesian Optimal Active Search and Surveying

@inproceedings{Garnett2012BayesianOA, title={Bayesian Optimal Active Search and Surveying}, author={R. Garnett and Yamuna Krishnamurthy and Xuehan Xiong and Jeff G. Schneider and Richard Philip Mann}, booktitle={ICML}, year={2012} }

We consider two active binary-classification problems with atypical objectives. In the first, active search, our goal is to actively uncover as many members of a given class as possible. In the second, active surveying, our goal is to actively query points to ultimately predict the proportion of a given class. Numerous real-world problems can be framed in these terms, and in either case typical model-based concerns such as generalization error are only of secondary importance.
We approach… Expand

#### Paper Mentions

#### 85 Citations

Efficient Nonmyopic Active Search

- Computer Science
- ICML
- 2017

This work proposes a novel active search policy that always considers the entire remaining budget and is thus nonmyopic, yet remains efficient, and develops a bounding technique to achieve greater efficiency when using certain natural probability models. Expand

Cost Effective Active Search

- Computer Science
- NeurIPS
- 2019

A principled Bayesian approach is adopted for the first time, which derives the Bayesian optimal policy and establishes a strong hardness result: the optimal policy is hard to approximate, with the best-possible approximation ratio lower bounded by $\Omega(n^{0.16})$. Expand

Active search on graphs

- Computer Science
- KDD
- 2013

This work proposes a myopic method for active search on graphs that suggests selecting points by maximizing a score considering the potential impact of selecting a node, meant to emulate lookahead while avoiding exponential search. Expand

Efficient nonmyopic batch active search

- Computer Science
- NeurIPS
- 2018

This work first derive the Bayesian optimal policy for batch active search, then proves a lower bound on the performance gap between sequential and batch optimal policies: the ``cost of parallelization. Expand

Active Search with Complex Actions and Rewards

- Computer Science
- 2017

This work designed an algorithm called APPS, which optimizes for onestep look-ahead expected rewards for finding positive regions with high probability, and designed a new exploration criterion called Σ-optimality, which is motivated by a different objective, active surveying, yet empirically performed better due to a tendency to query cluster centers. Expand

Active Search for High Recall: A Non-stationary Extension of Thompson Sampling

- Computer Science
- ECIR
- 2018

This work proposes an approach based on a non-stationary (aka restless) extension of Thompson Sampling, a well-known strategy for Multi-Armed Bandits problems that can be considered as an insurance for achieving a nearly "total" recall with less efforts in the long run. Expand

Active Search and Bandits on Graphs using Sigma-Optimality

- Computer Science
- UAI
- 2015

This work relates the active search setting to multi-armed bandits whose rewards are binary values indicating search hits or misses and arms cannot be pulled more than once and proposes new active search algorithms suitable for graphs with theoretical guarantees and demonstrates their effectiveness on several real-world datasets. Expand

Submodularity in Batch Active Learning and Survey Problems on Gaussian Random Fields

- Mathematics, Computer Science
- ArXiv
- 2012

This work shows that the V-optimality on GRFs as a function of the batch query set is submodular and hence its greedy selection algorithm guarantees an (1-1/e) approximation ratio and proposes a similar survey criterion which minimizes 1'(Sigma)1. Expand

Nonmyopic Multifidelity Active Search

- Computer Science
- ArXiv
- 2021

A model of multifidelity active search, as well as a novel, computationally efficient policy for this setting that is motivated by state-of-the-art classical policies are proposed, allowing for a dynamic tradeoff between exploration and exploitation. Expand

Efficient nonmyopic active search with applications in drug and materials discovery

- Computer Science, Mathematics
- ArXiv
- 2018

A novel approach to nonmyopic approximations of the optimal policy that admits efficient computation is introduced, and two approaches to tackle the combinatorial search challenge are proposed. Expand

#### References

SHOWING 1-10 OF 13 REFERENCES

Active learning for logistic regression: an evaluation

- Mathematics, Computer Science
- Machine Learning
- 2007

A re-derive of the variance reduction method known in experimental design circles as ‘A-optimality’ and comparisons against different variations of the most widely used heuristic schemes are run to discover which methods work best for different classes of problems and why. Expand

Bayesian Optimal Active Search on Graphs

- 2011

In many classification problems, including numerous examples on modern large-scale graph datasets, a large quantity of unlabeled data are available. The cost of obtaining a label for such data can be… Expand

Active Learning Literature Survey

- Computer Science
- 2009

This report provides a general introduction to active learning and a survey of the literature, including a discussion of the scenarios in which queries can be formulated, and an overview of the query strategy frameworks proposed in the literature to date. Expand

Efficient Global Optimization of Expensive Black-Box Functions

- Mathematics, Computer Science
- J. Glob. Optim.
- 1998

This paper introduces the reader to a response surface methodology that is especially good at modeling the nonlinear, multimodal functions that often occur in engineering and shows how these approximating functions can be used to construct an efficient global optimization algorithm with a credible stopping rule. Expand

Combining active learning and semi-supervised learning using Gaussian fields and harmonic functions

- Mathematics
- ICML 2003
- 2003

Active and semi-supervised learning are important techniques when labeled data are scarce. We combine the two under a Gaussian random field model. Labeled and unlabeled data are represented as… Expand

Rare Class Discovery Based on Active Learning

- Computer Science
- ISAIM
- 2008

This paper focuses on a new approach, based on local-topology density estimation, applicable to discovering examples of the rare classes rapidly, despite non-separability with the majority class(es). Expand

Optimal Search for the Best Alternative

- Economics
- 1979

This paper completely characterizes the solution to the problem of searching for the best outcome from alternative sources with different properties. The optimal strategy is an elementary reservation… Expand

Random-Walk Computation of Similarities between Nodes of a Graph with Application to Collaborative Recommendation

- Computer Science
- IEEE Transactions on Knowledge and Data Engineering
- 2007

The model, which nicely fits into the so-called "statistical relational learning" framework, could also be used to compute document or word similarities, and could be applied to machine-learning and pattern-recognition tasks involving a relational database. Expand

A sequential algorithm for training text classifiers

- Computer Science
- SIGIR '94
- 1994

An algorithm for sequential sampling during machine learning of statistical classifiers was developed and tested on a newswire text categorization task and reduced by as much as 500-fold the amount of training data that would have to be manually classified to achieve a given level of effectiveness. Expand

Multi‐Armed Bandit Allocation Indices

- Mathematics
- 1990

3. Multi‐armed Bandit Allocation Indices. By J. C. Gittins. ISBN 0 471 92059 2. Wiley, Chichester, 1989. xii + 252pp. £29.95.