Neural Algorithmic Reasoning Without Intermediate Supervision

• URL: http://arxiv.org/abs/2306.13411v2
• Date: Wed, 1 Nov 2023 14:28:11 GMT
• Title: Neural Algorithmic Reasoning Without Intermediate Supervision
• Authors: Gleb Rodionov, Liudmila Prokhorenkova
• Abstract summary: 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.
• Score: 21.852775399735005
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Neural algorithmic reasoning is an emerging area of machine learning focusing on building models that can imitate the execution of classic algorithms, such as sorting, shortest paths, etc. One of the main challenges is to learn algorithms that are able to generalize to out-of-distribution data, in particular with significantly larger input sizes. Recent work on this problem has demonstrated the advantages of learning algorithms step-by-step, giving models access to all intermediate steps of the original algorithm. In this work, we instead focus on learning neural algorithmic reasoning only from the input-output pairs without appealing to the intermediate supervision. We propose simple but effective architectural improvements and also 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 CLRS Algorithmic Reasoning Benchmark and achieves new state-of-the-art results for several problems, including sorting, where we obtain significant improvements. Thus, learning without intermediate supervision is a promising direction for further research on neural reasoners.

Related papers

• From Decoding to Meta-Generation: Inference-time Algorithms for Large Language Models [63.188607839223046]
  This survey focuses on the benefits of scaling compute during inference. We explore three areas under a unified mathematical formalism: token-level generation algorithms, meta-generation algorithms, and efficient generation.
  arXiv  Detail & Related papers  (2024-06-24T17:45:59Z)
• Discrete Neural Algorithmic Reasoning [18.497863598167257]
  We propose to force neural reasoners to maintain the execution trajectory as a combination of finite predefined states. trained with supervision on the algorithm's state transitions, such models are able to perfectly align with the original algorithm.
  arXiv  Detail & Related papers  (2024-02-18T16:03:04Z)
• Neural Algorithmic Reasoning for Combinatorial Optimisation [20.36694807847833]
  We propose leveraging recent advancements in neural reasoning to improve the learning of CO problems. We suggest pre-training our neural model on relevant algorithms before training it on CO instances. Our results demonstrate that by using this learning setup, we achieve superior performance compared to non-algorithmically informed deep learning models.
  arXiv  Detail & Related papers  (2023-05-18T13:59:02Z)
• Representation Learning with Multi-Step Inverse Kinematics: An Efficient and Optimal Approach to Rich-Observation RL [106.82295532402335]
  Existing reinforcement learning algorithms suffer from computational intractability, strong statistical assumptions, and suboptimal sample complexity. We provide the first computationally efficient algorithm that attains rate-optimal sample complexity with respect to the desired accuracy level. Our algorithm, MusIK, combines systematic exploration with representation learning based on multi-step inverse kinematics.
  arXiv  Detail & Related papers  (2023-04-12T14:51:47Z)
• Neural Algorithmic Reasoning with Causal Regularisation [18.299363749150093]
  We make an important observation: there are many different inputs for which an algorithm will perform certain intermediate computations identically. This insight allows us to develop data augmentation procedures that, given an algorithm's intermediate trajectory, produce inputs for which the target algorithm would have exactly the same next trajectory step. We prove that the resulting method, which we call Hint-ReLIC, improves the OOD generalisation capabilities of the reasoner.
  arXiv  Detail & Related papers  (2023-02-20T19:41:15Z)
• Dual Algorithmic Reasoning [9.701208207491879]
  We propose to learn algorithms by exploiting duality of the underlying algorithmic problem. We demonstrate that simultaneously learning the dual definition of these optimisation problems in algorithmic learning allows for better learning. We then validate the real-world utility of our dual algorithmic reasoner by deploying it on a challenging brain vessel classification task.
  arXiv  Detail & Related papers  (2023-02-09T08:46:23Z)
• Improved Algorithms for Neural Active Learning [74.89097665112621]
  We improve the theoretical and empirical performance of neural-network(NN)-based active learning algorithms for the non-parametric streaming setting. We introduce two regret metrics by minimizing the population loss that are more suitable in active learning than the one used in state-of-the-art (SOTA) related work.
  arXiv  Detail & Related papers  (2022-10-02T05:03:38Z)
• A Generalist Neural Algorithmic Learner [18.425083543441776]
  We build a single graph neural network processor capable of learning to execute a wide range of algorithms. We show that it is possible to effectively learn algorithms in a multi-task manner, so long as we can learn to execute them well in a single-task regime.
  arXiv  Detail & Related papers  (2022-09-22T16:41:33Z)
• RANK-NOSH: Efficient Predictor-Based Architecture Search via Non-Uniform Successive Halving [74.61723678821049]
  We propose NOn-uniform Successive Halving (NOSH), a hierarchical scheduling algorithm that terminates the training of underperforming architectures early to avoid wasting budget. We formulate predictor-based architecture search as learning to rank with pairwise comparisons. The resulting method - RANK-NOSH, reduces the search budget by 5x while achieving competitive or even better performance than previous state-of-the-art predictor-based methods on various spaces and datasets.
  arXiv  Detail & Related papers  (2021-08-18T07:45:21Z)
• Evolving Reinforcement Learning Algorithms [186.62294652057062]
  We propose a method for meta-learning reinforcement learning algorithms. The learned algorithms are domain-agnostic and can generalize to new environments not seen during training. We highlight two learned algorithms which obtain good generalization performance over other classical control tasks, gridworld type tasks, and Atari games.
  arXiv  Detail & Related papers  (2021-01-08T18:55:07Z)
• Strong Generalization and Efficiency in Neural Programs [69.18742158883869]
  We study the problem of learning efficient algorithms that strongly generalize in the framework of neural program induction. By carefully designing the input / output interfaces of the neural model and through imitation, we are able to learn models that produce correct results for arbitrary input sizes.
  arXiv  Detail & Related papers  (2020-07-07T17:03:02Z)

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.