An adaptive multiclass nearest neighbor classifier
This is an incremental improvement for researchers in statistical learning, addressing parameter selection in nearest-neighbor methods.
The paper tackles the problem of multiclass classification by proposing an adaptive k-nearest-neighbors classifier that aggregates multiple estimates to avoid tricky parameter choices, achieving rates of convergence that adapt to unknown smoothness and margin conditions.
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) = η_m(x)$, $1 \leq m \leq M$, and $η_1(x), \dots, η_M(x)$ are unknown $α$-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 $η_1(X), \dots, η_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 $α$ and to the margin and establish rates of convergence under mild assumptions.