Diameter-Based Active Learning

In many situations where a classifier is to be learned, it is easy to collect unlabeled data but costly to obtain labels. This has motivated the pool-based active learning model, in which a learner has access to a collection of unlabeled data points and is allowed to ask for individual labels in an adaptive manner. The hope is that choosing these queries intelligently will rapidly yield a low-error classifier, much more quickly than with random querying. A central focus of active learning is developing efficient querying strategies and understanding their label complexity. Over the past decade or two, there has been substantial progress in developing such rigorously-justified active learning schemes for general concept classes. For the most part, these schemes can be described as mellow: rather than focusing upon maximally informative points, they query any point whose label cannot reasonably be inferred from the information received so far.