Active Nearest-Neighbor Learning in Metric Spaces
We propose a pool-based non-parametric active learning algorithm for general metric spaces, called MArgin Regularized Metric Active Nearest Neighbor (MARMANN), which outputs a nearest-neighbor classifier. We give prediction error guarantees that depend on the noisy-margin properties of the input sample, and are competitive with those obtained by previously proposed passive learners. We prove that the label complexity of MARMANN is significantly lower than that of any passive learner with similar error guarantees. MARMANN is based on a generalized sample compression scheme, and a new label-efficient active model-selection procedure.
Code (0)
등록된 구현이 없습니다.
Tasks
Active LearningModel SelectionSimilar Papers 제목 키워드 기반
A Nearest Neighbor Characterization of Lebesgue Points in Metric Measure Spaces
The property of almost every point being a Lebesgue point has proven to be crucial for the consistency of several classification algorithms based on nearest neighbors. We characterize Lebesgue points in terms of a 1-Near…
ClassificationGeneral ClassificationregressionRates of Convergence for Nearest Neighbor Classification
Nearest neighbor methods are a popular class of nonparametric estimators with several desirable properties, such as adaptivity to different distance scales in different regions of space. Prior work on convergence rates f…
ClassificationGeneral ClassificationAsymmetric Learning Vector Quantization for Efficient Nearest Neighbor Classification in Dynamic Time Warping Spaces
The nearest neighbor method together with the dynamic time warping (DTW) distance is one of the most popular approaches in time series classification. This method suffers from high storage and computation requirements fo…
ClassificationDynamic Time WarpingGeneral ClassificationQuantization+3A Two-Stage Active Learning Algorithm for $k$-Nearest Neighbors
$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 ac…
Active LearningVocal Bursts Valence PredictionNear-optimal sample compression for nearest neighbors
We present the first sample compression algorithm for nearest neighbors with non-trivial performance guarantees. We complement these guarantees by demonstrating almost matching hardness lower bounds, which show that our …
General Classification