7 ms·

Inferring Algorithmic Patterns with Stack

113 points by antman 11y ago

waterlesscloud 11y ago
Can someone knowledgeable in the field elaborate on the differences between this and other NN approaches that also use additional memory structures (LSTM, etc)?
- crazypyro 11y ago
  They address this in the paper under section 3, "Related work". From the paper (there's more on other things besides LSTM, but here's the LSTM specific mention): Hochreiter and Schmidhuber [20] introduced the Long Short Term Memory network (LSTM) architecture. While this model was orginally developed to address the vanishing and exploding gradient problems, LSTM is also able to learn simple context-free and context-sensitive grammars [17, 37]. This is possible because its hidden units can choose through a multiplicative gating mechanism to be either linear or non-linear. The linear units allow the network to potentially count (one can easily add and subtract constants) and store a finite amount of information for a long period of time. These mechanisms are also used in the Gated Recurrent Unit network [7, 9]. In our work we investigate the use of a similar mechanism in a context where the memory is unbounded and structured. As opposed to previous work, we do not need to “erase” our memory to store a new unit. Edit: They also provide a table in the paper showing improvements over LSTM for certain types of algorithms.
- andrewtbham 11y ago
  I will hazard a guess as to why this might be better than LSTM. LSTM maintains a vector that represents the long short term memory, but once information is cleared from the vector, there is no way to get it back... whereas a stack you can keep going further down the stack if needed. http://colah.github.io/posts/2015-08-Understanding-LSTMs/ http://colah.github.io/posts/2015-08-Understanding-LSTMs/
  - sxyuan 11y ago
    One related work that came to mind was Neural Turing Machines, which augments the LSTM network with a (fixed size) memory [1]. I did see a brief reference to the Graves et al. paper in the paper linked to in the original post, but I'm also wondering if someone more knowledgeable could elaborate on the difference. My own guess would be that the models are similar (both using NNs with external memory, trained through backprop), but this has a simpler memory structure and so could be trained more easily. It seems like the choice of regular RNNs vs. an LSTM network doesn't matter much since the Graves paper also compared LSTM vs. feedforward controllers and the results were about the same, with the feedforward controllers actually learning a bit faster. The key of both works seems to be in making a continuous system that can be trained to use external memory through backprop. [1] http://arxiv.org/abs/1410.5401 http://arxiv.org/abs/1410.5401
- eli_gottlieb 11y ago
  From reading the page and these comments... A feedforward neural network can be viewed as a "continuous generalization" of a fixed-size circuit, which makes it able to learn any function within the circuit complexity of the network. A deep neural network biases towards circuits that are deeper than they are wide, towards functions composed out of smaller functions. Since many useful functions are such (and for other theoretical reasons, such as deep networks having "funnels" in their free-energy landscapes), deep learning works well. A recurrent neural network goes from circuits to deterministic finite-state automata. LSTM basically turns the whole thing into a small, fixed-size almost sorta-kinda pushdown automaton, and Neural Turing Machines generalize to a sorta-kinda linear-bounded automaton. This stack approach makes things much more like a real pushdown automaton. So a feedforward network with a stack should be able to "learn any PDA", and a recurrent network with an unlimited-size stack should be able to learn more-or-less any Turing machine (though it's biased towards Turing machines that "look like" PDAs with funny state transitions). Kinda. waves hands
- robryk 11y ago
  A difference between the two is that LSTM has a constant amount of memory, defined at training time. In this model, the stacks can grow arbitrarily large. Also, using a finite state machine and two stacks one can simulate any Turing machine, so one can represent arbitrary computations in this model (assuming we structure the input in such a way that there is time to do the computation in question).
discardorama 11y ago
"It should be noted that similar line of research has been pursued by several research groups already in the 90's" I chuckled at that, because I bet it's a reference to Schmidhuber. :D
andrewtbham 11y ago
Reasons this high has probability of credibility: Research probably used on Facebook digital assistant M. Tomas Mikolov, the author of word2vec. Paper with source code. http://arxiv.org/pdf/1503.01007.pdf http://arxiv.org/pdf/1503.01007.pdf https://github.com/facebook/Stack-RNN https://github.com/facebook/Stack-RNN
- ching_wow_ka 11y ago
  I doubt that it's used in M. "Why not just build M with neural nets from the beginning? Without the right data, neural nets couldn’t provide a service much more powerful than, well, Siri, and Wit.ai’s tech can get things started with relatively little data. “This is a good way to bootstrap. With a few thousand data-points, you can start to build a model,” Lebrun says. “Then, using this model, you get more data, and once you have about a million data points, you go to Yann and get some deep learning.”" [1] [1] http://www.wired.com/2015/08/how-facebook-m-works/ http://www.wired.com/2015/08/how-facebook-m-works/
  - Irishsteve 11y ago
    They are probably using M to get more data to learn from.
  - andrewtbham 11y ago
    That was a month ago... I'm sure they have some data by now or at least a plan on what to do once they get more data.
reader5000 11y ago
I wonder why gradient descent (gating all compute/memory operations with parameters, gradient updates to parameter vectors along sample loss gradient) ended up dominant over genetic programming (algorithms as parse trees, mutate/recombine to minimize sample loss). Both seem equally theoretically unjustified, although I guess SGD is more friendly for gpus. Also I wonder if all programming should just be done by showing a sgd-solver example i/o. Of course this notion has been around since the 80s with prolog but apparently representing "concepts" as 1000 dimension feature vectors is more robust than single boolean variables.
- lars 11y ago
  With SGD, you know how to take steps in the direction of a better solution. You don't have that with genetic programming, there you just know if a solution happened to be better.
  - p1esk 11y ago
    There's a weight perturbation algorithm, which is somewhat similar to genetic programming. The reason it's not as popular as SGD/backprop is it's computationally intensive, and it's hard to parallelize.
  - reader5000 11y ago
    With sgd you only know a locally better solution. GP has this as well: take the best current instance and mutate it/recombine it.
- raverbashing 11y ago
  I'm guessing the search space of SGD is more manageable and GP is too generic How would you go about designing a GP to identify handwritten digits from, let's say, 32x32 px images? You would need operators operating on the images, then other operators reducing its dimensionality to an answer between 0 and 9 I'm a big fan of GP but it seems they're stuck into a niche for now
  - skimpycompiler 11y ago
andrewtbham 11y ago
Here is a recent Facebook research paper that addresses the problem I believe this paper is intended to solve. Towards AI-Complete Question Answering: A Set of Prerequisite Toy Tasks http://arxiv.org/pdf/1502.05698v6.pdf http://arxiv.org/pdf/1502.05698v6.pdf This recent paper is an algorithm to solve simple question answering from the context of a conversation... like the ones in the older paper... for instance. John is in the playground. Bob is in the office. Where is John? A:playground I believe a traditional LSTM RNN would have likely cleared the information about John from from it's long short term memory vector. Whereas you would still have access to the information about John in a stack. fta: "Since the machine can essentially learn how to operate its memory, it can learn how to program itself by producing sequences of instructions."
- cs702 11y ago
  I have shivers going down my spine at the idea of feeding, say, skip-thought vectors representing sentences[1] into stack-augmented recurrent neural nets as proposed in Facebook's paper[2], for all sorts of interesting tasks. -- [1] http://arxiv.org/pdf/1506.06726v1.pdf http://arxiv.org/pdf/1506.06726v1.pdf [2] http://arxiv.org/pdf/1503.01007.pdf http://arxiv.org/pdf/1503.01007.pdf
- Smerity 11y ago
  If people are interested in playing with the dataset from "Towards AI-Complete Question Answering: A Set of Prerequisite Toy Tasks", I added an example to Keras that uses recurrent neural networks[1]. It achieves similar accuracy to the baseline LSTM approach in the paper. I also did a write-up that explains the task and architecture[2]. The dataset (bAbi tasks[3]) released by Facebook is interesting but has a number of limitations. The code used to produce it is also not open source. If someone has the interest and/or past experience in MUD style environments, creating an open source dataset would be amazing! [1]: https://github.com/fchollet/keras/blob/master/examples/babi_rnn.py https://github.com/fchollet/keras/blob/master/examples/babi_... [2]: http://smerity.com/articles/2015/keras_qa.html http://smerity.com/articles/2015/keras_qa.html [3]: https://research.facebook.com/researchers/1543934539189348 https://research.facebook.com/researchers/1543934539189348
skybrian 11y ago
I wonder if this sort of thing would be useful in american fuzzy lop? (It already uses genetic algorithms.)

113 points by antman 11y ago

Can someone knowledgeable in the field elaborate on the differences between this and other NN approaches that also use additional memory structures (LSTM, etc)?

crazypyro 11y ago
They address this in the paper under section 3, "Related work". From the paper (there's more on other things besides LSTM, but here's the LSTM specific mention): Hochreiter and Schmidhuber [20] introduced the Long Short Term Memory network (LSTM) architecture. While this model was orginally developed to address the vanishing and exploding gradient problems, LSTM is also able to learn simple context-free and context-sensitive grammars [17, 37]. This is possible because its hidden units can choose through a multiplicative gating mechanism to be either linear or non-linear. The linear units allow the network to potentially count (one can easily add and subtract constants) and store a finite amount of information for a long period of time. These mechanisms are also used in the Gated Recurrent Unit network [7, 9]. In our work we investigate the use of a similar mechanism in a context where the memory is unbounded and structured. As opposed to previous work, we do not need to “erase” our memory to store a new unit. Edit: They also provide a table in the paper showing improvements over LSTM for certain types of algorithms.
andrewtbham 11y ago
I will hazard a guess as to why this might be better than LSTM. LSTM maintains a vector that represents the long short term memory, but once information is cleared from the vector, there is no way to get it back... whereas a stack you can keep going further down the stack if needed. http://colah.github.io/posts/2015-08-Understanding-LSTMs/ http://colah.github.io/posts/2015-08-Understanding-LSTMs/
- sxyuan 11y ago
  One related work that came to mind was Neural Turing Machines, which augments the LSTM network with a (fixed size) memory [1]. I did see a brief reference to the Graves et al. paper in the paper linked to in the original post, but I'm also wondering if someone more knowledgeable could elaborate on the difference. My own guess would be that the models are similar (both using NNs with external memory, trained through backprop), but this has a simpler memory structure and so could be trained more easily. It seems like the choice of regular RNNs vs. an LSTM network doesn't matter much since the Graves paper also compared LSTM vs. feedforward controllers and the results were about the same, with the feedforward controllers actually learning a bit faster. The key of both works seems to be in making a continuous system that can be trained to use external memory through backprop. [1] http://arxiv.org/abs/1410.5401 http://arxiv.org/abs/1410.5401
eli_gottlieb 11y ago
From reading the page and these comments... A feedforward neural network can be viewed as a "continuous generalization" of a fixed-size circuit, which makes it able to learn any function within the circuit complexity of the network. A deep neural network biases towards circuits that are deeper than they are wide, towards functions composed out of smaller functions. Since many useful functions are such (and for other theoretical reasons, such as deep networks having "funnels" in their free-energy landscapes), deep learning works well. A recurrent neural network goes from circuits to deterministic finite-state automata. LSTM basically turns the whole thing into a small, fixed-size almost sorta-kinda pushdown automaton, and Neural Turing Machines generalize to a sorta-kinda linear-bounded automaton. This stack approach makes things much more like a real pushdown automaton. So a feedforward network with a stack should be able to "learn any PDA", and a recurrent network with an unlimited-size stack should be able to learn more-or-less any Turing machine (though it's biased towards Turing machines that "look like" PDAs with funny state transitions). Kinda. waves hands
robryk 11y ago
A difference between the two is that LSTM has a constant amount of memory, defined at training time. In this model, the stacks can grow arbitrarily large. Also, using a finite state machine and two stacks one can simulate any Turing machine, so one can represent arbitrary computations in this model (assuming we structure the input in such a way that there is time to do the computation in question).

discardorama 11y ago

"It should be noted that similar line of research has been pursued by several research groups already in the 90's" I chuckled at that, because I bet it's a reference to Schmidhuber. :D

andrewtbham 11y ago

Reasons this high has probability of credibility: Research probably used on Facebook digital assistant M. Tomas Mikolov, the author of word2vec. Paper with source code. http://arxiv.org/pdf/1503.01007.pdf http://arxiv.org/pdf/1503.01007.pdf https://github.com/facebook/Stack-RNN https://github.com/facebook/Stack-RNN

ching_wow_ka 11y ago
I doubt that it's used in M. "Why not just build M with neural nets from the beginning? Without the right data, neural nets couldn’t provide a service much more powerful than, well, Siri, and Wit.ai’s tech can get things started with relatively little data. “This is a good way to bootstrap. With a few thousand data-points, you can start to build a model,” Lebrun says. “Then, using this model, you get more data, and once you have about a million data points, you go to Yann and get some deep learning.”" [1] [1] http://www.wired.com/2015/08/how-facebook-m-works/ http://www.wired.com/2015/08/how-facebook-m-works/
- Irishsteve 11y ago
  They are probably using M to get more data to learn from.
- andrewtbham 11y ago
  That was a month ago... I'm sure they have some data by now or at least a plan on what to do once they get more data.

reader5000 11y ago

I wonder why gradient descent (gating all compute/memory operations with parameters, gradient updates to parameter vectors along sample loss gradient) ended up dominant over genetic programming (algorithms as parse trees, mutate/recombine to minimize sample loss). Both seem equally theoretically unjustified, although I guess SGD is more friendly for gpus. Also I wonder if all programming should just be done by showing a sgd-solver example i/o. Of course this notion has been around since the 80s with prolog but apparently representing "concepts" as 1000 dimension feature vectors is more robust than single boolean variables.

lars 11y ago
With SGD, you know how to take steps in the direction of a better solution. You don't have that with genetic programming, there you just know if a solution happened to be better.
- p1esk 11y ago
  There's a weight perturbation algorithm, which is somewhat similar to genetic programming. The reason it's not as popular as SGD/backprop is it's computationally intensive, and it's hard to parallelize.
- reader5000 11y ago
  With sgd you only know a locally better solution. GP has this as well: take the best current instance and mutate it/recombine it.
raverbashing 11y ago
I'm guessing the search space of SGD is more manageable and GP is too generic How would you go about designing a GP to identify handwritten digits from, let's say, 32x32 px images? You would need operators operating on the images, then other operators reducing its dimensionality to an answer between 0 and 9 I'm a big fan of GP but it seems they're stuck into a niche for now
- skimpycompiler 11y ago

andrewtbham 11y ago

Here is a recent Facebook research paper that addresses the problem I believe this paper is intended to solve. Towards AI-Complete Question Answering: A Set of Prerequisite Toy Tasks http://arxiv.org/pdf/1502.05698v6.pdf http://arxiv.org/pdf/1502.05698v6.pdf This recent paper is an algorithm to solve simple question answering from the context of a conversation... like the ones in the older paper... for instance. John is in the playground. Bob is in the office. Where is John? A:playground I believe a traditional LSTM RNN would have likely cleared the information about John from from it's long short term memory vector. Whereas you would still have access to the information about John in a stack. fta: "Since the machine can essentially learn how to operate its memory, it can learn how to program itself by producing sequences of instructions."

cs702 11y ago
I have shivers going down my spine at the idea of feeding, say, skip-thought vectors representing sentences[1] into stack-augmented recurrent neural nets as proposed in Facebook's paper[2], for all sorts of interesting tasks. -- [1] http://arxiv.org/pdf/1506.06726v1.pdf http://arxiv.org/pdf/1506.06726v1.pdf [2] http://arxiv.org/pdf/1503.01007.pdf http://arxiv.org/pdf/1503.01007.pdf
Smerity 11y ago
If people are interested in playing with the dataset from "Towards AI-Complete Question Answering: A Set of Prerequisite Toy Tasks", I added an example to Keras that uses recurrent neural networks[1]. It achieves similar accuracy to the baseline LSTM approach in the paper. I also did a write-up that explains the task and architecture[2]. The dataset (bAbi tasks[3]) released by Facebook is interesting but has a number of limitations. The code used to produce it is also not open source. If someone has the interest and/or past experience in MUD style environments, creating an open source dataset would be amazing! [1]: https://github.com/fchollet/keras/blob/master/examples/babi_rnn.py https://github.com/fchollet/keras/blob/master/examples/babi_... [2]: http://smerity.com/articles/2015/keras_qa.html http://smerity.com/articles/2015/keras_qa.html [3]: https://research.facebook.com/researchers/1543934539189348 https://research.facebook.com/researchers/1543934539189348

skybrian 11y ago

I wonder if this sort of thing would be useful in american fuzzy lop? (It already uses genetic algorithms.)