Improved Active Covering via Density-Based Space Transformation

In this work, we study active covering, a variant of the active-learning problem that involves labeling (or identifying) all of the examples with a positive label. We propose a couple of algorithms, namely Density-Adjusted Non-Adaptive (DANA) learner and Density-Adjusted Adaptive (DAA) learner, that query the labels according to a distance function that is adjusted by the density function. Under mild assumptions, we prove that our algorithms discover all of the positive labels while querying only a sublinear number of examples from the support of negative labels for constant-dimensional spaces (see Theorems 5 and 6). Our experiments show that our champion algorithm DAA consistently improves over the prior work on some standard benchmark datasets, including those used by the previous work, as well as a couple of data sets on credit card fraud. For instance, when measuring performance using AUC, our algorithm is the best in 25 out of 27 experiments over 7 different datasets.