Apple Tasting Revisited: Bayesian Approaches to Partially Monitored Online Binary Classification

• URL: http://arxiv.org/abs/2109.14412v2
• Date: Mon, 22 Apr 2024 16:24:55 GMT
• Title: Apple Tasting Revisited: Bayesian Approaches to Partially Monitored Online Binary Classification
• Authors: James A. Grant, David S. Leslie,
• Abstract summary: We consider a variant of online binary classification where a learner sequentially assigns labels to items with unknown true class. If, but only if, the learner chooses label $1$ they immediately observe the true label of the item. The learner faces a trade-off between short-term classification accuracy and long-term information gain.
• Score: 4.204990010424083
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We consider a variant of online binary classification where a learner sequentially assigns labels ($0$ or $1$) to items with unknown true class. If, but only if, the learner chooses label $1$ they immediately observe the true label of the item. The learner faces a trade-off between short-term classification accuracy and long-term information gain. This problem has previously been studied under the name of the `apple tasting' problem. We revisit this problem as a partial monitoring problem with side information, and focus on the case where item features are linked to true classes via a logistic regression model. Our principal contribution is a study of the performance of Thompson Sampling (TS) for this problem. Using recently developed information-theoretic tools, we show that TS achieves a Bayesian regret bound of an improved order to previous approaches. Further, we experimentally verify that efficient approximations to TS and Information Directed Sampling via P\'{o}lya-Gamma augmentation have superior empirical performance to existing methods.

Related papers

• On Characterizing and Mitigating Imbalances in Multi-Instance Partial Label Learning [57.18649648182171]
  We make contributions towards addressing a problem that hasn't been studied so far in the context of MI-PLL. We derive class-specific risk bounds for MI-PLL, while making minimal assumptions. Our theory reveals a unique phenomenon: that $sigma$ can greatly impact learning imbalances.
  arXiv  Detail & Related papers  (2024-07-13T20:56:34Z)
• 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)
• Revisiting Discriminative vs. Generative Classifiers: Theory and Implications [37.98169487351508]
  This paper is inspired by the statistical efficiency of naive Bayes. We present a multiclass $mathcalH$-consistency bound framework and an explicit bound for logistic loss. Experiments on various pre-trained deep vision models show that naive Bayes consistently converges faster as the number of data increases.
  arXiv  Detail & Related papers  (2023-02-05T08:30:42Z)
• Dist-PU: Positive-Unlabeled Learning from a Label Distribution Perspective [89.5370481649529]
  We propose a label distribution perspective for PU learning in this paper. Motivated by this, we propose to pursue the label distribution consistency between predicted and ground-truth label distributions. Experiments on three benchmark datasets validate the effectiveness of the proposed method.
  arXiv  Detail & Related papers  (2022-12-06T07:38:29Z)
• Label Matching Semi-Supervised Object Detection [85.99282969977541]
  Semi-supervised object detection has made significant progress with the development of mean teacher driven self-training. Label mismatch problem is not yet fully explored in the previous works, leading to severe confirmation bias during self-training. We propose a simple yet effective LabelMatch framework from two different yet complementary perspectives.
  arXiv  Detail & Related papers  (2022-06-14T05:59:41Z)
• On tuning a mean-field model for semi-supervised classification [0.0]
  Semi-supervised learning (SSL) has become an interesting research area due to its capacity for learning in scenarios where both labeled and unlabeled data are available. We study how classification results depend on $beta$ and find that the optimal phase depends highly on the amount of labeled data available.
  arXiv  Detail & Related papers  (2022-04-28T14:11:55Z)
• SparseDet: Improving Sparsely Annotated Object Detection with Pseudo-positive Mining [76.95808270536318]
  We propose an end-to-end system that learns to separate proposals into labeled and unlabeled regions using Pseudo-positive mining. While the labeled regions are processed as usual, self-supervised learning is used to process the unlabeled regions. We conduct exhaustive experiments on five splits on the PASCAL-VOC and COCO datasets achieving state-of-the-art performance.
  arXiv  Detail & Related papers  (2022-01-12T18:57:04Z)
• Label, Verify, Correct: A Simple Few Shot Object Detection Method [93.84801062680786]
  We introduce a simple pseudo-labelling method to source high-quality pseudo-annotations from a training set. We present two novel methods to improve the precision of the pseudo-labelling process. Our method achieves state-of-the-art or second-best performance compared to existing approaches.
  arXiv  Detail & Related papers  (2021-12-10T18:59:06Z)
• Active learning for online training in imbalanced data streams under cold start [0.8155575318208631]
  We propose an Active Learning (AL) annotation system for datasets with orders of magnitude of class imbalance. We present a computationally efficient Outlier-based Discriminative AL approach (ODAL) and design a novel 3-stage sequence of AL labeling policies. The results show that our method can more quickly reach a high performance model than standard AL policies.
  arXiv  Detail & Related papers  (2021-07-16T06:49:20Z)
• Imbalanced Continual Learning with Partitioning Reservoir Sampling [46.427023757892336]
  Continual learning from a sequential stream of data is a crucial challenge for machine learning research. We identify unanticipated adversity innately existent in many multi-label datasets, the long-tailed distribution. We propose a new sampling strategy for replay-based approach named Partitioning Reservoir Sampling (PRS)
  arXiv  Detail & Related papers  (2020-09-08T10:28:18Z)

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.