Sufficient Conditions for Agnostic Active Learnable
Liwei Wang · 2009
We study pool-based active learning in the presence of noise, i.e. the agnostic set-ting. Previous works have shown that the effectiveness of agnostic active learning depends on the learning problem and the hypothesis space. Although there are many cases on which active learning is very useful, it is also easy to construct examples that no active learning algorithm can have advantage. In this paper, we propose intuitively reasonable sufficient conditions under which agnostic active learning algorithm is strictly superior to passive supervised learning. We show that under some noise condition, if the Bayesian classification boundary and the underlying distribution are smooth to a finite order, active learning achieves poly-nomial improvement in the label complexity; if the boundary and the distribution are infinitely smooth, the improvement is exponential. 1