A Neural Rewriting System to Solve Algorithmic Problems

• URL: http://arxiv.org/abs/2402.17407v2
• Date: Fri, 12 Jul 2024 15:42:45 GMT
• Title: A Neural Rewriting System to Solve Algorithmic Problems
• Authors: Flavio Petruzzellis, Alberto Testolin, Alessandro Sperduti,
• Abstract summary: We propose a modular architecture designed to learn a general procedure for solving nested mathematical formulas. Inspired by rewriting systems, a classic framework in symbolic artificial intelligence, we include in the architecture three specialized and interacting modules. We benchmark our system against the Neural Data Router, a recent model specialized for systematic generalization, and a state-of-the-art large language model (GPT-4) probed with advanced prompting strategies.
• Score: 47.129504708849446
• License: http://creativecommons.org/licenses/by-sa/4.0/
• Abstract: Modern neural network architectures still struggle to learn algorithmic procedures that require to systematically apply compositional rules to solve out-of-distribution problem instances. In this work, we focus on formula simplification problems, a class of synthetic benchmarks used to study the systematic generalization capabilities of neural architectures. We propose a modular architecture designed to learn a general procedure for solving nested mathematical formulas by only relying on a minimal set of training examples. Inspired by rewriting systems, a classic framework in symbolic artificial intelligence, we include in the architecture three specialized and interacting modules: the Selector, trained to identify solvable sub-expressions; the Solver, mapping sub-expressions to their values; and the Combiner, replacing sub-expressions in the original formula with the solution provided by the Solver. We benchmark our system against the Neural Data Router, a recent model specialized for systematic generalization, and a state-of-the-art large language model (GPT-4) probed with advanced prompting strategies. We demonstrate that our approach achieves a higher degree of out-of-distribution generalization compared to these alternative approaches on three different types of formula simplification problems, and we discuss its limitations by analyzing its failures.

Related papers

• Machine Learning Insides OptVerse AI Solver: Design Principles and Applications [74.67495900436728]
  We present a comprehensive study on the integration of machine learning (ML) techniques into Huawei Cloud's OptVerse AI solver. We showcase our methods for generating complex SAT and MILP instances utilizing generative models that mirror multifaceted structures of real-world problem. We detail the incorporation of state-of-the-art parameter tuning algorithms which markedly elevate solver performance.
  arXiv  Detail & Related papers  (2024-01-11T15:02:15Z)
• A Hybrid System for Systematic Generalization in Simple Arithmetic Problems [70.91780996370326]
  We propose a hybrid system capable of solving arithmetic problems that require compositional and systematic reasoning over sequences of symbols. We show that the proposed system can accurately solve nested arithmetical expressions even when trained only on a subset including the simplest cases.
  arXiv  Detail & Related papers  (2023-06-29T18:35:41Z)
• A Recursively Recurrent Neural Network (R2N2) Architecture for Learning Iterative Algorithms [64.3064050603721]
  We generalize Runge-Kutta neural network to a recurrent neural network (R2N2) superstructure for the design of customized iterative algorithms. We demonstrate that regular training of the weight parameters inside the proposed superstructure on input/output data of various computational problem classes yields similar iterations to Krylov solvers for linear equation systems, Newton-Krylov solvers for nonlinear equation systems, and Runge-Kutta solvers for ordinary differential equations.
  arXiv  Detail & Related papers  (2022-11-22T16:30:33Z)
• Neural-Symbolic Recursive Machine for Systematic Generalization [113.22455566135757]
  We introduce the Neural-Symbolic Recursive Machine (NSR), whose core is a Grounded Symbol System (GSS) NSR integrates neural perception, syntactic parsing, and semantic reasoning. We evaluate NSR's efficacy across four challenging benchmarks designed to probe systematic generalization capabilities.
  arXiv  Detail & Related papers  (2022-10-04T13:27:38Z)
• Towards the One Learning Algorithm Hypothesis: A System-theoretic Approach [0.0]
  The existence of a universal learning architecture in human cognition is a widely spread conjecture supported by experimental findings from neuroscience. We develop a closed-loop system with three main components: (i) a multi-resolution analysis pre-processor, (ii) a group-invariant feature extractor, and (iii) a progressive knowledge-based learning module. We introduce a novel learning algorithm that constructs progressively growing knowledge representations in multiple resolutions.
  arXiv  Detail & Related papers  (2021-12-04T05:54:33Z)
• Personalized Algorithm Generation: A Case Study in Meta-Learning ODE Integrators [6.457555233038933]
  We study the meta-learning of numerical algorithms for scientific computing. We develop a machine learning approach that automatically learns solvers for initial value problems.
  arXiv  Detail & Related papers  (2021-05-04T05:42:33Z)
• Neuro-algorithmic Policies enable Fast Combinatorial Generalization [16.74322664734553]
  Recent results suggest that generalization for standard architectures improves only after obtaining exhaustive amounts of data. We show that for a certain subclass of the MDP framework, this can be alleviated by neuro-algorithmic architectures. We introduce a neuro-algorithmic policy architecture consisting of a neural network and an embedded time-dependent shortest path solver.
  arXiv  Detail & Related papers  (2021-02-15T11:07:59Z)
• Model-Based Machine Learning for Communications [110.47840878388453]
  We review existing strategies for combining model-based algorithms and machine learning from a high level perspective. We focus on symbol detection, which is one of the fundamental tasks of communication receivers.
  arXiv  Detail & Related papers  (2021-01-12T19:55:34Z)

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.