THE CONFERENCE
FOR AUTHORS
FOR PARTICIPANTS

Timezone: »

 
Talk
Efficient Nonmyopic Active Search
Shali Jiang · Luiz Gustavo Malkomes · Geoff Converse · Alyssa Shofner · Benjamin Moseley · Roman Garnett

Mon Aug 07 12:15 AM -- 12:33 AM (PDT) @ C4.8
in Active learning »

Active search is an active learning setting with the goal of identifying as many members of a given class as possible under a labeling budget. In this work, we first establish a theoretical hardness of active search, proving that no polynomial-time policy can achieve a constant factor approximation ratio with respect to the expected utility of the optimal policy. We also propose a novel, computationally efficient active search policy achieving exceptional performance on several real-world tasks. Our policy is nonmyopic, always considering the entire remaining search budget. It also automatically and dynamically balances exploration and exploitation consistent with the remaining budget, without relying on a parameter to control this tradeoff. We conduct experiments on diverse datasets from several domains: drug discovery, materials science, and a citation network. Our efficient nonmyopic policy recovers significantly more valuable points with the same budget than several alternatives from the literature, including myopic approximations to the optimal policy.

[ PDF]  [ ss Summary/Notes]  [ Video] 

Author Information

Shali Jiang (Washington University in St. Louis)
Luiz Gustavo Malkomes (Washington University in St. Louis)
Geoff Converse (Simpson College)
Alyssa Shofner (University of South Carolina)
Benjamin Moseley (Washington University in St. Louis)
Roman Garnett (Washington University in St. Louis)

Related Events (a corresponding poster, oral, or spotlight)

More from the Same Authors