SCoRe: Submodular Combinatorial Representation Learning for Real-World Class-Imbalanced Settings

Anay Majee, Suraj Kothawade, Krishnateja Killamsetty, Rishabh K. Iyer

Introduction

Machine learning models often struggle with real-world datasets characterized by a "long-tail" distribution. In these scenarios, a few "head" classes possess abundant data, while numerous "tail" classes have very few examples. This imbalance leads to two primary challenges in representation learning: inter-class bias, where tail classes are confused with dominant head classes, and intra-class variance, where the model fails to learn cohesive features for diverse examples within a single class.

While state-of-the-art methods like Supervised Contrastive Learning (SupCon) address intra-class variance, they often fall short in mitigating inter-class bias under extreme imbalance. This paper introduces SCoRe (Submodular Combinatorial Representation Learning), a framework that leverages submodular set functions to redefine the representation learning objective.

The SCoRe Framework

SCoRe shifts the focus from traditional pairwise comparisons to a combinatorial perspective. Instead of treating images as individual points, it views the dataset as a collection of sets, where each set corresponds to a class. By applying submodular information measures as loss functions, SCoRe simultaneously optimizes for cluster compactness and inter-class separation.

SCoRe reduces inter-class bias and intra-class variance compared to standard contrastive methods.

The framework utilizes two main submodular formulations:

  1. Total Information ($S_f$): Minimizing this objective encourages "cooperation" within a class, leading to more compact feature clusters and reduced intra-class variance.
  2. Total Correlation ($C_f$): This measure captures the information gain of adding new instances. Minimizing it enforces both tight intra-class clusters and distinct separation between different classes, effectively tackling inter-class bias.

The authors propose three specific loss variants: SCoRe-FL (Facility Location), SCoRe-GC (Graph-Cut), and SCoRe-LogDet. Notably, SCoRe-FL possesses an inherent class-balancing property, naturally weighting rare tail classes more heavily without requiring manual intervention.

Theoretical Unification

A key contribution of this work is the mathematical demonstration that many popular representation learning losses are special cases of the SCoRe framework. As shown in the Venn diagram below, SCoRe provides a unifying theoretical foundation for disparate techniques such as N-pairs, Orthogonal Projection Loss (OPL), and SupCon.

SCoRe unifies various metric and contrastive learning objectives under submodular combinatorial logic.

Experimental Results

SCoRe was evaluated across diverse benchmarks, including ImageNet-LT, MedMNIST, and complex object detection datasets like LVIS and the India Driving Dataset (IDD).

  • Classification: SCoRe achieved significant improvements, including a 7.6% gain on CIFAR/MedMNIST and a 2.1% boost on ImageNet-LT over previous state-of-the-art methods.
  • Object Detection: The framework demonstrated exceptional performance in "in-the-wild" scenarios, delivering a 19.4% enhancement in Mean Average Precision (mAP) for rare classes on the IDD and LVIS datasets.
  • Robustness: Confusion matrix analysis revealed that SCoRe-FL reduced inter-class confusion by over 13% compared to SupCon, highlighting its effectiveness in resolving class ambiguity.

Conclusion

SCoRe represents a significant step forward in addressing class imbalance by moving beyond pairwise heuristics to a principled combinatorial approach. By unifying existing methods and providing robust tools for taming long-tail distributions, SCoRe offers a powerful framework for real-world machine learning applications. Future work will explore extending these submodular objectives to self-supervised learning settings.

Summary updated

BibTeX
@inproceedings{majee2024score,
  author = {Anay Majee and Suraj Kothawade and Krishnateja Killamsetty and Rishabh K. Iyer},
  title = {{SCoRe: Submodular Combinatorial Representation Learning for Real-World Class-Imbalanced Settings}},
  booktitle = {International Conference on Machine Learning},
  year = {2024},
  url = {https://openreview.net/forum?id=G8zDeKOp0R},
}
Figure