Active Boosted Learning (ActBoost)

Active learning deals with the problem of selecting a small subset of examples to la-bel, from a pool of unlabeled data, for train-ing a good classifier. We develop an ac-tive learning algorithm in the boosting frame-work. In contrast to much of the recent efforts, which has focused on selecting the most ambiguous unlabeled example to label based on the current learned classifier, our algorithm selects examples to maximally re-duce the volume of the version space of fea-sible boosted classifiers. We show that under suitable sparsity assumptions, this strategy achieves the generalization error performance of a boosted classifier trained on the entire data set while only selecting logarithmically many unlabeled samples to label. We also es-tablish a partial negative result, in that with out imposing structural assumptions it is dif-ficult to guarantee generalization error per-formance. We explicitly characterize our con-vergence rate in terms of the sign pattern dif-ferences produced by the weak learners on the unlabeled data. We also present a convex re-laxation to account for the non-convex sparse structure and show that the computational complexity of the resulting algorithm scales polynomially in the number of weak learners. We test ActBoost on several datasets to il-lustrate its performance and demonstrate its robustness to initialization.