Cost effective active search

We study a paradigm of active learning we call cost effective active search, where the goal is to find a given number of positive points from a large unlabeled pool with minimum labeling cost. Most existing methods solve this problem heuristically, and few theoretical results have been established. Here we adopt a principled Bayesian approach for the first time. We first derive the Bayesian optimal policy and establish a strong hardness result: the optimal policy is hard to approximate, with the best-possible approximation ratio bounded below by ?(n^0.16). We then propose an efficient and nonmyopic policy, simulating future search progress using the negative Poisson binomial distribution. We propose simple and fast approximations for its expectation, which serves as an essential role in our proposed policy. We conduct comprehensive experiments on drug and materials discovery datasets and demonstrate that our proposed method is superior to a popular (greedy) baseline.