Using Program Synthesis and Inductive Logic Programming to solve Bongard Problems

• URL: http://arxiv.org/abs/2110.09947v1
• Date: Tue, 19 Oct 2021 13:13:06 GMT
• Title: Using Program Synthesis and Inductive Logic Programming to solve Bongard Problems
• Authors: Atharv Sonwane, Sharad Chitlangia, Tirtharaj Dash, Lovekesh Vig, Gautam Shroff, Ashwin Srinivasan
• Abstract summary: We present a preliminary examination of whether programs constructed by Dreamcoder can be used for analogical reasoning to solve certain Bongard problems. We decorate the states using positional information in an automated manner and then encode the resulting sequence into logical facts in Prolog. Experiments on synthetically created Bongard problems for concepts such as 'above/below' and 'clockwise/counterclockwise' demonstrate that our end-to-end system can solve such problems.
• Score: 20.864990877667296
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: The ability to recognise and make analogies is often used as a measure or test of human intelligence. The ability to solve Bongard problems is an example of such a test. It has also been postulated that the ability to rapidly construct novel abstractions is critical to being able to solve analogical problems. Given an image, the ability to construct a program that would generate that image is one form of abstraction, as exemplified in the Dreamcoder project. In this paper, we present a preliminary examination of whether programs constructed by Dreamcoder can be used for analogical reasoning to solve certain Bongard problems. We use Dreamcoder to discover programs that generate the images in a Bongard problem and represent each of these as a sequence of state transitions. We decorate the states using positional information in an automated manner and then encode the resulting sequence into logical facts in Prolog. We use inductive logic programming (ILP), to learn an (interpretable) theory for the abstract concept involved in an instance of a Bongard problem. Experiments on synthetically created Bongard problems for concepts such as 'above/below' and 'clockwise/counterclockwise' demonstrate that our end-to-end system can solve such problems. We study the importance and completeness of each component of our approach, highlighting its current limitations and pointing to directions for improvement in our formulation as well as in elements of any Dreamcoder-like program synthesis system used for such an approach.

Related papers

• Bongards at the Boundary of Perception and Reasoning: Programs or Language? [18.717928534727864]
  Humans possess the puzzling ability to deploy their visual reasoning abilities in radically new situations.<n>We present a neurosymbolic approach to solving the Bongard problems.<n>We evaluate our method on classifying Bongard problem images given the ground truth rule, as well as on solving the problems from scratch.
  arXiv  Detail & Related papers  (2026-02-03T03:04:27Z)
• RECODE: Reasoning Through Code Generation for Visual Question Answering [68.86938437188964]
  We propose to leverage derendering -- the process of reverse-engineering visuals into executable code -- as a new modality for verifiable visual reasoning.<n>Our work demonstrates that grounding visual perception in executable code provides a new path toward more accurate and verifiable multimodal reasoning.
  arXiv  Detail & Related papers  (2025-10-15T17:05:37Z)
• Fuse, Reason and Verify: Geometry Problem Solving with Parsed Clauses from Diagram [78.79651421493058]
  We propose a neural-symbolic model for plane geometry problem solving (PGPS) with three key steps: modal fusion, reasoning process and knowledge verification. For reasoning, we design an explicable solution program to describe the geometric reasoning process, and employ a self-limited decoder to generate solution program autoregressively. We also construct a large-scale geometry problem dataset called PGPS9K, containing fine-grained annotations of textual clauses, solution program and involved knowledge solvers.
  arXiv  Detail & Related papers  (2024-07-10T02:45:22Z)
• When Do Program-of-Thoughts Work for Reasoning? [51.2699797837818]
  We propose complexity-impacted reasoning score (CIRS) to measure correlation between code and reasoning abilities. Specifically, we use the abstract syntax tree to encode the structural information and calculate logical complexity. Code will be integrated into the EasyInstruct framework at https://github.com/zjunlp/EasyInstruct.
  arXiv  Detail & Related papers  (2023-08-29T17:22:39Z)
• Synthesizing a Progression of Subtasks for Block-Based Visual Programming Tasks [21.33708484899808]
  We propose a novel synthesis algorithm that generates a progression of subtasks that are high-quality, well-spaced in terms of their complexity. We show the utility of our synthesis algorithm in improving the efficacy of AI agents for solving tasks in the Karel programming environment.
  arXiv  Detail & Related papers  (2023-05-27T16:24:36Z)
• Momentum Decoding: Open-ended Text Generation As Graph Exploration [49.812280360794894]
  Open-ended text generation with autoregressive language models (LMs) is one of the core tasks in natural language processing. We formulate open-ended text generation from a new perspective, i.e., we view it as an exploration process within a directed graph. We propose a novel decoding method -- textitmomentum decoding -- which encourages the LM to explore new nodes outside the current graph.
  arXiv  Detail & Related papers  (2022-12-05T11:16:47Z)
• Chaining Simultaneous Thoughts for Numerical Reasoning [92.2007997126144]
  numerical reasoning over text should be an essential skill of AI systems. Previous work focused on modeling the structures of equations, and has proposed various structured decoders. We propose CANTOR, a numerical reasoner that models reasoning steps using a directed acyclic graph.
  arXiv  Detail & Related papers  (2022-11-29T18:52:06Z)
• End-to-end Algorithm Synthesis with Recurrent Networks: Logical Extrapolation Without Overthinking [52.05847268235338]
  We show how machine learning systems can perform logical extrapolation without overthinking problems. We propose a recall architecture that keeps an explicit copy of the problem instance in memory so that it cannot be forgotten. We also employ a progressive training routine that prevents the model from learning behaviors that are specific to number and instead pushes it to learn behaviors that can be repeated indefinitely.
  arXiv  Detail & Related papers  (2022-02-11T18:43:28Z)
• DeepA: A Deep Neural Analyzer For Speech And Singing Vocoding [71.73405116189531]
  We propose a neural vocoder that extracts F0 and timbre/aperiodicity encoding from the input speech that emulates those defined in conventional vocoders. As the deep neural analyzer is learnable, it is expected to be more accurate for signal reconstruction and manipulation, and generalizable from speech to singing.
  arXiv  Detail & Related papers  (2021-10-13T01:39:57Z)
• Invariance, encodings, and generalization: learning identity effects with neural networks [0.0]
  We provide a framework in which we can rigorously prove that algorithms satisfying simple criteria cannot make the correct inference. We then show that a broad class of learning algorithms including deep feedforward neural networks trained via gradient-based algorithms satisfy our criteria. In some broader circumstances we are able to provide adversarial examples that the network necessarily classifies incorrectly.
  arXiv  Detail & Related papers  (2021-01-21T01:28:15Z)
• Analogy-Making as a Core Primitive in the Software Engineering Toolbox [7.396342576390398]
  We argue that analogy making should be seen as a core primitive in software engineering. We demonstrate this idea using Sifter, a new analogy-making algorithm suitable for software engineering applications.
  arXiv  Detail & Related papers  (2020-09-14T17:24:15Z)
• Generalizing Outside the Training Set: When Can Neural Networks Learn Identity Effects? [1.2891210250935143]
  We show that a class of algorithms including deep neural networks with standard architecture and training with backpropagation can generalize to novel inputs. We demonstrate our theory with computational experiments in which we explore the effect of different input encodings on the ability of algorithms to generalize to novel inputs.
  arXiv  Detail & Related papers  (2020-05-09T01:08:07Z)
• Machine Number Sense: A Dataset of Visual Arithmetic Problems for Abstract and Relational Reasoning [95.18337034090648]
  We propose a dataset, Machine Number Sense (MNS), consisting of visual arithmetic problems automatically generated using a grammar model--And-Or Graph (AOG) These visual arithmetic problems are in the form of geometric figures. We benchmark the MNS dataset using four predominant neural network models as baselines in this visual reasoning task.
  arXiv  Detail & Related papers  (2020-04-25T17:14:58Z)

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.