📊 statistics

CuBAS: Information Geometric Curvature-Based Adaptive Sampling for Supervised Classification

CuBAS is an information-geometric adaptive sampling framework for supervised classification that leverages local curvature derived from a Potts Markov random field model to identify and select both homogeneous and boundary-informative data points, achieving superior performance and efficiency across diverse datasets compared to existing methods.

Original authors: Alexandre L. M. Levada

Published 2026-07-07

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Alexandre L. M. Levada

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you are trying to teach a robot how to recognize different types of fruit. You have a massive crate full of apples, oranges, and bananas. Most of the time, you'd just grab a random handful of fruit to show the robot. But here's the problem: if you grab ten apples that all look exactly the same, you haven't taught the robot anything new. You've just wasted time showing it the same thing over and over.

This is the core problem the paper CuBAS tries to solve. It asks: How do we pick the absolute best, most informative handful of fruit to teach a machine, rather than just picking randomly?

Here is how the paper explains it, using simple analogies:

1. The Map of the Fruit Bowl

The authors imagine the entire dataset (all the fruit) not as a pile of objects, but as a landscape or a terrain.

Smooth Hills: In areas where all the apples are grouped together, the terrain is flat and smooth. These are "boring" spots because every piece of fruit looks like its neighbor.
Steep Cliffs: The interesting spots are where the terrain changes abruptly—where the apples suddenly turn into oranges. These are the "cliffs" or decision boundaries.

2. Measuring the "Bendiness" (Curvature)

The paper introduces a clever way to measure how "bendy" or "curvy" this landscape is at any specific point. They call this Curvature.

Low Curvature (Flat Ground): If you stand in the middle of a field of identical apples, the ground is flat. You don't need to show the robot every single apple here; one or two "prototypes" are enough.
High Curvature (The Cliff Edge): If you stand right on the edge where apples meet oranges, the ground bends sharply. This is where the most important information lives. The robot needs to see these specific fruits to learn the difference.

3. The Magic Formula (The Potts Model)

To measure this "bendiness" without actually building a 3D map, the authors use a mathematical tool called the Potts Model.

Think of this model as a way to ask every fruit: "How many of your neighbors look like you?"
If a fruit is surrounded by 10 identical apples, the answer is "10." The model says, "This is a flat, safe spot. Low curvature."
If a fruit is an apple surrounded by 5 apples and 5 oranges, the answer is mixed. The model says, "This is a chaotic, interesting spot. High curvature!"

They use a specific calculation (based on something called Fisher Information) to turn this "neighbor count" into a single number: a Curvature Score.

4. The Smart Filter (CuBAS)

The CuBAS method is essentially a smart filter that sorts the fruit based on these scores:

The "Low-Curvature" Group: These are the boring, repetitive samples. The method keeps only a few representative ones (prototypes) to save space.
The "High-Curvature" Group: These are the "cliff-edge" samples. The method makes sure to keep a good number of these because they are the most valuable for learning.

By mixing a few "prototypes" from the flat areas with the "cliff-edge" samples, CuBAS creates a tiny, super-efficient training set that teaches the robot just as well (or better) than a massive, random pile of data.

5. Why It's Better Than Other Methods

The paper compares CuBAS to two other common ways of picking data:

Random Sampling: Like grabbing fruit with your eyes closed. You might get 10 identical apples and miss the oranges entirely.
Uncertainty Sampling: This is like asking a teacher, "Which fruit are you confused about?" The problem is, if the teacher hasn't learned much yet, their guess about what is "confusing" might be wrong.

CuBAS is different because it doesn't need a teacher or a pre-trained robot to decide what is important. It looks at the shape of the data itself (the geometry) to find the most important spots. It's like looking at a map and seeing the cliffs without needing to walk the whole path first.

The Results

The authors tested this on over 60 different datasets (ranging from medical data to handwritten digits). They found that:

CuBAS consistently built smaller, smarter training sets.
The robots trained on these sets made fewer mistakes than those trained on random sets or sets chosen by "uncertainty."
It worked especially well when there was very little data to start with, proving that picking the right data is more important than having a lot of data.

In a Nutshell

CuBAS is a method that says: "Don't just collect more data; collect the right data." It does this by finding the "edges" and "bends" in the data landscape, ignoring the boring, repetitive parts, and focusing entirely on the spots where the real learning happens.

Technical Summary: CuBAS – Curvature-Based Adaptive Sampling for Supervised Classification

Problem Statement
The effectiveness of supervised classification relies heavily on the quality and representativeness of training samples rather than merely their quantity. Large datasets often contain significant redundancy, noise, and class imbalances, where many samples contribute little to defining decision boundaries. Traditional sampling and instance reduction techniques (e.g., random subsampling, prototype selection) are typically heuristic, operating in the input space without leveraging the intrinsic statistical geometry of the data distribution. Consequently, they often fail to distinguish between informative boundary samples and redundant observations in homogeneous regions. While recent graph-based methods capture neighborhood interactions, they rarely exploit the differential geometry induced by statistical interactions to quantify local sample informativeness.

Methodology: The CuBAS Framework
The paper introduces CuBAS (Curvature-Based Adaptive Sampling), a model-agnostic framework that treats a labeled dataset as a statistical manifold to identify the most informative samples. The methodology proceeds through the following stages:

Graph Construction: A $k$ -nearest-neighbor ( $k$ -NN) graph is constructed from the labeled data.
Statistical Modeling: The graph is modeled as an isotropic $q$ -state Potts Markov Random Field (MRF). In this model, the local conditional probability of a node's label depends on the labels of its neighbors, governed by an inverse temperature parameter $\beta$ that controls the strength of contextual dependence.
Parameter Estimation: The parameter $\beta$ is estimated efficiently using Maximum Pseudo-Likelihood (MPL), avoiding the intractable partition function of the global Gibbs distribution. The estimation employs the secant method for numerical root-finding.
Information Geometric Analysis: The core innovation lies in interpreting the Potts model's parameter space as a statistical manifold endowed with a Riemannian structure via the Fisher Information Metric.
- First-Order Fisher Information ( $\Phi_i$ ): Measures the local sensitivity of the log-likelihood to parameter perturbations (metric structure).
- Second-Order Fisher Information ( $\Psi_i$ ): Measures the curvature of the log-likelihood surface (curvature structure).
- Local Shape Operator: A scalar curvature score $S_i(\beta)$ is derived for each node $i$ as the ratio of the second-order to the first-order Fisher information: $S_i(\beta) = -\Psi_i(\beta) / (\Phi_i(\beta) + \lambda)$ . This score quantifies the local geometric complexity of the data manifold around the sample.
Adaptive Partitioning: The dataset is decomposed into two complementary regimes based on the curvature scores:
- High-Curvature ( $H$ ): Samples near decision boundaries and heterogeneous neighborhoods, which are highly informative.
- Low-Curvature ( $L$ ): Samples in smooth, homogeneous clusters, which are redundant but necessary for structural representation.
- Thresholding: An adaptive threshold $T^*$ is determined to separate these regimes. The method uses Otsu's criterion for bimodal distributions (validated by Ashman's $D$ coefficient) and falls back to a Tukey-fence (IQR) rule for unimodal distributions, ensuring robustness across diverse dataset geometries.
Sampling Strategy: CuBAS constructs a training subset by randomly sampling a proportional number of nodes from both the $H$ and $L$ sets, ensuring the final subset is both compact and maximally discriminative.

Key Contributions

Theoretical Framework: The paper establishes a rigorous connection between graph topology and differential geometry by modeling labeled datasets as statistical manifolds induced by a Potts MRF. It derives closed-form expressions for the first- and second-order Fisher information of the Potts model.
Curvature-Based Metric: It introduces a local shape operator that quantifies statistical curvature without requiring eigendecompositions, kernel density estimates, or pre-trained auxiliary classifiers.
Algorithm Design: The proposal of CuBAS, a computationally efficient algorithm ( $O(nm \log n + nk)$ ) that decomposes datasets into informative and redundant regions based on intrinsic geometric properties rather than classifier uncertainty.
Adaptive Thresholding: The development of a data-driven threshold estimation strategy that adapts to the specific curvature distribution of each dataset, avoiding fixed-quantile heuristics.

Experimental Results
The authors evaluated CuBAS on a benchmark of over 60 publicly available datasets (OpenML), spanning tabular, image, biological, and high-dimensional domains. The evaluation compared CuBAS against random sampling and entropy-based uncertainty sampling (a strong baseline) using a $k$ -NN classifier across 15 training set sizes (10% to 80%).

Performance: CuBAS consistently achieved the highest balanced accuracy across all datasets.
- On small/medium datasets, CuBAS achieved an average balanced accuracy of 0.8556, compared to 0.7416 for entropy sampling and 0.7202 for random sampling.
- On large-scale datasets, CuBAS averaged 0.8455, outperforming entropy (0.7623) and random (0.7273).
- On high-dimensional datasets (HDLSS regime), CuBAS averaged 0.8451, significantly outperforming entropy (0.7573) and random (0.7339).
Data Efficiency: In the most data-scarce regime (10% training budget), CuBAS showed a mean absolute gain of +13.5 percentage points over entropy sampling. The method demonstrated superior stability with lower standard deviations across repetitions.
Robustness: CuBAS maintained performance advantages even in challenging scenarios with high class overlap or extreme dimensionality, where entropy-based methods often failed due to reliance on potentially biased seed classifiers.

Significance and Claims
The paper claims that CuBAS offers a principled, scalable, and geometry-aware alternative to heuristic sampling. Its significance lies in:

Model Independence: Unlike uncertainty-based methods, CuBAS derives informativeness directly from the data's geometric structure, eliminating the need for an auxiliary classifier and avoiding seed-set bias.
Theoretical Grounding: It bridges information geometry and supervised learning, demonstrating that differential-geometric quantities (curvature) provide rigorous criteria for sample selection and redundancy reduction.
Practical Efficiency: The method is computationally efficient (linear in the number of edges) and directly interpretable in terms of the local shape operator of the data manifold.
Generalizability: The consistent improvements across 60+ diverse datasets suggest that exploiting the intrinsic geometry of labeled data manifolds is a robust strategy for constructing compact, high-performance training subsets, particularly in low-budget annotation scenarios.

The authors conclude that CuBAS opens a productive research direction at the intersection of geometric machine learning and data-efficient classification, with potential future extensions to active learning, curvature regularization for ultra-small samples, and integration with deep learning pipelines for warm-up set construction.