Active Pointillistic Pattern Search

Yifei Ma, Danica J. Sutherland, Roman Garnett, Jeff Schneider
Proceedings of the Eighteenth International Conference on Artificial Intelligence and Statistics, PMLR 38:672-680, 2015.

Abstract

We introduce the problem of active pointillistic pattern search (APPS), which seeks to discover regions of a domain exhibiting desired behavior with limited observations. Unusually, the patterns we consider are defined by large-scale properties of an underlying function that we can only observe at a limited number of points. Given a description of the desired patterns (in the form of a classifier taking functional inputs), we sequentially decide where to query function values to identify as many regions matching the pattern as possible, with high confience. For one broad class of models the expected reward of each unobserved point can be computed analytically. We demonstrate the proposed algorithm on three difficult search problems: locating polluted regions in a lake via mobile sensors, forecasting winning electoral districts with minimal polling, and identifying vortices in a fluid flow simulation.

Cite this Paper


BibTeX
@InProceedings{pmlr-v38-ma15, title = {{Active Pointillistic Pattern Search}}, author = {Yifei Ma and Danica J. Sutherland and Roman Garnett and Jeff Schneider}, booktitle = {Proceedings of the Eighteenth International Conference on Artificial Intelligence and Statistics}, pages = {672--680}, year = {2015}, editor = {Guy Lebanon and S. V. N. Vishwanathan}, volume = {38}, series = {Proceedings of Machine Learning Research}, address = {San Diego, California, USA}, month = {09--12 May}, publisher = {PMLR}, pdf = {http://proceedings.mlr.press/v38/ma15.pdf}, url = { http://proceedings.mlr.press/v38/ma15.html }, abstract = {We introduce the problem of active pointillistic pattern search (APPS), which seeks to discover regions of a domain exhibiting desired behavior with limited observations. Unusually, the patterns we consider are defined by large-scale properties of an underlying function that we can only observe at a limited number of points. Given a description of the desired patterns (in the form of a classifier taking functional inputs), we sequentially decide where to query function values to identify as many regions matching the pattern as possible, with high confience. For one broad class of models the expected reward of each unobserved point can be computed analytically. We demonstrate the proposed algorithm on three difficult search problems: locating polluted regions in a lake via mobile sensors, forecasting winning electoral districts with minimal polling, and identifying vortices in a fluid flow simulation.} }
Endnote
%0 Conference Paper %T Active Pointillistic Pattern Search %A Yifei Ma %A Danica J. Sutherland %A Roman Garnett %A Jeff Schneider %B Proceedings of the Eighteenth International Conference on Artificial Intelligence and Statistics %C Proceedings of Machine Learning Research %D 2015 %E Guy Lebanon %E S. V. N. Vishwanathan %F pmlr-v38-ma15 %I PMLR %P 672--680 %U http://proceedings.mlr.press/v38/ma15.html %V 38 %X We introduce the problem of active pointillistic pattern search (APPS), which seeks to discover regions of a domain exhibiting desired behavior with limited observations. Unusually, the patterns we consider are defined by large-scale properties of an underlying function that we can only observe at a limited number of points. Given a description of the desired patterns (in the form of a classifier taking functional inputs), we sequentially decide where to query function values to identify as many regions matching the pattern as possible, with high confience. For one broad class of models the expected reward of each unobserved point can be computed analytically. We demonstrate the proposed algorithm on three difficult search problems: locating polluted regions in a lake via mobile sensors, forecasting winning electoral districts with minimal polling, and identifying vortices in a fluid flow simulation.
RIS
TY - CPAPER TI - Active Pointillistic Pattern Search AU - Yifei Ma AU - Danica J. Sutherland AU - Roman Garnett AU - Jeff Schneider BT - Proceedings of the Eighteenth International Conference on Artificial Intelligence and Statistics DA - 2015/02/21 ED - Guy Lebanon ED - S. V. N. Vishwanathan ID - pmlr-v38-ma15 PB - PMLR DP - Proceedings of Machine Learning Research VL - 38 SP - 672 EP - 680 L1 - http://proceedings.mlr.press/v38/ma15.pdf UR - http://proceedings.mlr.press/v38/ma15.html AB - We introduce the problem of active pointillistic pattern search (APPS), which seeks to discover regions of a domain exhibiting desired behavior with limited observations. Unusually, the patterns we consider are defined by large-scale properties of an underlying function that we can only observe at a limited number of points. Given a description of the desired patterns (in the form of a classifier taking functional inputs), we sequentially decide where to query function values to identify as many regions matching the pattern as possible, with high confience. For one broad class of models the expected reward of each unobserved point can be computed analytically. We demonstrate the proposed algorithm on three difficult search problems: locating polluted regions in a lake via mobile sensors, forecasting winning electoral districts with minimal polling, and identifying vortices in a fluid flow simulation. ER -
APA
Ma, Y., Sutherland, D.J., Garnett, R. & Schneider, J.. (2015). Active Pointillistic Pattern Search. Proceedings of the Eighteenth International Conference on Artificial Intelligence and Statistics, in Proceedings of Machine Learning Research 38:672-680 Available from http://proceedings.mlr.press/v38/ma15.html .

Related Material