Neural-guided, Bidirectional Program Search for Abstraction and Reasoning

• URL: http://arxiv.org/abs/2110.11536v2
• Date: Tue, 26 Oct 2021 15:26:31 GMT
• Title: Neural-guided, Bidirectional Program Search for Abstraction and Reasoning
• Authors: Simon Alford, Anshula Gandhi, Akshay Rangamani, Andrzej Banburski, Tony Wang, Sylee Dandekar, John Chin, Tomaso Poggio, and Peter Chin
• Abstract summary: This paper lays the foundations for two approaches to abstraction and reasoning not based in brute-force search. We first apply an existing program synthesis system called DreamCoder to create symbolic abstractions out of tasks solved so far. Second, we design a reasoning algorithm motivated by the way humans approach ARC.
• Score: 3.2348834229786885
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: One of the challenges facing artificial intelligence research today is designing systems capable of utilizing systematic reasoning to generalize to new tasks. The Abstraction and Reasoning Corpus (ARC) measures such a capability through a set of visual reasoning tasks. In this paper we report incremental progress on ARC and lay the foundations for two approaches to abstraction and reasoning not based in brute-force search. We first apply an existing program synthesis system called DreamCoder to create symbolic abstractions out of tasks solved so far, and show how it enables solving of progressively more challenging ARC tasks. Second, we design a reasoning algorithm motivated by the way humans approach ARC. Our algorithm constructs a search graph and reasons over this graph structure to discover task solutions. More specifically, we extend existing execution-guided program synthesis approaches with deductive reasoning based on function inverse semantics to enable a neural-guided bidirectional search algorithm. We demonstrate the effectiveness of the algorithm on three domains: ARC, 24-Game tasks, and a 'double-and-add' arithmetic puzzle.

Related papers

• VisualPredicator: Learning Abstract World Models with Neuro-Symbolic Predicates for Robot Planning [86.59849798539312]
  We present Neuro-Symbolic Predicates, a first-order abstraction language that combines the strengths of symbolic and neural knowledge representations. We show that our approach offers better sample complexity, stronger out-of-distribution generalization, and improved interpretability.
  arXiv  Detail & Related papers  (2024-10-30T16:11:05Z)
• Program Synthesis using Inductive Logic Programming for the Abstraction and Reasoning Corpus [1.9662978733004604]
  The Abstraction and Reasoning Corpus (ARC) is unsolvable by any Machine Learning method. We propose a Program Synthesis system that uses Inductive Logic Programming (ILP), a branch of AI, to solve ARC.
  arXiv  Detail & Related papers  (2024-05-10T11:22:31Z)
• Neural networks for abstraction and reasoning: Towards broad generalization in machines [3.165509887826658]
  We look at novel approaches for solving the Abstraction & Reasoning Corpus (ARC) We adapt the DreamCoder neurosymbolic reasoning solver to ARC. We present the Perceptual Abstraction and Reasoning Language (PeARL) language, which allows DreamCoder to solve ARC tasks. We publish the arckit Python library to make future research on ARC easier.
  arXiv  Detail & Related papers  (2024-02-05T20:48:57Z)
• PathFinder: Guided Search over Multi-Step Reasoning Paths [80.56102301441899]
  We propose PathFinder, a tree-search-based reasoning path generation approach. It enhances diverse branching and multi-hop reasoning through the integration of dynamic decoding. Our model generalizes well to longer, unseen reasoning chains, reflecting similar complexities to beam search with large branching factors.
  arXiv  Detail & Related papers  (2023-12-08T17:05:47Z)
• Learning Differentiable Logic Programs for Abstract Visual Reasoning [18.82429807065658]
  Differentiable forward reasoning has been developed to integrate reasoning with gradient-based machine learning paradigms. NEUMANN is a graph-based differentiable forward reasoner, passing messages in a memory-efficient manner and handling structured programs with functors. We demonstrate that NEUMANN solves visual reasoning tasks efficiently, outperforming neural, symbolic, and neuro-symbolic baselines.
  arXiv  Detail & Related papers  (2023-07-03T11:02:40Z)
• Neural Algorithmic Reasoning Without Intermediate Supervision [21.852775399735005]
  We focus on learning neural algorithmic reasoning only from the input-output pairs without appealing to the intermediate supervision. We build a self-supervised objective that can regularise intermediate computations of the model without access to the algorithm trajectory. We demonstrate that our approach is competitive to its trajectory-supervised counterpart on tasks from the CLRSic Algorithmic Reasoning Benchmark.
  arXiv  Detail & Related papers  (2023-06-23T09:57:44Z)
• LLMs and the Abstraction and Reasoning Corpus: Successes, Failures, and the Importance of Object-based Representations [50.431003245201644]
  We show that GPT-4 is unable to "reason" perfectly within non-language domains such as the 1D-ARC or a simple ARC subset. We propose an object-based representation that is obtained through an external tool, resulting in nearly doubling the performance on solved ARC tasks and near-perfect scores on the easier 1D-ARC.
  arXiv  Detail & Related papers  (2023-05-26T16:32:17Z)
• Graphs, Constraints, and Search for the Abstraction and Reasoning Corpus [19.27379168184259]
  The Abstraction and Reasoning Corpus (ARC) aims at benchmarking the performance of general artificial intelligence algorithms. The ARC's focus on broad generalization and few-shot learning has made it impossible to solve using pure machine learning. We propose Abstract Reasoning with Graph Abstractions (ARGA), a new object-centric framework that first represents images using graphs and then performs a search for a correct program.
  arXiv  Detail & Related papers  (2022-10-18T14:13:43Z)
• Learning Iterative Reasoning through Energy Minimization [77.33859525900334]
  We present a new framework for iterative reasoning with neural networks. We train a neural network to parameterize an energy landscape over all outputs. We implement each step of the iterative reasoning as an energy minimization step to find a minimal energy solution.
  arXiv  Detail & Related papers  (2022-06-30T17:44:20Z)
• Abstract Reasoning via Logic-guided Generation [65.92805601327649]
  Abstract reasoning, i.e., inferring complicated patterns from given observations, is a central building block of artificial general intelligence. This paper aims to design a framework for the latter approach and bridge the gap between artificial and human intelligence. We propose logic-guided generation (LoGe), a novel generative DNN framework that reduces abstract reasoning as an optimization problem in propositional logic.
  arXiv  Detail & Related papers  (2021-07-22T07:28:24Z)
• BUSTLE: Bottom-Up Program Synthesis Through Learning-Guided Exploration [72.88493072196094]
  We present a new synthesis approach that leverages learning to guide a bottom-up search over programs. In particular, we train a model to prioritize compositions of intermediate values during search conditioned on a set of input-output examples. We show that the combination of learning and bottom-up search is remarkably effective, even with simple supervised learning approaches.
  arXiv  Detail & Related papers  (2020-07-28T17:46:18Z)

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.