Compositional Generalization via Neural-Symbolic Stack Machines

By Xinyun Chen, Chen Liang, Adams Wei Yu, Dawn Song, Denny Zhou. 2020

109 citations recorded by the source corpus.

Despite achieving tremendous success, existing deep learning models have exposed limitations in compositional generalization, the capability to learn compositional rules and apply them to unseen cases in a systematic manner. To tackle this issue, we propose the Neural-Symbolic Stack Machine (NeSS). It contains a neural network to generate traces, which are then executed by a symbolic stack machine enhanced with sequence manipulation operations. NeSS combines the expressive power of neural sequence models with the recursion supported by the symbolic stack machine. Without training supervision on execution traces, NeSS achieves 100% generalization performance in four domains: the SCAN benchmark of language-driven navigation tasks, the task of few-shot learning of compositional instructions, the compositional machine translation benchmark, and context-free grammar parsing tasks.

Subfields: Artificial Intelligence, Computer Vision and Pattern Recognition, Model Architectures

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 Computer Vision and Pattern Recognition

In Model Architectures

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.”
LEGO: Latent Execution-Guided Reasoning for Multi-Hop Question Answering on Knowledge Graphs (2021, methodology): “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).”
An Empirical Survey of Data Augmentation for Limited Data Learning in NLP (2021, background): “Compared with random swapping, compositional augmentation often requires more carefully designed rules such as lexical overlap (Andreas, 2020), neural-symbolic stack machines (Chen et al., 2020e), and neural program synthesis (Nye 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…”
Teaching Algorithmic Reasoning via In-context Learning (2022, methodology): “…the architecture align to the algorithms under consideration (Kaiser and Sutskever, 2015; Chiang and Chen, 2018; Xu et al., 2019; Gordon et al., 2019; Yan et al., 2020; Chen et al., 2020; Xhonneux et al., 2021; Veliˇckovi´c and Blundell, 2021) or to the input format (Thawani et al., 2021).”
Evaluating the Impact of Model Scale for Compositional Generalization in Semantic Parsing (2022, background): “…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), ensemble models (Shaw…”
Compositional Semantic Parsing with Large Language Models (2022, background): “Recent work has achieved perfect generalization accuracy on SCAN by inferring grammar rules in symbolic form (Chen et al., 2020; Nye et al., 2020; Liu et al., 2020; Shaw et al., 2021).”
How to Reuse and Compose Knowledge for a Lifetime of Tasks: A Survey on Continual Learning and Functional Composition (2022, methodology): “Recently, similar ideas have achieved compositional generalization by directly learning rules over fixed symbols (Nye et al., 2020) or by providing a curriculum (Chen et al., 2020b).”
Sequence-to-Sequence Learning with Latent Neural Grammars (2021, unknown): “Our baselines here include standard LSTM/Transformer models as well as approaches that explicitly target compositional generalization [70, 19].”
Compositional Generalization and Natural Language Variation: Can a Semantic Parsing Approach Handle Both? (2020, methodology): “Additionally, we include results for GECA 9 (Andreas, 2020), a data augmentation method, as well as LANE (Liu et al., 2020) and NSSM (Chen et al., 2020) 10 .”