Cost Effective Active Search.

Shali Jiang, Roman Garnett, Benjamin MoseleyNeurIPS 2019 · OpenReview

Abstract

We study a special paradigm of active learning, called 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. We derive the Bayesian optimal policy and establish a strong hardness result: the optimal policy is hard to approximate, with the best-possible approximation ratio lower bounded by $\Omega(n^{0.16})$. We then propose an efficient and nonmyopic policy, ENCES, using the negative Poisson binomial distribution and fast approximations for computing its expectation. Experiments on drug and materials discovery demonstrate that our proposed search procedure is superior to the widely used greedy baseline.

Introduction

In scientific research, identifying rare "positive" instances—such as viable drug leads or novel materials—from massive candidate pools is a critical "needle in a haystack" problem. While traditional active search focuses on maximizing positives within a fixed budget, many real-world projects are goal-oriented: "Find $T$ positives as cheaply as possible." This is the Cost Effective Active Search (CEAS) problem.

CEAS is fundamentally more challenging than its budgeted counterpart. Because the total search duration is unknown, planning "nonmyopically" (looking multiple steps ahead) is difficult. The authors demonstrate that the mathematical properties of cost-given-target distributions differ significantly from utility-given-budget distributions, necessitating specialized policies.

Theoretical Hardness and Methodology

The authors prove a "strong hardness result": any efficient algorithm for CEAS is likely to be at least $\Omega(n^{0.16})$ times worse than the optimal policy. This justifies the development of robust heuristics.

The ENCES Policy

The proposed policy, ENCES (Efficient Nonmyopic Cost Effective Search), addresses these challenges through two main innovations:

  1. Negative Poisson Binomial (NPB) Distribution: ENCES uses the NPB distribution to estimate the expected cost of finding $r$ additional positives. To maintain computational efficiency, the authors introduce ACCU', a fast approximation for calculating these expectations.
  2. Proxy Target Planning: Instead of planning for the final target, which may be far off, ENCES plans for a smaller "proxy target" (e.g., $r=20$). This prevents the algorithm from making long-term decisions based on an initially inaccurate model.
Approximation error of ACCU' (left) and cost comparison of search policies (right).

Experimental Results

The researchers evaluated ENCES on drug discovery (9 datasets) and materials discovery (alloy database).

Performance in Drug Discovery

On drug discovery tasks, ENCES reduced average costs by 56% to 73% compared to the standard greedy baseline. As shown in the table below for the BACE dataset, ENCES consistently achieves the lowest costs across various target numbers of positives.

Average cost to find target number of positives in the BACE drug discovery dataset.

Search Dynamics

A key insight is the difference in search behavior. Greedy algorithms often find "clumps" of positives and then wander aimlessly, resulting in a staircase-shaped cost curve. In contrast, ENCES produces a smoother, nearly linear cost curve (see Figure 1b), indicating it is more effective at transitioning between different regions of the search space.

Conclusion

ENCES provides a principled, nonmyopic approach to Cost Effective Active Search. By leveraging the NPB distribution and proxy targets, it offers significant cost savings in scientific discovery. Future work will explore automated parameter tuning for the proxy target and extending the framework to batch experimental settings.

Summary updated

Abstract

We study a special paradigm of active learning, called 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. 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 lower bounded by $\Omega(n^{0.16})$. We then propose an efficient and nonmyopic policy using the negative Poisson binomial distribution. We propose simple and fast approximations for computing its expectation, which serves as an essential role in our proposed policy. We conduct comprehensive experiments on various domains such as drug and materials discovery, and demonstrate that our proposed search procedure is superior to the widely used greedy baseline.
BibTeX
@inproceedings{jiang2019cost,
  author = {Shali Jiang and Roman Garnett and Benjamin Moseley},
  title = {{Cost Effective Active Search.}},
  booktitle = {NeurIPS},
  year = {2019},
  url = {https://openreview.net/forum?id=cpO8oWGImAR9},
}
Figure