TY - JOUR

T1 - An adaptive multiclass nearest neighbor classifier

AU - Puchkin, Nikita

AU - Spokoiny, Vladimir

N1 - Funding Information:
Financial support by the Russian Academic Excellence Project 5-100 and by the German Research Foundation (DFG) through the Collaborative Research Center 1294 is gratefully acknowledged.
Publisher Copyright:
© EDP Sciences, SMAI 2020
Copyright:
Copyright 2020 Elsevier B.V., All rights reserved.

PY - 2020

Y1 - 2020

N2 - We consider a problem of multiclass classification, where the training sample Sn = f(Xi; Yi)gn i=1 is generated from the model P(Y = mjX = x) = ηm(x), 1 6 m 6 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 k-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 k, which may become tricky in some situations. We fix several integers n1; : : : ; nK, com- pute 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.

AB - We consider a problem of multiclass classification, where the training sample Sn = f(Xi; Yi)gn i=1 is generated from the model P(Y = mjX = x) = ηm(x), 1 6 m 6 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 k-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 k, which may become tricky in some situations. We fix several integers n1; : : : ; nK, com- pute 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.

KW - Adaptive procedures

KW - K nearest neighbors

KW - Multiclass classification

UR - http://www.scopus.com/inward/record.url?scp=85094139550&partnerID=8YFLogxK

U2 - 10.1051/ps/2019021

DO - 10.1051/ps/2019021

M3 - Article

AN - SCOPUS:85094139550

VL - 24

SP - 69

EP - 99

JO - ESAIM - Probability and Statistics

JF - ESAIM - Probability and Statistics

SN - 1292-8100

ER -