Fermat ProbCover: Coverage-Based Active Learning on Fermat Distance Graphs
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.
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.
Figures & tables
| Variable | Description |
|---|---|
| dataset, vertex set (both data and covering graphs) | |
| labeled set | |
| unlabeled set | |
| query set | |
| , | Number of data points and feature dimension |
| Number of classes |
| 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 |
Active Learning
Active learning selects the examples, labels, features, or experiments most useful for improving a model under limited budgets.
See all 330 papers