Inferring Algorithmic Patterns with Stack-Augmented Recurrent Nets

By Armand Joulin, Tomas Mikolov. 2015

426 citations recorded by the source corpus.

Despite the recent achievements in machine learning, we are still very far from achieving real artificial intelligence. In this paper, we discuss the limitations of standard deep learning approaches and show that some of these limitations can be overcome by learning how to grow the complexity of a model in a structured way. Specifically, we study the simplest sequence prediction problems that are beyond the scope of what is learnable with standard recurrent networks, algorithmically generated sequences which can only be learned by models which have the capacity to count and to memorize sequences. We show that some basic algorithms can be learned from sequential data using a recurrent network associated with a trainable memory.

Subfields: Artificial Intelligence, Model Architectures, Signal 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 Model Architectures

In Signal Processing

Citations in the corpus

Can Active Memory Replace Attention? (2016, background): “If only a single attention mechanism is present, the model will have a hard time learning this task and will not generalize properly, as was demonstrated in [12, 13].”
Character-Level Language Modeling with Deeper Self-Attention (2018, background): “Giving RNNs access to external memory has also shown improvements in the language modeling domain [17, 47].”
Retrieval-Augmented Generation for Knowledge-Intensive NLP Tasks (2020, background): “There has been extensive previous work proposing architectures to enrich systems with non-parametric memory which are trained from scratch for speciﬁc tasks—e.g. in memory networks [58, 49], stack-augmented networks [21] and memory layers for transformers [26].”
Universal Transformers (2018, methodology): “Our experiments indicate that this inductive bias may be crucial for several algorithmic and language understanding tasks of varying complexity: in contrast to models such as the Neural Turing Machine [13], the Neural GPU [17] or Stack RNNs [16], the Transformer does not generalize well to input len”
Improving Neural Language Models with a Continuous Cache (2016, background): “Typically, they have to learn a parametrizable mechanism to read or write to memory cells (Graves et al., 2014; Joulin & Mikolov, 2015).”
ShapeWorld - A new test methodology for multimodal language understanding (2017, background): “Recent work in the context of deep learning has investigated sequence patterns (Joulin and Mikolov, 2015), combinatorial problems (Vinyals et al., 2015), or executing programming language code (Zaremba and Sutskever, 2014), amongst others.”
CLEVR: A Diagnostic Dataset for Compositional Language and Elementary Visual Reasoning (2016, methodology): “We plan to use CLEVR to study models with explicit short-term memory, facilitating comparisons between values [13, 18, 39, 42]; explore approaches that encourage learning disentangled representations [5]; and investigate methods that compile custom network architectures for different patterns of rea”
Neural Execution Engines: Learning to Execute Subroutines (2020, background): “Several papers have used neural networks to learn binary arithmetic with some success [11, 12].”
Least-to-Most Prompting Enables Complex Reasoning in Large Language Models (2022, background): “Notable examples of such tasks are: (1) Symbolic manipulation (Grefenstette et al., 2015; Joulin & Mikolov, 2015; Kaiser & Sutskever, 2016; Kurach et al., 2016; Graves et al., 2016; Dong et al., 2019), which usually involves manipulating lists of ∗Correspondence to: Denny Zhou…”
Analysing Mathematical Reasoning Abilities of Neural Models (2019, background): “…which aim capture algorithmic/systematic reasoning have often been drawn from this domain (Graves et al., 2016; Kaiser & Sutskever, 2015; Joulin & Mikolov, 2015), and thus in providing a large scale training and evaluation framework for such models, we hope to provide a solid foundation…”
Scalable Adaptive Computation for Iterative Generation (2022, background): “Recurrent Interface Networks bear resemblance to architectures that leverage auxiliary memory to decouple computation from the input structure such as Memory Networks (Weston et al., 2014; Sukhbaatar et al., 2015), Neural Turing Machines (Graves et al., 2014), Stack-RNN (Joulin & Mikolov, 2015), Set”
The Goldilocks Principle: Reading Children's Books with Explicit Memory Representations (2015, background): “Other recent papers have proposed RNN-like architectures with new ways of reading, storing and updating information to improve their capacity to learn algorithmic or syntactic patterns (Joulin & Mikolov, 2015; Dyer et al., 2015; Grefenstette et al., 2015).”
Ask Me Anything: Dynamic Memory Networks for Natural Language Processing (2015, background): “Various other neural memory or attention architectures have recently been proposed for algorithmic problems (Joulin & Mikolov, 2015; Kaiser & Sutskever, 2015), caption generation for images (Malinowski & Fritz, 2014; Chen & Zitnick, 2014), visual question answering (Yang et al., 2015) or other NLP…”
Assessing the Ability of LSTMs to Learn Syntax-Sensitive Dependencies (2016, neutral): “This makes it difficult to distinguish simple but robust sequence models from more expressive architectures (Socher, 2014; Grefenstette et al., 2015; Joulin and Mikolov, 2015).”
RobustFill: Neural Program Learning under Noisy I/O (2017, methodology): “…Riedel et al., 2016), and (2) neural program induction , where network learns to generate the output directly using a latent program representation (Graves et al., 2014; 2016; Kurach et al., 2016; Kaiser & Sutskever, 2015; Joulin & Mikolov, 2015; Reed & de Fre-itas, 2016; Neelakantan et al., 2016).”
Reasoning about Entailment with Neural Attention (2015, background): “, 2015), or other forms of differentiable memory (e.g. Grefenstette et al., 2015; Joulin and Mikolov, 2015) could help improve performance on RTE over the neural models presented in this paper.”
Neural Programmer: Inducing Latent Programs with Gradient Descent (2015, background): “…memory (Das et al., 1992a; Schmidhu-ber, 1993; Hochreiter & Schmidhuber, 1997; Graves et al., 2014; Weston et al., 2015; Kumar et al., 2015; Joulin & Mikolov, 2015), we are not aware of any other work that augments a neural network with a set of operations to enhance complex reasoning…”