Efficient Active Learning with Abstention

• URL: http://arxiv.org/abs/2204.00043v1
• Date: Thu, 31 Mar 2022 18:34:57 GMT
• Title: Efficient Active Learning with Abstention
• Authors: Yinglun Zhu, Robert Nowak
• Abstract summary: We develop the first computationally efficient active learning algorithm with abstention. A key feature of the algorithm is that it avoids the undesirable "noise-seeking" behavior often seen in active learning.
• Score: 12.315392649501101
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: The goal of active learning is to achieve the same accuracy achievable by passive learning, while using much fewer labels. Exponential savings in label complexity are provably guaranteed in very special cases, but fundamental lower bounds show that such improvements are impossible in general. This suggests a need to explore alternative goals for active learning. Learning with abstention is one such alternative. In this setting, the active learning algorithm may abstain from prediction in certain cases and incur an error that is marginally smaller than $\frac{1}{2}$. We develop the first computationally efficient active learning algorithm with abstention. Furthermore, the algorithm is guaranteed to only abstain on hard examples (where the true label distribution is close to a fair coin), a novel property we term "proper abstention" that also leads to a host of other desirable characteristics. The option to abstain reduces the label complexity by an exponential factor, with no assumptions on the distribution, relative to passive learning algorithms and/or active learning that are not allowed to abstain. A key feature of the algorithm is that it avoids the undesirable "noise-seeking" behavior often seen in active learning. We also explore extensions that achieve constant label complexity and deal with model misspecification.

Related papers

• DIRECT: Deep Active Learning under Imbalance and Label Noise [15.571923343398657]
  We conduct the first study of active learning under both class imbalance and label noise. We propose a novel algorithm that robustly identifies the class separation threshold and annotates the most uncertain examples. Our results demonstrate that DIRECT can save more than 60% of the annotation budget compared to state-of-art active learning algorithms.
  arXiv  Detail & Related papers  (2023-12-14T18:18:34Z)
• One-bit Supervision for Image Classification: Problem, Solution, and Beyond [114.95815360508395]
  This paper presents one-bit supervision, a novel setting of learning with fewer labels, for image classification. We propose a multi-stage training paradigm and incorporate negative label suppression into an off-the-shelf semi-supervised learning algorithm. In multiple benchmarks, the learning efficiency of the proposed approach surpasses that using full-bit, semi-supervised supervision.
  arXiv  Detail & Related papers  (2023-11-26T07:39:00Z)
• Neural Active Learning on Heteroskedastic Distributions [29.01776999862397]
  We demonstrate the catastrophic failure of active learning algorithms on heteroskedastic datasets. We propose a new algorithm that incorporates a model difference scoring function for each data point to filter out the noisy examples and sample clean examples.
  arXiv  Detail & Related papers  (2022-11-02T07:30:19Z)
• Active Learning with Neural Networks: Insights from Nonparametric Statistics [12.315392649501101]
  This paper provides the first near-optimal label complexity guarantees for deep active learning. Under standard low noise conditions, we show that active learning with neural networks can provably achieve the minimax label complexity. We also develop an efficient deep active learning algorithm that achieves $mathsfpolylog(frac1epsilon)$ label complexity, without any low noise assumptions.
  arXiv  Detail & Related papers  (2022-10-15T19:57:09Z)
• Learning with Proper Partial Labels [87.65718705642819]
  Partial-label learning is a kind of weakly-supervised learning with inexact labels. We show that this proper partial-label learning framework includes many previous partial-label learning settings. We then derive a unified unbiased estimator of the classification risk.
  arXiv  Detail & Related papers  (2021-12-23T01:37:03Z)
• Robust Long-Tailed Learning under Label Noise [50.00837134041317]
  This work investigates the label noise problem under long-tailed label distribution. We propose a robust framework,algo, that realizes noise detection for long-tailed learning. Our framework can naturally leverage semi-supervised learning algorithms to further improve the generalisation.
  arXiv  Detail & Related papers  (2021-08-26T03:45:00Z)
• Nonparametric adaptive active learning under local smoothness condition [0.76146285961466]
  This paper adresses the problem of adaptive active learning in a nonparametric setting with minimal assumptions. We present a novel algorithm that is valid under more general assumptions than the previously known algorithms. Our algorithm achieves a minimax rate of convergence, and therefore performs almost as well as the best known non-adaptive algorithms.
  arXiv  Detail & Related papers  (2021-02-22T14:47:21Z)
• Bounded Memory Active Learning through Enriched Queries [28.116967200489192]
  Active learning is a paradigm in which data-hungry learning algorithms adaptively select informative examples in order to lower expensive labeling costs. To combat this, a series of recent works have considered a model in which the learner may ask enriched queries beyond labels. While such models have seen success in drastically lowering label costs, they tend to come at the expense of requiring large amounts of memory.
  arXiv  Detail & Related papers  (2021-02-09T19:00:00Z)
• Minimax Active Learning [61.729667575374606]
  Active learning aims to develop label-efficient algorithms by querying the most representative samples to be labeled by a human annotator. Current active learning techniques either rely on model uncertainty to select the most uncertain samples or use clustering or reconstruction to choose the most diverse set of unlabeled examples. We develop a semi-supervised minimax entropy-based active learning algorithm that leverages both uncertainty and diversity in an adversarial manner.
  arXiv  Detail & Related papers  (2020-12-18T19:03:40Z)
• Meta-learning with Stochastic Linear Bandits [120.43000970418939]
  We consider a class of bandit algorithms that implement a regularized version of the well-known OFUL algorithm, where the regularization is a square euclidean distance to a bias vector. We show both theoretically and experimentally, that when the number of tasks grows and the variance of the task-distribution is small, our strategies have a significant advantage over learning the tasks in isolation.
  arXiv  Detail & Related papers  (2020-05-18T08:41:39Z)
• 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.