The Power of Comparisons for Actively Learning Linear Classifiers

In recent years, the availability of big data and the high cost of labeling has lead to a surge of interest in active learning, an adaptive, semi-supervised learning paradigm. In traditional active learning, given an instance space X, a distribution D on X, and a class of concepts c: X {0, 1}, the learner receives unlabeled samples x from D with the ability to query an oracle for the labeling c(x). Classically our goal would be to minimize the number of samples the learner draws before approximately learning the concept class with high probability (PAClearning). Instead, active learning assumes unlabeled samples are inexpensive, and rather aims to minimize expensive queries to the oracle. While active learning requires exponentially fewer labeled samples than PAClearning for simple classes such as intervals and thresholds, it fails to provide asymptotic improvement for classes essential to machine learning such as linear separators [1]. However, recent results point to the fact that with slight relaxations or additions to the paradigm, such concept classes can be learned with exponentially fewer queries.