Foundations and Trends® in Machine Learning > Vol 10 > Issue 5-6

Explaining the Success of Nearest Neighbor Methods in Prediction

By George H. Chen, Carnegie Mellon University, USA, georgechen@cmu.edu | Devavrat Shah, Massachusetts Institute of Technology, USA, devavrat@mit.edu

 
Suggested Citation
George H. Chen and Devavrat Shah (2018), "Explaining the Success of Nearest Neighbor Methods in Prediction", Foundations and TrendsĀ® in Machine Learning: Vol. 10: No. 5-6, pp 337-588. http://dx.doi.org/10.1561/2200000064

Publication Date: 31 May 2018
© 2018 G. H. Chen and D. Shah
 
Subjects
Nonparametric methods,  Statistical learning theory,  Classification and prediction
 
Keywords
Applications and case studies
 

Free Preview:

Download extract

Share

Download article
In this article:
1. Introduction
2. Background
3. Theory on Regression
4. Theory on Classification
5. Prediction Guarantees in Three Contemporary Applications
6. Computation
7. Adaptive Nearest Neighbors and Far Away Neighbors
References

Abstract

Many modern methods for prediction leverage nearest neighbor search to find past training examples most similar to a test example, an idea that dates back in text to at least the 11th century and has stood the test of time. This monograph aims to explain the success of these methods, both in theory, for which we cover foundational nonasymptotic statistical guarantees on nearest-neighbor-based regression and classification, and in practice, for which we gather prominent methods for approximate nearest neighbor search that have been essential to scaling prediction systems reliant on nearest neighbor analysis to handle massive datasets. Furthermore, we discuss connections to learning distances for use with nearest neighbor methods, including how random decision trees and ensemble methods learn nearest neighbor structure, as well as recent developments in crowdsourcing and graphons. In terms of theory, our focus is on nonasymptotic statistical guarantees, which we state in the form of how many training data and what algorithm parameters ensure that a nearest neighbor prediction method achieves a user-specified error tolerance. We begin with the most general of such results for nearest neighbor and related kernel regression and classification in general metric spaces. In such settings in which we assume very little structure, what enables successful prediction is smoothness in the function being estimated for regression, and a low probability of landing near the decision boundary for classification. In practice, these conditions could be difficult to verify empirically for a real dataset. We then cover recent theoretical guarantees on nearest neighbor prediction in the three case studies of time series forecasting, recommending products to people over time, and delineating human organs in medical images by looking at image patches. In these case studies, clustering structure, which is easier to verify in data and more readily interpretable by practitioners, enables successful prediction.

DOI:10.1561/2200000064
ISBN: 978-1-68083-454-3
264 pp. $99.00
Buy book (pb)
 
ISBN: 978-1-68083-455-0
264 pp. $280.00
Buy E-book (.pdf)
Table of contents:
1. Introduction
2. Background
3. Theory on Regression
4. Theory on Classification
5. Prediction Guarantees in Three Contemporary Applications
6. Computation
7. Adaptive Nearest Neighbors and Far Away Neighbors
References

Explaining the Success of Nearest Neighbor Methods in Prediction

Many modern methods for prediction leverage nearest neighbor search to find past training examples most similar to a test example, an idea that dates back in text to at least the 11th century and has stood the test of time. This monograph explains the success of these methods, both in theory, covering foundational nonasymptotic statistical guarantees on nearest-neighbor-based regression and classification, and in practice, gathering prominent methods for approximate nearest neighbor search that have been essential to scaling prediction systems reliant on nearest neighbor analysis to handle massive datasets. Furthermore, it looks at connections to learning distances for use with nearest neighbor methods, including how random decision trees and ensemble methods learn nearest neighbor structure, as well as recent developments in crowdsourcing and graphons.

 
MAL-064