Long-Tailed Recognition via Information-Preservable Two-Stage Learning

AI summary

Overview

• Research area: Machine learning — long-tailed (highly imbalanced) visual recognition, specifically two-stage learning that separates representation learning from classifier fine-tuning.
• Technical level: Advanced. The paper builds its method on mutual information estimation via noise contrastive estimation, Shannon information content, and determinantal point processes with spectral decomposition.
• Scope: The paper proposes a two-stage framework — Balanced Negative Sampling (BNS) for the representation stage and Information-Preservable Determinantal Point Process (IP-DPP) for the sampling stage — and evaluates it against nine long-tailed recognition baselines on four benchmark datasets.

What This Paper Is About

Real-world data often follows a long-tailed distribution, where a few head classes contain most of the data and many tail classes contain very little. Deep classifiers trained on such data develop decision boundaries biased toward head classes, so they perform poorly on tail classes — even though tail-class errors can be costly, as the paper illustrates with the example of failing to identify lung cancer from millions of biomedical images. The paper's goal is to build a two-stage training procedure that fixes this majority-biased tendency while still preserving the information contained in the discarded majority-class data.

Key Contributions

1. Balanced Negative Sampling (BNS) for representation learning. A contrastive representation learning method framed from an information-theoretic perspective. It maximizes mutual information between two augmented views of the same data, and the authors prove this is theoretically equivalent to minimizing intra-class distance, giving an effective and well-separated feature space.

2. Information-Preservable Determinantal Point Process (IP-DPP) for sampling. A sampling strategy that builds a valid DPP from a symmetric stochastic matrix and selects mathematically informative instances, prioritizing samples that are unlikely to be classified correctly, in order to rectify biased decision boundaries without losing overall performance.

3. Theoretical guarantees. The paper proves that the symmetric stochastic matrix used to build the DPP is positive semi-definite (Lemma 4.4) with eigenvalues bounded in [0, 1] (Lemma 4.5), that the resulting determinant-based measurement is a valid probability in [0, 1] (Theorem 4.6), and that sampling probability scales with Shannon information content (Remark 4.7).

4. A computationally efficient sampling algorithm. Algorithm 1 uses the spectral decomposition of the matrix (eigenvalues and orthonormal eigenvectors) to sample a fixed cardinality k per majority class, avoiding the prohibitive cost of directly evaluating Eq. (23).

Main Findings

• New state-of-the-art overall accuracy on CIFAR-10-LT: 76.4%, outperforming all counterparts by at least 2.6%. Breakdown: 82.0% many-shot, 76.3% medium-shot, 67.2% few-shot.

• New state-of-the-art overall accuracy on CIFAR-100-LT: 52.4%, surpassing the prior state-of-the-art DisA by 3.2%. Breakdown: 62.4% many-shot, 59.7% medium-shot, 31.9% few-shot.

• A consistent head-for-tail trade-off. The method lags behind competitors on many-shot accuracy but dominates on medium-shot and few-shot accuracy. On CIFAR-10-LT it trails OTmix by 5.9% in many-shot accuracy yet beats OTmix by 8.5% (medium-shot) and 19.9% (few-shot). On CIFAR-100-LT it trails OTmix by 10.7% in many-shot while improving by 11.7% (medium-shot), 12.8% (few-shot), and 4.3% (overall).

• Best overall accuracy on ImageNet-LT: 51.7%, beating the best baseline DisA by 2.3%. Breakdown: 59.7% many-shot, 50.8% medium-shot, 32.4% few-shot.

• Best overall accuracy on iNaturalist 2018: 74.0%, outperforming the best counterpart SBCL by 3.6%. Breakdown: 72.7% many-shot, 72.9% medium-shot, 75.7% few-shot.

• Highest medium-shot and few-shot accuracy on both large-scale datasets. The authors attribute this to the fact that prior methods produce majority-biased decision boundaries that disproportionately favor head classes.

• Theoretical result on sample size. The expected sample size of the plain DPP in Eq. (19) is N(1 − ln 2), which the authors note reduces the ground set to roughly one-third of its original size — inadequate for balancing class priors in a highly imbalanced setting, motivating the fixed-cardinality IP-DPP variant.

• Not reported: The provided paper content is truncated during Section 5.3 (the quantitative evaluation of BNS against KCL, TSC, and SBCL using linear probing accuracy). Results for that evaluation, the ablation studies, and the conclusion are not included in the available text.

Methodology in Plain English

The framework has two sequential stages.

Stage 1 — learn good features (BNS). The authors start from the idea of maximizing mutual information between two differently augmented views of the same image. Because that quantity cannot be computed directly, they reformulate it as a contrastive learning problem: a binary classifier must tell a matching pair of views apart from noise images drawn from other classes. Using Noise Contrastive Estimation, they show the mutual information is at least as large as a trainable lower bound (up to a constant log n), so maximizing that lower bound maximizes the mutual information itself.

Plain contrastive learning still produces a poorly separated feature space, because positive pairs from head classes dominate. The BNS fix is to draw, for each anchor image, an additional set of m images sharing the same label. This produces m+1 positive pairs and n(m+1) negative pairs per anchor. The authors show mathematically (Theorem 4.1) that maximizing mutual information over same-class views is proportional to minimizing the distance between them, i.e., minimizing intra-class distance. Decomposing the loss (Eq. 14) shows the anchor-itself terms push instance-level semantics, while the extra same-class terms push class-level semantics — together yielding both high-quality and well-separated features.

Stage 2 — fix the biased classifier (IP-DPP). In the second stage, the frozen feature extractor is fine-tuned on balanced subsets. The authors build a determinantal point process, a distribution over subsets where diverse or informative items are more likely to be selected together. Rather than constructing it from the usual marginal kernel — hard to do in long-tailed settings — they use the L-ensemble framework with a matrix S whose entries are built from the classifier's probability p(i) of correctly predicting image i's label. They prove S is positive semi-definite with eigenvalues in [0, 1] and that the resulting determinant ratio is a valid probability.

The key sampling property: for a pair {i, j}, the sampling probability is proportional to 1 − p(i)·p(j), so images the model is less likely to classify correctly are more likely to be sampled. Since Shannon information content is I(x) = −log[p(y|x)], this means the process prioritizes mathematically informative instances.

Two practical problems remain. First, the plain DPP's expected sample size is N(1 − ln 2), too large to balance priors, so the authors define a fixed-cardinality variant that picks k instances per majority class. Second, naive evaluation of that formula is expensive, so Algorithm 1 samples using the eigendecomposition of S — accepting an eigenvector with probability λᵢ/(λᵢ+1), then repeatedly selecting the item with the highest average squared projection onto the remaining subspace.

Why This Matters

The work matters because it attacks both sources of long-tail failure at once — bad feature spaces and biased decision boundaries — and does so with theoretical backing rather than only empirical tricks. The equivalence between mutual information maximization and intra-class distance minimization gives a principled reason why the representation stage should work, and the information-content analysis gives a principled reason why the sampling stage should preserve the majority-class information that naive undersampling discards. Empirically the gains are concentrated where they matter most for safety-critical use: medium-shot and few-shot accuracy.

Real-world applications (as identified in the paper):

• Online transactions, where fraudulent or rare events are the minority class.
• Medical diagnoses, including identifying lung cancer among millions of biomedical images, where a missed tail-class detection can be fatal.
• Social network spam detection, where spam is far rarer than legitimate activity.
• General long-tailed vision benchmarks such as iNaturalist 2018, covering 8,142 species around the world, where rare species are exactly the tail classes.

Industry relevance: The two-stage recipe is modular — BNS is a drop-in upgrade to the representation stage, and IP-DPP is an undersampling strategy that fits existing two-stage pipelines. Because the paper reports largest gains on the medium-shot and few-shot slices that dominate real production distributions, the approach is directly relevant to deployed classifiers where rare-class errors carry the highest cost. Code is released at https://github.com/fudong03/BNS_IPDPP.

Future Directions

1. Shrink the head-class accuracy gap. The method consistently trails baselines on many-shot accuracy (e.g., 5.9% behind OTmix on CIFAR-10-LT and 10.7% behind on CIFAR-100-LT). Closing this gap without surrendering tail-class gains is the most obvious open problem the results raise.

2. Extend beyond image classification. The paper states the approach was evaluated on four image benchmarks (CIFAR-10-LT, CIFAR-100-LT, ImageNet-LT, iNaturalist 2018). Whether BNS and IP-DPP transfer to text, tabular, or multimodal long-tailed problems is untested.

3. Handle extremely small minority classes. The authors note that m in BNS is set to a small value "due to the limited number of samples in minority classes," which suggests the method's behavior when a class has very few or single-digit examples remains an open question.

4. Reduce the cost of Stage 2 sampling. Algorithm 1 already replaces direct evaluation of Eq. (23) with a spectral procedure, but the paper does not report sampling overhead or full training-time numbers in the provided content, leaving efficiency comparisons against re-weighting and simple resampling unresolved.

Target Audience

This paper is for machine learning researchers and graduate students working on class imbalance, long-tailed recognition, and contrastive representation learning, and for practitioners who deploy classifiers on skewed real-world data. Readers will get the most out of it with working familiarity with mutual information, contrastive losses, and point processes; those without that background can still follow the two-stage structure and the benchmark comparisons, but the theoretical claims (Theorems 4.1 and 4.6, Lemmas 4.4 and 4.5) require comfort with linear algebra and information theory.

Authors’ abstract

The imbalance (or long-tail) is the nature of many real-world data distributions, which often induces the undesirable bias of deep classification models toward frequent classes, resulting in poor performance for tail classes. In this paper, we propose a novel two-stage learning approach to mitigate such a majority-biased tendency while preserving valuable information within datasets. Specifically, the first stage proposes a new representation learning technique from the information theory perspective. This approach is theoretically equivalent to minimizing intra-class distance, yielding an effective and well-separated feature space. The second stage develops a novel sampling strategy that selects mathematically informative instances, able to rectify majority-biased decision boundaries without compromising a model's overall performance. As a result, our approach achieves the state-of-the-art performance across various long-tailed benchmark datasets, validated via extensive experiments. Our code is available at https://github.com/fudong03/BNS_IPDPP.