Year: 2019

Abstract:
This paper proposes METAGROSS (Meta Gated Recursive Controller), a new neural sequence modeling unit. Our proposed unit is characterized by recursive parameterization of its gating functions, i.e., gating mechanisms of METAGROSS are controlled by instances of itself, which are repeatedly called in a recursive fashion. This can be interpreted as a form of meta-gating and recursively parameterizing a recurrent model. We postulate that our proposed inductive bias provides modeling benefits pertaining to learning with inherently hierarchically-structured sequence data (e.g., language, logical or music tasks). To this end, we conduct extensive experiments on recursive logic tasks (sorting, tree traversal, logical inference), sequential pixel-by-pixel classification, semantic parsing, code generation, machine translation and polyphonic music modeling, demonstrating the widespread utility of the proposed approach, i.e., achieving state-of-the-art (or close) performance on all tasks.

heading: 1 INTRODUCTION
text: Sequences are fundamentally native to the world we live in, i.e., language, logic, music and time are all well expressed in sequential form. To this end, the design of effective and powerful sequential inductive biases has far-reaching benefits across many applications. Across many of these domains, e.g., natural language processing or speech, the sequence encoder lives at the heart of many powerful state-of-the-art model architectures.
Models based on the notion of recurrence have enjoyed pervasive impact across many applications. In particular, the best recurrent models operate with gating functions that not only ameliorate vanishing gradient issues but also enjoy fine-grain control over temporal compositionality (Hochreiter & Schmidhuber, 1997; Cho et al., 2014). Specifically, these gating functions are typically static and trained via an alternate transformation over the original input.
In this paper, we propose a new sequence model that recursively parameterizes the recurrent unit. More concretely, the gating functions of our model are now parameterized repeatedly by instances of itself which imbues our model with the ability to reason deeply1 and recursively about certain inputs. To achieve the latter, we propose a soft dynamic recursion mechanism, which softly learns the depth of recursive parameterization at a per-token basis. Our formulation can be interpreted as a form of meta-gating since temporal compositionality is now being meta-controlled at various levels of abstractions.
Our proposed method, Meta Gated Recursive Controller Units (METAGROSS), marries the benefits of recursive reasoning with recurrent models. Notably, we postulate that this formulation brings about benefits pertaining to modeling data that is instrinsically hierarchical (recursive) in nature, e.g., natural language, music and logic, an increasingly prosperous and emerging area of research (Shen et al., 2018; Wang et al., 2019; Choi et al., 2018). While the notion of recursive neural networks is not new, our work is neither concerned with syntax-guided composition (Tai et al., 2015; Socher et al., 2013; Dyer et al., 2016) nor unsupervised grammar induction (Shen et al., 2017; Choi et al., 2018; Havrylov et al., 2019; Yogatama et al., 2016). Instead, our work is a propulsion on a different frontier, i.e., learning recursively parameterized models which bears a totally different meaning.
1This is meant literally.
Overall, the key contributions of this work are as follows:
• We propose a new sequence model. Our model is distinctly characterized by recursive parameterization of recurrent gates, i.e., compositional flow is controlled by instances of itself, á la repeatedly and recursively. We propose a soft dynamic recursion mechanism that dynamically and softly learns the recursive depth of the model at a token-level.
• We propose a non-autoregressive parallel variation of METAGROSS,that when equipped with the standard Transformer model (Vaswani et al., 2017), leads to gains in performance.
• We evaluate our proposed method on a potpourri of sequence modeling tasks, i.e., logical recursive tasks (sorting, tree traversal, logical inference), pixel-wise sequential image classification, semantic parsing, neural machine translation and polyphonic music modeling. METAGROSS achieves state-of-the-art performance (or close) on all tasks.

heading: 2 META GATED RECURSIVE CONTROLLERS (METAGROSS)
text: This section introduces our proposed model. METAGROSS is fundamentally a recurrent model. Our proposed model accepts a sequence of vectors X ∈ R`×d as input. The main unit of the Metagross unit ht = Metagrossn(xt, ht−1) is defined as follows:
fnt = σs(αt Metagrossn+1(xt, ht−1) + (1− αt) FFn (xt, ht−1)) ont = σs(βt Metagrossn+1(xt, h n t−1) + (1− βt) FOn (xt, ht−1))
znt = σr(F Z n (xt, ht)) cnt = (1− ft) ht−1 + (ft) zt hnt = ot ct hnt = ht + xt
where σr is a nonlinear activation such as tanh. σs is the sigmoid activation function. In a nutshell, the Metagross unit recursively calls itself until a max depth L is hit. When n = L, ft and ot are parameterized by:
fLt = σs(F F L (xt, ht−1))
oLt = σs(F O L (xt, ht−1))
where fLt , o L t is the forget and output gate of METAGROSS at time step t while at the maximum depth L. We also include an optional residual connection hnt = ht + xt to facilitate gradient flow down the recursive parameterization of METAGROSS.

heading: 2.1 SOFT DYNAMIC RECURSION
text: We propose learning the depth of recursion in a data-driven fashion. To learn αt, βt, we use the following:
αt = Fα(xt) and βt = Fβ(xt)
where F∗(xt) = Wxt + b is a simple linear transformation layer applied to sequence X across the temporal dimension. Intuitively, α, β control the extent of recursion, enabling a soft depth pertaining to the hierarchical parameterization. Alternatively, we may also consider a static variation where:
αt = Fα( ∑̀ t=0 xt) and βt = Fβ( ∑̀ t=0 xt)
where the same value of α, β is computed based on global information from the entire sequence. Note that this strictly cannot be used for autoregressive decoding. Finally, we note that it is also possible to assign α ∈ R, β ∈ R to be trainable scalar parameters.

heading: 2.2 LEVEL-WISE PARAMETERIZATION
text: Intuitively, F ∗n∀∗ ∈ F,O,Z are level-wise parameters of METAGROSS. We parameterize Fn with either level-wise RNN units or simple linear transformations.
F ∗n(xt) = RNN ∗ n(xt, h n t−1) or F ∗ n(xt) =W ∗ nxt + b ∗ n
Overall, METAGROSS is agnostic to the choice of F ∗n(xt) and even the RNN unit. Note that for RNN, the hidden states are initialized with zero and each level uses a new initial hidden state.

heading: 2.3 PARALLEL NON-AUTOREGRESSIVE VARIATION
text: We postulate that METAGROSS can also be useful as a non-autoregressive parallel model. This can be interpreted as a form of recursive feed-forward layer that is used in place of recurrent METAGROSS for speed benefits. In early experiments, we find this a useful enhancement to state-of-theart Transformer (Vaswani et al., 2017) models. The non-autoregressive variant of METAGROSS is written as follows:
fnt = σs(αt Metagrossn+1(xt) + (1− αt) FFn (xt)) ont = σs(βt Metagrossn+1(xt) + (1− βt) FOn (xt)) znt = σr(F Z n (xt)) hnt = (f n t xt) + (ot znt ) hnt = ht + xt
More concretely, we dispense with the reliance on the previous hidden state. This can be used in place of any position-wise feed-forward layer. In this case, note that F ∗n(xt) are typically positionwise functions as well.

heading: 3 EXPERIMENTS
text: We conduct experiments on a suite of diagnostic synthetic tasks and real world tasks.

heading: 3.1 LOGIC AND RECURSIVE TASKS
text: We evaluate our model on three diagnostic logical tasks as follows:
• Task 1 (SORT SEQUENCES) - The input to the model is a sequence of integers. The correct output is the sorted sequence of integers. Since mapping sorted inputs to outputs can be implemented in a recursive fashion, we evaluate our model’s ability to better model recursively structured sequence data. Example input output pair would be 9, 1, 10, 5, 3→ 1, 3, 5, 9, 10. • Task 2 (TREE TRAVERSAL) - We construct a binary tree of maximum depth N . The goal
is to generate the postorder tree traversal given the inorder and preorder traversal of the tree. Note that this is known to arrive at only one unique solution. The constructed trees have random sparsity where we assign a probability p of growing the tree up to maximum
depth N . Hence, the trees can be of varying depths2. This requires inferring hierarchical structure and long-term reasoning across sequences. We concatenate the postorder and inorder sequences, delimiteted by a special token. We evaluate on n ∈ {3, 4, 5, 8, 10}. For n = {5, 8}, we ensure that each tree traversal has at least 10 tokens. For n = 10, we ensure that each path has at least 15 tokens. Example input output pair would be 13, 15, 4, 7, 5, X, 13, 4, 15, 5, 7→ 7, 15, 13, 4, 5.
• Task 3 (LOGICAL INFERENCE) - We use the standard logical inference dataset3 proposed in (Bowman et al., 2014). This is a classification task in which the goal is to determine the semantic equivalence of two statements expressed with logic operators such as not, and, and or. The language vocabulary is of six words and three logic operators. As per prior work (Shen et al., 2018), the model is trained on sequences with 6 or less operations and evaluated on sequences of 6 to 12 operations.
For Task 1 and Task 2, we frame these tasks as a Seq2Seq (Sutskever et al., 2014) task and evaluate models on exact match accuracy and perplexity (P) metrics. We use a standard encoder-decoder architecture with attention (Bahdanau et al., 2014). We vary the encoder module with BiLSTMs, Stacked BiLSTMs (3 layers) and Ordered Neuron LSTMs (Shen et al., 2018). For Task 3 (logical inference), we use the common setting in other published works.
Results on Sorting and Tree Traversal Table 1 reports our results on the Sorting and Tree Traversal task. All models solve the task with n = 3. However, the task gets increasingly harder with a greater maximum possible length and largely still remains a challenge for neural models today. The relative performance of METAGROSS is on a whole better than any of the baselines, especially pertaining to perplexity. We also found that S-BiLSTMs are always better than LSTMs on this task and Ordered LSTMs are slightly worst than vanilla BiLSTMs. However, on sorting, ON-LSTMs are much better than standard BiLSTMs and S-BiLSTMs.
# Operations Model 7 8 9 10 11 12 Tree-LSTM† (Tai et al., 2015) 93 90 87 89 86 87 LSTM (Bowman et al., 2014) 88 85 80 78 71 69 RRNet (Jacob et al., 2018) 84 81 78 74 72 71 ON-LSTM (Shen et al., 2018) 91 87 86 81 78 76 METAGROSS 97 95 93 92 90 88
Table 2: Experimental results on Logical Inference task. † denotes models with access to ground truth syntax. Results reported from (Shen et al., 2018). METAGROSS achieves state-of-the-art performance.
Results on Logical Inference Table 2 reports our results on logical inference task. We compare with mainly other published work. METAGROSS is a strong and competitive model on this task, outperforming ON-LSTM by a wide margin (+12% on the longest nunber of operations). Performance of our model also exceeds Tree-LSTM, which has access to ground truth syntax. Our model achieves state-of-the-art performance on this dataset even when considering models with access to syntactic information.
2Note that all our models solves the problem entirely when the tree is fixed and full. Hence, random trees provide a necessary challenge.
33https://github.com/sleepinyourhat/vector-entailment.

heading: 3.2 PIXEL-WISE SEQUENTIAL IMAGE CLASSIFICATION
text: We evaluate our model on its ability to model and capture long-range dependencies. More specifically, the sequential pixel-wise image classification problem treats pixels in images as sequences. We use the well-established pixel-wise MNIST and CIFAR-10 datasets. We use 3 layered METAGROSS of 128 hidden units each.
Model |θ| MNIST CIFAR DilatedGRU (Chang et al., 2017) - 99.00 - IndRNN (Li et al., 2018a) - 99.00 - r-LSTM (Trinh et al., 2018) - 98.52 72.20 Transformer (Trinh et al., 2018) - 98.90 62.20 TrellisNet (Bai et al., 2018b) 8.0M 99.20 73.42 TrellisNet (Our run) 8.0M 97.59 55.83 METAGROSS 0.9M 99.04 73.01 METAGROSS] 0.9M 99.09 73.95

heading: 3.3 SEMANTIC PARSING / CODE GENERATION
text: We evaluate METAGROSS on semantic parsing (GEO, ATIS, JOBS) and code generation (DJANGO). We run our experiments on the publicly released code4 of (Yin & Neubig, 2018), replacing the recurrent decoder with our METAGROSS decoder. Hyperparameter details followed the codebase of (Yin & Neubig, 2018) quite strictly.
the ablative benefits of METAGROSS.

heading: 3.4 NEURAL MACHINE TRANSLATION
text: We conduct experiments on two IWSLT datasets which are collections derived from TED talks. Specifically, we compare on the IWSLT 2014 German-English and IWSLT 2015 EnglishVietnamese datasets. We compare against a suite of published results and strong baselines. For our method, we replaced the multi-head aggregation layer in the Transformer networks (Vaswani et al., 2017) with a parallel non-autoregressive adaptation of METAGROSS. The base models are all linear layers. For our experiments, we use the standard implementation and hyperparameters in Tensor2Tensor5 (Vaswani et al., 2018), using the small (S) and base (B) setting for Transformers. Model averaging is used and beam size of 8/4 and length penalty of 0.6 is adopted for De-En and En-Vi respectively. For our model, max depth is tuned amongst {1, 2, 3}. We also ensure to compare, in an ablative fashion, our own reported runs of the base Transformer models.
4https://github.com/pcyin/tranX 5https://github.com/tensorflow/tensor2tensor
Model BLEU (Luong & Manning, 2015) 23.30 Att-Seq2Seq (Bahdanau et al., 2014) 26.10 NPMT (Huang et al., 2017) 27.69 NPMT + LM (Huang et al., 2017) 28.07 Transformer B (Vaswani et al., 2017) 28.43 Transformer B + METAGROSS 30.81
Table 6: Experimental results on Neural Machine Translation on IWSLT 2015 En-Vi.
Results on Neural Machine Translation Table 5 reports results on IWSLT 2014 de-en task. Our proposed model performs very competitively (37.09 BLEU), outperforming many well-established baselines. Our results also show that equipping Transformer models with METAGROSS can also lead to improvements in performance. Notably there is a +0.69 BLEU improvement on Transformer Base and +0.42 BLEU improvement for Transformer Small. On the other hand, our method achieves 30.81 BLEU on the IWSLT 2015 En-Vi dataset, with +2.38 improvement in BLEU from the standard Transformer Base model.

heading: 3.5 POLYPHONIC MUSIC MODELING
text: We evaluate METAGROSS on the polyphonic music modeling. We use three well-established datasets, namely Nottingham, JSB Chorales and Piano Midi (Boulanger-Lewandowski et al., 2012). The input to the model are 88-bit sequences, each corresponding to the 88 keys of the piano. The task is evaluated on the Negative Log-likelihood (NLL). We compare with a wide range of published works (Chung et al., 2014; Bai et al., 2018a; Song et al., 2019)

heading: 3.6 ANALYSIS AND DISCUSSION
text: This section reports some analysis and discussion regarding the proposed model.

heading: 3.6.1 EFFECT OF MAXIMUM DEPTH AND BASE UNIT
text: Table 8 reports some ablation studies on the semantic parsing and code generation tasks. We observe that the base unit and optimal maximum depth used is task dependent. For ATIS dataset, using the linear transform as the base unit performs the best. Conversely, the linear base unit performs worse than the recurrent base unit (LSTM) on the DJANGO dataset.
On a whole, we also observed this across other tasks, i.e., the base unit and maximum depth of METAGROSS is a critical choice for most tasks. Table 9 reports the optimal max depth N and best base unit for each task.

heading: 3.6.2 ANALYSIS OF SOFT DYNAMIC RECURSION
text: Figure 6 illustrates the depth gate values on CIFAR and MNIST datasets. These values reflect the α and β values in METAGROSS, signifying how the parameter tree is being constructed during training. This is reflected as L and R in the figures representing left and right gates. Firstly, we observe that our model indeed builds data-specific parameterization of the network. This is denoted by how METAGROSS builds different6 trees for CIFAR and MNIST.
Figure 7: Dynamic Recursion on CIFAR.
recursion over time if necessary. We find that compelling.
0 50 100 150 200 250 Temporal
0.0
0.2
0.4
0.6
0.8
Ac tiv
at io
n
L R LL LR RL RR LLR LLL RRL RRR
Figure 8: Dynamic Recursion on Music.
6Though not depicted, we also found that the probability of each node expanding to children has low variance across batches in the same dataset.
The adaptive recursive depth is made more intriguing by observing how the recursive parameterization alters on CIFAR and Music datasets. From Figure 8 we observe that the structure of the network changes in a rhythmic fashion, in line with our intuition of musical data. When dealing with pixel information, the tree structure changes adaptively according to the more complex information processed by the network.

heading: 4 RELATED WORK
text: The study of effective inductive biases for sequential representation learning has been a prosperous research direction. This has spurred on research across multiple fronts, starting from gated recurrent models (Hochreiter & Schmidhuber, 1997; Cho et al., 2014), convolution (Bai et al., 2018a) to the recently popular self-attention based models (Vaswani et al., 2017).
The intrinsic hierarchical structure native to many forms of sequences have long fascinated and inspired many researchers (Socher et al., 2013; Bowman et al., 2014; 2016; Dyer et al., 2016). The study of recursive networks, popularized by (Socher et al., 2013) has provided a foundation for learning syntax-guided composition in language processing research. Along the same vein, (Tai et al., 2015) proposed Tree-LSTMs which guide LSTM composition with grammar. Recent attempts have been made to learn this process without guidance nor syntax-based supervision (Choi et al., 2018; Shen et al., 2017; Havrylov et al., 2019; Yogatama et al., 2016). Ordered Neuron LSTMs (Shen et al., 2018) proposed structured gating mechanisms, imbuing the recurrent unit with a tree-structured inductive bias. (Tran et al., 2018) shows that recurrence is important for modeling hierarchical structure. Notably, learning hierachical representations across multiple time-scales (El Hihi & Bengio, 1996; Schmidhuber, 1992; Koutnik et al., 2014; Chung et al., 2016; Hafner et al., 2017) have also demonstrated reasonable success.
Learning an abstraction and controller over a base recurrent unit is also another compelling direction. First proposed by Fast Weights (Schmidhuber, 1992), several recent works explore this notion. HyperNetworks (Ha et al., 2016) learns to generate weights for another recurrent unit, i.e., a form of relaxed weight sharing. On the other hand, RCRN (Tay et al., 2018) explicitly parameterizes the gates of a RNN unit with other RNN units. Recent attempts to speed up the recurrent unit are also reminiscent of this particular notion (Bradbury et al., 2016; Lei et al., 2018).
The marriage of recursive and recurrent architectures is also notable. This direction is probably the closest relevance to our proposed method, although with vast differences. (Liu et al., 2014) proposed Recursive Recurrent Networks for machine translation which are concerned with the more traditional syntactic supervision concept of vanilla recursive nets. (Jacob et al., 2018) proposed RRNet, which learns hierarchical structures on the fly. RR-Net proposes to learn to split or merge nodes at each time step, which makes it reminiscent of (Choi et al., 2018; Shen et al., 2018). (AlvarezMelis & Jaakkola, 2016) proposed doubly recurrent decoders for tree-structured decoding. The core of their method is a depth and breath-wise recurrence which is similar to our model. However, METAGROSS is concerned with learning gating controllers which is different from the objective of decoding trees.
Our work combines the idea of external meta-controllers (Schmidhuber, 1992; Ha et al., 2016; Tay et al., 2018) with recursive architectures. In particular, our recursive parameterization is also a form of dynamic memory which gives our model improved expressiveness in similar spirit to memoryaugmented recurrent models (Santoro et al., 2018; Graves et al., 2014; Tran et al., 2016).

heading: 5 CONCLUSION
text: We proposed Meta Gated Recursive Controller Units (METAGROSS) a sequence model characterized by recursive parameterization of gating functions. Our proposed method achieves very promising and competitive results on a spectrum of benchmarks across multiple modalities (e.g., language, logic, music). We propose a non-autoregressive variation of METAGROSS, which allows simple drop-in enhancement to state-of-the-art Transformers. We study and visualise our network as it learns a dynamic recursive parameterization, shedding light on the expressiveness and flexibility to learn dynamic parameter structures depending on the data.

Review summaries:
The authors propose a variant of gating functions for recurrent neural networks and feed-forward layers of Transformer and apply it to variety of tasks including toy tasks such as sorting, tree traversal and more realistic tasks such as machine translation. The gating function is applied recursively for N number of steps and depth of recursion is learned softly in data-driven function. Authors show similar or slightly better performance of their approach when applied to LSTM and Transformer compared to vanilla LSTM and Transformer.  

This paper proposes a neural sequence modelling unit called METAGROSS.  In principle, the aim of this unit is to introduce recursive parametrization of  gating functions, building on the gated RNN paradigm.  The authors motivate this work by arguing that while gated-RNNs tackle vanishing gradient problems and facilitate learning long-range dependencies in sequences, improvements can be made with respect to learning on hierarchically-structured data.  The authors propose a method to do so by also learning the depth of the parametrization, and claim that the inductive bias that emerges from this configuration is beneficial to learning such tasks.