Learning Compositional Rules via Neural Program Synthesis

By Maxwell Nye, Armando Solar-Lezama, Josh Tenenbaum, Brenden M. Lake. 2020

120 citations recorded by the source corpus.

Many aspects of human reasoning, including language, require learning rules from very little data. Humans can do this, often learning systematic rules from very few examples, and combining these rules to form compositional rule-based systems. Current neural architectures, on the other hand, often fail to generalize in a compositional manner, especially when evaluated in ways that vary systematically from training. In this work, we present a neuro-symbolic model which learns entire rule systems from a small set of examples. Instead of directly predicting outputs from inputs, we train our model to induce the explicit system of rules governing a set of previously seen examples, drawing upon techniques from the neural program synthesis literature. Our rule-synthesis approach outperforms neural meta-learning techniques in three domains: an artificial instruction-learning domain used to evaluate human learning, the SCAN challenge datasets, and learning rule-based translations of number words into integers for a wide range of human languages.

Subfields: Artificial Intelligence, Natural Language Processing

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Natural Language Processing

Citations in the corpus

Least-to-Most Prompting Enables Complex Reasoning in Large Language Models (2022, methodology): “In the prompt constructed to solve SCAN, we actually used both natural language and Python notation.”
An Empirical Study on Robustness to Spurious Correlations using Pre-trained Language Models (2020, methodology): “To enable extrapolation, we might need additional inductive bias (Nye et al., 2019) or new learning algorithms (Arjovsky et al.”
Planning with Large Language Models for Code Generation (2023, unknown): “, 2021) and neural-symbolic methods (Nye et al., 2020) were explored.”
Improving Coherence and Consistency in Neural Sequence Models with Dual-System, Neuro-Symbolic Reasoning (2021, methodology): “Similar methods, such as guess-and-check or beam search pruning, have had success in neural program synthesis (Devlin et al., 2017; Nye et al., 2020).”
How to Reuse and Compose Knowledge for a Lifetime of Tasks: A Survey on Continual Learning and Functional Composition (2022, background): “, 2021), natural language (Nye et al., 2020; Chen et al., 2020b), vision (Wu et al.”
Compositional Semantic Parsing with Large Language Models (2022, background): “However, SCAN is an artificial task built upon a synthetic language with a tiny vocabulary and is generated from a small set of grammar rules, and it is unclear whether strong results transfer to more realistic tasks that are based on a larger vocabulary and more complicated grammars (Furrer et al.,”
Unlocking Compositional Generalization in Pre-trained Models Using Intermediate Representations (2021, background): “Both new architectures (Li et al., 2019; Lake, 2019; Nye et al., 2020; Chen et al., 2020, inter alia ) and general-purpose pre-trained seq2seq models such as T5 (Raffel et al., 2020) have shown improvements on some evaluations of compositional generalization, but strong performance in general…”
Compositional Generalization via Neural-Symbolic Stack Machines (2020, methodology): “…[28] 20.3 83.2 98.8 99.9 Equivariant seq2seq [16] 15.9 92.0 99.1 100.0 [25] 16.64 98.71 99.95 − Synth (no search) [36] 0.0 0.0 3.5 13.3 Synth (with search) [36] 100.0 100.0 100.0 100.0 Table 4: Accuracy on the compositional machine translation benchmark in [24], measured by semantic equivalence.”
The EOS Decision and Length Extrapolation (2020, background): “Others have proposed search-based approaches— modifying beam search to prevent EOS from being assigned too much probability mass (Murray and Chiang, 2018), or searching through programs to produce sequences rather than having neural models produce sequences themselves (Nye et al., 2020).”
LEGO: Latent Execution-Guided Reasoning for Multi-Hop Question Answering on Knowledge Graphs (2021, background): “Besides structured databases, there are other works on learning to synthesize programs for unstructured text understanding, including reading comprehension (Chen et al., 2020b; Amini et al., 2019) and sequence-to-sequence translation (Chen et al., 2020a; Nye et al., 2020b).”
A Benchmark for Systematic Generalization in Grounded Language Understanding (2020, background): “deep networks to handle at least some of the SCAN challenges [2, 27, 34, 36, 14].”
An Empirical Survey of Data Augmentation for Limited Data Learning in NLP (2021, background): “, 2020), semantic parsing (Andreas, 2020; Nye et al., 2020; Furrer et al., 2020), language modeling (Andreas, 2020; Shaw et al.”
Span-based Semantic Parsing for Compositional Generalization (2020, background): “, 2019), and proposing specialized architectures mainly for the SCAN task (Lake, 2019; Nye et al., 2020; Gordon et al., 2020; Liu et al., 2020; Gupta and Lewis, 2018).”
Evaluating the Impact of Model Scale for Compositional Generalization in Semantic Parsing (2022, background): “…2021; Qiu et al., 2022; Yang et al., 2022), specialized architectures (Li et al., 2019; Russin et al., 2019; Gordon et al., 2020; Liu et al., 2020; Nye et al., 2020; Chen et al., 2020; Zheng and Lapata, 2021; Oren et al., 2020; Herzig and Berant, 2021; Ruiz et al., 2021; Wang et al., 2021),…”
Compositional Generalization and Natural Language Variation: Can a Semantic Parsing Approach Handle Both? (2020, methodology): “This has motivated many specialized architectures with stronger compositional biases that improve peformance on SCAN (Li et al., 2019; Russin et al., 2019; Gordon et al., 2019; Lake, 2019; Liu et al., 2020; Nye et al., 2020; Chen et al., 2020).”