# Learning with Biased Complementary Labels

arXiv: https://arxiv.org/abs/1711.09535 · HTML: https://mlsanity.com/paper/1711.09535/

## Key facts

- Cited by 93 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 27 Nov 2017.

## Built on by (most cited first, 30 of 93)

- [Provably End-to-end Label-Noise Learning without Anchor Points](https://mlsanity.com/paper/2102.02400/) (2021)
- [FINE Samples for Learning with Noisy Labels](https://mlsanity.com/paper/2102.11628/) (2021)
- [Learning Noise Transition Matrix from Only Noisy Labels via Total Variation Regularization](https://mlsanity.com/paper/2102.02414/) (2021)
- [Instance-dependent Label-noise Learning under a Structural Causal Model](https://mlsanity.com/paper/2109.02986/) (2021)
- [Instance-Dependent Label-Noise Learning with Manifold-Regularized Transition Matrix Estimation](https://mlsanity.com/paper/2206.02791/) (2022)
- [ProMix: Combating Label Noise via Maximizing Clean Sample Utility](https://mlsanity.com/paper/2207.10276/) (2022)
- [LongReMix: Robust Learning with High Confidence Samples in a Noisy Label Environment](https://mlsanity.com/paper/2103.04173/) (2021)
- [SoLar: Sinkhorn Label Refinery for Imbalanced Partial-Label Learning](https://mlsanity.com/paper/2209.10365/) (2022)
- [Estimating Instance-dependent Bayes-label Transition Matrix using a Deep Neural Network](https://mlsanity.com/paper/2105.13001/) (2021)
- [Twin Contrastive Learning with Noisy Labels](https://mlsanity.com/paper/2303.06930/) (2023)
- [Progressive Purification for Instance-Dependent Partial Label Learning](https://mlsanity.com/paper/2206.00830/) (2022)
- [MutexMatch: Semi-Supervised Learning with Mutex-Based Consistency Regularization](https://mlsanity.com/paper/2203.14316/) (2022)
- [Long-Tailed Partial Label Learning via Dynamic Rebalancing](https://mlsanity.com/paper/2302.05080/) (2023)
- [On the Robustness of Average Losses for Partial-Label Learning](https://mlsanity.com/paper/2106.06152/) (2021)
- [Learning with Noisy Labels by Efficient Transition Matrix Estimation to Combat Label Miscorrection](https://mlsanity.com/paper/2111.14932/) (2021)
- [Learning from Similarity-Confidence Data](https://mlsanity.com/paper/2102.06879/) (2021)
- [Two Wrongs Don't Make a Right: Combating Confirmation Bias in Learning with Label Noise](https://mlsanity.com/paper/2112.02960/) (2021)
- [BadLabel: A Robust Perspective on Evaluating and Enhancing Label-noise Learning](https://mlsanity.com/paper/2305.18377/) (2023)
- [Rethinking Precision of Pseudo Label: Test-Time Adaptation via Complementary Learning](https://mlsanity.com/paper/2301.06013/) (2023)
- [ScanMix: Learning from Severe Label Noise via Semantic Clustering and Semi-Supervised Learning](https://mlsanity.com/paper/2103.11395/) (2021)
- [Tackling Instance-Dependent Label Noise via a Universal Probabilistic Model](https://mlsanity.com/paper/2101.05467/) (2021)
- [Unsupervised Abstract Reasoning for Raven's Problem Matrices](https://mlsanity.com/paper/2109.10011/) (2021)
- [Realistic Evaluation of Deep Partial-Label Learning Algorithms](https://mlsanity.com/paper/2502.10184/) (2025)
- [PADDLES: Phase-Amplitude Spectrum Disentangled Early Stopping for Learning with Noisy Labels](https://mlsanity.com/paper/2212.03462/) (2022)
- [Instance-dependent Label Distribution Estimation for Learning with Label Noise](https://mlsanity.com/paper/2212.08380/) (2022)
- [Balanced Destruction-Reconstruction Dynamics for Memory-replay Class Incremental Learning](https://mlsanity.com/paper/2308.01698/) (2023)
- [Learning with Complementary Labels Revisited: The Selected-Completely-at-Random Setting Is More Practical](https://mlsanity.com/paper/2311.15502/) (2023)
- [Adaptive Hierarchical Similarity Metric Learning with Noisy Labels](https://mlsanity.com/paper/2111.00006/) (2021)
- [Learning with Proper Partial Labels](https://mlsanity.com/paper/2112.12303/) (2021)
- [Semantic Clustering based Deduction Learning for Image Recognition and Classification](https://mlsanity.com/paper/2112.13165/) (2021)

## Abstract (arXiv)

In this paper, we study the classification problem in which we have access to easily obtainable surrogate for true labels, namely complementary labels, which specify classes that observations do not belong to. Let Y and barY be the true and complementary labels, respectively. We first model the annotation of complementary labels via transition probabilities P(barY=i|Y=j), ineq j∈1,cdots,c, where c is the number of classes. Previous methods implicitly assume that P(barY=i|Y=j), forall ineq j, are identical, which is not true in practice because humans are biased toward their own experience. For example, as shown in Figure 1, if an annotator is more familiar with monkeys than prairie dogs when providing complementary labels for meerkats, she is more likely to employ "monkey" as a complementary label. We therefore reason that the transition probabilities will be different. In this paper, we propose a framework that contributes three main innovations to learning with biased complementary labels: (1) It estimates transition probabilities with no bias. (2) It provides a general method to modify traditional loss functions and extends standard deep neural network classifiers to learn with biased complementary labels. (3) It theoretically ensures that the classifier learned with complementary labels converges to the optimal one learned with true labels. Comprehensive experiments on several benchmark datasets validate the superiority of our method to current state-of-the-art methods.