An adaptive multiclass nearest neighbor classifier

Abstract

We consider a problem of multiclass classification, where the training sample $S_n=\{(X_i,Y_i){\}}_{i=1}^n$ is generated from the model $\mathbb{P}(Y=m|X=x)={\eta }_m(x)$, $1\le m\le M$, and ${\eta }_1(x),\dots ,{\eta }_M(x)$ are unknown $\alpha$-Holder continuous functions.Given a test point $X$, our goal is to predict its label. A widely used $\mathsf{k}$-nearest-neighbors classifier constructs estimates of ${\eta }_1(X),\dots ,{\eta }_M(X)$ and uses a plug-in rule for the prediction. However, it requires a proper choice of the smoothing parameter $\mathsf{k}$, which may become tricky in some situations. In our solution, we fix several integers $n_1,\dots ,n_K$, compute corresponding $n_k$-nearest-neighbor estimates for each $m$ and each $n_k$ and apply an aggregation procedure. We study an algorithm, which constructs a convex combination of these estimates such that the aggregated estimate behaves approximately as well as an oracle choice. We also provide a non-asymptotic analysis of the procedure, prove its adaptation to the unknown smoothness parameter $\alpha$ and to the margin and establish rates of convergence under mild assumptions.

arXiv commentAccepted in ESAIM: Probability & Statistics. The original publication is available at www.esaim-ps.org

References in corpus (12)

• Fast learning rates for plug-in classifiers
• Optimal weighted nearest neighbour classifiers
• The multi-armed bandit problem with covariates
• Learning by mirror averaging
• Sparse Estimation by Exponential Weighting
• Deviation optimal learning using greedy Q-aggregation
• Kullback-Leibler aggregation and misspecified generalized linear models
• Spatial aggregation of local likelihood estimates with applications to classification
• Optimal learning with $Q$-aggregation
• Parameter tuning in pointwise adaptation using a propagation approach
• Optimal rates of aggregation in classification under low noise assumption
• Empirical risk minimization is optimal for the convex aggregation problem