Embracing Biased Transition Matrices for Complementary-Label Learning with Many Classes

• URL: http://arxiv.org/abs/2605.15586v2
• Date: Mon, 18 May 2026 09:18:55 GMT
• Title: Embracing Biased Transition Matrices for Complementary-Label Learning with Many Classes
• Abstract summary: Complementary-label learning (CLL) is a weakly supervised paradigm where instances are labeled with classes they do not belong to.<n>We propose Bias-Induced Constrained Labeling (BICL), a principled framework spanning data collection to training.<n>BICL enables effective learning on CIFAR-100 and TinyImageNet-200, achieving more than sevenfold accuracy improvements over traditional methods.
• Score: 52.84921213617238
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Complementary-label learning (CLL) is a weakly supervised paradigm where instances are labeled with classes they do not belong to. Despite a decade of research, CLL methods remain competitive mainly on 10-class classification, with scaling to large label spaces continuing to be an enduring bottleneck. This limitation stems from the common assumption of uniform label generation in traditional methods, which fatally dilutes the learning signal in many-class settings. In this paper, we demonstrate that this long-standing barrier can be overcome by deliberately designing a biased (non-uniform) generation process that restricts complementary labels to a subset of classes. This finding motivates us to propose Bias-Induced Constrained Labeling (BICL), a principled framework spanning data collection to training that leverages this bias. BICL enables effective learning on CIFAR-100 and TinyImageNet-200, achieving more than sevenfold accuracy improvements over traditional methods. Our findings establish a new trajectory for making CLL feasible for many classes in real-world applications.

Related papers

• Mitigating Label Length Bias in Large Language Models [16.378998802160375]
  normalized contextual calibration (NCC) is an effective method that normalizes and calibrates predictions at the full-label level.<n>NCC achieves statistically significant improvements over prior approaches across multiple datasets and models, with gains of up to 10% F1.<n>Our analysis shows that, when combined with in-context learning, NCC is less sensitive to few-shot example selection, requires fewer examples for competitive performance, and produces more reliable confidence estimates.
  arXiv  Detail & Related papers  (2025-11-18T11:45:24Z)
• Completely Weakly Supervised Class-Incremental Learning for Semantic Segmentation [2.7855886538423182]
  This work addresses the task of completely weakly supervised class-incremental learning for semantic segmentation.<n>To achieve this, we propose to generate robust pseudo-labels by combining pseudo-labels from a localizer and a sequence of foundation models.<n>We also introduce an exemplar-guided data augmentation method that generates diverse images containing both previous and novel classes with guidance.
  arXiv  Detail & Related papers  (2025-05-16T01:43:36Z)
• Exploring Vacant Classes in Label-Skewed Federated Learning [113.65301899666645]
  This paper introduces FedVLS, a novel approach to label-skewed federated learning.<n>It integrates vacant-class distillation and logit suppression simultaneously.<n>Experiments validate the efficacy of FedVLS, demonstrating superior performance compared to previous state-of-the-art (SOTA) methods.
  arXiv  Detail & Related papers  (2024-01-04T16:06:31Z)
• Virtual Category Learning: A Semi-Supervised Learning Method for Dense Prediction with Extremely Limited Labels [63.16824565919966]
  This paper proposes to use confusing samples proactively without label correction. A Virtual Category (VC) is assigned to each confusing sample in such a way that it can safely contribute to the model optimisation. Our intriguing findings highlight the usage of VC learning in dense vision tasks.
  arXiv  Detail & Related papers  (2023-12-02T16:23:52Z)
• Complementary Labels Learning with Augmented Classes [22.460256396941528]
  Complementary Labels Learning (CLL) arises in many real-world tasks such as private questions classification and online learning. We propose a novel problem setting called Complementary Labels Learning with Augmented Classes (CLLAC) By using unlabeled data, we propose an unbiased estimator of classification risk for CLLAC, which is guaranteed to be provably consistent.
  arXiv  Detail & Related papers  (2022-11-19T13:55:27Z)
• Class-Imbalanced Complementary-Label Learning via Weighted Loss [8.934943507699131]
  Complementary-label learning (CLL) is widely used in weakly supervised classification. It faces a significant challenge in real-world datasets when confronted with class-imbalanced training samples. We propose a novel problem setting that enables learning from class-imbalanced complementary labels for multi-class classification.
  arXiv  Detail & Related papers  (2022-09-28T16:02:42Z)
• SoLar: Sinkhorn Label Refinery for Imbalanced Partial-Label Learning [31.535219018410707]
  Partial-label learning (PLL) is a peculiar weakly-supervised learning task where the training samples are generally associated with a set of candidate labels instead of single ground truth. We propose SoLar, a novel framework that allows refine the disambiguated labels towards matching the marginal class prior distribution. SoLar exhibits substantially superior results on standardized benchmarks compared to the previous state-the-art methods.
  arXiv  Detail & Related papers  (2022-09-21T14:00:16Z)
• Transductive CLIP with Class-Conditional Contrastive Learning [68.51078382124331]
  We propose Transductive CLIP, a novel framework for learning a classification network with noisy labels from scratch. A class-conditional contrastive learning mechanism is proposed to mitigate the reliance on pseudo labels. ensemble labels is adopted as a pseudo label updating strategy to stabilize the training of deep neural networks with noisy labels.
  arXiv  Detail & Related papers  (2022-06-13T14:04:57Z)
• Prototypical Classifier for Robust Class-Imbalanced Learning [64.96088324684683]
  We propose textitPrototypical, which does not require fitting additional parameters given the embedding network. Prototypical produces balanced and comparable predictions for all classes even though the training set is class-imbalanced. We test our method on CIFAR-10LT, CIFAR-100LT and Webvision datasets, observing that Prototypical obtains substaintial improvements compared with state of the arts.
  arXiv  Detail & Related papers  (2021-10-22T01:55:01Z)
• Federated Learning with Only Positive Labels [71.63836379169315]
  We propose a generic framework for training with only positive labels, namely Federated Averaging with Spreadout (FedAwS) We show, both theoretically and empirically, that FedAwS can almost match the performance of conventional learning where users have access to negative labels.
  arXiv  Detail & Related papers  (2020-04-21T23:35:02Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.