CS Paper Radar

Diversity-Based Active Learning: An Evaluation of Metric Spaces for Active Learning Selection

Siddharth Chilamkur, Dorit S. Hochbaum

cs.LG ·submitted 2026-08-24 16:30 UTC · v1

Abstract

With rapid advancement over the last few years, many different methods are now widely used for classification. However, training these models requires substantial labeled data. Active Learning is a potential solution to this problem. Pool-based active learning minimizes costs by querying only the most informative samples from an unlabeled dataset. Diversity-based approaches, on the other hand, attempt to select a representative subset of the data. There are many different objectives for determining the selection process, including exact K-center, exact K-median, and Greedy K-center. In this paper, we will focus on evaluating the performance of Greedy K-center across a variety of metric spaces: the raw feature space, a Linear Discriminant Analysis (LDA) space, and a model-derived probability space (with and without entropy-based weighting). Using Random Forest classifiers as a baseline evaluator, our empirical results on synthetic and real-world datasets demonstrate that mapping unlabeled instances into a predictive probability space and weighting the result by entropy often dominates the other options for active learning selection with Greedy K-center.

Closest papers

Nearest neighbours by meaning across the whole index.

k-Volume: a Unified Active Learning Strategy

cs.LG stat.ML ·2026-11-06 ·Eliot Tron, Alain Celisse, Christophe Denis, Alice Le Brigant
similarity 0.70
Abstract

In the classification context where revealing the label of a sample is costly, we propose a new Active Learning (AL) strategy named k-Volume (kVol). It randomly selects a sample to be labeled according to the volume of the smallest ball containing its k nearest neighbors. kVol is highly versatile: it can be applied either in the input space or in the output space, and it enjoys the desirable properties of the three main families of AL strategies: density, diversity, and (when performed in the output space) uncertainty. From a theoretical perspective, we establish that kVol is asymptotically equivalent to uniform sampling over the support of the (input or output) data distribution. Based on experiments on various synthetic and real-life tabular datasets and images, we observe that kVol is surprisingly stable: whatever the classifier or the experimental setup, it still lies among the best AL strategies unlike other competitors that fail dramatically. In particular, kVol outperforms state-of-the-art competitors such as CoreSet, TypiClust or Uncertainty on several real-life datasets, at a low computational cost.

0.19

Fermat ProbCover: Coverage-Based Active Learning on Fermat Distance Graphs

cs.LG ·2026-11-10 ·Gokul Bhusal, Delanna Do, Kevin Miller, Ekaterina Merkurjev, Stephan Wojtowytsch
similarity 0.62
Abstract

Active learning aims to reduce annotation cost by selecting the most informative examples for labeling. In the low-budget regime, where uncertainty-based methods often fail, coverage-based active learning methods such as ProbCover have been shown to be effective. However, these methods typically rely on Euclidean distance, which may not adequately capture the underlying geometry of data. In this article, we propose PC-Fermat, a coverage-based active learning method that replaces Euclidean coverage neighborhoods with neighborhoods defined by a Fermat distance, i.e., a data-adaptive distance that reflects the underlying distribution of the data points. To facilitate computation, we construct a weighted Euclidean neighborhood graph and use a truncated shortest-path algorithm to compute the Fermat coverage graph. We also establish sufficient conditions under which this construction exactly preserves the Fermat coverage computed on the complete graph. Finally, we evaluate PC-Fermat on eight classification datasets across varying labeling budgets, with particular emphasis on the very low-budget regime. Our experimental results demonstrate that PC-Fermat outperforms several existing active learning methods on the majority of the datasets.

0.31

Active Learning of Robust Models

cs.LG cs.AI ·2026-11-06 ·Mizu Nishikawa-Toomey, Andreas Kirsch, Laurent Charlin, Dhanya Sridhar
similarity 0.62
Abstract

In many domains from species identification to cancer diagnosis, labelling data to train predictive models remains costly. In these settings, it is advantageous to intelligently select data points to label to achieve the maximum information gain, this is the motivation behind the study of active learning. In addition to the high costs of acquiring data in such domains, there is the added complexity of data distribution shifts that can occur between training and deployment. For example, the features of cancerous skin cells taken in one country may be different in another region of the world. These two challenges - efficient labelling of data, and learning models robust to distribution shifts have been studied separately but not together, even though these challenges often co-occur in real-life settings. We identify failure modes of standard active learning approaches when the distribution of data at deployment is different from the distribution in which the data is sampled for labelling. We propose a new strategy for efficiently learning classifiers that generalise under specific forms of distribution shift, namely subpopulation shift. Drawing on work in learning from heterogeneous data, we aim to train models that perform well across subpopulations of the data, through active learning. To handle this challenging setting, we exploit the fact that many datasets include metadata about data collection that can serve as a noisy proxy for each sample's underlying subpopulation. We demonstrate how to leverage these noisy labels during active learning selection, and demonstrate empirically that our approach improves classifier accuracy across subpopulations.

0.28

Improving Category-Aware Active Domain Adaptation via Uncertainty-Guided Region Coverage

cs.CV ·2026-10-14 ·My Tra Nguyen Huynh, Viet Cuong Ta
top venuecode/data similarity 0.61
Abstract · Accepted at Machine Learning Journal through ACML Journal Track 2026

Active domain adaptation researches focus on alleviating the annotation cost, which comprises source data and target data labelling, as well as enhancing the performance of unsupervised domain adaptation. However, optimizing the adaptation model based on the average accuracy can lead to the drop in performance of some difficult categories. To overcome this issue, a point-wise selection strategy built upon the influence function can be used to improve domain adaptation performance. In our work, we first address the sensitive and redundant aspects of point-wise selection, which can lead to overfitting of the acquisition function. We thus introduce a region-based approach that ensures the improvement of the adaptation model by maximizing a positive manifold coverage. An uncertainty score is further introduced to the selection mechanism to learn a better decision boundary for the target domain. In comprehensive experiments, our proposed method surpasses the first category-aware active domain adaptation baseline as well as existing active domain adaptation methods across multiple domain adaptation benchmarks. Our implementation is available at: https://github.com/nhtm2702/WHO IS NEXT.

0.45

Enhancing Active Learning Performance with Initial Data Selection Based on Foundation Models

cs.CV cs.AI ·2026-11-18 ·Mohammad Mirzaee, Mehrshad Fallah Estalkhzir, Mohammad Reza Mohammadi
code/data similarity 0.60
Abstract · 26 pages, 18 figures

In active object detection, selecting the initial labeled pool is essential, especially in complex datasets with expensive labeling and low resource budget. This study presents an active learning framework designed to optimize the initial training cycle of active learning for the object detection task. Our approach diverges from traditional methods by utilizing feature-based clustering from the YOLO-World model and refining images based on objectness scores rather than relying on uncertainty sampling in the initial cycle. This approach focuses on finding samples with various features and emphasizes training in areas where the foundation model is most confident. Doing so helps the model better understand different types of objects. For subsequent cycles, we employ a consistency-based sampling technique to maintain the robustness of the training process. To evaluate our method, we use two complex datasets called Aquarium and NWPU VHR-10, which are well known for their diverse object sizes and challenging conditions. In the NWPU dataset, our method increases mAP50 by an average of 6.6% in image-based evaluation. Moreover, the image refinement method shows an improvement of approximately 11% in object-based evaluation. The results show improvements in model performance and labeling time, demonstrating the advantages of using foundation models in early cycles of active learning. An implementation of the algorithm is available at https://github.com/Mhrshd-fllh/ALBoost-FM

0.44

Query Complexity of Learning Axis-Aligned Partitions

cs.DS cs.CGcs.LG ·2026-10-26 ·Hadley Black, Arya Mazumdar, Barna Saha, Geelon So
theory similarity 0.59
Abstract

This work establishes the query complexity of learning high-dimensional boxes in the exact query learning setting. Let $X \subset \mathbb{R}^d$ be a set of $n$ points, labeled by a collection of $k$ boxes: the label of each point in $X$ is determined by the unique box containing it. A learner aims to exactly recover the labels for every point in $X$ given access to a label oracle. We consider three increasingly-structured settings. In the most general setting, there are no conditions on the boxes, and they may overlap. We show that CAL (Cohn-Atlas-Ladner 1994), a classical active learning algorithm, is minimax-optimal with query complexity $Θ(kd \log (n/kd))$. When the boxes are disjoint, we examine two regimes. In the large-$k$ regime, CAL remains minimax-optimal. For the constant-$k$ regime, an optimized variant of the Halving algorithm (Hegedüs 1995) can beat CAL by a $\log(d)$ factor. Finally, in the most-structured settings, the boxes correspond to the leaves of a constant-sized decision tree. We prove a tight query complexity of $Θ(d + \log n)$ that is additive in $d$ and $\log n$, generalizing a recent result (Black-Larsen-Mazumdar-Saha-So 2026) that establishes the query complexity of learning decision stumps.

0.23

Random Feature Pruning for Multi-Class Classification

cs.LG ·2026-10-10 ·Mohammad Amin Omidi, Babak Seyfe, Shahrokh Valaee
theorycode/data similarity 0.58
Abstract · 43 Pages, 6 Figures

Weighted sums of random kitchen sinks (W-RKS) is a commonly used feature extraction technique for supervised learning tasks. A major drawback of this method is the redundancy and ineffectiveness of many extracted random features. This paper investigates efficient methods for reducing such redundancy in multi-class classification problems. We specifically formulate feature selection as a variant of the sequentially nested model selection problem and introduce the Successive Empirical Excess Risk Difference Maximization (SEED-MAX) algorithm. It recursively computes empirical risks to identify the most parsimonious yet informative set of features. We derive an analytical lower bound for the probability of correct feature selection by the SEED-MAX algorithm. This lower bound on the probability of correct feature selection can be made arbitrarily close to one by increasing the training dataset size. To further enhance the rate of pruning, we evaluate the features retained by SEED-MAX using the Fisher test (F-Test). Empirical evaluations on UCR time-series classification datasets show that the sequential application of SEED-MAX with the Fisher test achieves approximately 92 percent rate of pruning with negligible degradation in classification accuracy. Implementations of the SEED-MAX and SEED-MAX-F-Test methods are available at https://github.com/OmidiAmin/seed-max-ftest.

0.45

VC-Dimension and Generalization in Geometric Machine Learning with Applications to Active Learning

cs.LG stat.MLmath.DG ·2026-11-09 ·Gokul Bhusal, Delanna Do, Ekaterina Merkurjev, Kevin Miller, Stephan Wojtowytsch
theory similarity 0.58
Abstract · 19 pages + appendices

We compute the VC-dimension of metric ball classifiers in the model spaces of Riemannian geometry (Euclidean, spherical, hyperbolic) and present upper and lower bounds on the VC-dimension of metric balls in several other situations, including general normed vector spaces (potentially infinite VC-dimension), vector spaces with $\ell^p$-norms (VC-dimension grows at least linearly in the dimension, faster than Euclidean for $p=1$), flat tori, and general Riemannian manifolds (arbitrarily large VC-dimension after a conformal change). In several situations where the VC-dimension is large or even infinite, we prove generalization bounds under additional assumptions on the data distribution using covering arguments. Both in the VC-dimension and covering setting, we consider data on low-dimensional subsets of high-dimensional Euclidean spaces. As an application, we consider coverage-based algorithms in active learning.

0.37