Venue: ICLR 2022 Conference

Reviews:

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: This paper aims to improve the performance of the Nondeterministic Stack RNN (NS-RNN) using unnormalized positive weights instead of probabilities for stack actions and allowing the model to directly observe the state.

The paper also uses the new NS-RNN for a language modelling task on the Penn Treebank by introducing a memory-limiting technique.
main_review: Strengths
- The discussion on previous stack RNNs was a strong segment of the paper as the authors connect the various approaches using common notation. 
- The modifications to the NS-RNN are well motivated by appealing to toy problems or an explanation of what happens numerically during training. 
- Transitioning the discussion from formal languages to natural languages was a good motivation for introducing the memory-limited technique. Good use of SG score metric instead of just perplexity.

Weaknesses
- It would have been good to explain what Hardest CFL (Greibach, 1973) is in the paper. **[addressed by author response and paper update]**
- I might be missing something, but what is the intuition behind the choice of $Q$ or $\Gamma$ for the models in Table 1? **[addressed by author response and paper update]**
summary_of_the_review: Overall, I think this work is marginally above the acceptance threshold. The improvements made to NS-RNN are well-motivated. While this may seem to be incremental, I think the contribution of the memory-limiting approach enhances the paper's relevance by allowing for language modeling over natural language.
review_title: null

final_score: rating: 8: accept, good paper
review_content: summary_of_the_paper: This work continues a recent work on nondeterministic stack RNNs (in which an RNN controls a nondeterministic pushdown automaton, which I will refer to here as an N-PDA), proposing two changes to the architecture which create an RNS-RNN (renormalised NS-RNN) as follows:
1. Where in the NS-RNN the RNN-controller outputs a set of distributions over the next possible PDA actions (one distribution for every current state and stack-top pair), the RNS-RNN outputs scores over these actions. This is achieved simply by not softmaxing the scores that are anyway computed in the NS-RNN. The goal/effect is that the score of each (current state,current stack) pair being maintained in the N-PDA does not tend to zero as the input sequence length increases (as it would when probabilities are used), and in fact can even be increased at certain transitions.
2. Where in the NS-RNN the RNN-controller receives as part of its input at each time step a distribution over the current stack top token, it now also receives a distribution over the current PDA state. (These are normalised back to distributions here, normalised from the scores kept in the N-PDA.)

The authors evaluate the RNS-RNN against the NS-RNN and several other architectures, showing its success on various formal languages and even a greater success on a "hardest" context free grammar. 

The NS-RNN requires quadratic space and cubic time in the input sequence length*, which is impractical for natural language processing. The authors propose a memory-limited version which reduces the complexity to linear time and space in the input sequence length, and discuss truncated BPTT for this version. They evaluate a memory limited RNS-RNN on the Penn Treebank. 

*Because it is maintaining the probabilities of all possible configurations of non-deterministic PDA on the current input---in fact we are lucky this is not exponential! A dynamic algorithm by Lang is used to maintain the PDA, I am not sure of the details

main_review: =quick pros=
- proposed changes are simple, clear, and appear to improve the model on some synthetic tasks (even significantly for one of them).

=quick cons=
- the model does not seem very good on natural language tasks. However, if my understanding of stack-rnn research is correct, this is to be expected.

=full review=

Note: I have reviewed this paper before, and appreciate that the authors have added experiments and metrics as requested. 

I am adding some presentation comments, some of which are new, and some of which I think are important (even if they are minor), please take a look through them! Note: I recognise you responded to some of these questions in the previous review round, but I would like them answered in the paper too! :)

==some comments==

1. I find the first change ((1) in the summary) interesting, if simple, and the second ((2) in the summary) a little odd: intuitively, because the RNN outputs a next-move distribution for *every* current top-token and current-state pair, why would it need to know what the current one *actually* is? I am glad that you evaluated each change independently as well as together, and so I can be convinced that the change is necessary (e.g. through the results on unmarked reversal), but still I do not fully understand it.  I would appreciate a greater discussion of *why* this change is good here - why does it help despite my intuition? (The explanation of section 3.2 is not working for me: following my intuition here, I still don't see the importance of the state-read.)

2. It is not clear what the SG score adds to the discussion, or what I should conclude from it, if at all. It would help to add a definition of the SG score to the paper (as done for cross entropy), or at least some greater discussion if this is not possible, and provide some intuition on what it means.

3 (important!). I appreciate that the authors have been very explicit in all of their constructions and all details of their experiments, I find this very valuable. However, I would also like to note that as someone not familiar with the NS-RNN, I do struggle with the formulas. In particular in equation 2 I would like some more explanation on the [i->t] inputs - it seems there are jumps over several time steps?? This is a very confusing point that could do with some plain-english explanation. 

(3b. Maybe personal preference: Another thing to note in this direction is that the last paragraph of the introduction describes the RNS-RNN according to how it differs from the NS-RNN, but for anyone who is not already familiar with the NS-RNN, it is not useful. If possible, I think adding another paragraph that more deeply explains---in non-technical terms (i.e., no formulas)---what exactly an NS-RNN is doing would be very helpful. (Approximately, though will need rephrasing: defining and maintaining a distribution over all possible configurations of a non-deterministic PDA, by computing at each step: for each state and stack-top combination, a distribution over all possible next-state and stack-actions. And from this, each configuration's probability is the sum of the products of each sequence of transitions and state-actions that get to that configuration). )

4. In figure 3, it would be nice to also see this plot for NS, JM, Gref, and NS+U! Maybe in the appendix at least?

5. Section 4, paragraph after Hardest CFL: "...hardest CFL requiring the most." I don't understand what this means - what does it mean for one non-deterministic language to require "more" non-determinism than another?

==some questions==
1. In unmarked reversal, it is interesting to note that each of the changes alone seems to barely improve on the NS-RNN, but that together they improve the model significantly. Could you add a discussion, sharing any intuition on why this is? (Section 3.2 is not enough - at that point I still do not feel I understand why the second change is needed, as noted above in my review).

2. In figure 3, there is a white line in the middle of the image for both models, suggesting that it is not learning the correct action at the point where the reversing 'begins'. Could you add some discussion explaining this?

3. Can you explain the intuition behind adding the EOS tokens to the end of each sample (as opposed to the experiments in the original NS-RNN paper)? I understand that it makes the model define a proper distribution (as opposed to weights) over the sequences, but I don't understand why this is important for these evaluations. (Is predicting the EOS hard for any of these tasks, or something like that? I see that you comment that it makes things harder for the baseline NS, do you have ideas on why?)


==typos, presentation, minor comments==
1. Section 2.3 (superposition) is hard to understand, an analogy (similar to cake for stratification) could help. If one is not available, at least a concrete example, e.g., what happens if I have a stack of depth 5 and push/pop/noop with probabilities 0.3/0.5/0.2 ?
2. Section 2.4, second paragraph, the description of the possible operations: the paragraph says that it is showing Op(Gamma), but it seems you are showing Q \times Op(Gamma). Consider removing the "r"'s from each operation, or introducing the list as Q\times Op(Gamma).
3. Formal languages results: Can you explain the higher difference in cross entropy, for all models and languages, on the shorter (but in train range) sequences? 

summary_of_the_review: This paper makes straightforward (this is good) changes to an existing stack-augmented RNN model, the NS-RNN, evaluating the new model on some formal languages and even one natural language dataset. The improvements are modest (and on the natural language dataset, unclear), but sufficient to be of interest. The paper is well written, though it could do with some expansions and clarifications as elaborated in the main review.
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: The paper proposes a new stack-augmented RNN, RNS-RNN that includes two modifications to the Nondeterministic Stack RNN:
1. RNS-RNN uses unnormalized transition weights to avoid probability vanishing problems, such that gradient can be easier backpropagated to certain decisions at a previous time step.
2. RNS-RNN feeds the hidden state y into the controller while reading the stack, this allows the controller has more complete information to make decisions.
main_review: The proposed method solves two defects of NS-RNN. The ideas are technically sound and empirically proved.
However, I have several concerns:
1. The RNS-RNN is based on a weighted PDA, which has a finite set of states. This setting limits the capacity and expressiveness of the proposed model, especially when modern deep learning methods usually use very large hidden states to achieve high expressiveness.
2. The RNS-RNN achieves a marginally better result on PTB language modeling task while comparing to NS-RNN, but still falling far behind any strong baselines. 
3. The formal language tasks are toyish. It would be interesting to test the proposed method on less toyish formal language tasks, for example, logical inference (Bowman et al., 2015) and ListOps (Nangia and Bowman, 2018).

Missing reference:
- Shen, Yikang, et al. "Ordered Memory." Advances in Neural Information Processing Systems 32 (2019): 5037-5048.
summary_of_the_review: Overall the paper proposed useful improvements to the NS-RNN. However, the novelty and impact of this paper are not significant enough.
review_title: null

final_score: rating: 8: accept, good paper
review_content: summary_of_the_paper: This work presents various improvements over the differentiable non-deterministic push-down automaton. Basic idea of non-deterministic push-down automaton is to explore all the space for state id with stack with push/replace/pop operators with dynamic programming. Given the prior work of DuSell & Chiang (2020), this work has three contributions:

- Do not normalize for transition, which is similar to migrating from maximum entropy Markov model to conditional random filed, so that the model is not biased by local transitions, but globally normalilzed.

- Consider the joint distribution of stack symbol and state, not only stack symbol, so that the controller can differentiate by the current state of the PDA.

- The model is not space efficient in that the stack is unbound, and thus, consumes large memory. This work proposes to limit the stack memory so that the model can run on the real World data, e.g., PTB.

Experimental results on synthetic data show large improvement in terms of per-symbol cross-entropy. The perplexities on PTB do not achieve better results when compared with other simpler variants or LSTM. However, the scores on Syntactic Generalization show some gains.
main_review: # Strength

- It is a very interesting work on differentiable non-deterministic PDA in terms of the theoretical view point. Although the gains are not large and computationally demanding, the proposed enhancements over prior work are very interesting in that they allow its application to the real World data, i.e., PTB.

# Weakness

- The gains are not large, but meaningful improvements are observed in the synthetic data set and the gains in SG scores would be good enough, I believe.

- I feel the bound for stack could be treated as one of the contribution of this work. I'd suggest moving the description of section 5.1 into section 3 to emphasize the nice contribution.

- I'd like to see further analysis to indicate whether the proposed model could learn hierarchical structures as indicated in the title under PTB. Probably manual assessments would be good enough to show some evidence.
summary_of_the_review: The proposed method is sound and the experiments are designed nicely to prove the improvements of this work. Although the gains are not significant, I'd rather like to see this paper accepted given that it is an interesting contribution to computational linguistics, and might have an impact in the future.
review_title: null

Meta-review: This paper advances the long running thread of sequence modelling research focussed on differentiable instantiations of stack based models. In particular it builds upon recent work on the Nondeterministic Stack RNN (NS-RNN) by introducing three extensions. The first is to relax the need for a normalised distribution over the state and action distribution and allow unnormalised weights, this mostly serves to facilitate gradient flow and thus easier training. The second extension allows the RNN to condition on the top stack state as well as the symbol, improving expressiveness. The third improvement introduces a method for limiting the memory required to run the proposed model on long sequences, thus allowing its application to practical language modelling tasks. Each of these requires substantial algorithmic innovations.

The reviewers all agree that this is a strong paper worthy of publication. The paper includes a useful review of previous differentiable stack models which nicely sets up the rest of the paper where the contributions are well motivated and clearly presented. The reviewers had a number of clarification questions, partly due to the author's use of overly concise citations for key algorithms rather than inline descriptions. This situation has been improved by updates made to the paper.
The evaluation includes a series of synthetic experiments which are clear and provide a good elucidation of the various stack models properties. The practical evaluation on language modelling is more limited and serves mostly to demonstrate that the nondeterministic model can be scaled to a basic language modelling task.

Overall this is a strong paper with a well motivated and clear hypothesis. It provides a substantial extension to the prior work on nondeterministic stack models and progresses this line of research toward practical applications.
Decision: Accept (Spotlight)