In some learning problems, unlabeled data is freely available, but labeling is costly since it must be done by an expert. Active learning approaches have been shown in many cases to be quite effective in reducing the labeling cost. Active learning algorithms sequentially select points to be labeled to more efficiently explore the hypothesis space. In some applications the cost of labeling may depend on the label value; a positive label may result in a reward, for example. We study an extreme version of this problem, which we call auditing: for binary labels, querying a point with positive label costs nothing, while a negative label costs a single point. In this talk I will describe this new problem, how the new cost structure leads to different algorithms and asymptotic costs than regular active learning for specific hypothesis classes, as well as a competitive approach for the general case. I will close with some ongoing work on applying active learning to problems in linear classification and subspace learning.

Much of this work is with Sivan Sabato (Ben Gurion U.) and Nati Srebro (TTI-Chicago/Technion)