Weak to Strong Learning from Aggregate Labels

• URL: http://arxiv.org/abs/2411.06200v1
• Date: Sat, 09 Nov 2024 14:56:09 GMT
• Title: Weak to Strong Learning from Aggregate Labels
• Authors: Yukti Makhija, Rishi Saket,
• Abstract summary: We study the problem of using a weak learner on such training bags with aggregate labels to obtain a strong learner. A weak learner has at a constant accuracy 1 on the training bags, while a strong learner's accuracy can be arbitrarily close to 1. Our work is the first to theoretically study weak to strong learning from aggregate labels, with an algorithm to achieve the same for LLP.
• Score: 9.804335415337071
• License:
• Abstract: In learning from aggregate labels, the training data consists of sets or "bags" of feature-vectors (instances) along with an aggregate label for each bag derived from the (usually {0,1}-valued) labels of its instances. In learning from label proportions (LLP), the aggregate label is the average of the bag's instance labels, whereas in multiple instance learning (MIL) it is the OR. The goal is to train an instance-level predictor, typically achieved by fitting a model on the training data, in particular one that maximizes the accuracy which is the fraction of satisfied bags i.e., those on which the predicted labels are consistent with the aggregate label. A weak learner has at a constant accuracy < 1 on the training bags, while a strong learner's accuracy can be arbitrarily close to 1. We study the problem of using a weak learner on such training bags with aggregate labels to obtain a strong learner, analogous to supervised learning for which boosting algorithms are known. Our first result shows the impossibility of boosting in LLP using weak classifiers of any accuracy < 1 by constructing a collection of bags for which such weak learners (for any weight assignment) exist, while not admitting any strong learner. A variant of this construction also rules out boosting in MIL for a non-trivial range of weak learner accuracy. In the LLP setting however, we show that a weak learner (with small accuracy) on large enough bags can in fact be used to obtain a strong learner for small bags, in polynomial time. We also provide more efficient, sampling based variant of our procedure with probabilistic guarantees which are empirically validated on three real and two synthetic datasets. Our work is the first to theoretically study weak to strong learning from aggregate labels, with an algorithm to achieve the same for LLP, while proving the impossibility of boosting for both LLP and MIL.

Related papers

• Boosting Consistency in Dual Training for Long-Tailed Semi-Supervised Learning [49.07038093130949]
  Long-tailed semi-supervised learning (LTSSL) algorithms assume that the class distributions of labeled and unlabeled data are almost identical. We propose a new simple method that can effectively utilize unlabeled data from unknown class distributions. We show that BOAT achieves state-of-the-art performance on a variety of standard LTSSL benchmarks.
  arXiv  Detail & Related papers  (2024-06-19T03:35:26Z)
• PAC Learning Linear Thresholds from Label Proportions [13.58949814915442]
  Learning from label proportions (LLP) is a generalization of supervised learning. We show that it is possible to efficiently learn LTFs using LTFs when given access to random bags of some label proportion. We include an experimental evaluation of our learning algorithms along with a comparison with those of [Saket'21, Saket'22] and random LTFs.
  arXiv  Detail & Related papers  (2023-10-16T05:59:34Z)
• Learning from Label Proportions: Bootstrapping Supervised Learners via Belief Propagation [18.57840057487926]
  Learning from Label Proportions (LLP) is a learning problem where only aggregate level labels are available for groups of instances, called bags, during training. This setting arises in domains like advertising and medicine due to privacy considerations. We propose a novel algorithmic framework for this problem that iteratively performs two main steps.
  arXiv  Detail & Related papers  (2023-10-12T06:09:26Z)
• MixBag: Bag-Level Data Augmentation for Learning from Label Proportions [4.588028371034407]
  Learning from label proportions (LLP) is a promising weakly supervised learning problem. We propose a bag-level data augmentation method for LLP called MixBag.
  arXiv  Detail & Related papers  (2023-08-17T07:06:50Z)
• Shrinking Class Space for Enhanced Certainty in Semi-Supervised Learning [59.44422468242455]
  We propose a novel method dubbed ShrinkMatch to learn uncertain samples. For each uncertain sample, it adaptively seeks a shrunk class space, which merely contains the original top-1 class. We then impose a consistency regularization between a pair of strongly and weakly augmented samples in the shrunk space to strive for discriminative representations.
  arXiv  Detail & Related papers  (2023-08-13T14:05:24Z)
• Multi-Instance Partial-Label Learning: Towards Exploiting Dual Inexact Supervision [53.530957567507365]
  In some real-world tasks, each training sample is associated with a candidate label set that contains one ground-truth label and some false positive labels. In this paper, we formalize such problems as multi-instance partial-label learning (MIPL) Existing multi-instance learning algorithms and partial-label learning algorithms are suboptimal for solving MIPL problems.
  arXiv  Detail & Related papers  (2022-12-18T03:28:51Z)
• Trustable Co-label Learning from Multiple Noisy Annotators [68.59187658490804]
  Supervised deep learning depends on massive accurately annotated examples. A typical alternative is learning from multiple noisy annotators. This paper proposes a data-efficient approach, called emphTrustable Co-label Learning (TCL)
  arXiv  Detail & Related papers  (2022-03-08T16:57:00Z)
• L2B: Learning to Bootstrap Robust Models for Combating Label Noise [52.02335367411447]
  This paper introduces a simple and effective method, named Learning to Bootstrap (L2B) It enables models to bootstrap themselves using their own predictions without being adversely affected by erroneous pseudo-labels. It achieves this by dynamically adjusting the importance weight between real observed and generated labels, as well as between different samples through meta-learning.
  arXiv  Detail & Related papers  (2022-02-09T05:57:08Z)
• Fast learning from label proportions with small bags [0.0]
  In learning from label proportions (LLP), the instances are grouped into bags, and the task is to learn an instance classifier given relative class proportions in training bags. In this work, we focus on the case of small bags, which allows designing more efficient algorithms by explicitly considering all consistent label combinations.
  arXiv  Detail & Related papers  (2021-10-07T13:11:18Z)
• Training image classifiers using Semi-Weak Label Data [26.04162590798731]
  In Multiple Instance learning (MIL), weak labels are provided at the bag level with only presence/absence information known. This paper introduces a novel semi-weak label learning paradigm as a middle ground to mitigate the problem. We propose a two-stage framework to address the problem of learning from semi-weak labels.
  arXiv  Detail & Related papers  (2021-03-19T03:06:07Z)
• Are Fewer Labels Possible for Few-shot Learning? [81.89996465197392]
  Few-shot learning is challenging due to its very limited data and labels. Recent studies in big transfer (BiT) show that few-shot learning can greatly benefit from pretraining on large scale labeled dataset in a different domain. We propose eigen-finetuning to enable fewer shot learning by leveraging the co-evolution of clustering and eigen-samples in the finetuning.
  arXiv  Detail & Related papers  (2020-12-10T18:59:29Z)

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.