Honey, I shrunk the hypothesis space (through logical preprocessing)

• URL: http://arxiv.org/abs/2506.06739v1
• Date: Sat, 07 Jun 2025 09:53:02 GMT
• Title: Honey, I shrunk the hypothesis space (through logical preprocessing)
• Authors: Andrew Cropper, Filipe Gouveia, David M. Cerna,
• Abstract summary: We introduce an approach that'shrinks' the hypothesis space before an ILP system searches it.<n>Our approach uses background knowledge to find rules that cannot be in an optimal hypothesis regardless of the training examples.<n>Our experiments show that our approach can substantially reduce learning times whilst maintaining predictive accuracies.
• Score: 19.54008511592332
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Inductive logic programming (ILP) is a form of logical machine learning. The goal is to search a hypothesis space for a hypothesis that generalises training examples and background knowledge. We introduce an approach that 'shrinks' the hypothesis space before an ILP system searches it. Our approach uses background knowledge to find rules that cannot be in an optimal hypothesis regardless of the training examples. For instance, our approach discovers relationships such as "even numbers cannot be odd" and "prime numbers greater than 2 are odd". It then removes violating rules from the hypothesis space. We implement our approach using answer set programming and use it to shrink the hypothesis space of a constraint-based ILP system. Our experiments on multiple domains, including visual reasoning and game playing, show that our approach can substantially reduce learning times whilst maintaining predictive accuracies. For instance, given just 10 seconds of preprocessing time, our approach can reduce learning times from over 10 hours to only 2 seconds.

Related papers

• Efficient rule induction by ignoring pointless rules [21.961097463200232]
  We introduce an ILP approach that identifies pointless rules.<n>A rule is pointless if it contains a redundant literal or cannot discriminate against negative examples.<n>We show that ignoring pointless rules allows an ILP system to soundly prune the hypothesis space.
  arXiv  Detail & Related papers  (2025-02-03T10:46:18Z)
• Simple and Provable Scaling Laws for the Test-Time Compute of Large Language Models [70.07661254213181]
  We propose two algorithms that enjoy provable scaling laws for the test-time compute of large language models.<n>One is a two-stage knockout-style algorithm, where each candidate is evaluated by its average win rate against multiple opponents.<n>The other is a two-stage league-style algorithm, where each candidate is evaluated by its average win rate against multiple opponents.
  arXiv  Detail & Related papers  (2024-11-29T05:29:47Z)
• 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)
• Increasing Probability Mass on Answer Choices Does Not Always Improve Accuracy [60.18632773935895]
  Spreading probability mass across multiple surface forms with identical meaning is thought to cause an underestimation of a model's true performance. We propose a mathematical formalism for SFC which allows us to quantify and bound its impact for the first time. We identify a simple method for reducing it -- namely, increasing probability mass on the given answer choices by a) including them in the prompt and b) using in-context learning with even just one example.
  arXiv  Detail & Related papers  (2023-05-24T00:27:00Z)
• Visual Abductive Reasoning [85.17040703205608]
  Abductive reasoning seeks the likeliest possible explanation for partial observations. We propose a new task and dataset, Visual Abductive Reasoning ( VAR), for examining abductive reasoning ability of machine intelligence in everyday visual situations.
  arXiv  Detail & Related papers  (2022-03-26T10:17:03Z)
• Learning logic programs by discovering where not to search [18.27510863075184]
  We introduce an approach that, before searching for a hypothesis, first discovers where not to search' We use given BK to discover constraints on hypotheses, such as that a number cannot be both even and odd. Our experiments on multiple domains show that our approach can substantially reduce learning times.
  arXiv  Detail & Related papers  (2022-02-20T12:32:03Z)
• Observing Interventions: A logic for thinking about experiments [62.997667081978825]
  This paper makes a first step towards a logic of learning from experiments. Crucial for our approach is the idea that the notion of an intervention can be used as a formal expression of a (real or hypothetical) experiment. For all the proposed logical systems, we provide a sound and complete axiomatization.
  arXiv  Detail & Related papers  (2021-11-25T09:26:45Z)
• Learning logic programs by explaining their failures [26.955785230358963]
  We introduce failure explanation techniques for inductive logic programming. If a hypothesis fails, we explain the failure in terms of failing sub-programs. We show that fine-grained failure analysis allows for learning fine-grained constraints on the hypothesis space.
  arXiv  Detail & Related papers  (2021-02-18T14:32:20Z)
• 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)
• Learning programs by learning from failures [26.955785230358963]
  We describe an inductive logic programming (ILP) approach called learning from failures. In this approach, an ILP system decomposes the learning problem into three separate stages: generate, test, and constrain. We introduce Popper, an ILP system that implements this approach by combining answer set programming and Prolog.
  arXiv  Detail & Related papers  (2020-05-05T14:55:07Z)
• Learning large logic programs by going beyond entailment [18.27510863075184]
  We implement our idea in Brute, a new ILP system which uses best-first search, guided by an example-dependent loss function, to incrementally build programs. Our experiments show that Brute can substantially outperform existing ILP systems in terms of predictive accuracies and learning times.
  arXiv  Detail & Related papers  (2020-04-21T09:31:06Z)

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.