Papperoni

2015

Inferring Algorithmic Patterns With Stack-Augmented Recurrent Nets

Armand Joulin, Tomas Mikolov

Open PDF Google Scholar

citations

Cite Score

22

AI summary

This paper introduces Stack-Augmented Recurrent Nets, a model that extends recurrent networks with structured memory (pushdown stack, list) and learnable controllers, and shows that the approach can infer algorithmic patterns from sequential data.

Main Contributions

Introduces stack-augmented recurrent networks with multiplicative gating mechanisms as learnable controllers over the memory.
Shows that the model can operate as if it was performing simple read and write operations, such as PUSH or POP for a stack.
The model is able to learn regularities in sequences of symbols as algorithmic patterns.
The model can address algorithmic tasks such as memorization and binary addition.
The model achieves competitive results on the Penn Treebank corpus.

Abstract

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.

Citation Graph

Loading graph...

References [38]

Sort:

Filter:

[1]ImageNet Classification With Deep Convolutional Neural Networks

Alex Krizhevsky, Ilya Sutskever, Geoffrey E. Hinton - 2012

71 papers in library cite

I'm giving this a 5 just because of the impact, but this is VEEERY derivative of earlier work. Kudos for them for putting it all together, but really there's nothing revolutionary here.

[2]Long Short-Term Memory

Sepp Hochreiter, Jürgen Schmidhuber - 1997

94 papers in library cite

LSTMs FTW!

[3]Gradient-Based Learning Applied to Document Recognition

Yann Lecun, Leon Bottou, Yoshua Bengio, Patrick Haffner - 1998

62 papers in library cite

I absolutely hated this paper. Has ~50 pages but seems like 200 pages. Takes too long to explain some things that really is just repeating itself. Also doesn't seem to add too much on top of LeNet-5. Also, focuses a lot on GTNs, which really didn't stick.

[4]Learning Phrase Representations Using RNN Encoder-Decoder for Statistical Machine Translation

Kyunghyun Cho, B. V. Merrienboer, C. G. Gulcehre, D. Bahdanau, F. Bougares, Holger Schwenk, Yoshua Bengio - 2014

38 papers in library cite

Introduces RNN encoder-decoder. I love it :)

[5]Learning Internal Representations by Error Propagation

D. E. Rumelhart, Geoffrey E. Hinton, Ronald J. Williams - 1986

46 papers in library cite

I expected very little of this, but was so good in explaining concepts! Very good read. It gets a bit boring when it starts explaining things by the end of the chapter, but good nonetheless.

[6]Finding Structure in Time

Jeffrey L. Elman - 1990

23 papers in library cite

Good paper overall that introduces the concept of an RNN. However, applications and results are still very primitive.

[7]Context-Dependent Pre-Trained Deep Neural Networks for Large-Vocabulary Speech Recognition

G. Dahl, D. Yu, L. Deng, Alex Acero - 2012

19 papers in library cite

Good paper, very well written and probably the best explanation of RBMs and DBNs I've seen. However, I don't see a lot of impact and seems very derivative from other works.

[8]Neural Turing Machines

Alex Graves, G. Wayne, Ivo Danihelka - 2014

18 papers in library cite

This paper is amazing. If someone told me that NNs could use and address memory by position I wouldn't believe it worked. Very nice, but it's a shame that it's just a toy example.

[9]Memory Networks

Jason Weston, S. Chopra, Antoine Bordes - 2015

18 papers in library cite

The first half of the paper (when they discuss the concept in a very abstract way) is amazing. However, the actual methodology was very convoluted - I did not like it. I thought that Neural Turing Machines were inspired in this, but actually they are contemporary... So anyway, the concept is nice, execution is not.

[10]Scaling Learning Algorithms Towards AI

Yoshua Bengio, Yann Lecun - 2007

15 papers in library cite

I should have read this sooner! Such a good explanation of why deep learning > other stuff! Also, better than Bengio's 2006 Learning Deep Archs for AI

[11]Probabilistic Interpretation of Feedforward Classification Network Outputs, With Relationship to Statistical Pattern Recognition

John S. Bridle - 1990

12 papers in library cite

Explains using softmax as output. Nice read, but I am not sure if too relevant.

[12]Generalization of Backpropagation With Application to a Recurrent Gas Market Model

Paul J. Werbos - 1988

11 papers in library cite

The first two sections are amazing. Very nice concepts, well explained. From section 3 on it gets more abstract and too formalized, and it's mostly for Hopfield recurrent nets (so not very relevant now). Section 4 is just the application to the gas market, which I don't care for at all.

[13]Gradient-Based Learning Algorithms for Recurrent Networks and Their Computational Complexity

Ronald J. Williams, David Zipser - 1992

8 papers in library cite

Oof, this was a hard read. I had to force myself to finish. I think this is too theoretical and deals with RNNs that are not really used nowadays. I skimmed through the second half.

[14]High-Performance Neural Networks for Visual Object Classification

Dan C. Ciresan, Ueli Meier, Jonathan Masci, Luca M. Gambardella, Jürgen Schmidhuber - 2011

5 papers in library cite

OK, I can see why this is important (implementing CNNs in GPUs before it was cool), but nothing too surprising. BTW, I read the 6 page version but this one has color so I kept this one.

[15]Perceptrons

M. Minsky, S. Papert - 1969

12 papers in library cite

Book, 500 pages

[16]Gated Feedback Recurrent Neural Networks

J. Chung, C. G. Gulcehre, Kyunghyun Cho, Yoshua Bengio - 2015

3 papers in library cite

Youshua Bengio + Gated Networks

[17]Learning to Execute

Wojciech Zaremba, Ilya Sutskever - 2014

8 papers in library cite

They try to execute python code

[18]Learning Longer Memory in Recurrent Neural Networks

Tomas Mikolov, Armand Joulin, S. Chopra, M. Mathieu, Marc'aurelio Ranzato - 2015

8 papers in library cite

RNNs + longer memory

[19]Statistical Language Models Based on Neural Networks

Tomas Mikolov - 2012

17 papers in library cite

Mikolov's Thesis

[20]Hogwild: A Lock-Free Approach to Parallelizing Stochastic Gradient Descent

Benjamin Recht, C. Re, S. Wright, F. Niu - 2011

6 papers in library cite

[21]Learning Context-Free Grammars: Capabilities and Limitations of a Recurrent Neural Network With an External Stack Memory

S. Das, C. Giles, G. Sun - 1992

5 papers in library cite

[22]Random Forests

L. Breiman - 2001

5 papers in library cite

[23]The Induction of Dynamical Recognizers

J. Pollack - 1991

4 papers in library cite

[24]LSTM recurrent Networks Learn Simple Context-Free and Context-Sensitive Languages

Felix A. Gers, Jürgen Schmidhuber - 2001

3 papers in library cite

[25]A Connectionist Symbol Manipulator That Discovers the Structure of Context-Free Languages

M. C. Mozer, S. Das - 1993

2 papers in library cite

[26]Learning to Count Without a Counter: A Case Study of Dynamics and Activation Landscapes in Recurrent Networks

J. Wiles, J. Elman - 1995

2 papers in library cite

[27]A Recurrent Network That Performs a Context-Sensitive Prediction Task

P. Grunwald - 1996

1 paper in library cites

[28]A Recurrent Neural Network That Learns to Count

P. Rodriguez, J. Wiles, Jeffrey L. Elman - 1999

1 paper in library cites

[29]Context-Free and Context-Sensitive Dynamics in Recurrent Neural Networks

M. Boden, J. Wiles - 2000

1 paper in library cites

[30]Context-Free Parsing in Connectionist Networks

M. Fanty - 1994

1 paper in library cites

[31]Designing a Counter: Another Case Study of Dynamics and Activation Landscapes in Recurrent Networks

S. Holldobler, Y. Kalinke, H. Lehmann - 1997

1 paper in library cites

[32]Discrete Recurrent Neural Networks for Grammatical Inference

Z. Zeng, R. M. Goodman, P. Smyth - 1994

1 paper in library cites

[33]Fractal Encoding of Context-Free Grammars in Connectionist Networks

W. Tabor - 2000

1 paper in library cites

[34]Large-Scale Machine Learning With Stochastic Gradient Descent

Leon Bottou - 2010

1 paper in library cites

[35]Mechanisms for Sentence Processing

M. W. Crocker - 1996

1 paper in library cites

[36]Pattern Recognition and Machine Learning

C. M. Bishop - 2006

1 paper in library cites

[37]Toward a Connectionist Model of Recursion in Human Linguistic Performance

M. H. Christiansen, N. Chater - 1999

1 paper in library cites

[38]Using Prior Knowledge in a Nnpda to Learn Context-Free Languages

S. Das, C. L. Giles, G. Z. Sun - 1993

1 paper in library cites

Cited by

9

papers in your library

Cites

18

papers in your library

Read

on October 13, 2025

Very underwhelming TBH. I expected more after reading the Neural Turing Machine paper. This reads like "yeah, we lost the race, here's what we were doing before they did something better"

Tags

Paper Aliases

No aliases