Beyond Disagreement-based Agnostic Active Learning

In this paper, we study active learning of classifiers in an agnostic setting, where no assumptions are made on the true function that generates the labels. The learner has access to a large pool of unlabelled examples, and can interactively request labels for a small subset of these; the goal is to learn an accurate classifier in a pre-specified class with as few label queries as possible. Specifically, we are given a hypothesis class H and a target ǫ, and our aim is to find a binary classifier in H whose error is at most ǫ more than that of the best classifier in H, while minimizing the number of requested labels. There has been a large body of previous work on active learning; see the surveys by [Das11, Set10] for overviews. The main challenge in active learning is ensuring consistency in the agnostic setting while still maintaining low label complexity. In particular, a very natural approach to active learning is to view it as a generalization of binary search [FSST97, Das05, Now11]. While this strategy has been extended to several different noise models [Kää06, Now11, NJC13], it is generally inconsistent in the agnostic case [DH08]. The primary algorithm for agnostic active learning is called disagreement-based active learning.