Analysis of Perceptron-Based Active Learning
We start by showing that in an active learning setting, the Perceptron algorithm needs Omega(1/epsilon(2)) labels to learn linear separators within generalization error epsilon. We then present a simple active learning algorithm for this problem, which combines a modification of the Perceptron update with an adaptive filtering rule for deciding which points to query. For data distributed uniformly over the unit sphere, we show that our algorithm reaches generalization error e after asking for just (O) over tilde (d log1/epsilon) labels. This exponential improvement over the usual sample complexity of supervised learning had previously been demonstrated only for the computationally more complex query-by-committee algorithm.
perceptron active learning label complexity bounds online learning