Venue: ICLR 2017 conference

Reviews:

final_score: rating: 7: Good paper, accept
review_content: Neural Programmer-Interpreters (NPI) achieves greatly reduced sample complexity and better generalization than flat seq2seq models for program induction, but requires program traces at multiple levels of abstraction for training, which is a very strong form of supervision. One obvious way to improve this situation, addressed in this work, is to only train on the lowest-level traces, with a latent compositional program structure. This makes sense because the "raw" low-level traces can be cheaply gathered in many cases just by watching expert demonstrations, without being explicitly told the more temporally abstract structures.

This paper shows that a variant of NPI, named NPL, can achieve even better generalization performance with weaker supervision (mostly flat traces), and also extends the model to a new grid world task. Unfortunately, it still requires being told the overall program structure by being given a few *full* execution traces. Still, I see this as important progress. It extends NPI in a quite nontrivial way by introducing a stack mechanism modeling the latent program call structure, which makes the training process much more closely match what the model does at test time. The results tell us that flat execution traces can take us almost all the way toward learning compositional programs from demonstrations - the hard part is of course learning to actually discover the subprogram structure.
review_title: Progress in reducing the supervision required by NPI

final_score: rating: 4: Ok but not good enough - rejection
review_content: First I would like to apologize for the late review.

This paper proposes an extension of the NPI model (Reed & de Freitas) by using an extension of the probabilistic stacks introduced in Mikolov et al.. This allows them to train their model with less supervision than Reed & de Freitas. 

Overall the model is a nice extension of NPI. While it requires less supervision than NPI, it still requires "sequences of elementary operations paired with environment observations, and [...] a couple of examples which include the full abstraction hierarchy". This may limit the scope of this work.

The paper claims that their "method is leverages stronger supervision in the form of elementary action sequences rather than just input-output examples (sic).  Such sequences are relatively easy to gather in many natural settings". It would be great if the authors clarify what they mean by "relatively easy to gather in many natural settings". They also claim that "the additional supervision improves the data efficiency and allow our technique to scale to more complicated problems". However, this paper only addresses two toy problems which are neither "natural settings" nor of a large scale (or at least not larger than those addressed in the related literature, see Zaremba et al. for addition). 

In the introduction, the author states that "Existing techniques, however, cannot be applied on data like this because it does not contain the abstraction hierarchy." What are the "existing techniques", they are referring to? This work only addresses the problem of long addition and puzzle solving in a block world. Afaik, Zaremba et al. has shown that with no supervision, it can solve the long addition problem and Sukhbaatar et al. ("Mazebase: A sandbox for learning from games") shows that a memory network can solve puzzles in a blockworld with little supervision.

In the conclusion,  the author states that "remarkably, NPL achieves state-of-the-art performances with much less supervision compared to existing models, making itself more applicable to real-world applications where full program traces are hard to get." However for all the experiments, they "include a small number of FULL samples" (FULL == "samples with full program traces"). Unfortunately even if this means that they need less FULL examples, they still need "full program traces", contradicting their final claim. Moreover, as shown figure 7, their model does not use a "small number of FULL samples" but rather a significantly smaller amount of FULL examples than NPI, i.e., 16 vs 128. 

"All experiments were run with 10 different random seeds": does the environment change as well between the runs, i.e. are the FULL examples different between the runs? If it is the case and since you select the best run (on a validation set), the NPL model does not consume 16 FULL examples but 160 FULL examples for nanoCraft. 

Concerning the NanoCraft example, it would be good to have more details about how the examples are generated: how do you make sure that the train/val/test sets are different? How the rectangular shape are generated? If I consider all possible rectangles in a 6x6 grid, there are (6x6)x(6x6)/2 = 648 possibilities, thus taking 256 examples sum up to ~40% of the total number of rectangles. This does not even account for the fact that from an initial state, many rectangles can be made, making my estimate probably lower than the real coverage of examples.

Concerning the addition, it would interesting to show what an LSTM would do: Take a 2 layer LSTM that takes the 2 current digits as an input and produce the current output ( "123+45" would be input[0] = [3,5], input[1]=[2,4], input[2]=[1, 0] and output[0] = 8...). I would be curious to see how such baseline would work. It can be trained on input/output and it is barely different from a standard sequence model. Also, would it be possible to compare with Zaremba et al.?

Finally, as discussed previously with the authors, it would be good if they discuss more in length the relation between their probabilistic stacks and Mikolov et al.. They have a lot of similarities and it is not addressed in the current version. It should be addressed in the section describing the approach. I believe the authors agreed on this and I will wait for the updated version.

Overall, it is a nice extension of Reed & de Freitas, but I'm a bit surprised by the lack of discussion about the rest of the literature (beside Reed & de Freitas, most previous work are only lightly discussed in the related work). This would have been fine if this paper would not suffer from a relatively weak experiment section that does not support the claims made in this work or show results that were not obtained by others before. 

Missing references:
"Learning simple arithmetic procedures", Cottrell et al.
"Neural gpus learn algorithms", Kaiser & Sutskever
"Mazebase: A sandbox for learning from games", Sukhbaatar et al.
"Learning simple algorithms from examples", Zaremba et al.


review_title: Review

final_score: rating: null
review_content: In the introduction, the paper mentions an example of abstracting human tasks from Kinect skeletons. However, it is difficult to easily imagine how the proposed approach can learn the model from such noisy observations possibly having multiple variations. We would like to see more clarifications/discussions on this.
review_title: noisy observations

final_score: rating: null
review_content: The stack in this work resembles the one proposed by Mikolov et al (https://arxiv.org/abs/1503.01007). Was there a particular requirement that led to the choice of this type of stack, versus other neural stack/queue models, e.g. https://arxiv.org/abs/1506.02516?
review_title: Choice of neural stack

final_score: rating: 7: Good paper, accept
review_content: The paper presents the Neural Program Lattice (NPL), extending the previous Neural Programmer-Interpreters (NPI). The main idea is to generalize stack manipulation of NPI by making it probabilistic. This allows the content of the stack to be stochastic than deterministic, and the paper describes the feed-forward steps of NPL's program inference similar to the NPI formulation. A new objective function is provided to train the model that maximizes the probability of NPL model correctly predicting operation sequences, from execution traces. We believe this is an important extension. The experimental results illustrate that the NPL is able to learn task executions in a clean setting with perfect observations.

The paper is clearly presented and its background literature (i.e., NPI) is well covered. We also believe the paper is presenting a conceptually/technically meaningful extension of NPI, which will be of interest to a broad audience. We are still a bit concerned whether the NPL would be directly applicable for noisy observations (e.g., human skeletons) in a continuous space with less explicit structure, so more discussions will be interesting.

review_title: well formulated paper

Meta-review: This paper demonstrates a novel (although somewhat obvious) extension to NPI, namely moving away from training exclusively on full traces (in order to model the nested calling of subprograms) to training, in part on low-level program traces. By exploiting a continuous stack in the vein of Das et al. 1992, Joulin and Mikolov 2015, or Grefenstette et al. 2015 (any of which could plausibly have been used here, by my reading, contrary to claims made by the authors in discussion), they can model nested calls with a stack-like structure which needs only partial supervision of a few full traces. The claim is that the resulting model is more sample efficient than the NPI of Reed and de Freitas.
 
 The reviews are mixed. R1 is grumpy about citations, which I see as grounds for rejection, but raises the point that the claims to data efficiency may be overblown since it is only shown that few full traces are needed to train the model, not that it can infer structure without full traces, which would be more impressive. Confusingly, they refer to continuous stacks as probabilistic, which is misleading as while there is (in all variants mentioned above) a possible probabilistic interpretation of non-{0, 1} push/pop operations, the updates to the stack state are deterministic, as are all other aspects of the network except test-time sampling of actions from the multivariate distribution induced by the softmax on output.
 
 R2 has not understood the paper or background material if they mistakenly believe that the stack-like structure and resulting model are probabilistic, as there is no sampling of actions on the stack, but only deterministic state updates. The superficiality of the review combined with the fairly crucial misunderstanding sadly means I cannot rely on it to make a recommendation.
 
 R3 is broadly sympathetic to the paper, while recognising that it still requires information about the program structure through partial FULL supervision in order to learn to manipulate the continuous stack (and thus nested function calls). It is disappointing that the authors did not reply to this point in this review. I acknowledge that they address this claim in part in a response to R1, but the reply is mostly that they will rewrite the formulation of their claims.
 
 Overall, the novelty of this paper lies in the integration of an existing flavour of differentiable data structure, variants of which have recently been presented at NIPS in 2015, into NPI in order to learn program structure. This would have made for an excellent paper if this augmentation had shown that, without partial supervision on the stack operations (thus training solely from low level traces) the model had been able to infer program structures. The need to provide some full traces is disappointing in this respect, although the claim about providing a more data-efficient training regime thanks to the data structure is plausible. 

Stil, overall, the PCs encourage the authors to address the remainig issues in the camera reasy version of their paper and to present this as a poster at the main conference.
Decision: Accept (Poster)