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
- 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) - Deep Unlearning: Fast and Efficient Gradient-free Approach to Class Forgetting [9.91998873101083]
We introduce a novel class unlearning algorithm designed to strategically eliminate specific classes from the learned model.
Our algorithm exhibits competitive unlearning performance and resilience against Membership Inference Attacks (MIA)
arXiv Detail & Related papers (2023-12-01T18:29:08Z) - 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) - ASPEST: Bridging the Gap Between Active Learning and Selective
Prediction [56.001808843574395]
Selective prediction aims to learn a reliable model that abstains from making predictions when uncertain.
Active learning aims to lower the overall labeling effort, and hence human dependence, by querying the most informative examples.
In this work, we introduce a new learning paradigm, active selective prediction, which aims to query more informative samples from the shifted target domain.
arXiv Detail & Related papers (2023-04-07T23:51:07Z) - 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.