Analysis of a greedy active learning strategy
Sanjoy Dasgupta · 2004
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. 1