conftrace_

2012 COLT COLT 2012

Consistency of Nearest Neighbor Classification under Selective Sampling

Abstract

This paper studies nearest neighbor classification in a model where unlabeled data points arrive in a stream, and the learner decides, for each one, whether to ask for its label. Are there generic ways to augment or modify any selective sampling strategy so as to ensure the consistency of the resulting nearest neighbor classifier?

Authors

Sanjoy Dasgupta

Topics

Machine Learning > Core Methods > Classification Machine Learning > Learning Types > Active Learning Machine Learning > Optimization & Theory > Statistical Learning Machine Learning > Learning Types > Online Learning

Keywords

active learning online learning selective sampling nearest neighbor classification distribution-free learning stream learning

More from COLT 2012

All COLT 2012 papers →

Learning Functions of Halfspaces Using Prefix Covers

Computational Bounds on Statistical Query Learning

Learning DNF Expressions from Fourier Spectrum

Active Learning Using Smooth Relative Regret Approximations with Applications

Robust Interactive Learning

Rare Probability Estimation under Regularly Varying Heavy Tails