Learning Hierarchical Structures with Differentiable Nondeterministic Stacks
Authors: Brian DuSell
David Chiang
Venue: ICLR 2022 Spotlight (2022)
Keywords: RNN
pushdown automata
nondeterminism
formal languages
language modeling

Abstract: Learning hierarchical structures in sequential data -- from simple algorithmic patterns to natural language -- in a reliable, generalizable way remains a challenging problem for neural language models. Past work has shown that recurrent neural networks (RNNs) struggle to generalize on held-out algorithmic or syntactic patterns without supervision or some inductive bias. To remedy this, many papers have explored augmenting RNNs with various differentiable stacks, by analogy with finite automata and pushdown automata (PDAs). In this paper, we improve the performance of our recently proposed Nondeterministic Stack RNN (NS-RNN), which uses a differentiable data structure that simulates a nondeterministic PDA, with two important changes. First, the model now assigns unnormalized positive weights instead of probabilities to stack actions, and we provide an analysis of why this improves training. Second, the model can directly observe the state of the underlying PDA. Our model achieves lower cross-entropy than all previous stack RNNs on five context-free language modeling tasks (within 0.05 nats of the information-theoretic lower bound), including a task on which the NS-RNN previously failed to outperform a deterministic stack RNN baseline. Finally, we propose a restricted version of the NS-RNN that incrementally processes infinitely long sequences, and we present language modeling results on the Penn Treebank.

Published as a conference paper at ICLR 2022
LEARNING HIERARCHICAL STRUCTURES WITH DIFFERENTIABLE NONDETERMINISTIC STACKS
Brian DuSell and David Chiang
Department of Computer Science and Engineering, University of Notre Dame (bdusell1, d,hii annhainn) edu
ABSTRACT
Learning hierarchical structures sequential data- from simple algorithmic patterns to natural language-in a reliable, generalizable way remains a challenging problem for neural language models. Past work has shown that recurrent neural networks (RNNs) struggle generalize on held-out algorithmic syntactic patterns without supervision or some inductive bias. To remedy this, many papers have explored augmenting RNNs with various differentiable stacks, by analogy with finite automata and pushdown automata (PDAs). In this paper, we improve the performance of recently proposed Nondeterministic Stack RNN (NS-RNN), which uses a differentiable data structure that simulates a nondeterministic PDA, with two important changes. First, the model now assigns unnormalized positive weights instead of probabilities to stack actions, and we provide an analysis of why this improves training. Second, the model can directly observe the state of the underlying PDA. Our model achieves lower cross-entropy than all previous stack RNÑs on five context-free language modeling tasks (within 0.05 nats of the information-theoreet lower bound), including a task which the NS-RNN previously failed to outperform a deterministic stack RNN baseline. Finally, we propose restricted version of the NS-RNN that incrementally processes infinitely long sequences, and we present language modeling results on the Penn Treebank.
INTRODUCTION
Many machine learning problems involve sequential data with hierarchical structures, such as modeling context-free languages (Grefenstette et al., 2015; DuSell & Chiang. 2020), evaluating mathematical expressions (Nangia & Bowman, 2018; Hao et al., 2018), logical inference (Bowman et al., 2015), and modeling syntax in natural language (Dyer et al., 2016; Shen et al., 2019b; Kim et al., 2019). However, recurrent neural networks (RNNs) have difficulty learning to solve these tasks, or generalizing to held-out sequences, unless they have supervision et al., 2019; Wilcox et al., 2019; McCoy et al., 2020). A limiting factor of RNNs is their reliance on memory whose size is constant across time. For example, predict the second half of string of the form R a simple RNN would need to store all of w in its hidden state before predicting its reversal wR, memory of finite size will inevitably fail do this for inputs exceeding certain length.
hierarchical inductive bias (van Schijndel
To remedy this, some previous work has investigated the addition of differentiable stack data structures RNNs (Sun al., 1995; Grefenstette et al., 2015; Joulin & Mikolov, 2015; DuSell & Chiang, 2020), which is closely related to work on neural networks that model shift-reduce parsers (Bowman al., 2016; Dyer al., 2016; Shen al., 2019a). Just as adding stack to a finite state machine, which makes it a pushdown automaton (PDA), enables it to recognize context- free languages (CFLs), the hope is that adding stacks RNNs will increase the range of problems on which they can be used effectively. We also expect stacks to aid training by introducing an inductive bias for learning hierarchical patterns, and to increase generalization power by structuring the model's memory in a way that better predicts held-out hierarchical data.
Previously (DuSell & Chiang, 2020), we proposed a stack- based RNN called the Nondeterministic Stack RNN (NS-RNN) that outperformed other stack RNNs range of CFL language modeling tasks. Its defining feature is that its external data structure is a nondeterministic PDA, allowing it to simulate exponential number of sequences of stack operations in parallel. This is in contrast prior

---

Published as a conference paper at ICLR 2022
stack RNNs (Grefenstette et al., 2015; Joulin & Mikolov, 2015) which model deterministic stacks, being designed to learn one correct stack operation at each time step. One reason nondeterminism is important is that deterministic CFLs are proper subset of CFLs. If the analogy with PDAs holds true, then equipping an RNN with a deterministic stack would only enable it to model deterministic CFLss, whereas nondeterministic stack should enable it to model all CFLss. This is important for natural language processing, as human language is known to be high in syntactic ambiguity.
Another benefit of nondeterminism, even on deterministic CFLs, applies to training. In order for model to receive a reward for an action, it must try the action (that is, give it nonzero probability so that it receives gradient during backpropagation). For example, in the digit-recognition task, classifier tries all ten digits, and is rewarded for the correct one. But in stack slack-augmented model, the space of possible action sequences very large. Whereas a deterministic stack can only try one of them, nondeterministic stack can try all of them and always receives a reward for the correct one. But as explained $3.1, because the NS-RNN's ' probability for an action sequence the product of many probabilities, it can be extremely small, so the NS-RNN sometimes learns very slowly.
In this paper we present new model, the Renormalizing NS-RNN (RNS-RNN), which is based on the NS-RNN, but improves its performance on all of the CFL tasks it was originally tested on, thanks to two key changes. The first is that stack actions have weights that do not necessarily form a probability distribution ($3.1). They define unnormalized distribution over stacks that is renormalized whenever the model queries it. Second, the RNS-RNN includes not only top stack symbols but also PDA states in this query ($3.2). These changes allow the RNS-RNN to attain lower cross-entropy on CFL tasks (in fact, very close to the informationnthhorrele lower bound) and to surpass deterministic stack RNNs on a task on which the NS-RNN fails do ("padded reversal"). Finally, as a third modification, we present a memory-restricted version of the RNS-RNN that requires only (n) time and space ($5). This restricted RNS-RNN -NNN can be run incrementally on arbitrarily long sequences. which is necessity for language modeling on natural language, for which we provide experimental results. Our code is available at https: /ttpt/ggtttbbbtt com cowm///uuslll/oodeeeemmmim stissstiiceeeeeess stack-rnn rnn.
PREVIOUS STACK RNNs
We begin by discussing three previously proposed stack RNNs, each of which uses different style of differentiable stack: stratification (Das et al., 1992; Sun et al., 1995; Grefenstette et al., 2015), superposition (Joulin & Mikolov, 2015), and nondeterminism (DuSell & Chiang, 2020).
2.1
FONTROILER-SSAACK INTERFACE
Each type of stack RNN consists of simple RNN (or variant such as LSTM), called the controller, connected to a differentiable stack. The stack has no parameters of its own: its role accept actions from the controller to push and pop elements at each time step, simulate those actions, and return a reading to the controller as an extra input to the next time step that serves as a representation of the updated top element of the stack. The stack actions and stack reading take on continuous values so that they may be differentiable; their form and interpretation vary with architecture.
Following prior work (DuSell & Chiang, 2020), we make minor changes to the original model definitions given by Grefenstette et al. (2015) and Joulin & Mikolov (2015) to ensure that three of these stack RNN models conform to the same controller-stack interface. This allows to isolate differences in the style of stack data structure employed while keeping other parts of the network the same. We assume the input w W .... W,, is encoded a sequence of vectors xI, X,, In all of our experiments, we use an LSTM (Hochreiter & Schmidhuber, 1997) as the controller, whose memory consists of hidden state h, and memory cell e,. The controller computes the next state (h,, c,) given the previous state (h,-1, 1,,,,, input vector X,, and stack reading r₁-
(h,, c,) = LSTM (h.-1.c--),,
r1-1
We set ho Co- O. The hidden state is used to compute the stack actions a, and predict the logits y, for the next word Wr+1. The previous stack and new actions are used to compute a new stack sy, which in turn is used to produce new reading r,:
a, ACTIONs(h.)
y, Whyh, bay
s, STACK(S
r, READING(S,)
2

---

Published as a conference paper at ICLR 2022
In order to change the stack data structure, we need only change the definitions of ACTIONS, STACK, READING, and 5o. which may depend on parameters of the model; for our changes to the NS-RNN, we will only need to change ACTIONS and READING.
2.2 STRATIFICATION
Based on work by Das et al. (1992) and Sun et al. (1995), the stack of Grefenstette et al. (2015) relies on a strategy we have dubbed "stratification" (DuSell & Chiang, 2020). The elements of the stack are vectors, each of which is associated with a "thickness" between 0 and 1, which represents the degree which the vector element is present on the stack. A helpful analogy is that of layers of cake; the stack elements are like cake layers of varying thickness. In this model, d₁ = (4₁, dy. Vr), where the pop signal u, (0, 1) indicates the amount be removed from the top of the stack, V, a learned vector to be pushed as new element onto the stack, and the push signal d, E (0, 1) is the thickness of that newly pushed vector. This model has quadratic time and space complexity with respect to input length. We refer the reader to Appendix A.1 for full details.
2.3 SUPERPOSITION
The stack of Joulin & Mikolov (2015) simulates a combination of partial stack actions by computing three new, separate stacks: one with all cells shifted down (push), kept the same (no-op), and shifted up (pop). The new stack is then an element wise interpolation ("superposition") of these three stacks. In this model, stack elements are again vectors, and a, (a, ve), where the vector a, a probability distribution over three stack operations: push new vector, no-op, and pop the top vector; V, is the vector be pushed. The vector v, can be learned can be set to h, (Yogatama et al., 2018). The stack reading is the top cell of the stack. This model has quadratic time and space complexity with respect input length. We refer the reader Appendix A.2 for full details.
2.4 NONDETERMINISM
The stack module in the Nondeterministic Stack RNN (NS-RNN) model (DuSell & Chiang, 2020) maintains a probability distribution over whole stacks by simulating weighted PDA. has cubic time complexity and quadratic space complexity with respect to input length, leading to higher wall-clock run time than other stack RNNs, but often better task performance.
The simulated weighted PDA maintains state drawn from finite set Q. which includes initial state qo, and a stack with symbols drawn from an alphabet I,, which includes an initial symbol L. At each time step, the PDA executes weighted transition that changes its state and manipulates the stack. Stack operations are drawn from the set Op(T) = of TTUTUU (e), where for any y E T, oy means "push y,", y means "replace top element with y." and means "pop top element." A valid sequence of transitions is called a run, and the weight of a run is the product of the weights of its transitions.
The RNN controller emits transition weights to the stack module. Note that the stack module, not the controller, keeps track of PDA states and stack configurations, so the controller emits distributions over transitions conditioned on the PDA's current state and top stack symbol. More precisely, a, [[[] is a tensor where the meaning of element A A[][q,x - v] is: if the PDA is in state q and the top - r, r.v]. go to state and perform stack operation OT")) The original NS-RNN definition requires that for all q, and x, the weights form a probability distribution. Accordingly, they are computed from the hidden state using a softmax layer:
stack symbol is x, then, with weight [[]][q.x
[[r] softmax (Whah, + bba).
(1)
4.X
The stack module marginalizes over all runs ending at time step r and returns the distribution over top stack symbols / to the controller. may appear that computing this distribution is intractable because the number of possible runs is exponential in r, but Lang (1974) gives dynamic programming algorithm that simulates all runs of a nondeterministic PDA cubic time and quadratic space. Lang's algorithm exploits structural similarities in PDA runs. First, multiple runs can result in the same stack. Second, for k > 0, a stack of height& must have been derived from a stack of height k - 1, so in principle representing stack of height k requires only storing its top symbol and pointer to stack of height & 1. The resulting data structure is a weighted graph where edges represent individual stack symbols, and paths (of which there exponentially many) represent stacks
3

---

Published as a conference paper at ICLR 2022
We may equivalently view this graph weighted finite automaton (WFA) that encodes distribution over stacks, and accordingly the WSS-RNN's s stack module is called the stack WFA. Indeed, the language of stacks a given time step is always regular (Autebert et al., 1997). and Lang's algorithm gives an explicit construction for the WFA encoding this language. Its states are PDA configurations of the form (i, 4,),, where 0 Σ S n, 9 E Q, and I' is the stack top. A stack WFA transition from qi, to (t,r,) means the PDA went from configuration (i, q. x) to (r,r,y) (possibly via multiple time steps), where the only difference in the stack is that single y was pushed, and the was never modified in between. The weights of these transitions are stored in tensor of shape n X x 1Q1 x [T] x (2) x (T], where elements are written yli - x]l..x-> r,y]. For & < S n,
y(i- Xl - r.
I[i [-1] [/ - r,
push
Σ y|i 1111
[
repl.
2
ΣΣ yli u. - s, A[ss, + r, pop 5,2
k=/+1
The NS-RNN sums over all stacks (accepting paths in the stack WFA) using tensor of forward weights of xx The weight [r] is the total weight of reaching configuration (t, y). These weights normalized to get the distribution over top stack symbols at r:
a[0][r.y] = I[r 40 A ===
(3)
1=1
a[[[rr.] = Σ Σ
(15I5m)
(4)
1-1 9.X
Σx add[r
ry [y] = Σy E, [[]rr
(5)
We refer the reader to our earlier paper (DuSell & Chiang, 2020) for details of deriving these equations from Lang's algorithm. To avoid underflow and overflow, in practice, A, y, and are computed in log space. The model's time complexity is (122")173,;)) and its space complexity is 1())))))3)
3 RENORMALIZING NS-RNN
Here, we introduce the Renormalizing NS-RNN, which differs from the NS-RNN in two ways.
3.1 UNNORMALIZED TRANSITION WEIGHTS
To make a good prediction at time 1, the model may need a certain top stack symbol y, which may in turn require previous actions to be orchestrated correctly. For example, consider the language (v#PR), where n is odd and w, = Wn-1+1 for all f. In order to do better than chance when predicting w, (for r in the second half), the model has to push stack symbol that encodes w, at time (л 1+ 1), and that same symbol must be on top at time 1. How does the model learn to do this? Assume that the gradient of the log-likelihood with respect to r, [y] is positive; this gradient "flows" the PDA transition probabilities via (among other things) the partial derivatives of log with respect to log A.
To calculate these derivatives more easily, we express a directly (albeit less efficiently) in terms of A:
a[r][r.y]=
Σ
π [[]]
where each 6, a PDA transition of the form X1 - x2, [ = A[i][gı, - q2. x2]. and
the summation over d ... 8, ~ y means that after following transitions òj...., o, then the PDA will be in state and its top stack symbol will be y. Then the partial derivatives are:
log [r)
Es, -or--- (11 A[F]))>] [[; 6]
8 log A [6]]]
E I7 |[]]]]]]
4

---

Published as a conference paper at ICLR 2022
This is the posterior probability of having used transition ó at time given that the PDA has read the input up to time I and reached state r and top stack symbol y.
So if a correct prediction time depends that action is proportional to its probability given the correct prediction. This probability is always nonzero, desired. However, this probability is the product of individual action probabilities, which are always strictly less than one. If a correct prediction depends on orchestrating many stack actions, then this probability may become very small. Returning our example, we expect the model begin by learning to predict the middle of the string, where only a few stack actions must be orchestrated, then working its way outwards, more and more slowly as more and more actions must be orchestrated. In $4 we verify empirically that this is the case.
stack action an earlier time i, the gradient flow to
The solution we propose is to use unnormalized (non-negative) transition weights, not probabilities. and to normalize weights only when reading. Equation (1) now becomes
[[]] ha + bna)-
The gradient flowing to a transition is still proportional to its posterior probability, but now each transition weight has the ability "amplify" (Lafferty et al., 2001) other transitions in shared runs. Equation (5) is not changed (yet), but its interpretation is. The NS-RNN maintains a probability distribution over stacks and updates it by performing probabilistic operations. Now, the model maintains an unnormalized weight distribution, and when it reads from the stack at each time step. it renormalizes this distribution and marginalizes it to get a probability distribution over readings. For this reason, we call our new model Renormalizing NS-RNN (RNS-RNN).
3.2 PDA STATES INCLUDED IN STACK READING
In the NS-RNN, the controller can read the distribution over the PDA's current top stack symbol, but cannot observe its current state. To see why this a problem, consider the language (vv&). While reading v, the controller should predict the uniform distribution, but while reading vR. it should predict based on the top stack symbol. PDA with two states can nondeterministically guess whether the current position is in or R. The controller should interpolate the two distributions based on the weight of being in each state, but cannot do this without input from the stack WFA, since the state is entangled with the stack contents. We solve this in the RNS-RNN by computing joint distribution over top stack symbols and PDA states, making r, a vector of size [Q[[[]] Equation 5 becomes
a[t][r,)]
rr((r, = Er
EXPERIMENTS ON FORMAL LANGUAGES
In order to assess the benefits of using unnormalized transition weights and including PDA states in the stack reading, same five CFL language modeling tasks used previously (DuSell & Chiang, 2020). We use the same experimental setup and PCFG settings, except for one important difference: we require the model to predict an ond-of-sequence (EOS) symbol at the end of every string. This way, the model defines a proper probability distribution over strings, improving the interpretability of the results.
the ENS-RNN with and without the two proposed modifications the
Each task is a weighted CFL specified as PCFG:
Marked reversal The palindrome language with middle marker ([v#v R v E (0, 1}")).
Unmarked reversal The palindrome language without middle marker ([vr v E (0, 1)))). Padded reversal Like unmarked reversal, but with long stretch of repeated symbols in the middle ([vaPyR R e (0. 1)", E (0, 1). 2 0}).
Dyck language The language D2 of strings with balanced brackets (two bracket types).
Hardest CFL A language shown by Greibach (1973) to be at least as hard to parse as any other CFL.
The marked reversal and Dyck languages are deterministic tasks that could be solved optimally with a deterministic PDA. On the other hand, the unmarked reversal, padded reversal, and hardest CFL tasks
5

---

Published as a conference paper at ICLR 2022
require nondeterminism, with hardest CFL requiring the most (DuSell & Chiang, 2020, Appendix A). We randomly sample from these languages to create training, validation, and test sets. All strings represented as sequences of one-hot vectors. Please see Appendix B for additional experimental details.
We evaluate models according per-symbol cross-entropy (lower is better). For any set of strings S and probability distribution p. it is defined as
H(S. -Eees log p(w EO-)
Ewes(w)|+1
Since the validation and test strings are all sampled from known distributions, formula to compute the per-symbol entropy of the true distribution (DuSell & Chiang, 2020). In our experiments we measure performance the difference between the model cross-entropy and the true entropy. per-symbol and measured in nats (lower is better, and zero is optimal).
also use this
We compare seven models on the CFL tasks, each of which consists of an LSTM connected to different type of stack: none ("LSTM""): stratification ("Gref"); superposition ("JM""); nondeterministic, aka NS-RNN ("NS"); NS with PDA states in the reading and normalized action weights ("NS+S"); NS with no states in the reading and unnormalized action weights ("NS+U"); and NS with PDA states and unnormalized action weights, or RNS- RNN ("NS+S+U").
Results We show validation set performance as a function of training time in Figure 1, and test performance binned by string length in Figure 2 (see also Appendix C for wall-clock training times). For all tasks, we see that our ENS-RNN (denoted US+S+U) attains near-optimal cross-entropy (within 0.05 nats) on the validation set. All stack models effectively solve the deterministic marked reversal and Dyck tasks, although we note that on marked reversal the NS models do not generalize well on held-out lengths. Our new model excels on the three nondeterministic tasks: unmarked reversal, padded reversal, and hardest CFL. We find that the combination of both enhancements (+S+U) greatly improves performance on unmarked reversal and hardest CFL over previous work. For unmarked reversal, merely changing the task by adding EOS causes the baseline NS model to perform worse than Gref and JM; this may be because it requires the NS-RNN to learn a correlation between the two most distant time steps. Both enhancements (+S+U) in the RNS-RNN are essential here; without unnormalized weights, the model does not find a good solution during training, and without PDA states, the model does not have enough information to make optimal decisions. For padded reversal, we see that the addition of PDA states in the stack reading (+S) proves essential to improving performance. Although NS+S and NS+S+U have comparable performance on padded reversal, NS+S+U converges much faster. On hardest CFL, using unnormalized weights by itself (+U) improves performance, but only both modifications together (+S+U) achieve the best performance.
In Figure 3, we show the evolution of stack actions for the NS+S (normalized) and NS+S+U (unnormalized) models over training time on the simplest of the CFL tasks: marked reversal. We see that the normalized model begins solving the task by learning to push and pop symbols close to the middle marker. It then gradually learns to push and pop matching pairs of symbols further and further away from the middle marker. On the other hand, the unnormalized model learns the correct actions for all time steps almost immediately.
5 INCREMENTAL EXECUTION
Having demonstrated improvements on synthetic tasks, we now turn to language modeling on natural language. For standard language modeling benchmarks, during both training and evaluation, RNN language models customarily process the entire data set in order as if were one long sequence, since being able to retain contextual knowledge of past sentences significantly improves predictions for future sentences. Running a full forward and backward pass during training on such a long sequence would be infeasible, so the data set is processed incrementally using a technique called truncated backpropagation through time (BPTT). This technique is feasible for models whose time and space complexity is linear with respect to sequence length, but for memory-augment RNNs, something must be done to limit the time and storage requirements. Yogatama et al. (2018) did this for the superposition stack by limiting the stack to 10 elements. In this section, propose technique for limiting the space and time requirements of the RNN- (or NS- RNN), allowing us to use truncated BPTT and retain contextual information.
models such as stack

---

Published as a conference paper at ICLR 2022
LSTM
Gref
JM
NS
NS+S
NS+U
NS+S+U
Difference Cross Entropy
Marked Reversal
Marked Reversal
0.4
0.3
0.2
0.2
0.1
0.1
Mm
100
Difference Cross Entropy
Unmarked Reversal
Unrnarked Reversal
0.4
0.3
0.3
0.2
0.2
0.1
0.1
50
100
150
40
50
60
70
80
90
100
Difference Cross Entropy
Padded Reversal
0.3
Padded Reversal
0.2
0.2
0.1
0.1
0
50
100
150
200
40
50
60
70
80
90
100
Difference in Cross Entropy
Dyck
Dyck
0.1
0.2
0.1
0
20
40
60
80
100
40
50
60
70
90
100
Difference Cross Entropy
0.2
Hardest CFL
Hardest CFL
0.2
0.1
0.1
0
150
200
50
100
Epoch
Length
Figure I: Cross-entropy difference in nats be- tween model and source distribution valida- tion set vs. training time. Each line corresponds to the model which attains the lowest difference in cross-entropy out of all random restarts.
Figure 2: Cross-entropy difference nats on the test set, binned by string length. These models are the same as those shown in Figure
7

---

Published as a conference paper at ICLR 2022
NS+S
NS+S+U
0
< -Eoochs Elapsed
10
20
20
30
30
30 40
10
Figure 3: Visualization of the first 30 epochs of training (top bottom) the marked reversal task. In each plot, the horizontal axis the string position (time step). Darkness indicates the weight assigned the correct stack action type, normalized by the weight of all actions at time (black correct, white = incorrect). The white band in the middle occurs because "replace" is considered the correct action type for the middle time step. but the models apparently learned perform different action without affecting the results. Both models were trained with learning rate 0.005.
5.1 MEMORY-LIMITED RNS-RNN
We introduce the constraint that the stack WFA only contain transitions ylı x]lq,x- r,y] where r does not exceed a hyperparameter D; other transitions are treated as having zero weight. may be easier get intuition for this constraint in terms of CFGs. The stack WFA formulation is based on Lang's algorithm (1974), which can be thought of as converting a PDA to a CFG and then parsing with a C-y-style algorithm. The equation for (Equation 2) has three terms, corresponding to rules of the form (A - b) (push), (A - Bc) (replace), and (A - BCd) (pop). The constraint i-is on y means that these rules can only used when they span most D positions.
The equations for a (3-4) have two cases, which correspond to rules of the form (A - c) and (A AB.. The definition a allows these rules to be used for spans starting at O and ending anywhere. This is essentially equivalent to the constraint used in the Hiero machine translation system (Chiang, 2005), which uses synchronous CFGs under the constraint that no nonterminal spans more than 10 symbols, with the exception of so-called glue rules S - X, SX.
As consequence of this constraint, we consider the tensor y. which contains the weights of the stack WFA, as matrix with axes for the variables and then the only non-zero entries in y lie band of height along the diagonal. Crucially, column / of y depends only on y(i r'l for and -- D S r' S Similarly, [[r] depends only
r- < and y for - S D. So, just as truncated BPTT for an RNN involves freezing the hidden state and forwarding it to the next wowarrdbbackwrr pass, truncated BPTT for the (R)NS-RNN involves forwarding the hidden state of the controller and forwarding a slice and a. This reduces the time complexity of the (R)NS-RNN to ((( and its space complexity to ((
[i] for D s r-11
EXPERIMENTS
Limiting the memory of the (R)NS-RNY now makes it feasbile to run experiments on natural language modeling benchmarks, although the high computational cost of increasing [@] and [[]] still limits us to settings with little information bandwidth the stack. We believe this will make difficult for the (R)NS-RNN to store lexical information the stack, but it might succeed in using I small set of syntactic categories. To this end, we ran exploratory experiments with the NS-RNN, RNS- -NNN and other language models on the Penn Treebank (PTB) preprocessed Mikolov al. (2011).
We compare four types of model: LSTM, superposition ("JM") with maximum stack depth of 10. and memory-limite NS-RNNs ("NS") and hyperparameters for our LSTM baseline and training schedule on those of Semeniuta et al. (2016) (details in Appendix D). We also test variants of JM, pushing either the hidden state learned
("RNS") with D 35. We based the
8

---

Published as a conference paper at ICLR 2022
Table I: Language modeling results on PTB, measured by perplexity and SG score. The setting I@I 1, [T] = 2 represents minimal capacity in the (R)NS-RNH models and is meant to serve as a baseline for the other settings. The other two settings are meant to test the upper limits of model capacity before computational cost becomes too great. The setting lQ| 1, |[|= represents the greatest number of stack symbol types we can afford to use, using only one PDA state. We selected the setting [2] 3, ||| 4 by increasing the number of PDA states, and then the number of stack symbol types, until computational cost became too great (recall that the time complexity is 0(121 so adding states is more expensive than adding stack symbol types).
Model
# Params
Val
Test
SG Score
LSTM, 256 units
5,656,336
125.78
120.95
0.433
LSTM, 258 units
5,704,576
122,08
118.20
0.420
LSTM, 267 units
5,922,448
125.20
120.22
0.437
JM (push hidden state), 247 units
5,684.828
121.24
115.35
0.387
JM (push learned), |v, 22
5,685,289
122.87
117.93
0.431
NS. [2] 1, [[]
5,660,954
126.10
122.62
0.414
NS, [21 = -1,
11
5,732.621
129.11
124.98
0.431
NS, [2] = [[] =4
5,743,700
126.71
122.53
0.447
RNS, [Q] = [ =2
5,660,954
122.64
117.56
0.435
RNS, [ = 1,
11
5,732,621
127.21
121.84
0.386
RNS, Q2 = 3, | =4
5,751,892
122.67
118.09
0.408
vector. Unless otherwise noted, the LSTM controller has 256 units, layer, and dropout. For each model, we randomly search for initial learning rate and gradient clipping threshold; we report results for the model with the best validation perplexity out of 10 random restarts. In addition to perplexity, we also report the recently proposed Syntactic Generalization (SG) score metric (Hu et al., 2020: Gauthier et al.. 2020). This score, which ranges from to puts language model through battery of seehhooinnuisticlllymtiaaaattt nested syntactic patterns, Hu et al. (2020) noted that perplexity does not, in general, agree with SG score, we hypothesized the SG score would provide crucial insight into the stack's s effectiveness.
tests that test how well model generalizes to non-linear,
Results We show the results of experiments the Penn Treebank in Table 1. We reproduce the finding of Yogatama et al. (2018) that JM can achieve lower perplexity than an LSTM with a comparable number of parameters, but this does not translate into better SG score. The results for NS and RNS do not show a clear trend in perplexity or SG score as the number of states or stack symbols increases, or the modifications in RNS are applied, even when breaking down SG score by type of syntactic test (see Appendix E). We hypothesize that this is due to the information bottleneck caused by using small discrete set of symbols I in both models, a limitation we hope address in future work. The interested reader can find experiments for additional model sizes in Appendix E. For all models we find that SG score is highly variable and uncorrelated perplexity, corroborating findings by Hu et al. (2020). In fact, when we inspected all randomly searched LSTMs, we found that it is sometimes able to attain scores higher than 0.48 (see Appendix E for details). From this we conclude that improving syntax generalization on natural language remains elusive for all stack RNNs we tested, and that we may need to look beyond crosseentropy/perpeetty as a training criterion.
6 CONCLUSION
The Renormalizing NS-RNN (RNS-RNN) builds upon the strengths of the NS-RNN by letting stack action weights remain unnormalized and providing information about PDA states to the controller. Both of these changes substantially improve learning, allowing the RNS-RNN to surpass other stack RNNs on a range of CFL modeling tasks. Our memory-limited version of the RNS-RNN is a crucial modification towards practical use on natural language. We tested this model on the Penn Treebank, although we did not performance improvements with the model sizes fact no stack RNNs excel in terms of syntactic generalization. We are encouraged by the large improvements on CFL tasks and leave improvements on natural language to future work.
able test, and in

---

Published as a conference paper at ICLR 2022
REPRODUCIBILITY STATEMENT
In order to foster reproducibility, we have released all code and scripts used to generate our experi- mental results and figures at https:/ htos:///ittt httbb/httuuu./.. com/bdusell, http///uuul/oooneeeeeeeeeeeeeeee /noodeeeeeiiiiiiieeeeeeeeee stic- stack rnn. To ensure that others can replicate a Docker container, whose image definition included in the code repository (see the README for more details). The repository includes the original commands we used to run our experiments, scripts for downloading and preprocessing the PTB dataset of Mikolov et al. (2011), and the test suite definitions needed to compute SG scores. All experimental settings for the CFL experiments described $4 and our previous paper (DuSell & Chiang, 2020), and all experimental settings for the PTB experiments may be found in $5.2 and Appendix D.
software environment, we developed and ran code in
ACKNOWLEDGEMMENS
This research was supported in part by a Google Faculty Research Award to Chiang.
REFERENCES
Jean-Michel Autebert, Jean Berstel, and Luc Boasson. Context-free languages and pushdown automata. In Grzegorz Rozenberg and Arto Salomaa (eds.), Handbook of Formal Languages, pp. 111-174. Springer, 1997. doi: (007/978-3-642-999
Samuel R. Bowman, Christopher D. Manning, and Christopher Potts. Tree-structured composition in neural networks without tree-structured architectures. Proc. International Conference on Cognitive Computation (CoCo): Integrating Neural and Symbolic Approaches, pp. 37-42, 2015.
Samuel Bowman, Jon Gauthier, Abhinav Rastogi, Raghav Gupta, Christopher D. Manning, and Christopher Potts. A fast unified model for parsing and sentence understanding. In Proceedings of the 54th Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers), pp. 1466-1477, Berlin, Germany, August 2016. Association for Computational Linguistics. doi: 10.18653/v1/PP 139. URL https: / /aclanthoology org/P16- 1139.
David Chiang. A hierarchical phrase-based based model for statistical machine translation. In Proc. ACL, pp. 263-270, 2005. doi: 10.31 //111191/1110.// 221999..1..19777 1219873. URL httpp::////tt https://www.ac..ett aclweb. org/ anthology/ 705-1033.
Sreerupa Das, C. Lee Giles, and Guo Guo-Zheng Sun. Learning context-free grammars: Capabilities and limitations of recurrent neural network with external stack memory. In Proc. CogSci, 1992.
Brian DuSell and David Chiang. Learning context-free languages with nondeterministic stack RNNs. In Proc. Conference on Computational Natural Language Learning, pp. 507-519, 2020. URI https://wwe aclweb. org/ arg/antholoog/2000
1at.thhoooog//2222.ommm11111111. con1l-1.41
Chris Dyer, Adhiguna Kuncoro, Miguel Ballesteros. and Noah A. Smith. Recurrent neural network grammars. In Proc. NAACL HLT', pp. 199-209, 2016. doi: 10.18653/w1/116-1022 URL
httpp::/aclaatthology oro/No6-g111 1024.
Jon Gauthier, Jennifer Hu, Ethan Wilcox, Peng Qian, and Roger Levy. SyntaxGym: An online platform for targeted evaluation of language models. In Proc. ACL: System Demonstrations, pp. 70-76, 2020. doi: 2020 acl-demos 10.
URL https://vww. aclweb. org/ aathallgyy////
Edward Grefenstette, Karl Moritz Hermann, Mustafa Suleyman, and Phil Blunsom. Learning to trans- duce with unbounded memory. In Proc. NewrIPS, volume 2, pp. 1828-1836. 2015. URL https: //papers. ceapers.nips.o wwtpccccppppeeeeeeeee 5548 learning- to- transduce- whteeewwthh-ubbbeeeeeeeeeee th-unbounded -emory.. pdf.
Sheila A. Greibach. The hardest context-free language. SIAM J. Comput., 2(4))304-310, 1973. doi: 10.1 137/0202025.
10

---

Published as a conference paper at ICLR 2022
Yiding Hao, William Merrill, Dana Angluin, Robert Frank, Noah Amsel, Andrew Benz, and Simon Mendelsohn. Context-free transductions with neural stacks. In Proc. BlackboxNLP, pp. 306-315, November 2018. doi: 7118-533..
URL https://www www.ww.wwwbb....... http://bb.rgg//ttooooggoooo
Sepp Hochreiter and Jürgen Schmidhuber. Long short-term memory. Neural Computation, (8):1735-1780, November 1997. ISSN 0899-7667. doi: 10. 10.1162/neco. 997.99.8 17335. URL https://doi.org hetg//0.1112//eee www2/necoo..o..
1735.
Jennifer Hu, Jon Gauthier, Peng Qian, Ethan Wilcox, and Roger Levy. A systematic assessment of
syntactic generalizionn in neural language models. In Proc. ACL, pp. 1725-1744, July 2020. URL https://ww// aclweb. waweeboorgggatnan hergg/nthllogy//// 2202 acl-main. 158.
Armand Joulin and Tomas Mikolov. Inferring algorithmic patterns with stack-augmented recurrent nets. In Proc. NeurlPS, volume 1, pp. 190-198, 2015. URL ttt.:ttttt:/ppersaaatt nips cccppprr//ppe///////////pppp. 5857-inferring aalorllgrriii thwic-patteeeeeeeee patterns- th- stack-ttttttttttt wwwmentedd pdf.
Yoon Kim, Chris Dyer, and Alexander Rush. Compound probabilistic context-free grammars for grammar induction. In Proc. ACL, pp. 2369-2385, 2019, doi: 10. 00.18653/1//11--2228, URL ht https://aclanthoolgyy wwwpahooooyoooooooooooooooo 0tg//19-11/00
John D. Lafferty, Andrew McCallum, and Fernando N. Pereira. Conditional random fields: Probabilistic models for segmenting and labeling sequence data. In Proceedings of the Eighteenth International Conference on Machine Learning, pp. 289,289, 2001.
Bernard Lang. Deterministic techniques for efficient non-deterministic parsers. In Proc. Colloquium on Automata, Languages, and Programming, pp. 255-269, 1974. doi: 10.
Richard McCoy, Robert H. Frank, and Tal Linzen. Does syntax need to grow on trees? Sources of hierarchical inductive bias in sequence-to-seqqeecce networks, Trans. ACL, 8: 8:125-140, 2020. URL /ttps://www. mi tpress journall wrg./o/ppd//.....1.e...... 1aa11///tacl_ae0 a_00044.
Stephen Merity, Nitish Shirish Keskar, and Richard Socher. Regularizing and optimizing LSTM lan- guage models. In Proc. ICLR, 2018. URL http:////opppaeeeeeeeeeeeerrrrre
William Merrill, Lenny Khazan, Noah Amsel, Yiding Hao, Simon Mendelsohn, and Robert Frank. Finding hierarchical structure in neural stacks using unsupervised parsing. In Proceedings of the 2019 ACL Workshop BlackboxNLP: Analyzing and Interpreting Neural Networks for NLP, pp. 224 232, Florence, Italy, August 2019. Association for Computational Linguistics. URL https: : //t:://wwww. wwwwwwlwwa........ wwwwww.oww/aaaaaaeee.oooaoo..a.a
htc.lweb.ogg/nnteee httg///nhhlloyy///e /W19 4823.
Tomas Mikolov, Anoop Deoras, Stefan Kombrink, L. Burget, and J. Cernocky. Empirical evaluation and combination of advanced language modeling techniques. Proc. INTERSPEECH, 2011.
Nikita Nangia and Samuel Bowman. ListOps: diagnostic dataset for latent tree learning. In Proc. NAACL Student Research Workshop, pp. 92-99, 2018. doi: 10.18653/v1/N188 https://www. aclweb. org httgg/nnhologyy/// (N10yy//8880000000 N111-413.
URL
Stanislau Semeniuta, Aliaksei Severyn, and Erhardt Barth. Recurrent dropout without memory loss. In Proc. COLING, pp. 1757-1766, 2016. URL URL.https https: /twp//wwww//.. aclweb. org/ anthhloggy/cii-1166
Yikang Shen, Shawn Tan, Arian Hosseini, Zhouhan Lin, Alessandro Sordoni, and Aaron Courville. Ordered memory. In Proc. NewrIPS. volume 32, 2019a. URL https: httcs://rrcces neurips.. cc/ cc/paper/2019, http:////..........././/.//////.
Paper .ddf.
Yikang Shen, Shawn Tan, Alessandro Sordoni, and Aaron Courville. Ordered neurons: Integrating tree structures recurrent neural networks. In Proc. ICLR, 2019b. URL httpp::/oppnrrete
net/forumidd-B11 111111F7..
G. Z. Sun, C. Lee Giles, H. H. Chen, and Y. C. Lee. The neural network pushdown automaton: Model, stack, and learning simulations. Technical Report UMIACS-TR-93-. 93-77 and CS-TR-3118, University of Maryland, 1995. URL https://arxx http///xxv..og//b////////
org/abs//7111 05738. revised version.

---

Published as a conference paper at ICLR 2022
Mirac Suzgun, Sebastian Gehrmann, Yonatan Belinkov, and Stuart M. Shieber. Memory- recurrent neural networks can learn generalized Dyck languages, 2019. URL https: //axivv./ org/abs/ 1et...191...00 03329. arXiv:1922.03329,
Marten van Schijndel, Aaron Mueller, and Tal Linzen. Quantity doesn't 't buy quality syntax with neural language models. In Proc. EMNLP-IJCNLP, pp. 5831-5837, 2019. doi: 10.18653/v 1/D19-1992
URL httph:://wwwt wtc.lee..org/aathooogooooooo
1592.
Ethan Wilcox. Roger Levy, and Richard Futrell. Hierarchical representation in neural language models: Suppression and recovery of expectations. In Proc. BlackboxNI.P, pp- 181-190, August 2019. doi: 10. 10.18653/1//W11944819 URL. hwtph::ttww..tt.. acwweb..l.b.....
Dani Yogatama, Yishu Miao, Gábor Melis, Wang Ling, Adhiguna Kuncoro, Chris Dyer, and Phil Blunsom. Memory architectures in recurrent neural network language models. In Proc. ICLR, 2018. URL
A BASELINE STACK RNNs
A.I STRATIFICATION STACK
We implement the stratification stack of Grefenstette al. (2015) with the following equations. In the original definition, the controller produces a hidden state h, and separate output of that is used to compute a, and yr, but for simplicity and parity with DuSell Chiang (2020), we set of h, Let = |v,l be the stack embedding size.
a, ACTIONS(h,) (u, d, vi)
= o Wnah, bnu)
d, o (Whah, bad)
tanh (anhh + bav)
5, STAAKKSS-11, a.1)) (V,, S,)
Vi-ili] isisr
vi[ =
i=1
max s,1 max(0, u, - Ej s--lli)) isist
8, [i]
d,
i=l
Vo is O x m matrix
So is vector of size
(min(s, [i], max(0, Σ sDD) V[
r, READING(S,)
Yogatama et al. (2018) noted that the strafication stack implement multiple pops per time step by allowing u, > 1, although the push action immediately following would still be conditioned on the previous stack top r,. Hao al. (2018) augmented this model with differentiable queues that allow to buffer input and output and act as a transducer. Merrill et al. (2019) experimented with variations of this model where u, and d, E (0,4), d, 1 and u, = (0, 4), and u, (0, 4) and d, (0, 1).
A.2 SUPERPOSITION
We implement the superposition stack of Joulin & Mikolov (2015) with the following equations. We deviate slightly from the original definition by adding the bias terms b and b The original definition also connects the controller multiple stacks that push scalars; instead, push a vector to a single stack, which equivalent to multiple scalar stacks whose push/pop actions are synchronized. The original definition includes the top stack elements in the stack reading, but only include the
12

---

Published as a conference paper at ICLR 2022
top element. We also treat the value of the bottom of the stack as 0 instead of -1.
a, ACTIONS h,)
a Vz)
a pushi
a, a
hoop
softmax Whah, Dna)
pop
a
(Whyh, bbv)
STACK(S,-1, =
Vr push
i=0
sy [ =
a
8y-1 1i 1]+a,
s,-1 ",
noop
+ pop
s--1
0<i<l
i=t
r, READING(s)) = s,[1]
Yogatama et al. (2018) developed an extension to this model called the Multipop Adaptive Computation Stack that executes a variable number of pops per time step, up to fixed limit K. They also restricted the stack to maximum size of 10 elements, where the bottom element of full stack is discarded when new element is pushed; in other words, sy [i] 0 for i > K. Suzgun et al. (2019) experimented with modification of the parameterization a, and different softmax operators for normalizing the weights used to compute a,
B DETAILS OF FORMAL LANGUAGE EXPERIMENTS
For every training run, we sample a training set 10,000 strings from the PCFG, with lengths drawn uniformly from [40, 80). Similarly, we sample validation set of 1,000 strings with lengths drawn uniformly from [40, 80]. For each task, we sample a test set of 100 strings per length for each length in [40, 100]. Whereas the training and validation sets randomized for each experiment, the test sets are the same across all models and random restarts.
In all cases, the LSTM has single layer with 20 hidden units. We grid-search the initial learning rate from {0.01, 0.005, 0.001, 0.0005). For Gref and JM, we search for stack vector element sizes in (2, 20, 40) (the pushed vector in JM is learned). For the NS models, number of PDA states and stack symbol types based on how we would expect PDA to solve the task. For marked reversal, unmarked reversal, and Dyck, we use [@] 2 and [[] 3; and for padded reversal and hardest CFL, we use |Q| 3 and [T] 3. For each hyperparameter setting searched, we run five random restarts. For each type of model, we select the model with the lowest difference in cross-entrops between the model and true distribution on the validation set. We use the same initialization and optimization settings as our earlier paper (DuSell & Chiang, 2020) and train for maximum of 200 epochs.
manually choose small
C WALL-CLOCK TRAINING TIME
We report wall-clock execution time for each model on the marked reversal task in Table 2. We ran the LSTM, Gref, and JM models in CPU mode, as this was faster than running GPU due to the small model size. We ran experiments for the NS models in GPU mode on pool of the following NVIDIA GPU models, automatically selected based availability: GeForce GTX TITAN X. TITAN (Pascal), and GeForce GTX 1080 Ti.
D DETAILS OF NATURAL LANGUAGE EXPERIMENTS
The hyperparameters for our baseline LSTM, initialization, and optimization scheme are based on the unregularized LSTM experiments Semeniuta et al. (2016). We train all models using simple stochastic gradient descent (SGD) recommended by prior language modeling work (Merity et al., 2018) and truncated BPTT with a sequence length of 35. For all models, we use a minibatch size of 32. We randomly initialize all parameters uniformly from the interval [-0.05, 0.05J. We divide the
13

---

Published as a conference paper at ICLR 2022
Table 2:
Wall-clock execution time for each model on the marked reversal task, measured in seconds per epoch of training (averaged over all epochs). The speed of the NS models is roughly the same; there some variation here due differences training data and GPU model.
Model
Time per epoch (s)
LSTM
51
Gref
801
JM
169
NS
1022
NS+S
980
NS+U
960
NS+S+U
1060
learning rate by 1.5 whenever the validation perplexity does not improve, and we stop training after epochs of no improvement in validation perplexity.
For each model, we randomly search for initial learning rate and gradient clipping threshold; we report results for the model with the best validation perplexity out of 10 randomly searched models. The learning rate, which is divided by batch size and sequence length, is drawn from a log-uniform distribution over [1, 100], and the gradient clipping threshold, which is multiplied by batch size and sequence length, is drawn from a uniformf distribution over [1 X 10-5, x 10-3). (We scale the learning rate and gradient clipping threshold this way because, under our implementation, sequence length and batch size can vary when the data set is not evenly divisible by the prescribed values. Other language modeling papers follow a different scaling convention for these two hyperparameters. typically scaling the learning rate by sequence length but not by batch size, and not rescaling the gradient clipping threshold. Under this convention the learning rate would be drawn from [0.03125, 3. 3.125] and the gradient clipping threshold from [0.0112,1.12j]
E ADDITIONAL. RESULTS FOR NATURAL LANGUAGE EXPERIMENTS
In Table 3 we show additional experimental results on the Penn Treebank. In Table 4 we show the same experiments with SG score broken down by syntactic "circuit" as defined by Hu al. (2020), offering more fine-grained look at the classes of errors the models make. We see that SG score is highly variable and does not follow the same trends as perplexity. Figure 4, we plot SG score vs. test perplexity for all 10 random restarts of an LSTM and an RNS-RNN We see that many of the models that were not selected actually have a much higher SG score (even above 0.48), suggesting that the standard validation perplexity criterion is poor choice for syntactic generalization.
14

---

Published as a conference paper at ICLR 2022
Table Language modeling results on PTB, measured by perplexity and SG score, with additional experiments included.
Model
Params
Val
Test
SG Score
LSTM, 256 units
5,656,336
125.78
120.95
0.433
LSTM, 258 units
5,704.576
122.08
118.20
0.420
LSTM, 267 units
5,922,448
125.20
120.22
0.437
JM (push hidden state), 247 units
5,684,828
121.24
115.35
0.387
JM (push learned), |v, 22
5,685,289
122.87
117.93
0.431
NS. [Q1 1, [[]
5,660,954
126.10
122.62
0.414
NS, [Q] 1, [ 3
5,664,805
123,41
119.25
0.430
NS, [Q] I, [ 4
5,669,684
121.66
117.91
0.432
NS. [Q] = 1, [ 5
5,675,591
123.01
119.54
0.452
NS. [Q] 1, [ 6
5,682,526
129.94
125.45
0.432
NS. QQ] 1, [ 7
5,690,489
126.11
121.94
0.443
NS. JQ1 I, [[]
5,732.621
129.11
124.98
0.431
NS, [Q1 2, [[] 2
5,668,664
128.16
123.52
0.412
NS. 1Q = 2, [ 3
5,680,996
129.51
126.00
0.471
NS. 121 2, [
4
5,697,440
124.28
120.18
0.433
NS. 12 = 2, [ 5
5,717,996
124.24
119.34
0.429
NS. 121 3, [
2
5,681,514
125.32
120.62
0.470
NS. |21 = 3, [ 3
5,707,981
122.96
118.89
0.420
NS, 1Q1 3, [[]
4
5,743,700
126.71
122.53
0.447
RNS, [Q1 = I,
2
5,660,954
122.64
117.56
0.435
RNS, 2 I,
5,664,805
121.83
116.46
0.430
RNS, Q = I, [ 4
5,669,684
127.99
123.06
0.437
RNS, Q = I, [
5,675,591
126.41
122.25
0.441
RNS, Q = I, [ 6
5,682,526
122.57
117.79
0.416
RNS, Q I,
5,690,489
123.51
120.48
0.430
RNS. Q = I,
[[
5,732,621
127.21
121.84
0.386
RNS. Q = 2,
5,670,712
122.11
117.22
0.399
RNS, Q 2,
3
5,684,068
131.46
127.57
0.463
RNS, Q = 2,
5,701,536
124.96
121.61
0.431
RNS. Q 2,
5,723,116
122.92
117.87
0.423
RNS. Q = 3,
2
5,685,610
129.48
124.66
0.433
RNS. Q 3, L
5,714,125
127.57
123.00
0.434
RNS,
Q = 3,
5,751,892
122.67
118.09
0.408
15

---

Published as a conference paper at ICLR 2022
Table scores broken down by circuit. Agr. = Agreement, Lic. = Licensing, GPE Garden-Pafi
Effects, GSE = Gross Syntactic Expectation, CE Dependencies.
Center Embedding, LDD Long-Distance
Model
Agr.
Lic.
GPE
GSE
CE
LDD
LSTM, 256 units
0.667
0.446
0.330
0.397
0.482
0.414
LSTM, 258 units
0,658
0.447
0.335
0.375
0.518
0.357
LSTM, 267 units
0.667
0.497
0.343
0.446
0.411
0.350
JM (push hidden state)
0.640
0.408
0.296
0.310
0.464
0.352
JM (push learned)
0.684
0.439
0.340
0.408
0.482
0.395
NS, [21 1, | 2
0.588
0.452
0.298
0.391
0.339
0.418
NS, [ = I, [ =
0.623
0.467
0.400
0.413
0.393
0.354
NS. [2 = 1, [ 4
0,640
0.497
0.331
0.375
0.571
0.340
NS, Q = 1, [ =
0.605
0.514
0.394
0.413
0.589
0.344
NS, Q I,
0.632
0.424
0.408
0.391
0.464
0.399
NS, Q = I, [ =
0.719
0.470
0.351
0.473
0.500
0.344
NS, Q 1,
11
0.640
0.432
0.329
0.424
0.500
0.413
NS, Q = 2,
[[ =
0.702
0.388
0.329
0.446
0.446
0.371
NS, Q 2,
[
0.658
0.527
0.367
0.446
0.518
0.411
NS, [ = 2,
Г =
0.632
0.464
0.345
0,386
0.518
0.387
NS, [1 = 2.
0.711
0.464
0.307
0.413
0.518
0.355
NS, [ = 3,
Г 2
0.711
0.528
0.349
0.435
0.518
0.406
NS. Q = 3,
[[' =
0.746
0.439
0.316
0.375
0.411
0.376
NS. Q = 3, [ 4
0.702
0.450
0.364
0.484
0.536
0.369
RNS, Q1 = I, [[]
0.702
0.460
0.280
0.451
0.464
0.404
RNS. Q I, [[]
0.649
0.427
0.438
0,418
0.446
0.347
RNS. Q I, [
0.658
0.412
0.342
0.565
0.339
0.418
RNS, Q 1, [[]
0.728
0.449
0.370
0.429
0.482
0.371
RNS, Q = I, [[] =
0.614
0.422
0.314
0.435
0.518
0.377
RNS. 2
[[]
0.649
0.460
0.374
0.337
0.411
0.404
RNS, Q = I, [[] = 11
0.614
0.447
0.291
0.266
0.446
0.338
RNS. Q 2,
[[]
0.649
0.417
0.365
0.375
0.339
0.334
RNS. Q = 2,
[[] =
0.640
0.474
0.411
0.446
0.554
0.408
RNS. 1 2,
[[]
0.658
0.469
0.336
0.326
0.500
0.403
RNS, 1 = 2,
[[] 5
0.693
0.420
0.339
0.370
0.607
0.376
RNS. 11 3,
[[] =
0.579
0.435
0.295
0.440
0.554
0.445
RNS. Q = 3,
[[] = 3
0.632
0.444
0.356
0.418
0.482
0.403
RNS. Q = 3,
[[] =
0.588
0.427
0.342
0.353
0.482
0.373
16

---

Published as a conference paper at ICLR 2022
0.48
0.46
SG SG Score
0.44
0.42
0.4
LSTM, 258 units
RNS, |0| 2,
100
200
300
400
500
600
Perplexity
Figure SG score vs. test perplexity, shown all 10 random restarts for an LSTM and an RNS-RNN. SG score is uncorrelated with perplexity, and models that narrowly miss out on having the best perplexity often have much higher SG scores.
17


Reviews:
[{"review_id": "qX86kWdll7", "reviewer": "Reviewer_THSf", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "The proposed method solves two defects of NS-RNN. The ideas are technically sound and empirically proved.\nHowever, I have several concerns:\n1. 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.\n2. 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. \n3. 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).\n\nMissing reference:\n- Shen, Yikang, et al. \"Ordered Memory.\" Advances in Neural Information Processing Systems 32 (2019): 5037-5048.", "summary_of_the_paper": "The paper proposes a new stack-augmented RNN, RNS-RNN that includes two modifications to the Nondeterministic Stack RNN:\n1. 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.\n2. 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.", "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.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "Nwc7HUgrQVm", "reviewer": "Reviewer_Cbcr", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "# Strength\n\n- 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.\n\n# Weakness\n\n- 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.\n\n- 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.\n\n- 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_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:\n\n- 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.\n\n- 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.\n\n- 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.\n\nExperimental 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.", "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.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "4: The contributions are significant, and do not exist in prior works.", "empirical_novelty_and_significance": "4: The contributions are significant, and do not exist in prior works."}, "extra_text": {}}, {"review_id": "83zw0h6nxhH", "reviewer": "Reviewer_cb1a", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Strengths\n- The discussion on previous stack RNNs was a strong segment of the paper as the authors connect the various approaches using common notation. \n- The modifications to the NS-RNN are well motivated by appealing to toy problems or an explanation of what happens numerically during training. \n- 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.\n\nWeaknesses\n- It would have been good to explain what Hardest CFL (Greibach, 1973) is in the paper. **[addressed by author response and paper update]**\n- 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_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.\n\nThe paper also uses the new NS-RNN for a language modelling task on the Penn Treebank by introducing a memory-limiting technique.", "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.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "4: The contributions are significant, and do not exist in prior works.", "empirical_novelty_and_significance": "4: The contributions are significant, and do not exist in prior works."}, "extra_text": {}}, {"review_id": "5Z3YxvMGRge", "reviewer": "Reviewer_vA7w", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "=quick pros=\n- proposed changes are simple, clear, and appear to improve the model on some synthetic tasks (even significantly for one of them).\n\n=quick cons=\n- 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.\n\n=full review=\n\nNote: I have reviewed this paper before, and appreciate that the authors have added experiments and metrics as requested. \n\nI 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! :)\n\n==some comments==\n\n1. 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.)\n\n2. 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.\n\n3 (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. \n\n(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). )\n\n4. 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?\n\n5. 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?\n\n==some questions==\n1. 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).\n\n2. 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?\n\n3. 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?)\n\n\n==typos, presentation, minor comments==\n1. 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 ?\n2. 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).\n3. 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? \n", "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:\n1. 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.\n2. 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.)\n\nThe 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. \n\nThe 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. \n\n*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\n", "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. \n", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}]

Author rebuttal:

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)