Abstract
Active learning enhances the performance of machine learning methods,particularly in semi-supervised cases, by judiciously selecting a limitednumber of unlabeled data points for labeling, with the goal of improving theperformance of an underlying classifier. In this work, we introduce theMulticlass Active Learning with Auction Dynamics on Graphs (MALADY) frameworkwhich leverages the auction dynamics algorithm on similarity graphs forefficient active learning. In particular, we generalize the auction dynamicsalgorithm on similarity graphs for semi-supervised learning in [24] toincorporate a more general optimization functional. Moreover, we introduce anovel active learning acquisition function that uses the dual variable of theauction algorithm to measure the uncertainty in the classifier to prioritizequeries near the decision boundaries between different classes. Lastly, usingexperiments on classification tasks, we evaluate the performance of ourproposed method and show that it exceeds that of comparison algorithms.