Abstract:

We study the problem of active learning in a stream-based setting, allowing
the distribution of the examples to change over time.  We prove upper bounds
on the number of prediction mistakes and number of label requests for established
disagreement-based active learning algorithms, both in the realizable case and under
Tsybakov noise. We further prove minimax lower bounds for this problem.

We also explore a transfer learning setting, in which a finite sequence of target
concepts are sampled independently with an unknown distribution from a known family.
We study the total number of labeled examples required to learn all targets
to an arbitrary specified expected accuracy, focusing on the asymptotics in the
number of tasks and the desired accuracy.  Our primary interest is formally understanding
the fundamental benefits of transfer learning, compared to learning each target 
independently from the others.  Our approach to the transfer problem is general,
in the sense that it can be used with a variety of learning protocols.  The key 
insight driving our approach is that the distribution of the target concepts is 
identifiable from the joint distribution over a number of random labeled data 
points equal the Vapnik-Chervonenkis dimension of the concept space.  This is 
not necessarily the case for the joint distribution over any smaller number of points.
This work has particularly interesting implications when applied to active learning 
methods. In particular, we study in detail the benefits of transfer for self-verifying 
active learning; in this setting, we find that the number of labeled examples 
required for learning with transfer is often significantly smaller than that 
required for learning each target independently.