PACMAN: PAC-style bounds accounting for the Mismatch between Accuracy and Negative log-loss

• URL: http://arxiv.org/abs/2112.05547v1
• Date: Fri, 10 Dec 2021 14:00:22 GMT
• Title: PACMAN: PAC-style bounds accounting for the Mismatch between Accuracy and Negative log-loss
• Authors: Matias Vera, Leonardo Rey Vega and Pablo Piantanida
• Abstract summary: The ultimate performance of machine learning algorithms for classification tasks is usually measured in terms of the empirical error probability (or accuracy) based on a testing dataset. For classification tasks, this loss function is often the negative log-loss that leads to the well-known cross-entropy risk. We introduce an analysis based on point-wise PAC approach over the generalization gap considering the mismatch of testing based on the accuracy metric and training on the negative log-loss.
• Score: 28.166066663983674
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: The ultimate performance of machine learning algorithms for classification tasks is usually measured in terms of the empirical error probability (or accuracy) based on a testing dataset. Whereas, these algorithms are optimized through the minimization of a typically different--more convenient--loss function based on a training set. For classification tasks, this loss function is often the negative log-loss that leads to the well-known cross-entropy risk which is typically better behaved (from a numerical perspective) than the error probability. Conventional studies on the generalization error do not usually take into account the underlying mismatch between losses at training and testing phases. In this work, we introduce an analysis based on point-wise PAC approach over the generalization gap considering the mismatch of testing based on the accuracy metric and training on the negative log-loss. We label this analysis PACMAN. Building on the fact that the mentioned mismatch can be written as a likelihood ratio, concentration inequalities can be used to provide some insights for the generalization problem in terms of some point-wise PAC bounds depending on some meaningful information-theoretic quantities. An analysis of the obtained bounds and a comparison with available results in the literature are also provided.

Related papers

• Error Exponent in Agnostic PAC Learning [4.772817128620037]
  Probably Approximately Correct (PAC) is widely used to analyze learning problems and algorithms. In this paper, we consider PAC learning using the error exponent - a well established analysis method in Information Theory. We find, under some assumptions, an improved distribution dependent error exponent for a wide range of problems, establishing the exponential behavior of the PAC error probability in learning.
  arXiv  Detail & Related papers  (2024-05-01T18:08:03Z)
• Probabilistic Contrastive Learning for Long-Tailed Visual Recognition [78.70453964041718]
  Longtailed distributions frequently emerge in real-world data, where a large number of minority categories contain a limited number of samples. Recent investigations have revealed that supervised contrastive learning exhibits promising potential in alleviating the data imbalance. We propose a novel probabilistic contrastive (ProCo) learning algorithm that estimates the data distribution of the samples from each class in the feature space.
  arXiv  Detail & Related papers  (2024-03-11T13:44:49Z)
• Correcting Underrepresentation and Intersectional Bias for Classification [49.1574468325115]
  We consider the problem of learning from data corrupted by underrepresentation bias. We show that with a small amount of unbiased data, we can efficiently estimate the group-wise drop-out rates. We show that our algorithm permits efficient learning for model classes of finite VC dimension.
  arXiv  Detail & Related papers  (2023-06-19T18:25:44Z)
• On Leave-One-Out Conditional Mutual Information For Generalization [122.2734338600665]
  We derive information theoretic generalization bounds for supervised learning algorithms based on a new measure of leave-one-out conditional mutual information (loo-CMI) Contrary to other CMI bounds, our loo-CMI bounds can be computed easily and can be interpreted in connection to other notions such as classical leave-one-out cross-validation. We empirically validate the quality of the bound by evaluating its predicted generalization gap in scenarios for deep learning.
  arXiv  Detail & Related papers  (2022-07-01T17:58:29Z)
• Controlling Multiple Errors Simultaneously with a PAC-Bayes Bound [21.273964864852612]
  We provide the first PAC-Bayes bound capable of providing rich information by bounding the Kullback-Leibler divergence between the empirical and true probabilities of a set of M error types. Our bound is especially useful in cases where the severity of different mis-classifications may change over time.
  arXiv  Detail & Related papers  (2022-02-11T11:35:21Z)
• Rethinking and Reweighting the Univariate Losses for Multi-Label Ranking: Consistency and Generalization [44.73295800450414]
  (Partial) ranking loss is a commonly used evaluation measure for multi-label classification. There is a gap between existing theory and practice -- some pairwise losses can lead to promising performance but lack consistency.
  arXiv  Detail & Related papers  (2021-05-10T09:23:27Z)
• Theoretical Insights Into Multiclass Classification: A High-dimensional Asymptotic View [82.80085730891126]
  We provide the first modernally precise analysis of linear multiclass classification. Our analysis reveals that the classification accuracy is highly distribution-dependent. The insights gained may pave the way for a precise understanding of other classification algorithms.
  arXiv  Detail & Related papers  (2020-11-16T05:17:29Z)
• 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)
• Good Classifiers are Abundant in the Interpolating Regime [64.72044662855612]
  We develop a methodology to compute precisely the full distribution of test errors among interpolating classifiers. We find that test errors tend to concentrate around a small typical value $varepsilon*$, which deviates substantially from the test error of worst-case interpolating model. Our results show that the usual style of analysis in statistical learning theory may not be fine-grained enough to capture the good generalization performance observed in practice.
  arXiv  Detail & Related papers  (2020-06-22T21:12:31Z)
• Information-theoretic analysis for transfer learning [5.081241420920605]
  We give an information-theoretic analysis on the generalization error and the excess risk of transfer learning algorithms. Our results suggest, perhaps as expected, that the Kullback-Leibler divergence $D(mu||mu')$ plays an important role in characterizing the generalization error.
  arXiv  Detail & Related papers  (2020-05-18T13:23:20Z)

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.