A Finite-Horizon Approach to Active Level Set Estimation
This addresses the problem of efficient spatial sampling for level set estimation, which is incremental as it generalizes existing approaches with a tunable trade-off.
The paper tackles the problem of active level set estimation by developing a finite-horizon approach that optimally balances estimation error and travel distance for a fixed number of samples, achieving roughly one fifth the estimation error at less than half the cost on real air quality data.
We consider the problem of active learning in the context of spatial sampling for level set estimation (LSE), where the goal is to localize all regions where a function of interest lies above/below a given threshold as quickly as possible. We present a finite-horizon search procedure to perform LSE in one dimension while optimally balancing both the final estimation error and the distance traveled for a fixed number of samples. A tuning parameter is used to trade off between the estimation accuracy and distance traveled. We show that the resulting optimization problem can be solved in closed form and that the resulting policy generalizes existing approaches to this problem. We then show how this approach can be used to perform level set estimation in higher dimensions under the popular Gaussian process model. Empirical results on synthetic data indicate that as the cost of travel increases, our method's ability to treat distance nonmyopically allows it to significantly improve on the state of the art. On real air quality data, our approach achieves roughly one fifth the estimation error at less than half the cost of competing algorithms.