Learning from Complementary Labels

Abstract

Collecting labeled data is costly and thus a critical bottleneck in real-world classification tasks. To mitigate this problem, we propose a novel setting, namely learning from complementary labels for multi-class classification. A complementary label specifies a class that a pattern does not belong to. Collecting complementary labels would be less laborious than collecting ordinary labels, since users do not have to carefully choose the correct class from a long list of candidate classes. However, complementary labels are less informative than ordinary labels and thus a suitable approach is needed to better learn from them. In this paper, we show that an unbiased estimator to the classification risk can be obtained only from complementarily labeled data, if a loss function satisfies a particular symmetric condition. We derive estimation error bounds for the proposed method and prove that the optimal parametric convergence rate is achieved. We further show that learning from complementary labels can be easily combined with learning from ordinary labels (i.e., ordinary supervised learning), providing a highly practical implementation of the proposed method. Finally, we experimentally demonstrate the usefulness of the proposed methods.

NIPS 2017 camera-ready version

Cited by in corpus (32)

• A Survey of Label-noise Representation Learning: Past, Present and Future
• On Symmetric Losses for Learning from Corrupted Labels
• Provably Consistent Partial-Label Learning
• Progressive Identification of True Labels for Partial-Label Learning
• Instance-Dependent PU Learning by Bayesian Optimal Relabeling
• Learning with Bounded Instance- and Label-dependent Label Noise
• Learning Noise Transition Matrix from Only Noisy Labels via Total Variation Regularization
• Learning with Multiple Complementary Labels
• Complementary-Label Learning for Arbitrary Losses and Models
• Online Multiclass Classification Based on Prediction Margin for Partial Feedback
• Learning from a Complementary-label Source Domain: Theory and Algorithms
• Learning with Biased Complementary Labels
• Negative Confidence-Aware Weakly Supervised Binary Classification for Effective Review Helpfulness Classification
• Learning from Indirect Observations
• Multi-Complementary and Unlabeled Learning for Arbitrary Losses and Models
• Clarinet: A One-step Approach Towards Budget-friendly Unsupervised Domain Adaptation
• Learnability with Indirect Supervision Signals
• Bridging Ordinary-Label Learning and Complementary-Label Learning
• Pointwise Binary Classification with Pairwise Confidence Comparisons
• NLNL: Negative Learning for Noisy Labels
• Robust conditional GANs under missing or uncertain labels
• Lower-Bounded Proper Losses for Weakly Supervised Classification
• Generative-Discriminative Complementary Learning
• Learning from Ambiguous Labels for Lung Nodule Malignancy Prediction
• Binary Classification from Positive Data with Skewed Confidence
• Learning from Multiple Noisy Partial Labelers
• Binary Classification from Multiple Unlabeled Datasets via Surrogate Set Classification
• Multi-Class Classification from Single-Class Data with Confidences
• Learning from Similarity-Confidence Data
• Unsupervised Abstract Reasoning for Raven's Problem Matrices
• Multi-Label Learning from Single Positive Labels
• Negative Pseudo Labeling using Class Proportion for Semantic Segmentation in Pathology