Fermat ProbCover: Coverage-Based Active Learning on Fermat Distance Graphs
Authors: Gokul Bhusal, Delanna Do, Kevin Miller, Ekaterina Merkurjev, Stephan Wojtowytsch
Organizations: Department of Mathematics, University of California, Los Angeles, CA 90095, USA. · Department of Mathematics, University of Pittsburgh, Pittsburgh, PA 15213, USA. · Department of Mathematics, Brigham Young University, UT 84602, USA. · Department of Mathematics and CMSE, Michigan State University, MI 48824, USA.
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.
Figures & tables
Variable
Description
X
dataset, vertex set (both data and covering graphs)
L
labeled set
U
unlabeled set
Q
query set
n , d
Number of data points and feature dimension
C
Number of classes
TABLE I : Notation Table
Fig. 1 : Fermat paths between two points at opposite ends of a moon-shaped dataset for different p values.
Fig. 2 : (a) The two-moon dataset with the chosen center (star) at the tip of the lower moon. (b) Euclidean ball with ϵ=0.3 ; the dashed circle marks its radius. (c) Fermat ball with p=3 and r=0.15p . The Euclidean ball crosses the gap into the upper moon, while the Fermat ball, despite containing more points, follows the dense region of the lower moon and contains points that are mostly of the same class.
Fig. 3 : Flowchart of PC-Fermat framework. Given an input dataset, we construct a weighted Euclidean ϵ -neighborhood graph and obtain the Fermat coverage graph using shortest-path computations. A greedy coverage-based selection procedure then identifies b representative samples. Finally, predictions are made using a 1-NN classifier, and classification accuracy is evaluated across different labeling budgets.
Dataset
Samples
Features
Type
Classes
Coil-20
1,440
1,024
Raw
20
Opt-Digits
5,620
64
Raw
10
Landsat
6,435
36
Raw
6
USPS
9,298
256
Raw
10
Jasper
10,000
198
Raw
4
Pendigits
10,992
16
Raw
10
TABLE II : Datasets used in the experiments.
Fig. 4 : Accuracy vs. # of labeled points for each dataset: (a) COIL-20 (b) Opt-Digits (c) Landsat (d) USPS (e) Pendigits (f) Jasper (g) Fashion-MNIST (h) MNIST.
Fig. 5 : Evolution of largest connected components of the ϵ -neighborhood graph with increasing ϵ . Each colored band shows the size of one component; the black line shows their total size, and the red dashed line marks the total number of points. COIL-20 (left) contains several well-separated clusters, while Landsat (right) is dominated by a single connected component.
Two active learning algorithms for hyperspectral image (HSI) classification are proposed that combine density-aware Fermat distances with Poisson-reweighted harmonic label propagation. Our methods actively query points using an uncertainty-based acquisition function, extending Poisson ReWeighted Laplace Learning (PWLL). Our first algorithm, Fermat Active Laplace Learning (FALL), builds an affinity matrix using Fermat distances between all data points. Then, PWLL is run with a diagonal perturbation using the minimum-norm acquisition function. In contrast, Approximate FALL (A-FALL) computes Fermat distances between each data point and landmark pixels selected via farthest-point sampling and constructs the affinity matrix using landmark multidimensional scaling. After several query rounds, A-FALL selects the Fermat exponent p using a leave-one-out cross-validation variant. FALL and A-FALL leverage Fermat distances and subsequent harmonic label propagation to provide a density-aware estimation of the data manifold, improving labeling accuracy. Experiments on Salinas A and Pavia show the effectiveness of FALL and the scalability of A-FALL to large HSI scenes.
Vutichart Buranasiri, James M. Murphy
Department of Mathematics Tufts University Medford, MA 02155, USA
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.
Training medical image classifiers on entire datasets is wasteful when annotation budgets are limited: not all samples contribute equally, yet acquiring expert labels is expensive. Active learning reduces annotation cost through iterative querying, but assumes repeated access to an oracle and requires multiple rounds of model training. One-shot geometry-based methods such as facility location avoid retraining but operate on pairwise distances that ignore the local structure of the data manifold. We propose a graph-based one-shot selection method that operates entirely on frozen foundation model embeddings. Given embeddings from a pretrained encoder, we construct a k-nearest neighbor graph over all training samples and derive a two-term coverage kernel from the heat diffusion kernel, capturing both direct and two-hop neighborhood relationships. Greedy facility location on this kernel selects class-balanced subsets that maximize coverage of the data manifold. The two-term kernel matches the full spectral heat kernel in selection behavior while reducing computation to sparse matrix operations with a single hyperparameter. We evaluate on five MedMNIST datasets spanning histopathology, radiology, and microscopy, comparing against both training-dynamics and geometry-based baselines. Our method achieves the highest balanced accuracy on nine of ten dataset-ratio conditions, with the largest gains on class-imbalanced datasets where global graph construction captures cross-class structure that per-class methods miss, all without any model training during selection. Code is available at https://github.com/zahiriddin-rustamov/graph-coverage-selection.