Worst-Case Analysis of Selective Sampling for Linear Classification
Nicolò Cesa‐Bianchi, Claudio Gentile, Luca Zaniboni · 2006
A selective sampling algorithm is a learning algorithm for classification that, based on the past observed data, decides whether to ask the label of each new instance to be classified. In this paper, we introduce a general technique for turning linear-threshold classification algorithms from the general additive family into randomized selective sampling algorithms. For the most popular algorithms in this family we derive mistake bounds that hold for individual sequences of examples. These bounds