Inferring Algorithmic Patterns with Stack-Augmented Recurrent Nets
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.
The authors motivate the study of problems that are generated from algorithms, as the next step in learning algorithms that goes beyond just learning of statistical regularities. The authors propose a recurrent model that uses augmented memory that is independent from the computational model itself. Specifically, the authors use RNNs (and LSTM-RNNs) to control a memory store through soft PUSH/POP actions (for stacks) (or soft INSERT/LEFT/RIGHT for doubly linked lists). The current contents of memory stores themselves are used to compute the hidden states of the RNNs, along with data and past hidden states. At each step the RNN first computes the hidden state using the memory stores and the inputs and the past hidden state. From this hidden state the next step action is generated, which is then used, along with the hidden state to update the memory store at the next time step.Learning is done with SGD and a strategy that amounts to beam searching on actions. Results presented on toy problems show that indeed the method can perform better than RNNs and LSTMs. Results on the Penn Tree bank task on the other hand are worse than LSTMs. My comments on the paper follow in somewhat of a random order: Some of the results are curious and unintuitive. For example the LIST RNN gets 100% on the anbncndn task but worse on the easier task of anbncn. Also anbmc(n+m) does worse then anbncndn task on Stack RNN 40+10, even though the latter are generally longer and possibly more complicated. Is this probably just a relic of the difficulty of training this models and the stochasticity in the optimization procedure described in the supplementary materials ? Thepaper does try to control overfitting on Penn Tree bank task carefully, as can be seen from the results, which are much worse than the best results on this task by Vinyals et al. As such it does disservice to the exploration of the method itself, since its not clear if its actually performing worse than LSTMs or is just overfitting more. I wish that the optimization procedure was described in the paper itself, not shuffled off to the appendix since it is a crucial part of the paper. It is not clear to me if the extra memory that is provided actually serves as anything other than extra computation, since memory is read /write and can be used only for the current problem. When a new instance of a problem is encountered, the memory is reset. This would be different from a model that could separate algorithms from data needed to solve a problem. I was looking to see if the stacks had a size to them.. I would expect in practical implementation where the authors blend the stack contents from one time to the next, there would a certain size of the stack that's stored ? Is it perhaps tied to the number of time steps ? Small note: Is the equation for linked lists updates correct ? I would have expected that insert would add an element at i, and for i < HEAD all the elements would be unchanged and copied from the last time step, whereas for i > HEAD things would be copied from i-1 elements of the last time step.. Perhaps insert is defined slightly different here, or I'm mistaken..