Online Selective Classification with Limited Feedback

• URL: http://arxiv.org/abs/2110.14243v1
• Date: Wed, 27 Oct 2021 08:00:53 GMT
• Title: Online Selective Classification with Limited Feedback
• Authors: Aditya Gangrade, Anil Kag, Ashok Cutkosky, Venkatesh Saligrama
• Abstract summary: We study selective classification in the online learning model, wherein a predictor may abstain from classifying an instance. Two salient aspects of the setting we consider are that the data may be non-realisable, due to which abstention may be a valid long-term action. We construct simple versioning-based schemes for any $mu in (0,1],$ that make most $Tmu$ mistakes while incurring smash$tildeO(T1-mu)$ excess abstention against adaptive adversaries.
• Score: 82.68009460301585
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Motivated by applications to resource-limited and safety-critical domains, we study selective classification in the online learning model, wherein a predictor may abstain from classifying an instance. For example, this may model an adaptive decision to invoke more resources on this instance. Two salient aspects of the setting we consider are that the data may be non-realisable, due to which abstention may be a valid long-term action, and that feedback is only received when the learner abstains, which models the fact that reliable labels are only available when the resource intensive processing is invoked. Within this framework, we explore strategies that make few mistakes, while not abstaining too many times more than the best-in-hindsight error-free classifier from a given class. That is, the one that makes no mistakes, while abstaining the fewest number of times. We construct simple versioning-based schemes for any $\mu \in (0,1],$ that make most $T^\mu$ mistakes while incurring \smash{$\tilde{O}(T^{1-\mu})$} excess abstention against adaptive adversaries. We further show that this dependence on $T$ is tight, and provide illustrative experiments on realistic datasets.

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)
• Agnostic Smoothed Online Learning [5.167069404528051]
  We propose an algorithm to guarantee sublinear regret for smoothed online learning without prior knowledge of $mu$. R-Cover has adaptive regret $tilde O(sqrtdT/sigma)$ for function classes with dimension $d$, which is optimal up to logarithmic factors.
  arXiv  Detail & Related papers  (2024-10-07T15:25:21Z)
• Rejection via Learning Density Ratios [50.91522897152437]
  Classification with rejection emerges as a learning paradigm which allows models to abstain from making predictions. We propose a different distributional perspective, where we seek to find an idealized data distribution which maximizes a pretrained model's performance. Our framework is tested empirically over clean and noisy datasets.
  arXiv  Detail & Related papers  (2024-05-29T01:32:17Z)
• Label-Retrieval-Augmented Diffusion Models for Learning from Noisy Labels [61.97359362447732]
  Learning from noisy labels is an important and long-standing problem in machine learning for real applications. In this paper, we reformulate the label-noise problem from a generative-model perspective. Our model achieves new state-of-the-art (SOTA) results on all the standard real-world benchmark datasets.
  arXiv  Detail & Related papers  (2023-05-31T03:01:36Z)
• Characterizing Datapoints via Second-Split Forgetting [93.99363547536392]
  We propose $$-second-$split$ $forgetting$ $time$ (SSFT), a complementary metric that tracks the epoch (if any) after which an original training example is forgotten. We demonstrate that $mislabeled$ examples are forgotten quickly, and seemingly $rare$ examples are forgotten comparatively slowly. SSFT can (i) help to identify mislabeled samples, the removal of which improves generalization; and (ii) provide insights about failure modes.
  arXiv  Detail & Related papers  (2022-10-26T21:03:46Z)
• Learning When to Say "I Don't Know" [0.5505634045241288]
  We propose a new Reject Option Classification technique to identify and remove regions of uncertainty in the decision space. We consider an alternative formulation by instead analyzing the complementary reject region and employing a validation set to learn per-class softmax thresholds. We provide results showing the benefits of the proposed method over na"ively thresholding/uncalibrated softmax scores with 2-D points, imagery, and text classification datasets.
  arXiv  Detail & Related papers  (2022-09-11T21:50:03Z)
• A Low Rank Promoting Prior for Unsupervised Contrastive Learning [108.91406719395417]
  We construct a novel probabilistic graphical model that effectively incorporates the low rank promoting prior into the framework of contrastive learning. Our hypothesis explicitly requires that all the samples belonging to the same instance class lie on the same subspace with small dimension. Empirical evidences show that the proposed algorithm clearly surpasses the state-of-the-art approaches on multiple benchmarks.
  arXiv  Detail & Related papers  (2021-08-05T15:58:25Z)
• Cold-start Active Learning through Self-supervised Language Modeling [15.551710499866239]
  Active learning aims to reduce annotation costs by choosing the most critical examples to label. With BERT, we develop a simple strategy based on the masked language modeling loss. Compared to other baselines, our approach reaches higher accuracy within less sampling iterations and time.
  arXiv  Detail & Related papers  (2020-10-19T14:09:17Z)
• Identifying Wrongly Predicted Samples: A Method for Active Learning [6.976600214375139]
  We propose a simple sample selection criterion that moves beyond uncertainty. We show state-of-the-art results and better rates at identifying wrongly predicted samples.
  arXiv  Detail & Related papers  (2020-10-14T09:00:42Z)

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.