Timezone: »

 
Poster
Cost Effective Active Search
Shali Jiang · Roman Garnett · Benjamin Moseley

Thu Dec 12 10:45 AM -- 12:45 PM (PST) @ East Exhibition Hall B + C #3
in Algorithms -- Active Learning »
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.
Keywords: Active Learning · Algorithms
[ Paper]  [ Slides] 

Author Information

Shali Jiang (Washington University in St. Louis)
Roman Garnett (Washington University in St. Louis)
Benjamin Moseley (Carnegie Mellon University)

More from the Same Authors