Analysis of Perceptron-Based Active Learning

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