Cardinality-Aware Set Prediction and Top-$k$ Classification

• URL: http://arxiv.org/abs/2407.07140v1
• Date: Tue, 9 Jul 2024 17:57:07 GMT
• Title: Cardinality-Aware Set Prediction and Top-$k$ Classification
• Authors: Corinna Cortes, Anqi Mao, Christopher Mohri, Mehryar Mohri, Yutao Zhong,
• Abstract summary: We present a novel approach that aims to learn an accurate top-$k$ set predictor while maintaining a low cardinality. We introduce a new target loss function tailored to this setting that accounts for both the classification error and the cardinality of the set predicted. Minimizing these loss functions leads to new cardinality-aware algorithms that we describe in detail.
• Score: 33.00927499966789
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We present a detailed study of cardinality-aware top-$k$ classification, a novel approach that aims to learn an accurate top-$k$ set predictor while maintaining a low cardinality. We introduce a new target loss function tailored to this setting that accounts for both the classification error and the cardinality of the set predicted. To optimize this loss function, we propose two families of surrogate losses: cost-sensitive comp-sum losses and cost-sensitive constrained losses. Minimizing these loss functions leads to new cardinality-aware algorithms that we describe in detail in the case of both top-$k$ and threshold-based classifiers. We establish $H$-consistency bounds for our cardinality-aware surrogate loss functions, thereby providing a strong theoretical foundation for our algorithms. We report the results of extensive experiments on CIFAR-10, CIFAR-100, ImageNet, and SVHN datasets demonstrating the effectiveness and benefits of our cardinality-aware algorithms.

Related papers

• The Central Role of the Loss Function in Reinforcement Learning [46.72524235085568]
  We demonstrate how different regression loss functions affect the sample efficiency and adaptivity of value-based decision making algorithms. Across multiple settings, we prove that algorithms using the binary cross-entropy loss achieve first-order bounds scaling with the optimal policy's cost. We hope that this paper serves as a guide analyzing decision making algorithms with varying loss functions, and can inspire the reader to seek out better loss functions to improve any decision making algorithm.
  arXiv  Detail & Related papers  (2024-09-19T14:10:38Z)
• Top-$k$ Classification and Cardinality-Aware Prediction [30.389055604165222]
  We show that comp-sum and constrained losses are supported by $H$-consistency bounds with respect to the top-$k$ loss. We introduce cardinality-aware loss functions through instance-dependent cost-sensitive learning. Minimizing these losses leads to new cardinality-aware algorithms for top-$k$ classification.
  arXiv  Detail & Related papers  (2024-03-28T17:45:03Z)
• Predictor-Rejector Multi-Class Abstention: Theoretical Analysis and Algorithms [30.389055604165222]
  We study the key framework of learning with abstention in the multi-class classification setting. In this setting, the learner can choose to abstain from making a prediction with some pre-defined cost. We introduce several new families of surrogate losses for which we prove strong non-asymptotic and hypothesis set-specific consistency guarantees.
  arXiv  Detail & Related papers  (2023-10-23T10:16:27Z)
• Theoretically Grounded Loss Functions and Algorithms for Score-Based Multi-Class Abstention [30.389055604165222]
  We introduce new families of surrogate losses for the abstention loss function. We prove strong non-asymptotic and hypothesis set-specific consistency guarantees for these surrogate losses. Our results show that the relative performance of the state-of-the-art score-based surrogate losses can vary across datasets.
  arXiv  Detail & Related papers  (2023-10-23T10:13:35Z)
• Improved Regret for Efficient Online Reinforcement Learning with Linear Function Approximation [69.0695698566235]
  We study reinforcement learning with linear function approximation and adversarially changing cost functions. We present a computationally efficient policy optimization algorithm for the challenging general setting of unknown dynamics and bandit feedback.
  arXiv  Detail & Related papers  (2023-01-30T17:26:39Z)
• Label Distributionally Robust Losses for Multi-class Classification: Consistency, Robustness and Adaptivity [55.29408396918968]
  We study a family of loss functions named label-distributionally robust (LDR) losses for multi-class classification. Our contributions include both consistency and robustness by establishing top-$k$ consistency of LDR losses for multi-class classification. We propose a new adaptive LDR loss that automatically adapts the individualized temperature parameter to the noise degree of class label of each instance.
  arXiv  Detail & Related papers  (2021-12-30T00:27:30Z)
• Learning with Multiclass AUC: Theory and Algorithms [141.63211412386283]
  Area under the ROC curve (AUC) is a well-known ranking metric for problems such as imbalanced learning and recommender systems. In this paper, we start an early trial to consider the problem of learning multiclass scoring functions via optimizing multiclass AUC metrics.
  arXiv  Detail & Related papers  (2021-07-28T05:18:10Z)
• Learning by Minimizing the Sum of Ranked Range [58.24935359348289]
  We introduce the sum of ranked range (SoRR) as a general approach to form learning objectives. A ranked range is a consecutive sequence of sorted values of a set of real numbers. We explore two applications in machine learning of the minimization of the SoRR framework, namely the AoRR aggregate loss for binary classification and the TKML individual loss for multi-label/multi-class classification.
  arXiv  Detail & Related papers  (2020-10-05T01:58:32Z)
• Adversarially Robust Learning via Entropic Regularization [31.6158163883893]
  We propose a new family of algorithms, ATENT, for training adversarially robust deep neural networks. Our approach achieves competitive (or better) performance in terms of robust classification accuracy.
  arXiv  Detail & Related papers  (2020-08-27T18:54:43Z)
• AP-Loss for Accurate One-Stage Object Detection [49.13608882885456]
  One-stage object detectors are trained by optimizing classification-loss and localization-loss simultaneously. The former suffers much from extreme foreground-background imbalance due to the large number of anchors. This paper proposes a novel framework to replace the classification task in one-stage detectors with a ranking task.
  arXiv  Detail & Related papers  (2020-08-17T13:22:01Z)

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.