Reduction from Complementary-Label Learning to Probability Estimates

• URL: http://arxiv.org/abs/2209.09500v2
• Date: Tue, 11 Apr 2023 06:17:03 GMT
• Title: Reduction from Complementary-Label Learning to Probability Estimates
• Authors: Wei-I Lin, Hsuan-Tien Lin
• Abstract summary: Complementary-Label Learning (CLL) is a weakly-supervised learning problem. This paper introduces a novel perspective--reduction to probability estimates of complementary classes. It offers explanations of several key CLL approaches and allows us to design an improved algorithm.
• Score: 15.835526669091157
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Complementary-Label Learning (CLL) is a weakly-supervised learning problem that aims to learn a multi-class classifier from only complementary labels, which indicate a class to which an instance does not belong. Existing approaches mainly adopt the paradigm of reduction to ordinary classification, which applies specific transformations and surrogate losses to connect CLL back to ordinary classification. Those approaches, however, face several limitations, such as the tendency to overfit or be hooked on deep models. In this paper, we sidestep those limitations with a novel perspective--reduction to probability estimates of complementary classes. We prove that accurate probability estimates of complementary labels lead to good classifiers through a simple decoding step. The proof establishes a reduction framework from CLL to probability estimates. The framework offers explanations of several key CLL approaches as its special cases and allows us to design an improved algorithm that is more robust in noisy environments. The framework also suggests a validation procedure based on the quality of probability estimates, leading to an alternative way to validate models with only complementary labels. The flexible framework opens a wide range of unexplored opportunities in using deep and non-deep models for probability estimates to solve the CLL problem. Empirical experiments further verified the framework's efficacy and robustness in various settings.

Related papers

• Probably Approximately Precision and Recall Learning [62.912015491907994]
  Precision and Recall are foundational metrics in machine learning. One-sided feedback--where only positive examples are observed during training--is inherent in many practical problems. We introduce a PAC learning framework where each hypothesis is represented by a graph, with edges indicating positive interactions.
  arXiv  Detail & Related papers  (2024-11-20T04:21:07Z)
• Appeal: Allow Mislabeled Samples the Chance to be Rectified in Partial Label Learning [55.4510979153023]
  In partial label learning (PLL), each instance is associated with a set of candidate labels among which only one is ground-truth. To help these mislabeled samples "appeal," we propose the first appeal-based framework.
  arXiv  Detail & Related papers  (2023-12-18T09:09:52Z)
• Probabilistic Safety Regions Via Finite Families of Scalable Classifiers [2.431537995108158]
  Supervised classification recognizes patterns in the data to separate classes of behaviours. Canonical solutions contain misclassification errors that are intrinsic to the numerical approximating nature of machine learning. We introduce the concept of probabilistic safety region to describe a subset of the input space in which the number of misclassified instances is probabilistically controlled.
  arXiv  Detail & Related papers  (2023-09-08T22:40:19Z)
• PatchMix Augmentation to Identify Causal Features in Few-shot Learning [55.64873998196191]
  Few-shot learning aims to transfer knowledge learned from base with sufficient categories labelled data to novel categories with scarce known information. We propose a novel data augmentation strategy dubbed as PatchMix that can break this spurious dependency. We show that such an augmentation mechanism, different from existing ones, is able to identify the causal features.
  arXiv  Detail & Related papers  (2022-11-29T08:41:29Z)
• 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)
• Rethinking Clustering-Based Pseudo-Labeling for Unsupervised Meta-Learning [146.11600461034746]
  Method for unsupervised meta-learning, CACTUs, is a clustering-based approach with pseudo-labeling. This approach is model-agnostic and can be combined with supervised algorithms to learn from unlabeled data. We prove that the core reason for this is lack of a clustering-friendly property in the embedding space.
  arXiv  Detail & Related papers  (2022-09-27T19:04:36Z)
• Multi-Class Classification from Single-Class Data with Confidences [90.48669386745361]
  We propose an empirical risk minimization framework that is loss-/model-/optimizer-independent. We show that our method can be Bayes-consistent with a simple modification even if the provided confidences are highly noisy.
  arXiv  Detail & Related papers  (2021-06-16T15:38:13Z)
• Unbiased Subdata Selection for Fair Classification: A Unified Framework and Scalable Algorithms [0.8376091455761261]
  We show that many classification models within this framework can be recast as mixed-integer convex programs. We then show that in the proposed problem, when the classification outcomes, "unsolvable subdata selection," is strongly-solvable. This motivates us to develop an iterative refining strategy (IRS) to solve the classification instances.
  arXiv  Detail & Related papers  (2020-12-22T21:09:38Z)
• Progressive Identification of True Labels for Partial-Label Learning [112.94467491335611]
  Partial-label learning (PLL) is a typical weakly supervised learning problem, where each training instance is equipped with a set of candidate labels among which only one is the true label. Most existing methods elaborately designed as constrained optimizations that must be solved in specific manners, making their computational complexity a bottleneck for scaling up to big data. This paper proposes a novel framework of classifier with flexibility on the model and optimization algorithm.
  arXiv  Detail & Related papers  (2020-02-19T08:35:15Z)

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.