Robust Selective Sampling from Single and Multiple Teachers
Ofer Dekel, Claudio Gentile and Karthik Sridharan
We present a new online learning algorithm in the selective sampling
framework, where labels must be actively queried before they are
revealed. We prove bounds on the regret of our algorithm and on the
number of labels it queries when faced with an adaptive adversarial
strategy of generating the instances. Our bounds both generalize and
strictly improve over previous bounds in similar settings.
Using a simple online-to-batch
conversion technique, our selective sampling algorithm can be
converted into a statistical (pool-based) active learning
algorithm. We extend our algorithm and analysis to the
multiple-teacher setting, where the algorithm can choose which
subset of teachers to query for each label.