When Is Inductive Inference Possible?

• URL: http://arxiv.org/abs/2312.00170v2
• Date: Wed, 25 Sep 2024 19:38:47 GMT
• Title: When Is Inductive Inference Possible?
• Authors: Zhou Lu,
• Abstract summary: We provide a tight characterization of inductive inference by establishing a novel link to online learning theory. We prove that inductive inference is possible if and only if the hypothesis class is a countable union of online learnable classes. Our main technical tool is a novel non-uniform online learning framework, which may be of independent interest.
• Score: 3.4991031406102238
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Can a physicist make only a finite number of errors in the eternal quest to uncover the law of nature? This millennium-old philosophical problem, known as inductive inference, lies at the heart of epistemology. Despite its significance to understanding human reasoning, a rigorous justification of inductive inference has remained elusive. At a high level, inductive inference asks whether one can make at most finite errors amidst an infinite sequence of observations, when deducing the correct hypothesis from a given hypothesis class. Historically, the only theoretical guarantee has been that if the hypothesis class is countable, inductive inference is possible, as exemplified by Solomonoff induction for learning Turing machines. In this paper, we provide a tight characterization of inductive inference by establishing a novel link to online learning theory. As our main result, we prove that inductive inference is possible if and only if the hypothesis class is a countable union of online learnable classes, potentially with an uncountable size, no matter the observations are adaptively chosen or iid sampled. Moreover, the same condition is also sufficient and necessary in the agnostic setting, where any hypothesis class meeting this criterion enjoys an $\tilde{O}(\sqrt{T})$ regret bound for any time step $T$, while others require an arbitrarily slow rate of regret. Our main technical tool is a novel non-uniform online learning framework, which may be of independent interest.

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)
• Machine learning and information theory concepts towards an AI Mathematician [77.63761356203105]
  The current state-of-the-art in artificial intelligence is impressive, especially in terms of mastery of language, but not so much in terms of mathematical reasoning. This essay builds on the idea that current deep learning mostly succeeds at system 1 abilities. It takes an information-theoretical posture to ask questions about what constitutes an interesting mathematical statement.
  arXiv  Detail & Related papers  (2024-03-07T15:12:06Z)
• Betting on what is neither verifiable nor falsifiable [18.688474183114085]
  We propose an approach to betting on such events via options, or equivalently as bets on the outcome of a "verification-falsification game" Our work thus acts as an alternative to the existing framework of Garrabrant induction for logical uncertainty, and relates to the stance known as constructivism in the philosophy of mathematics.
  arXiv  Detail & Related papers  (2024-01-29T17:30:34Z)
• Phenomenal Yet Puzzling: Testing Inductive Reasoning Capabilities of Language Models with Hypothesis Refinement [92.61557711360652]
  Language models (LMs) often fall short on inductive reasoning, despite achieving impressive success on research benchmarks. We conduct a systematic study of the inductive reasoning capabilities of LMs through iterative hypothesis refinement. We reveal several discrepancies between the inductive reasoning processes of LMs and humans, shedding light on both the potentials and limitations of using LMs in inductive reasoning tasks.
  arXiv  Detail & Related papers  (2023-10-12T17:51:10Z)
• Learnability with PAC Semantics for Multi-agent Beliefs [38.88111785113001]
  The tension between deduction and induction is perhaps the most fundamental issue in areas such as philosophy, cognition and artificial intelligence. Valiant recognised that the challenge of learning should be integrated with deduction. Although weaker than classical entailment, it allows for a powerful model-theoretic framework for answering queries.
  arXiv  Detail & Related papers  (2023-06-08T18:22:46Z)
• 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)
• A Note on Bell's Theorem Logical Consistency [0.0]
  Counterfactual definiteness is supposed to underlie the Bell theorem. We show that counterfactual definiteness is an unnecessary and inconsistent assumption.
  arXiv  Detail & Related papers  (2020-12-16T22:14:06Z)
• A Weaker Faithfulness Assumption based on Triple Interactions [89.59955143854556]
  We propose a weaker assumption that we call $2$-adjacency faithfulness. We propose a sound orientation rule for causal discovery that applies under weaker assumptions.
  arXiv  Detail & Related papers  (2020-10-27T13:04:08Z)
• Inferences and Modal Vocabulary [8.475081627511166]
  There are different types of inferences that are not monotonic, e.g. abductive inferences. Material inferences express good inferences based on the principle of material incompatibility. I propose a modal interpretation of implications to express conceptual relations.
  arXiv  Detail & Related papers  (2020-07-06T01:04:06Z)
• Logical Neural Networks [51.46602187496816]
  We propose a novel framework seamlessly providing key properties of both neural nets (learning) and symbolic logic (knowledge and reasoning) Every neuron has a meaning as a component of a formula in a weighted real-valued logic, yielding a highly intepretable disentangled representation. Inference is omni rather than focused on predefined target variables, and corresponds to logical reasoning.
  arXiv  Detail & Related papers  (2020-06-23T16:55:45Z)
• L2R2: Leveraging Ranking for Abductive Reasoning [65.40375542988416]
  The abductive natural language inference task ($alpha$NLI) is proposed to evaluate the abductive reasoning ability of a learning system. A novel $L2R2$ approach is proposed under the learning-to-rank framework. Experiments on the ART dataset reach the state-of-the-art in the public leaderboard.
  arXiv  Detail & Related papers  (2020-05-22T15:01:23Z)

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.