Local nearest neighbour classification with applications to semi-supervised learning

DOI10.1214/19-AOS1868MaRDI QIDQ2196247zbMATH OpenFDO

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

Publication date 28 August 2020

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

Full work available at URL https://arxiv.org/abs/1704.00642, https://projecteuclid.org/euclid.aos/1594972839

zbMATH Keywords

classification problemsnearest neighboursnonparametric classificationsemi-supervised learning

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)

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.

Review text

As known very well, in the year of 1951, in the article of \textit{E. Fix} and \textit{J. L. Hodges}, [``Discriminatory analysis -- nonparametric discrimination: consistency properties, Technical Report to USAF School of Medicine (Randolph Field, TX), see also Zbl 0715.62080], a simple nonparametric classifier, the \(k\)-nearest neighbour classifier, has been defined. The present article starts with the review of some contributions in the domain of supervised classification problems. In the second section, the local-\(k\)-nearest neighbour classifier which allows the number of neighbours to vary depending on the location of the test point is defined. In the third section, under some special assumptions, an asymptotic expansion for the global excess risk of the standard \(k\)-nearest neighbour classifier is presented. A discussion on different choices of \(k\) covers the fourth section. In the fifth section, the minimax lower bound is presented. The sixth section is devoted to all proofs. The authors report that additional theoretical results and a simulation study are contained in a supplementary material: ``Local nearest neighbour classification with applications to semi-supervised learning [\textit{T. I. Cannings} et al., Ann. Stat. 48, No. 3, 1789--1814 (2020; Zbl 07241612)].

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

Cites work

• A Nonparametric Estimate of a Multivariate Density Function
• Bandwidth choice for nonparametric classification
• Choice of neighbor order in nearest-neighbor classification
• Classification in general finite dimensional spaces with the \(k\)-nearest neighbor rule
• Concentration inequalities. A nonasymptotic theory of independence
• Consistent nonparametric regression. Discussion
• Discriminatory Analysis. Nonparametric Discrimination: Consistency Properties
• Efficient multivariate entropy estimation via \(k\)-nearest neighbour distances
• Fast learning rates for plug-in classifiers
• scientific article; zbMATH DE number 5604036 (Why is no real title available?)
• scientific article; zbMATH DE number 893887 (Why is no real title available?)
• Lectures on the nearest neighbor method
• Multivariate k-nearest neighbor density estimates
• Multivariate Two-Sample Tests Based on Nearest Neighbors
• Nearest neighbor pattern classification
• Nonparametric independence testing via mutual information
• On bandwidth variation in kernel estimates. A square root law
• On the rate of convergence of the bagged nearest neighbor estimate
• Optimal weighted nearest neighbour classifiers
• Rate of strong uniform convergence of k-NN density estimates
• Rates of convergence of nearest neighbor estimation under arbitrary sampling
• 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)
• Robust Subspace Clustering via Thresholding
• Sample estimate of the entropy of a random vector
• Smooth discrimination analysis
• Theoretical analysis of cross-validation for estimating the risk of the \(k\)-nearest neighbor classifier
• Theory of Classification: a Survey of Some Recent Advances
• Uniform asymptotics for kernel density estimators with variable bandwidths
• Variable Kernel Estimates of Multivariate Densities

Cited in

(18)

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

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)