Inferring Algorithmic Patterns with Stack | Hacker News Reader

Inferring Algorithmic Patterns with Stack

research.facebook.com

113 pointsantman33 comments

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

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."

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

[2] http://arxiv.org/pdf/1503.01007.pdf

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_...

[2]: http://smerity.com/articles/2015/keras_qa.html

[3]: https://research.facebook.com/researchers/1543934539189348

Oh!! This is something I must try.

I remember you've mentioned issues with the bAbi question set previously. Have you (or anyone else) tried using the same approach on a non-artificial dataset?

I'm thinking something like blending this with the approach Richard Socher used on the Quizbowl code[1].

[1] http://cs.umd.edu/~miyyer/qblearn/

I also like this vaguely related paper from one of the ex-IBM-Watson team members: http://arxiv.org/abs/1508.06924

"Using Thought-Provoking Children's Questions to Drive Artificial Intelligence Research"

Weston uses Memory Networks[1] to mostly solve this set of tasks. Some researches out of Huawei and I think Hong Kong University had some recent success using a different technique on the tasks memory networks failed at[2].

[1] http://arxiv.org/abs/1506.02075

[2] http://arxiv.org/abs/1508.05508

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.

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.

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.

With sgd you only know a locally better solution. GP has this as well: take the best current instance and mutate it/recombine it.

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

GP has operators operating on a multidimensional input. GP builds simple programs, GP is good enough for the task, you could discover the same function that SGD discovers, but unfortunately in practice they are too slow, because they are blind to the landscape of the function.

It doesn't have anything to do with GPUs. Genetic programming simply does not actually work for solving any nontrivial problem, in particular it does not work significantly better (and oftentimes worse) than brute force search.

Well, finding stable lifeforms is a nontrivial problem, assuming GP is somewhat faithful to biological evolution.

That's definitely the best problem ever solved by GP, though given the unfathomably enormous computational resources poured into it, it's still hard to say it was any better than a brute force approach! ;)

It's almost definitely better than brute force. The number of possible sequences of dna of size n base pairs is exponential in n.

The earth has only existed ~1e9 years. Assuming some finite average number of "computational ops per year", the number of possible dna strands quickly exceeds the total computational capacity of the planet since its birth.

Evolution is not trying to find one particular DNA string out of that exponentially sized set. There are lots of members of that set that are viable organisms.

In any case this is beside the point. The fact remains that genetic programming is a class of algorithms that has not been succesful in the slightest. People should just stop talking about it as if it was anything other than a complete failure, since that will only lead to even more wasted human effort. Gradient descent on the other hand is hugely succesful in solving a wide variety of real problems.

Im not advocating GP > nn+grad. I'm just saying nobody knows why nn+grad performs better on practical problems. Also nn+grad methods were essentially complete failures for the first 3-4 decades of their existence (invented in 60s, legit results like Lecun or Hinton in like 90s/00s).

This is so wrong at so many levels (sadly quite characteristic of the GA crowd) that I can only suggest reading up on the background and the math of it. Good keywords would be stochastic gradient descent, spin glasses and renormalization groups.

Whether nns have an interpretation as spin systems is completely nonresponsive to the hardness of training them. Ie minimizing "free energy" in spin systems is as NP-hard as minimizing training error in nns.

FAIRie here. GA is essentially guess-and-check. SGD doesn't require guess or even check; if your error function is differentiable, and you didn't screw up the chain rule, you know what direction to head in to make it go down. For large models with lots of parameters, finding a setting for each parameter that makes the model as a whole go down by random choice has complexity n * f(n) for some monotonically increasing f, while SGD really finds you your next model, with decent guarantees it will be better, in O(n) time.

The theoretical hand-wringing about SGD for neural nets is that their loss surface isn't convex. It turns out this doesn't matter. The loss surface is a high-dimensional egg-carton, and you need to get winning-the-lottery-while-struck-by-lightning unlucky to find a significantly shallow local minimum. There are lots of saddle points, and you need to do something to drive out of those, but stochasticity seems sufficient in practice.

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

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.

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/

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

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

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).

"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

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

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

https://github.com/facebook/Stack-RNN

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/

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.

They are probably using M to get more data to learn from.

Reply on news.ycombinator.com