In the quest to build AI that learns like we do, we often overlook a messy reality: the world isn't balanced. While standard machine learning benchmarks provide neatly organized, perfectly distributed classes, real-world data arrives in a chaotic, "long-tailed" stream.
A new paper by Aristotelis Chrysakis and Marie-Francine Moens introduces a simple yet powerful algorithm to handle this: Class-Balancing Reservoir Sampling (CBRS).
TL;DR
Most continual learning algorithms fail when data is imbalanced, leading to "catastrophic forgetting" of rare classes. This paper introduces CBRS, a memory management strategy that actively balances stored examples to ensure rare classes aren't drowned out. It outperforms state-of-the-art methods by up to 40% on complex datasets with negligible computational overhead.
What Problem Does This Paper Address?
Neural networks are notoriously bad at Continual Learning (CL)—the ability to learn from a stream of data without forgetting previous tasks. This is known as catastrophic forgetting.
The authors identify a major blind spot in CL research: imbalance. Most researchers assume that every class appears with equal frequency. In reality, a robot or a self-driving car might see thousands of "pedestrian" examples but only a handful of "fallen tree" examples.
In the Online CL setting, the model sees a "continuum" of data in tiny batches and cannot revisit old batches unless it saves them in a tiny, fixed-size "episodic memory." If that memory is populated using standard methods (like Reservoir Sampling), it will naturally mirror the imbalance of the input stream, causing the model to effectively "forget" that rare classes ever existed.
Methods
The authors propose a two-pronged approach to keep the model's "memory" healthy:
-
Class-Balancing Reservoir Sampling (CBRS): Unlike standard reservoir sampling, which treats all incoming points equally, CBRS prioritizes balance.
-
Stage 1: Fill the memory with whatever comes first.
- Stage 2: Once the memory is full, if a new instance belongs to a class that is underrepresented (not "full"), the algorithm finds an instance from the currently largest class in memory and overwrites it.
- If the new instance belongs to a class that is already well-represented, it uses standard reservoir sampling logic to decide whether to replace an existing instance of the same class.
- Weighted Random Replay: Even with CBRS, some classes might still be smaller than others if the stream simply didn't provide enough examples. To fix this during training, the authors use a custom replay scheme where the probability of picking an instance for a training update is inversely proportional to its class frequency in memory. This effectively "oversamples" the minority classes during the replay phase.
Datasets & Key Insights
The researchers evaluated their approach on four standard image benchmarks (MNIST, Fashion-MNIST, CIFAR-10, and CIFAR-100), modified to simulate extreme real-world imbalance. They applied "retention factors" to each class, creating streams where the most common class could be 100 times more frequent than the rarest.
- The "Fairness" Guarantee: A key mathematical property of CBRS is that if a class has fewer than $m/n_c$ instances (where $m$ is memory size and $n_c$ is the number of classes), every single instance of that class will be stored. It guarantees that the rarest data is never discarded.
- IID Sampling: Within each class, CBRS maintains an "independent and identically distributed" (iid) sample. This ensures the memory isn't just full of the most recent examples of a class, but a representative cross-section.
- Efficiency is King: Many CL methods (like GSS) require calculating gradients for every incoming point to decide what to store, which is computationally expensive. CBRS is nearly as fast as random sampling and requires almost no extra memory overhead (just a few integers to track class counts).
Key Results
The results were striking, particularly as the complexity of the dataset increased:
- CIFAR-100: CBRS achieved 40.2% accuracy, while the previous state-of-the-art (Reservoir Sampling) trailed at 28.1%. Gradient-Space Sampling (GSS) performed even worse at 23.0%.
- Computational Speed: On CIFAR-100, CBRS processed batches in roughly 358ms, while GSS took over 3600ms—an order of magnitude slower for worse performance.
- Ablation: The authors showed that while Weighted Replay helps, the heavy lifting is done by the CBRS memory population strategy itself.
Limitations and Future Work
While CBRS is highly effective, the authors note a few areas for growth:
- Class Difficulty: Currently, CBRS assumes all classes are equally hard to learn. Future versions could potentially prioritize storing instances from "difficult" classes rather than just "rare" ones.
- Supervised Requirement: The algorithm relies on knowing the class labels ($y_i$) to perform balancing. In a purely unsupervised or self-supervised stream, a different proxy for "balance" would be needed.
- Fixed Class Count: The current logic for the loss weighting ($a = 1/n_c$) assumes the learner knows how many classes it has seen so far, which might be tricky in completely open-ended environments.
Summary updated