Beyond Disagreement-based Agnostic Active Learning
We study agnostic active learning, where the goal is to learn a classifier in a prespecified hypothesis class interactively with as few label queries as possible, while making no assumptions on the true function generating the labels. The main algorithm for this problem is disagreement-based active learning, which has a high label requirement. Thus a major challenge is to find an algorithm which achieves better label complexity, is consistent in an agnostic setting, and applies to general classification problems. In this paper, we provide such an algorithm. Our solution is based on two novel contributions; first, a reduction from consistent active learning to confidence-rated prediction with guaranteed error, and second, a novel confidence-rated predictor.
This work is on general sample complexity analysis of active learning.  The paper proposes a strategy that requests labels in a subset of the region of disagreement, and thereby obtains sample complexityguarantees that are sometimes better than those obtained via the disagreement coefficient analysis of disagreement-based active learning methods.  This essentially represents a generalization of the margin-based active learning technique of BBZ07.  The sample complexity bounds are general (applicable to any VC class), and are instantiated for linear separators under distributional assumptions as an example.  Bounds are derived for several noise models, including the realizable case, agnostic case with a given noise rate, and Tsybakov noise.More abstractly, the paper establishes an elegant connection between the work on margin-based active learning techniques as refinements of disagreement-based methods, and the more-recent work of El-Yaniv & Wiener discussing the use of selective classification methods for selective sampling.Specifically, El-Yaniv & Wiener have studied the use of perfect selective classification methods to do active learning in the realizable case, and argued that the use of an optimal such method results in the classic CAL active learning algorithm,which is disagreement-based.  From this perspective, the present work is instead investigating the use of *imperfect* selective classification methods (which have a nonzero, but controlled, probability of error on their predictions), and argues that this approach can recover essentially similar behavior to the existing margin-based methods for linear separators (as a special case of this general approach).  This appears to be a nice contribution, and the idea may potentially generate future work.The two comments I might make are:1. It would be nice to have an example other than linear separators,to demonstrate that this general technique has interesting implications beyond what is already known.2. I suggest being a little careful about the claims in the paper.What is shown is that this upper bound on the sample complexity of this method is sometimes superior to the upper bound knownfor disagreement-based methods in terms of the disagreementcoefficient.  This is different from showing that the method sometimes achieves a sample complexity superior to that achievedby disagreement-based methods.