Choosing which data-point to label (active learning)

Question

For an online unsupervised learning algorithm, data-points are learned sequentially. The performance may improve if in addition to the unlabelled data we have some labelled data-points (i.e. semi-supervised learning with a small amount of labelled data). In this situation, it may be attractive to let the algorithm decide which data-points to label, that is, when the algorithm get a new data-point, it may actively decide to request the label of this data-point to the user, because it judges that it is an "important" example. As far as I know, this is called "active learning".

My question is: how or in which situations can a learning algorithm decide that the current example (data-point) is important, and thus requesting its label ? that is, which measures or criteria can allow us to know if we should or not request the label of a given data-point ?

Answer 1

Active learning is a quite recent domain. As far as my knowledge goes, theory doesn't match with practice yet, and you won't find a state-of-the-art method like in other areas. You will nevertheless find lots of recent literature on this field. In addition to the complete survey by Settles proposed by Dikran, I suggest to read the thesis of Daniel Hsu Algorithms for Active Learning, 2010. In this dissertation, the author reviews the theoretical work in active learning.

A well studied criterion for the question "which point the learner should query" is uncertainty sampling. You query the points in which you are the most uncertain of their label. For an intuitive example with SVM, those are the points with $\Pr[Y=1|X] \sim 0.5$ and are located near the margin.

More generally, this problem is often tackled via query by committee. Suppose that at iteration $n$ you don't learn a single classifier $c_n \in \mathcal{C}$ on your data, but a family of classifiers $\mathcal{V}_n \subset \mathcal{C}$ consistent with your labelled data [note 1]. The points considered "important" are then the points where some classifiers in $\mathcal{V}_n$ disagree. Formally, those are the points in the so called disagreement region $\mathcal{R}_n$, $$\mathcal{R}_n = \big\{ x \in \mathcal{X} \mid \exists c_1, c_2 \in \mathcal{V}_n\ s.t.\ c_1(x) \neq c_2(x) \big\}$$

You will find in the literature that after some iterations, this may build an heavily biased labelled set, and potentially mislead the learning algorithm. In order to preserve the consistency of the classifiers, the algorithms DHM and IWAL maintain in $\mathcal{V}_n$ the classifiers with a small error on your dataset.

In practice, this family of classifiers is often intractable, and you will need some heuristics. Some good heuristics are well described in the paper by Beygelzimer, Hsu, Langford and Zhang Agnostic Active Learning Without Constraints, 2010

[note 1] $c(x_i) = y_i ~ \forall c \in \mathcal{V_n}, \forall (x_i,y_i)\ in\ your\ labelled\ data$

Answer 2

There is a very good survey of active learning by Burr Settles that would be a good starting point in answering this question.

Also of interest is an open active learning challenge that was organised for AISTATS and WCII conferences, the proceedings are available here. I provided some of the baseline results for the challenge, and a simple approach based on linear (kernel) ridge regression with random active learning (i.e. just pick the next sample from the pool at random) would have finished in second place had I actually competed. I suspect this is because it is difficult to strike a good balance between exploration and exploitation (see my paper in the proceedings on the baseline methods).