Shachar Lovett

University of California, San Diego

January 23, 2017

An active learning algorithm for a classification problem has access to many unlabelled samples. The algorithm asks for the labels of a small number of samples, carefully chosen, such that that it can leverage this information to correctly label most of the unlabelled samples. It is motivated by many real world applications, where it is much easier and cheaper to obtain access to unlabelled data compared to labelled data. The main question is: can active learning algorithms out-perform classic passive learning algorithms? can we always choose a few unlabelled samples, such that revealing their label will teach us the labels for most of the unlabelled samples? A classical example where this is possible is that of thresholds in the real line. Consider an unknown distribution over $\mathbb R$, where a point $x$ is labelled as 0 if $x