Local nearest neighbour classification with applications to semi-supervised learning

DOI10.1214/19-AOS1868zbMATH Open1451.62071arXiv1704.00642MaRDI QIDQ2196247FDOQ2196247

Timothy I. Cannings, Thomas B. Berrett, Richard Samworth

Publication date: 28 August 2020

Published in: The Annals of Statistics (Search for Journal in Brave)

Abstract: We derive a new asymptotic expansion for the global excess risk of a local-$k$-nearest neighbour classifier, where the choice of $k$ may depend upon the test point. This expansion elucidates conditions under which the dominant contribution to the excess risk comes from the decision boundary of the optimal Bayes classifier, but we also show that if these conditions are not satisfied, then the dominant contribution may arise from the tails of the marginal distribution of the features. Moreover, we prove that, provided the $d$-dimensional marginal distribution of the features has a finite $ho$th moment for some $ho>4$ (as well as other regularity conditions), a local choice of $k$ can yield a rate of convergence of the excess risk of $O(n^{-4/(d+4)})$, where $n$ is the sample size, whereas for the standard $k$-nearest neighbour classifier, our theory would require $dgeq5$ and $ho>4d/(d-4)$ finite moments to achieve this rate. These results motivate a new $k$-nearest neighbour classifier for semi-supervised learning problems, where the unlabelled data are used to obtain an estimate of the marginal feature density, and fewer neighbours are used for classification when this density estimate is small. Our worst-case rates are complemented by a minimax lower bound, which reveals that the local, semi-supervised $k$-nearest neighbour classifier attains the minimax optimal rate over our classes for the excess risk, up to a subpolynomial factor in $n$. These theoretical improvements over the standard $k$-nearest neighbour classifier are also illustrated through a simulation study.

Full work available at URL: https://arxiv.org/abs/1704.00642

Recommendations

• Choice of neighbor order in nearest-neighbor classification
• An Optimal Global Nearest Neighbor Metric
• scientific article; zbMATH DE number 3879932
• Classification in general finite dimensional spaces with the \(k\)-nearest neighbor rule
• Asymptotic expansions of the \(k\) nearest neighbor risk
• Consistency of the \(k\)-nearest neighbors rule for functional data
• Nearest neighbor classification with dependent training sequences.
• Choice of the smoothing parameter and efficiency of k-nearest neighbor classification
• Lectures on the nearest neighbor method

zbMATH Keywords

nonparametric classificationsemi-supervised learningclassification problemsnearest neighbours

Mathematics Subject Classification ID

Asymptotic properties of nonparametric inference (62G20) Classification and discrimination; cluster analysis (statistical aspects) (62H30) Learning and adaptive systems in artificial intelligence (68T05)

Cites Work

• Rates of strong uniform consistency for multivariate kernel density estimators. (Vitesse de convergence uniforme presque sûre pour des estimateurs à noyaux de densités multivariées)
• Nearest neighbor pattern classification
• Sample estimate of the entropy of a random vector
• Consistent nonparametric regression. Discussion
• Multivariate k-nearest neighbor density estimates
• Title not available (Why is that?)
• Nonparametric independence testing via mutual information
• Efficient multivariate entropy estimation via \(k\)-nearest neighbour distances
• Classification in general finite dimensional spaces with the \(k\)-nearest neighbor rule
• Robust Subspace Clustering via Thresholding
• Multivariate Two-Sample Tests Based on Nearest Neighbors
• Title not available (Why is that?)
• Optimal weighted nearest neighbour classifiers
• Rate of strong uniform convergence of k-NN density estimates
• Smooth discrimination analysis
• Discriminatory Analysis. Nonparametric Discrimination: Consistency Properties
• Title not available (Why is that?)
• A Nonparametric Estimate of a Multivariate Density Function
• Choice of neighbor order in nearest-neighbor classification
• Fast learning rates for plug-in classifiers
• On bandwidth variation in kernel estimates. A square root law
• Theory of Classification: a Survey of Some Recent Advances
• Rates of convergence of nearest neighbor estimation under arbitrary sampling
• Bandwidth choice for nonparametric classification
• Variable Kernel Estimates of Multivariate Densities
• Uniform asymptotics for kernel density estimators with variable bandwidths
• Lectures on the nearest neighbor method
• On the rate of convergence of the bagged nearest neighbor estimate
• Theoretical analysis of cross-validation for estimating the risk of the k-Nearest Neighbor classifier

Cited In (14)

• Adaptive transfer learning
• E. Fix and J.L. Hodges (1951): An Important Contribution to Nonparametric Discriminant Analysis and Density Estimation: Commentary on Fix and Hodges (1951)
• Nonparametric estimation of surface integrals on level sets
• Theoretical analysis of cross-validation for estimating the risk of the k-Nearest Neighbor classifier
• Local learning integrating global structure for large scale semi-supervised classification
• Locally nearest neighbor classifiers for pattern classification
• Asymptotics and optimal bandwidth for nonparametric estimation of density level sets
• Strongly universally consistent nonparametric regression and classification with privatised data
• Nearest neighbor empirical processes
• Benefit of Interpolation in Nearest Neighbor Algorithms
• Marginal singularity and the benefits of labels in covariate-shift
• A nearest-neighbor based nonparametric test for viral remodeling in heterogeneous single-cell proteomic data
• An adaptive multiclass nearest neighbor classifier
• Hybrid learning based on Fisher linear discriminant

This page was built for publication: Local nearest neighbour classification with applications to semi-supervised learning

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2196247)