Measurability in the Fundamental Theorem of Statistical Learning

• URL: http://arxiv.org/abs/2410.10243v1
• Date: Mon, 14 Oct 2024 08:03:06 GMT
• Title: Measurability in the Fundamental Theorem of Statistical Learning
• Authors: Lothar Sebastian Krapp, Laura Wirth,
• Abstract summary: The Fundamental Theorem of Statistical Learning states that a hypothesis space is PAC learnable if and only if its VC dimension is finite. This paper presents sufficient conditions for the PAC learnability of hypothesis spaces defined over o-minimal expansions of the reals.
• Score: 0.0
• License: http://creativecommons.org/licenses/by-nc-nd/4.0/
• Abstract: The Fundamental Theorem of Statistical Learning states that a hypothesis space is PAC learnable if and only if its VC dimension is finite. For the agnostic model of PAC learning, the literature so far presents proofs of this theorem that often tacitly impose several measurability assumptions on the involved sets and functions. We scrutinize these proofs from a measure-theoretic perspective in order to extract the assumptions needed for a rigorous argument. This leads to a sound statement as well as a detailed and self-contained proof of the Fundamental Theorem of Statistical Learning in the agnostic setting, showcasing the minimal measurability requirements needed. We then discuss applications in Model Theory, considering NIP and o-minimal structures. Our main theorem presents sufficient conditions for the PAC learnability of hypothesis spaces defined over o-minimal expansions of the reals.

Related papers

• Computable learning of natural hypothesis classes [0.0]
  Examples have recently been given of hypothesis classes which are PAC learnable but not computably PAC learnable. We use the on-a-cone machinery from computability theory to prove that, under mild assumptions such as that the hypothesis class can be computably listable, any natural hypothesis class which is learnable must be computably learnable.
  arXiv  Detail & Related papers  (2024-07-23T17:26:38Z)
• The Foundations of Tokenization: Statistical and Computational Concerns [51.370165245628975]
  Tokenization is a critical step in the NLP pipeline. Despite its recognized importance as a standard representation method in NLP, the theoretical underpinnings of tokenization are not yet fully understood. The present paper contributes to addressing this theoretical gap by proposing a unified formal framework for representing and analyzing tokenizer models.
  arXiv  Detail & Related papers  (2024-07-16T11:12:28Z)
• Lean-STaR: Learning to Interleave Thinking and Proving [53.923617816215774]
  We present Lean-STaR, a framework for training language models to produce informal thoughts prior to each step of a proof. Lean-STaR achieves state-of-the-art results on the miniF2F-test benchmark within the Lean theorem proving environment.
  arXiv  Detail & Related papers  (2024-07-14T01:43:07Z)
• Prototype-based Aleatoric Uncertainty Quantification for Cross-modal Retrieval [139.21955930418815]
  Cross-modal Retrieval methods build similarity relations between vision and language modalities by jointly learning a common representation space. However, the predictions are often unreliable due to the Aleatoric uncertainty, which is induced by low-quality data, e.g., corrupt images, fast-paced videos, and non-detailed texts. We propose a novel Prototype-based Aleatoric Uncertainty Quantification (PAU) framework to provide trustworthy predictions by quantifying the uncertainty arisen from the inherent data ambiguity.
  arXiv  Detail & Related papers  (2023-09-29T09:41:19Z)
• Advancing Counterfactual Inference through Nonlinear Quantile Regression [77.28323341329461]
  We propose a framework for efficient and effective counterfactual inference implemented with neural networks. The proposed approach enhances the capacity to generalize estimated counterfactual outcomes to unseen data. Empirical results conducted on multiple datasets offer compelling support for our theoretical assertions.
  arXiv  Detail & Related papers  (2023-06-09T08:30:51Z)
• A Measure-Theoretic Axiomatisation of Causality [55.6970314129444]
  We argue in favour of taking Kolmogorov's measure-theoretic axiomatisation of probability as the starting point towards an axiomatisation of causality. Our proposed framework is rigorously grounded in measure theory, but it also sheds light on long-standing limitations of existing frameworks.
  arXiv  Detail & Related papers  (2023-05-19T13:15:48Z)
• Logical Satisfiability of Counterfactuals for Faithful Explanations in NLI [60.142926537264714]
  We introduce the methodology of Faithfulness-through-Counterfactuals. It generates a counterfactual hypothesis based on the logical predicates expressed in the explanation. It then evaluates if the model's prediction on the counterfactual is consistent with that expressed logic.
  arXiv  Detail & Related papers  (2022-05-25T03:40:59Z)
• Simplicial quantum contextuality [0.0]
  We introduce a new framework for contextuality based on simplicial sets, models of topological spaces that play a prominent role in homotopy theory. Our approach extends measurement scenarios to consist of spaces (rather than sets) of measurements and outcomes. We present a topologically inspired new proof of Fine's theorem for characterizing noncontextuality in Bell scenarios.
  arXiv  Detail & Related papers  (2022-04-13T22:03:28Z)
• Learning Topic Models: Identifiability and Finite-Sample Analysis [6.181048261489101]
  We propose a maximum likelihood estimator (MLE) of latent topics based on a specific integrated likelihood. We conclude with empirical studies on both simulated and real datasets.
  arXiv  Detail & Related papers  (2021-10-08T16:35:42Z)
• A Topological Perspective on Causal Inference [10.965065178451104]
  We show that substantive assumption-free causal inference is possible only in a meager set of structural causal models. Our results show that inductive assumptions sufficient to license valid causal inferences are statistically unverifiable in principle. An additional benefit of our topological approach is that it easily accommodates SCMs with infinitely many variables.
  arXiv  Detail & Related papers  (2021-07-18T23:09:03Z)

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.