# A Two-Stage Active Learning Algorithm for k-Nearest Neighbors

arXiv: https://arxiv.org/abs/2211.10773 · HTML: https://mlsanity.com/paper/2211.10773/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 7 of its 26 references that are in the map.
- First posted on arXiv 19 Nov 2022.

## Builds on (most cited first, 7 of 7)

- [Minimax Analysis of Active Learning](https://mlsanity.com/paper/1410.0996/) (2014)
- [Rates of Convergence for Nearest Neighbor Classification](https://mlsanity.com/paper/1407.0067/) (2014)
- [Beyond Disagreement-based Agnostic Active Learning](https://mlsanity.com/paper/1407.2657/) (2014)
- [An adaptive nearest neighbor rule for classification](https://mlsanity.com/paper/1905.12717/) (2019)
- [Adaptivity to Noise Parameters in Nonparametric Active Learning](https://mlsanity.com/paper/1703.05841/) (2017)
- [Active Nearest-Neighbor Learning in Metric Spaces](https://mlsanity.com/paper/1605.06792/) (2016)
- [Nonparametric adaptive active learning under local smoothness condition](https://mlsanity.com/paper/2102.11077/) (2021)

## Built on by (most cited first, 1 of 1)

- [Position: AI Evaluation Should Learn from How We Test Humans](https://mlsanity.com/paper/2306.10512/) (2023)

## Abstract (arXiv)

k-nearest neighbor classification is a popular non-parametric method because of desirable properties like automatic adaption to distributional scale changes. Unfortunately, it has thus far proved difficult to design active learning strategies for the training of local voting-based classifiers that naturally retain these desirable properties, and hence active learning strategies for k-nearest neighbor classification have been conspicuously missing from the literature. In this work, we introduce a simple and intuitive active learning algorithm for the training of k-nearest neighbor classifiers, the first in the literature which retains the concept of the k-nearest neighbor vote at prediction time. We provide consistency guarantees for a modified k-nearest neighbors classifier trained on samples acquired via our scheme, and show that when the conditional probability function mathbbP(Y=y|X=x) is sufficiently smooth and the Tsybakov noise condition holds, our actively trained classifiers converge to the Bayes optimal classifier at a faster asymptotic rate than passively trained k-nearest neighbor classifiers.