Efficient Nonmyopic Active Search

Shali Jiang, Gustavo Malkomes, Geoff Converse, Alyssa Shofner, Benjamin Moseley, Roman Garnett
Proceedings of the 34th International Conference on Machine Learning, PMLR 70:1714-1723, 2017.

Abstract

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.

Cite this Paper

BibTeX
@InProceedings{pmlr-v70-jiang17d, title = {Efficient Nonmyopic Active Search}, author = {Shali Jiang and Gustavo Malkomes and Geoff Converse and Alyssa Shofner and Benjamin Moseley and Roman Garnett}, booktitle = {Proceedings of the 34th International Conference on Machine Learning}, pages = {1714--1723}, year = {2017}, editor = {Precup, Doina and Teh, Yee Whye}, volume = {70}, series = {Proceedings of Machine Learning Research}, month = {06--11 Aug}, publisher = {PMLR}, pdf = {http://proceedings.mlr.press/v70/jiang17d/jiang17d.pdf}, url = {https://proceedings.mlr.press/v70/jiang17d.html}, abstract = {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.} }
Endnote
%0 Conference Paper %T Efficient Nonmyopic Active Search %A Shali Jiang %A Gustavo Malkomes %A Geoff Converse %A Alyssa Shofner %A Benjamin Moseley %A Roman Garnett %B Proceedings of the 34th International Conference on Machine Learning %C Proceedings of Machine Learning Research %D 2017 %E Doina Precup %E Yee Whye Teh %F pmlr-v70-jiang17d %I PMLR %P 1714--1723 %U https://proceedings.mlr.press/v70/jiang17d.html %V 70 %X 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.
APA
Jiang, S., Malkomes, G., Converse, G., Shofner, A., Moseley, B. & Garnett, R.. (2017). Efficient Nonmyopic Active Search. Proceedings of the 34th International Conference on Machine Learning, in Proceedings of Machine Learning Research 70:1714-1723 Available from https://proceedings.mlr.press/v70/jiang17d.html.

Related Material