An adaptive multiclass nearest neighbor classifier

ESAIM: Probability and Statistics. 2020. Vol. 24. P. 69–99.

Puchkin N., Spokoiny V.

We consider a problem of multiclass classification, where the training sample Sn={(Xi,Yi)}ni=1 is generated from the model ℙ(Y=m|X=x)=ηm(x), 1≤m≤M, and η1(x),…,ηM(x) are unknown α-Holder continuous functions.Given a test point X, our goal is to predict its label. A widely used 𝗄-nearest-neighbors classifier constructs estimates of η1(X),…,ηM(X) and uses a plug-in rule for the prediction. However, it requires a proper choice of the smoothing parameter 𝗄, which may become tricky in some situations. In our solution, we fix several integers n1,…,nK, compute corresponding nk-nearest-neighbor estimates for each m and each nk 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 α and to the margin and establish rates of convergence under mild assumptions.

Keywords: aggregation procedures, агрегация, multiclass learning, многоклассовая классификация

Publication based on the results of: Uncertainty quantification in high-dimensional models (2020)