A Two-stage Active Learning Algorithm For \(k\)-nearest Neighbors

Abstract

\(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 \(\mathbb\{P\}(Y=y|X=x)\) is sufficiently smooth and the Tsybakov noise condition holds, our ac

Stats

• citations0
• S2 citations—
• github stars0
• HF likes0
• heat score0.00
• arxiv keyrittler2022a

Related papers

• An Adaptive Nearest Neighbor Rule For Classification (2019)0.00
• Distributionally Robust Weighted \(k\)-nearest Neighbors (2020)0.00
• Interpretable Locally Adaptive Nearest Neighbors (2020)3.58
• Minimax Rate Optimal Adaptive Nearest Neighbor Classification And Regression (2019)8.35
• Adaptive Nearest Neighbor: A General Framework For Distance Metric Learning (2019)0.00
• A Theory-based Evaluation Of Nearest Neighbor Models Put Into Practice (2018)0.00
• Training-time Attacks Against K-nearest Neighbors (2022)2.26
• Minimax Optimal Algorithms With Fixed-\(k\)-nearest Neighbors (2022)0.00