Program Synthesis using Inductive Logic Programming for the Abstraction and Reasoning Corpus

• URL: http://arxiv.org/abs/2405.06399v1
• Date: Fri, 10 May 2024 11:22:31 GMT
• Title: Program Synthesis using Inductive Logic Programming for the Abstraction and Reasoning Corpus
• Authors: Filipe Marinho Rocha, Inês Dutra, Vítor Santos Costa,
• Abstract summary: 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.
• Score: 1.9662978733004604
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: The Abstraction and Reasoning Corpus (ARC) is a general artificial intelligence benchmark that is currently unsolvable by any Machine Learning method, including Large Language Models (LLMs). It demands strong generalization and reasoning capabilities which are known to be weaknesses of Neural Network based systems. In this work, we propose a Program Synthesis system that uses Inductive Logic Programming (ILP), a branch of Symbolic AI, to solve ARC. We have manually defined a simple Domain Specific Language (DSL) that corresponds to a small set of object-centric abstractions relevant to ARC. This is the Background Knowledge used by ILP to create Logic Programs that provide reasoning capabilities to our system. The full system is capable of generalize to unseen tasks, since ILP can create Logic Program(s) from few examples, in the case of ARC: pairs of Input-Output grids examples for each task. These Logic Programs are able to generate Objects present in the Output grid and the combination of these can form a complete program that transforms an Input grid into an Output grid. We randomly chose some tasks from ARC that dont require more than the small number of the Object primitives we implemented and show that given only these, our system can solve tasks that require each, such different reasoning.

Related papers

• Improving Complex Reasoning over Knowledge Graph with Logic-Aware Curriculum Tuning [89.89857766491475]
  We propose a complex reasoning schema over KG upon large language models (LLMs) We augment the arbitrary first-order logical queries via binary tree decomposition to stimulate the reasoning capability of LLMs. Experiments across widely used datasets demonstrate that LACT has substantial improvements(brings an average +5.5% MRR score) over advanced methods.
  arXiv  Detail & Related papers  (2024-05-02T18:12:08Z)
• 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)
• Language Models can be Logical Solvers [99.40649402395725]
  We introduce LoGiPT, a novel language model that directly emulates the reasoning processes of logical solvers. LoGiPT is fine-tuned on a newly constructed instruction-tuning dataset derived from revealing and refining the invisible reasoning process of deductive solvers.
  arXiv  Detail & Related papers  (2023-11-10T16:23:50Z)
• 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)
• A Divide-Align-Conquer Strategy for Program Synthesis [8.595181704811889]
  We show that compositional segmentation can be applied in the programming by examples setting to divide the search for large programs across multiple smaller program synthesis problems. A structural alignment of the constituent parts in the input and output leads to pairwise correspondences used to guide the program search.
  arXiv  Detail & Related papers  (2023-01-08T19:10:55Z)
• 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)
• Join-Chain Network: A Logical Reasoning View of the Multi-head Attention in Transformer [59.73454783958702]
  We propose a symbolic reasoning architecture that chains many join operators together to model output logical expressions. In particular, we demonstrate that such an ensemble of join-chains can express a broad subset of ''tree-structured'' first-order logical expressions, named FOET. We find that the widely used multi-head self-attention module in transformer can be understood as a special neural operator that implements the union bound of the join operator in probabilistic predicate space.
  arXiv  Detail & Related papers  (2022-10-06T07:39:58Z)
• GALOIS: Boosting Deep Reinforcement Learning via Generalizable Logic Synthesis [34.54658276390227]
  Deep reinforcement learning (DRL) lacks high-order intelligence regarding learning and generalization in complex problems. Previous works attempt to directly synthesize a white-box logic program as the DRL policy, manifesting logic-driven behaviors. We propose a novel Generalizable Logic Synthesis (GALOIS) framework to synthesize hierarchical and strict cause-effect logic programs.
  arXiv  Detail & Related papers  (2022-05-27T02:50:13Z)
• Neural-guided, Bidirectional Program Search for Abstraction and Reasoning [3.2348834229786885]
  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.
  arXiv  Detail & Related papers  (2021-10-22T00:41:47Z)
• Leveraging Language to Learn Program Abstractions and Search Heuristics [66.28391181268645]
  We introduce LAPS (Language for Abstraction and Program Search), a technique for using natural language annotations to guide joint learning of libraries and neurally-guided search models for synthesis. When integrated into a state-of-the-art library learning system (DreamCoder), LAPS produces higher-quality libraries and improves search efficiency and generalization.
  arXiv  Detail & Related papers  (2021-06-18T15:08:47Z)
• Representing Partial Programs with Blended Abstract Semantics [62.20775388513027]
  We introduce a technique for representing partially written programs in a program synthesis engine. We learn an approximate execution model implemented as a modular neural network. We show that these hybrid neuro-symbolic representations enable execution-guided synthesizers to use more powerful language constructs.
  arXiv  Detail & Related papers  (2020-12-23T20:40: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.