A New Look at Nearest Neighbours: Identifying Benign Input Geometries via Random Projections

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Authors

Colleges, School and Institutes

Abstract

It is well known that in general, the nearest neighbour rule (NN) has sample complexity that is exponential in the input space dimension d when only smoothness is assumed on the label posterior function. Here we consider NN on randomly projected data, and we show that, if the input domain has a small ”metric size”, then the sample complexity becomes exponential in the metric entropy integral of the set of normalised chords of the input domain. This metric entropy integral measures the complexity of the input domain, and can be much smaller than d – for instance in cases when the data lies in a linear or a smooth
nonlinear subspace of the ambient space, or when it has a sparse representation. We then show that the guarantees we obtain for the compressive NN also hold for the dataspace NN in bounded domains; thus the random projection takes the role of an analytic tool to identify benign structures under which NN learning is possible from a small sample size. Numerical simulations on data designed to have intrinsically low complexity confirm our theoretical findings, and display a striking agreement in the empirical performances of compressive NN and dataspace NN. This suggests that high dimensional data sets that have a low
complexity underlying structure are well suited for computationally cheap compressive NN learning.

Details

Original languageEnglish
Title of host publicationACML 2015 Proceedings
Publication statusPublished - 25 Feb 2016
Event7th Asian Conference on Machine Learning - Hong Kong, China
Duration: 20 Nov 201522 Nov 2015

Publication series

NameProceedings of Machine Learning Research
Volume45
ISSN (Print)1938-7228

Conference

Conference7th Asian Conference on Machine Learning
CountryChina
CityHong Kong
Period20/11/1522/11/15