Constrained Classification and Policy Learning

• URL: http://arxiv.org/abs/2106.12886v2
• Date: Mon, 24 Jul 2023 20:12:59 GMT
• Title: Constrained Classification and Policy Learning
• Authors: Toru Kitagawa, Shosei Sakaguchi, and Aleksey Tetenov
• Abstract summary: We study consistency of surrogate loss procedures under a constrained set of classifiers. We show that hinge losses are the only surrogate losses that preserve consistency in second-best scenarios.
• Score: 0.0
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Modern machine learning approaches to classification, including AdaBoost, support vector machines, and deep neural networks, utilize surrogate loss techniques to circumvent the computational complexity of minimizing empirical classification risk. These techniques are also useful for causal policy learning problems, since estimation of individualized treatment rules can be cast as a weighted (cost-sensitive) classification problem. Consistency of the surrogate loss approaches studied in Zhang (2004) and Bartlett et al. (2006) crucially relies on the assumption of correct specification, meaning that the specified set of classifiers is rich enough to contain a first-best classifier. This assumption is, however, less credible when the set of classifiers is constrained by interpretability or fairness, leaving the applicability of surrogate loss based algorithms unknown in such second-best scenarios. This paper studies consistency of surrogate loss procedures under a constrained set of classifiers without assuming correct specification. We show that in the setting where the constraint restricts the classifier's prediction set only, hinge losses (i.e., $\ell_1$-support vector machines) are the only surrogate losses that preserve consistency in second-best scenarios. If the constraint additionally restricts the functional form of the classifier, consistency of a surrogate loss approach is not guaranteed even with hinge loss. We therefore characterize conditions for the constrained set of classifiers that can guarantee consistency of hinge risk minimizing classifiers. Exploiting our theoretical results, we develop robust and computationally attractive hinge loss based procedures for a monotone classification problem.

Related papers

• 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)
• Probabilistic Safety Regions Via Finite Families of Scalable Classifiers [2.431537995108158]
  Supervised classification recognizes patterns in the data to separate classes of behaviours. Canonical solutions contain misclassification errors that are intrinsic to the numerical approximating nature of machine learning. We introduce the concept of probabilistic safety region to describe a subset of the input space in which the number of misclassified instances is probabilistically controlled.
  arXiv  Detail & Related papers  (2023-09-08T22:40:19Z)
• The Adversarial Consistency of Surrogate Risks for Binary Classification [20.03511985572199]
  adversarial training seeks to minimize the expected $0$-$1$ loss when each example can be maliciously corrupted within a small ball. We give a simple and complete characterization of the set of surrogate loss functions that are consistent. Our results reveal that the class of adversarially consistent surrogates is substantially smaller than in the standard setting.
  arXiv  Detail & Related papers  (2023-05-17T05:27:40Z)
• Minimax risk classifiers with 0-1 loss [7.650319416775203]
  This paper presents minimax risk classifiers (MRCs) that minize the worst-case 0-1 loss with respect to uncertainty sets of distributions. We show that MRCs can provide tight performance guarantees at learning and are strongly universally consistent using feature mappings given by characteristic kernels. The paper also proposes efficient optimization techniques for MRC learning and shows that the methods presented can provide accurate classification together with tight performance guarantees in practice.
  arXiv  Detail & Related papers  (2022-01-17T16:00:07Z)
• Lower-bounded proper losses for weakly supervised classification [73.974163801142]
  We discuss the problem of weakly supervised learning of classification, in which instances are given weak labels. We derive a representation theorem for proper losses in supervised learning, which dualizes the Savage representation. We experimentally demonstrate the effectiveness of our proposed approach, as compared to improper or unbounded losses.
  arXiv  Detail & Related papers  (2021-03-04T08:47:07Z)
• A Symmetric Loss Perspective of Reliable Machine Learning [87.68601212686086]
  We review how a symmetric loss can yield robust classification from corrupted labels in balanced error rate (BER) minimization. We demonstrate how the robust AUC method can benefit natural language processing in the problem where we want to learn only from relevant keywords.
  arXiv  Detail & Related papers  (2021-01-05T06:25:47Z)
• Classification with Rejection Based on Cost-sensitive Classification [83.50402803131412]
  We propose a novel method of classification with rejection by ensemble of learning. Experimental results demonstrate the usefulness of our proposed approach in clean, noisy, and positive-unlabeled classification.
  arXiv  Detail & Related papers  (2020-10-22T14:05:05Z)
• Provable tradeoffs in adversarially robust classification [96.48180210364893]
  We develop and leverage new tools, including recent breakthroughs from probability theory on robust isoperimetry. Our results reveal fundamental tradeoffs between standard and robust accuracy that grow when data is imbalanced.
  arXiv  Detail & Related papers  (2020-06-09T09:58:19Z)
• Calibrated Surrogate Losses for Adversarially Robust Classification [92.37268323142307]
  We show that no convex surrogate loss is respect with respect to adversarial 0-1 loss when restricted to linear models. We also show that if the underlying distribution satisfies the Massart's noise condition, convex losses can also be calibrated in the adversarial setting.
  arXiv  Detail & Related papers  (2020-05-28T02:40:42Z)
• Certified Robustness to Label-Flipping Attacks via Randomized Smoothing [105.91827623768724]
  Machine learning algorithms are susceptible to data poisoning attacks. We present a unifying view of randomized smoothing over arbitrary functions. We propose a new strategy for building classifiers that are pointwise-certifiably robust to general data poisoning attacks.
  arXiv  Detail & Related papers  (2020-02-07T21:28:30Z)

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.