Analysis of a greedy active learning strategy

Part of Advances in Neural Information Processing Systems 17 (NIPS 2004)

Bibtex Metadata Paper


Sanjoy Dasgupta


We abstract out the core search problem of active learning schemes, to better understand the extent to which adaptive labeling can improve sam- ple complexity. We give various upper and lower bounds on the number of labels which need to be queried, and we prove that a popular greedy active learning rule is approximately as good as any other strategy for minimizing this number of labels.