Tightening the Evaluation of PAC Bounds Using Formal Verification Results

• URL: http://arxiv.org/abs/2407.20122v1
• Date: Mon, 29 Jul 2024 15:53:14 GMT
• Title: Tightening the Evaluation of PAC Bounds Using Formal Verification Results
• Authors: Thomas Walker, Alessio Lomuscio,
• Abstract summary: We take the novel approach of using the formal verification of neural systems to inform the evaluation of PAC bounds. We show that conditioning existing bounds on verification results leads to a tightening proportional to the underlying probability mass of the verified region.
• Score: 16.671097256655777
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Probably Approximately Correct (PAC) bounds are widely used to derive probabilistic guarantees for the generalisation of machine learning models. They highlight the components of the model which contribute to its generalisation capacity. However, current state-of-the-art results are loose in approximating the generalisation capacity of deployed machine learning models. Consequently, while PAC bounds are theoretically useful, their applicability for evaluating a model's generalisation property in a given operational design domain is limited. The underlying classical theory is supported by the idea that bounds can be tightened when the number of test points available to the user to evaluate the model increases. Yet, in the case of neural networks, the number of test points required to obtain bounds of interest is often impractical even for small problems. In this paper, we take the novel approach of using the formal verification of neural systems to inform the evaluation of PAC bounds. Rather than using pointwise information obtained from repeated tests, we use verification results on regions around test points. We show that conditioning existing bounds on verification results leads to a tightening proportional to the underlying probability mass of the verified region.

Related papers

• A PAC-Bayesian Perspective on the Interpolating Information Criterion [54.548058449535155]
  We show how a PAC-Bayes bound is obtained for a general class of models, characterizing factors which influence performance in the interpolating regime. We quantify how the test error for overparameterized models achieving effectively zero training error depends on the quality of the implicit regularization imposed by e.g. the combination of model, parameter-initialization scheme.
  arXiv  Detail & Related papers  (2023-11-13T01:48:08Z)
• Fine-grained analysis of non-parametric estimation for pairwise learning [9.676007573960383]
  We are concerned with the generalization performance of non-parametric estimation for pairwise learning. Our results can be used to handle a wide range of pairwise learning problems including ranking, AUC, pairwise regression and metric and similarity learning.
  arXiv  Detail & Related papers  (2023-05-31T08:13:14Z)
• Testing for Overfitting [0.0]
  We discuss the overfitting problem and explain why standard and concentration results do not hold for evaluation with training data. We introduce and argue for a hypothesis test by means of which both model performance may be evaluated using training data.
  arXiv  Detail & Related papers  (2023-05-09T22:49:55Z)
• Practicality of generalization guarantees for unsupervised domain adaptation with neural networks [7.951847862547378]
  We evaluate existing bounds from the literature with potential to satisfy our desiderata on domain adaptation image classification tasks. We find that all bounds are vacuous and that sample generalization terms account for much of the observed looseness. We find that, when domain overlap can be assumed, a simple importance weighting extension of previous work provides the tightest estimable bound.
  arXiv  Detail & Related papers  (2023-03-15T16:05:05Z)
• Modeling Uncertain Feature Representation for Domain Generalization [49.129544670700525]
  We show that our method consistently improves the network generalization ability on multiple vision tasks. Our methods are simple yet effective and can be readily integrated into networks without additional trainable parameters or loss constraints.
  arXiv  Detail & Related papers  (2023-01-16T14:25:02Z)
• A New Family of Generalization Bounds Using Samplewise Evaluated CMI [14.147617330278662]
  We present a new family of information-theoretic generalization bounds, in which the training loss and the population loss are compared through a jointly convex function. We demonstrate the generality of this framework by extending previously known information-theoretic bounds. In some scenarios, this novel bound results in a tighter characterization of the population loss of deep neural networks than previous bounds.
  arXiv  Detail & Related papers  (2022-10-12T17:15:44Z)
• Predicting Unreliable Predictions by Shattering a Neural Network [145.3823991041987]
  Piecewise linear neural networks can be split into subfunctions. Subfunctions have their own activation pattern, domain, and empirical error. Empirical error for the full network can be written as an expectation over subfunctions.
  arXiv  Detail & Related papers  (2021-06-15T18:34:41Z)
• Counterfactual Maximum Likelihood Estimation for Training Deep Networks [83.44219640437657]
  Deep learning models are prone to learning spurious correlations that should not be learned as predictive clues. We propose a causality-based training framework to reduce the spurious correlations caused by observable confounders. We conduct experiments on two real-world tasks: Natural Language Inference (NLI) and Image Captioning.
  arXiv  Detail & Related papers  (2021-06-07T17:47:16Z)
• Deconfounding Scores: Feature Representations for Causal Effect Estimation with Weak Overlap [140.98628848491146]
  We introduce deconfounding scores, which induce better overlap without biasing the target of estimation. We show that deconfounding scores satisfy a zero-covariance condition that is identifiable in observed data. In particular, we show that this technique could be an attractive alternative to standard regularizations.
  arXiv  Detail & Related papers  (2021-04-12T18:50:11Z)
• A General Framework for the Practical Disintegration of PAC-Bayesian Bounds [2.516393111664279]
  We introduce new PAC-Bayesian generalization bounds that have the originality to provide disintegrated bounds. Our bounds are easily optimizable and can be used to design learning algorithms.
  arXiv  Detail & Related papers  (2021-02-17T09:36:46Z)
• Structural Causal Models Are (Solvable by) Credal Networks [70.45873402967297]
  Causal inferences can be obtained by standard algorithms for the updating of credal nets. This contribution should be regarded as a systematic approach to represent structural causal models by credal networks. Experiments show that approximate algorithms for credal networks can immediately be used to do causal inference in real-size problems.
  arXiv  Detail & Related papers  (2020-08-02T11:19:36Z)

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.