Learning Hierarchical Structures with Differentiable Nondeterministic Stacks
Year: 2021

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

heading: 1 Introduction
text: Manymachine 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 or a hierarchical inductive bias (van Schijndel 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, to predict the second half of a string of the form F#FR, a simple RNN would need to store all of F in its hidden state before predicting its reversal FR; a memory of finite size will inevitably fail to do this for inputs exceeding a certain length.
To remedy this, some previous work has investigated the addition of differentiable stack data structures to RNNs (Sun et 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 et al., 2016; Dyer et al., 2016; Shen et al., 2019a). Just as adding a 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 to 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.
DuSell & Chiang (2020) recently proposed a stack-based RNN called the Nondeterministic Stack RNN (NS-RNN) that outperformed other stack RNNs on a range of CFL language modeling tasks. This model’s defining feature is that its external data structure is a nondeterministic PDA, allowing it to simulate an exponential number of sequences of stack operations in parallel. This is in contrast to prior 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 a 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 CFLs, whereas a nondeterministic stack should enable it to model all CFLs. This is important for natural language processing, as human language is known to be full of syntactic ambiguity.
Another benefit of nondeterminism, even on deterministic CFLs, applies to training. In order for a 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, a classifier tries all ten digits, and is rewarded for the correct one. But in a stack-augmented model, the space of possible action sequences is very large. Whereas a deterministic stack can only try one of them, a nondeterministic stack can try all of them and always receives a reward for the correct one. But as explained in §3.1, because the NS-RNN’s probability for an action sequence is the product of many probabilities, it can be extremely small, so the NS-RNN sometimes learns very slowly.
In this paper we present a 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 an 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 information-theoretic lower bound) and to surpass deterministic stack RNNs on a task on which the NS-RNN fails to do so (“padded reversal”). Finally, as a third modification, we present a memory-restricted version of the RNS-RNN that requires only $ (=) time and space (§5). This restricted RNS-RNN can be run incrementally on arbitrarily long sequences, which is a necessity for language modeling on natural language, for which we provide experimental results. We will release our code publicly.

heading: 2 Previous stack RNNs
text: We begin by discussing three previously proposed stack RNNs, each of which uses a 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).

heading: 2.1 Controller-stack interface
text: Each type of stack RNN consists of a 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 is to 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 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 all three of these stack RNN models conform to the same controller-stack interface. This allows us to isolate differences in the style of stack data structure employed while keeping other parts of the network the same. We assume the input F = F1 · · ·F= is encoded as a sequence of vectors x1, · · · , x=. In all of our experiments, we use an LSTM (Hochreiter & Schmidhuber, 1997) as the controller, whose memory consists of a hidden state hC and memory cell cC . The controller computes the next state (hC , cC ) given the previous state (hC−1, cC−1), input vector xC , and stack reading rC−1:
(hC , cC ) = LSTM ( (hC−1, cC−1), [ xC
rC−1
] ) .
We set h0 = c0 = 0. The hidden state is used to compute the stack actions 0C and predict the logits yC for the next word FC+1. The previous stack and new actions are used to compute a new stack BC , which in turn is used to produce a new reading rC :
0C = Actions(hC ) yC = WhyhC + bhy BC = Stack(BC−1, 0C−1) rC = Reading(BC )
In order to change the stack data structure, we need only change the definitions of Actions, Stack, Reading, and B0, which may depend on parameters of the model; for our changes to the NS-RNN, we will only need to change Actions and Reading.

heading: 2.2 Stratification
text: Based on work by Das et al. (1992) and Sun et al. (1995), the stack of Grefenstette et al. (2015) relies on a strategy dubbed “stratification” by 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 to which the vector element is present on the stack. A helpful analogy is that of layers of a cake; the stack elements are like cake layers of varying thickness. In this model, 0C = (DC , 3C , vC ), where the pop signal DC ∈ (0, 1) indicates the amount to be removed from the top of the stack, vC is a learned vector to be pushed as a new element onto the stack, and the push signal 3C ∈ (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.

heading: 2.3 Superposition
text: 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 0C = (aC , vC ), where the vector aC is a probability distribution over three stack operations: push a new vector, no-op, and pop the top vector; vC is the vector to be pushed. The vector vC can be learned or can be set to hC (Yogatama et al., 2018). The stack reading is the top cell of the stack. This model has quadratic time and space complexity with respect to input length. We refer the reader to Appendix A.2 for full details.

heading: 2.4 Nondeterminism
text: The stack module in the Nondeterministic Stack RNN (NS-RNN) model of DuSell & Chiang (2020) maintains a probability distribution over whole stacks by simulating a weighted PDA. It 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 a state drawn from a finite set &, which includes an initial state @0, and a stack with symbols drawn from an alphabet Γ, which includes an initial symbol ⊥. At each time step, the PDA executes a weighted transition that changes its state and manipulates the stack. Stack operations are drawn from the set Op(Γ) = •Γ ∪ Γ ∪ {n}, where for any H ∈ Γ, •H means “push H,” H means “replace the top element with H,” and n means “pop the 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, 0C = Δ [C] is a tensor where the meaning of element Δ [C] [@, G → A, h] is: if the PDA is in state @ and the top stack symbol is G, then, with weight Δ [C] [@, G → A, h], go to state A and perform stack operation h ∈ Op(Γ). The original NS-RNN definition requires that for all C, @, and G, the weights form a probability distribution. Accordingly, they are computed from the hidden state using a softmax layer:
Δ [C] = softmax @,G (WhahC + bha). (1)
The stack module marginalizes over all runs ending at time step C and returns the distribution over top stack symbols at C to the controller. It may appear that computing this probability distribution is intractable because the number of possible runs is exponential in C, but Lang (1974) gives a dynamic programming algorithm that simulates all runs of a nondeterministic PDA in 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 : > 0, a stack of height : must have been derived from a stack of height : − 1, so in principle representing a stack of height : requires only storing its top symbol and a pointer to a stack of height : − 1. The resulting data structure is a weighted graph where edges represent individual stack symbols, and paths (of which there are exponentially many) represent stacks.
We may equivalently view this graph as a weighted finite automaton (WFA) that encodes a distribution over stacks, and accordingly the NS-RNN’s stack module is called the stack WFA. Indeed, the language of stacks at a given time step C 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 (8, @, G), where 0 ≤ 8 ≤ =, @ ∈ &, and G ∈ Γ is the stack top. A stack WFA transition from (8, @, G) to (C, A, H) means the PDA went from configuration (8, @, G) to (C, A, H) (possibly via multiple time steps), where the only difference in the stack is that a single H was pushed, and the G was never modified in between. The weights of these transitions are stored in a tensor W of shape = × = × |& | × |Γ| × |& | × |Γ |, where elements are written W [8 −→ C] [@, G −→ A, H]. For 0 ≤ 8 < C ≤ =, W [8 −→ C] [@, G −→ A, H] = I[8 = C−1] Δ [C] [@, G → A, •H] push +
∑ B,I W [8 −→ C−1] [@, G −→ B, I] Δ [C] [B, I → A, H] repl.
+ C−2∑
:=8+1 ∑ D ∑ B,I W [8 −→ :] [@, G −→ D, H] W [: −→ C−1] [D, H −→ B, I] Δ [C] [B, I → A, n] pop
(2)
The NS-RNNmarginalizes over all stacks/accepting paths in the stackWFA using a tensor U of forward weights of shape = × |& | × |Γ |. The weight U[C] [A, H] is the total weight of reaching configuration (C, A, H). These weights are normalized to compute the distribution over top stack symbols at C:
U[0] [A, H] = I[A = @0 ∧ H = ⊥] (3) U[C] [A, H] = C−1∑ 8=1 ∑ @,G U[8] [@, G] W [8 −→ C] [@, G −→ A, H] (1 ≤ C ≤ =) (4)
rC [H] = ∑
A U[C] [A, H]∑ H′ ∑ A U[C] [A, H′] . (5)
We refer the reader to DuSell & Chiang (2020) for details regarding the derivation of these equations from Lang’s algorithm. To avoid underflow and overflow, in practice, Δ , W, and U are computed in log space. The model’s time complexity is $ ( |& |4 |Γ |3=3), and its space complexity is $ ( |& |2 |Γ |2=2).

heading: 3 Renormalizing NS-RNN
text: Here, we introduce the Renormalizing NS-RNN, which differs from the NS-RNN in two ways.

heading: 3.1 Unnormalized transition weights
text: To make a good prediction at time C, the model may need a certain top stack symbol H, which may in turn require previous actions to be orchestrated correctly. For example, consider the language {E#ER}, where = is odd and FC = F=−C+1 for all C. In order to do better than chance when predicting FC (for C in the second half), the model has to push a stack symbol that encodes FC at time (= − C + 1), and that same symbol must be on top at time C. How does the model learn to do this? Assume that the gradient of the log-likelihood with respect to rC [H] is positive; this gradient “flows” to the PDA transition probabilities via (among other things) the partial derivatives of logU with respect to logΔ .
To calculate these derivatives more easily, we express U directly (albeit less efficiently) in terms of Δ: U[C] [A, H] = ∑
X1 · · ·XC{A ,H ∏ 8=1,...,C Δ [8] [X8]
where each X8 is a PDA transition of the form @1, G1 → @2, G2, Δ [8] [X8] = Δ [8] [@1, G1 → @2, G2], and the summation over X1 · · · XC { A, H means that after following transitions X1, . . . , XC , then the PDA will be in state A and its top stack symbol will be H. Then the partial derivatives are:
m logU[C] [A, H] m logΔ [8] [X] =
∑ X1 · · ·XC{A ,H (∏C 8′=1 Δ [8′] [X8′] ) I[X8 = X]∑
X1 · · ·XC{A ,H ∏C 8′=1 Δ [8] [X8′] .
This is the posterior probability of having used transition X at time 8, given that the PDA has read the input up to time C and reached state A and top stack symbol H.
So if a correct prediction at time C depends on a stack action at an earlier time 8, the gradient flow to that action is proportional to its probability given the correct prediction. This probability is always nonzero, as 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 to our example, we expect the model to 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.
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
Δ [C] = exp(WhahC + bha).
The gradient flowing to a transition is still proportional to its posterior probability, but now each transition weight has the ability to “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 a Renormalizing NS-RNN (RNS-RNN).

heading: 3.2 PDA states included in stack reading
text: In the NS-RNN, the controller can read the distribution over the PDA’s current top stack symbol, but it cannot observe its current state. To see why this is a problem, consider the language {EER}. While reading E, the controller should predict the uniform distribution, but while reading ER, it should predict based on the top stack symbol. A PDA with two states can nondeterministically guess whether the current position is in E or ER. The controller should interpolate the two distributions based on the weight of being in each state, but it 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 a joint distribution over top stack symbols and PDA states, making rC a vector of size |& | |Γ |. Equation 5 becomes
rC [(A, H)] = U[C] [A, H]∑
A ′,H′ U[C] [A ′, H′] .

heading: 4 Experiments on formal languages
text: In order to assess the benefits of using unnormalized transition weights and including PDA states in the stack reading, we ran the RNS-RNN with and without the two proposed modifications on the same five CFL language modeling tasks used in DuSell & Chiang (2020). We use the same experimental setup and PCFG settings, except for one important difference: we require the model to predict an end-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.
Each task is a weighted CFL specified as a PCFG:
Marked reversal The palindrome language with a middle marker ({E#ER | E ∈ {0, 1}∗}). Unmarked reversal The palindrome language without a middle marker ({EER | E ∈ {0, 1}∗}). Padded reversal Like unmarked reversal, but with a long stretch of repeated symbols in the middle ({E0?ER | E ∈ {0, 1}∗, 0 ∈ {0, 1}, ? ≥ 0}). Dyck language The language 2 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
require nondeterminism, with hardest CFL requiring the most (we refer the reader to Appendix A of DuSell & Chiang (2020) for more details as to why this is the case). We randomly sample from these languages to create training, validation, and test sets. All strings are represented as sequences of one-hot vectors. Please see Appendix B for additional experimental details.
We evaluate models according to per-symbol cross-entropy (lower is better). For any set of strings ( and probability distribution ?, it is defined as ((, ?) = − ∑
F ∈( log ?(F · EOS)∑ F ∈( ( |F | + 1) .
Since the validation and test strings are all sampled from known distributions, we can also use this formula to compute the per-symbol entropy of the true distribution per DuSell & Chiang (2020). In our experiments we measure performance as the difference between the model cross-entropy and the true entropy, per-symbol and measured in nats (lower is better and zero is optimal).
We compare seven models on the CFL tasks, each of which consists of an LSTM connected to a 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 RNS-RNN (denoted NS+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.

heading: 5 Incremental execution
text: 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 it 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-augmented models such as stack 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, we propose a technique for limiting the space and time requirements of the RNS-RNN (or NS-RNN), allowing us to use truncated BPTT and retain contextual information.
LSTM Gref JM NS NS+S NS+U NS+S+U
0 20 40 60 80 100 0
0.1
0.2
0.3 0.4 D iff er en ce in Cr os sE
nt ro py Marked Reversal
0 50 100 150 0
0.1
0.2
0.3
D iff er en ce
in Cr
os sE
nt ro py Unmarked Reversal
0 50 100 150 200 0
0.1
0.2
0.3
D iff er en ce
in Cr
os sE
nt ro py Padded Reversal
0 20 40 60 80 100 0
0.1
0.2
0.3
0.4
D iff er en ce
in Cr
os sE
nt ro py Dyck
0 50 100 150 200 0
0.1
0.2
Epoch
D iff er en ce
in Cr
os sE
nt ro py Hardest CFL
Figure 1: Cross-entropy difference in nats between model and source distribution on validation set vs. training time. Each line corresponds to themodelwhich attains the lowest difference in cross-entropy out of all random restarts.

heading: 5.1 Memory-limited RNS-RNN
text: We introduce the following constraint to the (R)NS-RNN: the stack WFA can only contain transitions W [8 −→ C] [@, G −→ A, H] where C − 8 ≤ , where is a hyperparameter; all other transitions are treated as having a weight of 0. To get an intuition for this constraint, it may help to think about it 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 (Hopcroft & Ullman, 1979) and then parsing with a CKY-style algorithm. The equation for W (Equation 2) has three terms, which correspond to rules of the form ( → 1) (push), ( → 2) (replace), and ( → 3) (pop). The constraint C − 8 ≤ on W means that these rules can only be used when the left-hand side span is at most .
The equations for U (3–4) have two cases, which correspond to rules of the form ( → n) and ( → ). The definition of U allows these rules to be used for spans starting at 0 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 ( → - , ( → (- . As a consequence of this constraint, if we consider the tensor W, which contains the weights of the stack WFA, as a matrix with axes for the variables 8 and C, then the only non-zero entries in W lie in a band of height along the diagonal. Crucially, column C of W depends only on W [8 −→ C ′] for C − ≤ 8 ≤ C − 2 and C − + 1 ≤ C ′ ≤ C − 1. Similarly, U[C] depends only on U[8] for C − ≤ 8 ≤ C − 1 and W [8 −→ C] for C − 8 ≤ . So, just as truncated BPTT for an RNN involves freezing the hidden state and forwarding it to the next forward-backward pass, truncated BPTT for the (R)NS-RNN involves forwarding the hidden state of the controller and forwarding a slice of W and U. This reduces the time complexity of the (R)NS-RNN to $ ( |& |4 |Γ |3 2=) and its space complexity to $ ( |& |2 |Γ |2 =).

heading: 5.2 Experiments
text: Limiting the memory of the (R)NS-RNN nowmakes 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 in the stack. We believe this will make it difficult for the (R)NS-RNN to store lexical information on the stack, but it might succeed in using Γ as a small set of syntactic categories. To this end, we ran exploratory experiments with the NS-RNN, RNS-RNN, and other language models on the Penn Treebank (PTB) as preprocessed by Mikolov et al. (2011).
We compare four types of model: LSTM, superposition (“JM”) with a maximum stack depth of 10, and memory-limited NS-RNNs (“NS”) and RNS-RNNs (“RNS”) with = 35. We based the hyperparameters for our LSTM baseline and training schedule on those of Semeniuta et al. (2016) (details in Appendix D). We also test two variants of JM, pushing either the hidden state or a learned vector. Unless otherwise noted, the LSTM controller has 256 units, one layer, and no 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 0 to 1, puts a language model through a battery of psycholinguistically-motivated tests that test how well a model generalizes to non-linear, nested syntactic patterns. Hu et al. (2020) noted that perplexity does not, in general, agree with SG score, so we hypothesized the SG score would provide crucial insight into the stack’s effectiveness.
Results We show the results of our experiments on the Penn Treebank in Table 1. We reproduce the finding in 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 a 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 as 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 a small discrete set of symbols Γ in both models, a limitation we hope to 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 to perplexity, corroborating findings in 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 cross-entropy/perplexity as a training criterion.

heading: 6 Conclusion
text: 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 see performance improvements with the model sizes we were able to test, and in fact no stack RNNs excel in terms of syntactic generalization. We are encouraged by the RNS-RNN’s large improvements on CFL tasks and leave improvements on natural language to future work.

heading: 7 Reproducibility Statement
text: In order to foster reproducibility, we have attached all code and scripts used to generate our experimental results and figures to this anonymous paper submission. To ensure that other users can replicate our software environment, we developed and ran our code in a Docker container, whose image definition is included in the attachment (see the README for more details). The code attachment includes the original commands used to run our experiments, scripts for downloading and preprocessing the PTB dataset of Mikolov et al. (2011), and the data files needed to compute SG scores. All experimental settings for the CFL experiments are described in §4 and DuSell & Chiang (2020), and all experimental settings for the PTB experiments may be found in §5.2 and Appendix D.

heading: A Baseline stack RNNs
text: A.1 Stratification stack
We implement the stratification stack of Grefenstette et al. (2015) with the following equations. In the original definition, the controller produces a hidden state hC and a separate output o′C that is used to compute 0C and yC , but for simplicity and parity with DuSell & Chiang (2020), we set o′C = hC . Let < = |vC | be the stack embedding size.
0C = Actions(hC ) = (DC , 3C , vC ) DC = f(WhuhC + bhu) 3C = f(WhdhC + bhd) vC = tanh(WhvhC + bhv)
BC = Stack(BC−1, 0C−1) = (+C , sC ) +C [8] = { +C−1 [8] 1 ≤ 8 < C vC 8 = C
sC [8] = { max(0, sC−1 [8] −max(0, DC − ∑C−1
9=8+1 sC−1 [ 9])) 1 ≤ 8 < C 3C 8 = C
+0 is a 0 × < matrix s0 is a vector of size 0
rC = Reading(BC ) = C∑
8=1 (min(sC [8],max(0, 1 − C∑ 9=8+1 sC [ 9]))) · +C [8]
Yogatama et al. (2018) noted that the strafication stack can implement multiple pops per time step by allowing DC > 1, although the push action immediately following would still be conditioned on the
previous stack top rC . Hao et al. (2018) augmented this model with differentiable queues that allow it to buffer input and output and act as a transducer. Merrill et al. (2019) experimented with variations of this model where DC = 1 and 3C ∈ (0, 4), 3C = 1 and DC = (0, 4), and DC ∈ (0, 4) and 3C ∈ (0, 1).
A.2 Superposition stack
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 bha and bhv. The original definition also connects the controller to multiple stacks that push scalars; instead, we push a vector to a single stack, which is equivalent to multiple scalar stacks whose push/pop actions are synchronized. The original definition includes the top : stack elements in the stack reading, but we only include the top element. We also treat the value of the bottom of the stack as 0 instead of −1.
0C = Actions(hC ) = (aC , vC ) aC =  0 push C 0 noop C 0 pop C  = softmax(WhahC + bha) vC = f(WhvhC + bhv)
Stack(BC−1, 0C−1) = BC
BC [8] =  vC 8 = 0 0 push C BC−1 [8 − 1] + 0 noop C BC−1 [8] + 0 pop C BC−1 [8 + 1] 0 < 8 < C
0 8 = C rC = Reading(BC ) = BC [1]
Yogatama et al. (2018) developed an extension to this model called theMultipopAdaptive Computation Stack that executes a variable number of pops per time step, up to a fixed limit . They also restricted the stack to a maximum size of 10 elements, where the bottom element of a full stack is discarded when a new element is pushed; in other words, BC [8] = 0 for 8 > . Suzgun et al. (2019) experimented with a modification of the parameterization of aC and different softmax operators for normalizing the weights used to compute aC .

heading: B Details of formal language experiments
text: For every training run, we sample a training set of 10,000 strings from the PCFG, with lengths drawn uniformly from [40, 80]. Similarly, we sample a 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 are randomized for each experiment, the test sets are the same across all models and random restarts.
In all cases, the LSTM has a 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, we manually choose a small number of PDA states and stack symbol types based on how we would expect a 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 |& | = 3 and |Γ | = 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-entropy between the model and true distribution on the validation set. We use the same initialization and optimization settings as DuSell & Chiang (2020) and train for a maximum of 200 epochs.

heading: C Wall-clock training time
text: 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 on GPU due to the small model size. We ran experiments for the NS models in GPU mode on a pool of the following
NVIDIA GPU models, automatically selected based on availability: GeForce GTX TITAN X, TITAN X (Pascal), and GeForce GTX 1080 Ti.

heading: D Details of natural language experiments
text: The hyperparameters for our baseline LSTM, initialization, and optimization scheme are based on the unregularized LSTM experiments in Semeniuta et al. (2016). We train all models using simple stochastic gradient descent (SGD) as 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.05]. We divide the learning rate by 1.5 whenever the validation perplexity does not improve, and we stop training after 2 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 log-uniform distribution over [1 × 10−5, 1 × 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.125] and the gradient clipping threshold from [0.0112, 1.12].)

heading: E Additional results for natural language experiments
text: 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 in Hu et al. (2020), offering a 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. In 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 a poor choice for syntactic generalization.

Review summaries:
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.

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 

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.