Explaining the Success of Nearest Neighbor Methods in Prediction

• URL: http://arxiv.org/abs/2502.15900v1
• Date: Fri, 21 Feb 2025 19:37:57 GMT
• Title: Explaining the Success of Nearest Neighbor Methods in Prediction
• Authors: George H. Chen, Devavrat Shah,
• Abstract summary: Methods for prediction leverage nearest neighbor search to find past training examples most similar to a test example.<n>This book aims to explain the success of these methods, both in theory and in practice.
• Score: 20.63799450632279
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• 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 for a real dataset. We then cover recent 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 enables successful prediction.

Related papers

• In-Context Parametric Inference: Point or Distribution Estimators? [66.22308335324239]
  We show that amortized point estimators generally outperform posterior inference, though the latter remain competitive in some low-dimensional problems.<n>Our experiments indicate that amortized point estimators generally outperform posterior inference, though the latter remain competitive in some low-dimensional problems.
  arXiv  Detail & Related papers  (2025-02-17T10:00:24Z)
• Efficient Nearest Neighbor based Uncertainty Estimation for Natural Language Processing Tasks [26.336947440529713]
  Trustworthiness in model predictions is crucial for safety-critical applications in the real world. Deep neural networks often suffer from the issues of uncertainty estimation, such as miscalibration. We propose $k$-Nearest Neighbor Uncertainty Estimation ($k$NN-UE), which uses not only the distances from the neighbors, but also the ratio of labels in the neighbors.
  arXiv  Detail & Related papers  (2024-07-02T10:33:31Z)
• Probabilistic Conformal Prediction with Approximate Conditional Validity [81.30551968980143]
  We develop a new method for generating prediction sets that combines the flexibility of conformal methods with an estimate of the conditional distribution. Our method consistently outperforms existing approaches in terms of conditional coverage.
  arXiv  Detail & Related papers  (2024-07-01T20:44:48Z)
• Improving Event Time Prediction by Learning to Partition the Event Time Space [13.5391816206237]
  Recently developed survival analysis methods improve upon existing approaches by predicting the probability of event occurrence in each of a number pre-specified (discrete) time intervals. In clinical settings with limited available data, it is often preferable to judiciously partition the event time space into a limited number of intervals well suited to the prediction task at hand. We show that in two simulated datasets, we are able to recover intervals that match the underlying generative model. We then demonstrate improved prediction performance on three real-world observational datasets, including a large, newly harmonized stroke risk prediction dataset.
  arXiv  Detail & Related papers  (2023-10-24T14:11:40Z)
• Iterative Methods for Vecchia-Laplace Approximations for Latent Gaussian Process Models [11.141688859736805]
  We introduce and analyze several preconditioners, derive new convergence results, and propose novel methods for accurately approxing predictive variances.<n>In particular, we obtain a speed-up of an order of magnitude compared to Cholesky-based calculations.<n>All methods are implemented in a free C++ software library with high-level Python and R packages.
  arXiv  Detail & Related papers  (2023-10-18T14:31:16Z)
• Optimal Extended Neighbourhood Rule $k$ Nearest Neighbours Ensemble [1.8843687952462742]
  A new optimal extended neighborhood rule based ensemble method is proposed in this paper. The ensemble is compared with state-of-the-art methods on 17 benchmark datasets using accuracy, Cohen's kappa, and Brier score (BS)
  arXiv  Detail & Related papers  (2022-11-21T09:13:54Z)
• When Rigidity Hurts: Soft Consistency Regularization for Probabilistic Hierarchical Time Series Forecasting [69.30930115236228]
  Probabilistic hierarchical time-series forecasting is an important variant of time-series forecasting. Most methods focus on point predictions and do not provide well-calibrated probabilistic forecasts distributions. We propose PROFHiT, a fully probabilistic hierarchical forecasting model that jointly models forecast distribution of entire hierarchy.
  arXiv  Detail & Related papers  (2022-06-16T06:13:53Z)
• A k nearest neighbours classifiers ensemble based on extended neighbourhood rule and features subsets [0.4709844746265484]
  kNN based ensemble methods minimise the effect of outliers by identifying a set of data points in the given feature space that are nearest to an unseen observation. This paper proposes a k nearest neighbour ensemble where the neighbours are determined in k steps.
  arXiv  Detail & Related papers  (2022-05-30T13:57:32Z)
• Reasoning Through Memorization: Nearest Neighbor Knowledge Graph Embeddings [29.94706167233985]
  kNN-KGE is a new knowledge graph embedding approach with pre-trained language models. We compute the nearest neighbors based on the distance in the entity embedding space from the knowledge store.
  arXiv  Detail & Related papers  (2022-01-14T17:35:16Z)
• Robustification of Online Graph Exploration Methods [59.50307752165016]
  We study a learning-augmented variant of the classical, notoriously hard online graph exploration problem. We propose an algorithm that naturally integrates predictions into the well-known Nearest Neighbor (NN) algorithm.
  arXiv  Detail & Related papers  (2021-12-10T10:02:31Z)
• Residual Overfit Method of Exploration [78.07532520582313]
  We propose an approximate exploration methodology based on fitting only two point estimates, one tuned and one overfit. The approach drives exploration towards actions where the overfit model exhibits the most overfitting compared to the tuned model. We compare ROME against a set of established contextual bandit methods on three datasets and find it to be one of the best performing.
  arXiv  Detail & Related papers  (2021-10-06T17:05:33Z)
• Near-optimal inference in adaptive linear regression [60.08422051718195]
  Even simple methods like least squares can exhibit non-normal behavior when data is collected in an adaptive manner. We propose a family of online debiasing estimators to correct these distributional anomalies in at least squares estimation. We demonstrate the usefulness of our theory via applications to multi-armed bandit, autoregressive time series estimation, and active learning with exploration.
  arXiv  Detail & Related papers  (2021-07-05T21:05:11Z)
• Adversarial Examples for $k$-Nearest Neighbor Classifiers Based on Higher-Order Voronoi Diagrams [69.4411417775822]
  Adversarial examples are a widely studied phenomenon in machine learning models. We propose an algorithm for evaluating the adversarial robustness of $k$-nearest neighbor classification.
  arXiv  Detail & Related papers  (2020-11-19T08:49:10Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.