Active pointillistic pattern search

May 2015

Active pointillistic pattern search

Authors:

Y. Ma, D. Sutherland, R. Garnett, and J. Schneider

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.
@conference{Ma-2015-119780,
author = {Y. Ma And D. Sutherland And R. Garnett And J. Schneider},
title = {Active pointillistic pattern search},
booktitle = {Proceedings of 18th International Conference on Artificial Intelligence and Statistics (AISTATS '15)},
year = {2015},
month = {May},
volume = {38},
pages = {672 - 680},
}
Copyright notice: This material is presented to ensure timely dissemination of scholarly and technical work. Copyright and all rights therein are retained by authors or by other copyright holders. All persons copying this information are expected to adhere to the terms and constraints invoked by each author's copyright. These works may not be reposted without the explicit permission of the copyright holder.