Active Nearest Neighbor Regression Through Delaunay Refinement
We introduce an algorithm for active function approximation based on nearest
neighbor regression. Our Active Nearest Neighbor Regressor (ANNR) relies on the
Voronoi-Delaunay framework from computational geometry to subdivide the space
into cells with constant estimated function value and select novel query points
in a way that takes the geometry of the function graph into account. We
consider the recent state-of-the-art active function approximator called DEFER,
which is based on incremental rectangular partitioning of the space, as the
main baseline. The ANNR addresses a number of limitations that arise from the
space subdivision strategy used in DEFER. We provide a computationally
efficient implementation of our method, as well as theoretical halting
guarantees. Empirical results show that ANNR outperforms the baseline for both
closed-form functions and real-world examples, such as gravitational wave
parameter inference and exploration of the latent space of a generative model.