Discover-Then-Rank Unlabeled Support Vectors in the Dual Space for Multi-Class Active Learning

We propose to approach active learning (AL) from a novel perspective of discovering and then ranking potential support vectors by leveraging the key properties of the dual space of a sparse kernel max-margin predictor. We theoretically analyze the change of a hinge loss in the dual form and provide both the upper and lower bounds that are deeply connected to the key geometric properties induced by the dual space, which then help us identify various types of important data samples for AL. These bounds inform the design of a novel sampling strategy that leverages classwise evidence as a key vehicle, formed through an affine combination of dual variables and kernel evaluation. We construct two distinct types of sampling functions, including 1) discovery, which focuses on samples with low total evidence from all classes to support exploration, and 2) ranking, which aims to further refine the decision boundary. These two functions are automatically arranged into a two-phase active sampling process to balance exploration and exploitation. Experiments on various real-world data demonstrate the state-ofthe-art AL performance achieved by our model.