A general non-parametric active learning framework for classification on multiple manifolds

Active learning is an important paradigm for investigating learners’ behavior and reducing costs on labeling. We propose a novel non-parametric active learning framework which utilizes label propagation to sense the potential data clusters/manifolds in the feature space and minimizes global uncertainty to investigate the unexplored clusters/manifolds for querying examples. Based on this framework, it is convenient to design new active learning algorithms for targeted problems. Furthermore, we analyze the sample selection mechanism of our proposed method and provide a formal proof. While selecting informative examples, our method has the following characteristics: (1) in each iteration, examples are primarily chosen from the cluster which contains unlabeled samples; (2) if there is more than one cluster with unlabeled samples, it will choose from the one containing the most samples; (3) the example which has the closest connection with the others will be preferentially selected for the same cluster. The designed algorithms achieve empirical success in multi-class classification and dramatically reduce the label costs on several real world datasets.