Doubly Aggressive Selective Sampling Algorithms for Classification
Koby Crammer · 2014
Online selective sampling algorithms learn to perform binary classification, and additionally they decided whether to ask, or query, for a la-bel of any given example. We introduce two stochastic linear algorithms and analyze them in the worst-case mistake-bound framework. Even though stochastic, for some inputs, our algo-rithms query with probability 1 and make an up-date even if there is no mistake, yet the margin is small, hence they are doubly aggressive. We prove bounds in the worst-case settings, which may be lower than previous bounds in some set-tings. Experiments with 33 document classifica-tion datasets, some with 100Ks examples, show the superiority of doubly-aggressive algorithms both in performance and number of queries. 1