Reducing Computation in Recurrent Networks by Selectively Updating State Neurons
Authors: Thomas Hartvigsen
Cansu Sen
Xiangnan Kong
Elke Rundensteiner
Venue:  (2020)
Keywords: recurrent neural networks
conditional computation
representation learning

Abstract: Recurrent Neural Networks (RNN) are the state-of-the-art approach to sequential learning. However, standard RNNs use the same amount of computation at each timestep, regardless of the input data. As a result, even for high-dimensional hidden states, all dimensions are updated at each timestep regardless of the recurrent memory cell. Reducing this rigid assumption could allow for models with large hidden states to perform inference more quickly. Intuitively, not all hidden state dimensions need to be recomputed from scratch at each timestep. Thus, recent methods have begun studying this problem by imposing mainly a priori-determined patterns for updating the state. In contrast, we now design a fully-learned approach, SA-RNN, that augments any RNN by predicting discrete update patterns at the fine granularity of independent hidden state dimensions through the parameterization of a distribution of update-likelihoods driven entirely by the input data. We achieve this without imposing assumptions on the structure of the update pattern. Better yet, our method adapts the update patterns online, allowing different dimensions to be updated conditional to the input. To learn which to update, the model solves a multi-objective optimization problem, maximizing accuracy while minimizing the number of updates based on a unified control. Using publicly-available datasets we demonstrate that our method consistently achieves higher accuracy with fewer updates compared to state-of-the-art alternatives. Additionally, our method can be directly applied to a wide variety of models containing RNN architectures.

Under review as a conference paper at ICLR 2020
REDUCING COMPUTATION IN RECURRENT NET- WORKS BY SELECTIVELY UPDATING STATE NEURONS
Anonymous authors Paper under double-blind review
ABSTRACT
Recurrent Neural Networks (RNNs) are the state-of-the-art approach to sequential learning. However, standard RNNs use the same amount of computation at each timestep, regardless of the input data. As result, even for high-dimensional hidden states, all dimensions are updated at each timestep no matter the choice of recurrent memory cell. Reducing this rigid assumption could allow for models with large hidden states to perform inference more quickly. Intuitively, not all hidden state dimensions need to be recomputed from scratch at each timestep. Thus, recent methods have begun studying this problem by imposing mainly a priori-determined patterns for updating the states at each step. In contrast, we now design a fully- learned approach, SA-RNN, that augments any RNN by predicting discrete update patterns at the fine granularity of independent hidden state dimensions. This is achieved through the parameterization of distribution of midate-likeelhhodds driven by the input data. Notably, through this approach we impose no assumptions on the structure of the update pattern. Better yet, our method adapts the update patterns online, allowing different dimensions to be updated conditional to the input. To learn which dimensions to update, the model solves a multi-objective optimization problem, maximizing task performance while minimizing the number of updates based on a unified control. Using publicly-availabl datasets we demonstrate that our method consistently achieves higher accuracy with fewer updates compared to tfate-oftthe-ar the-art alternatives. Additionally, our method can be directly applied to a wide variety of models containing RNN architectures.
INTRODUCTION
Recurrent Neural Networks (RNN) are the state-of-the-ar approach to many sequential learning problems including speech recognition (Graves et al., 2013). machine translation (Bahdanau et al., 2015), and sequence generation (Graves, 2013; Xu et al., 2015). However, RNNs typically rely on computationaally-taxiin
updates to their entire hidden state each timestep, cost that grows with hidden state size. As demonstrated by the success of gating mechanisms such as the GRU (Cho et al., 2014) and L.STM (Hochreiter & Schmidhuber, 1997), all dimensions rarely need to be re-computed from scratch at each timestep. By discretely selecting which dimensions to update at each timestep via learned update pattern, RNNs with a large hidden state can be trained with lower computational requirements (Bengio et al., 2013), inference in long RNNs can be expedited (Campos et al., 2018) 8), and hidden representations may be made more robust to misleading inputs such as outliers or noise.
Selective neuron activation in RNNs has recently gained attention in the literature (Koutnik et al., 2014; Neil et al., 2016; Shen et al., 2019; Jernite et al., 2017: Campos et al., 2018). The most popular methods hand-craft specific update patterns, dictating which dimensions of the hidden state will update at which timesteps according to prior knowledge of a task (Koutnik et al., 2014; Neil et al., 2016). This imposes undue challenges in implementation, limits extensibility, and ignores the data-driven curation of information-flow through the RNN, a signature property of recurrent memory cells (Hochreiter & Schmidhuber, 1997; Cho et al., 2014). More recent methods learn to react to input data but impose strict relationships between the update patterns across both hidden dimensions and time (Shen et al., 2019; Jernite et al., 2017; Campos et al., 2018). While applicable to tasks with clear hierarchical components, such as modeling character- text (Chung et al., 2017), these assumptions limit the expressiveness of the learned update patterns.

---

Under review as a conference paper at ICLR 2020
Specifically, we study the problem of generating a binary update-pattem for the hidden states learned by an RNN. The learned update-patted each timestep, similar to the motivation for Residual Networks (He et al., 2016; Wang & Tian, 2016) and Highway Networks (Srivastava et al., 2015; Zilly et al., 2017). Ideally, only a small subset of the hidden state's dimensions needs to be updated at each timestep, especially with high-dimensional hidden states, In this way, representations can be learned while both solving sequential learning task and minimizing the number of updates. This results reduction of the compute time. A solution to this nulti-objective optimization problem should have a comparable accuracy to a traditional constantlyuuddation RNN but save the majority of computation steps along the way, ultimately accelerating inference and training (Neil et al., 2016).
defines which dimensions of the hidden state to update at
Despite the potential for reducing computation required by RNNs, learning said update patterns is challenging problem. First, binary-output neurons making discrete decisions (whether or not to update hidden state dimension, for example) in the interior of a neural network is a classic challenge to gradient-based learning. This is because such decisions are non-differentiable by nature and therefore backpropagation cannot be directly used to update the weights. Second, the quality of a learned update pattern is unsupervised and thus the only feedback is task-specific. This discourages priori assumptions of the update patterns.
To address the aforementioned challenges, we propose the selective activation RNN, SA-RNN which parameterizes a distribution of update-iikelihoods, one per hidden state dimension, from which update-decistee -ecate-decissoos can be made at each timestep. We augment RNN with an update coordinator that adaptively controls which coordinate directions to update in the hidden state on the fly. The coordinator is modeled as a lightweight neural network that observes incoming data at each timestep and makes a discrete decision of whether or not enough information is stored in each individual hidden dimension to warrant an update. Subsequently, each hidden dimension is either computed by the RNN or copied from the previous timestep. The coordinator's 's architecture is kept as simple as possible so the complexity of the RNN can scale without simply outsourcing computation to another network, similar to the controller in Ha & Schmidhuber (2018). Most notably, in contrast to other recent approaches (Koutnik et al., 2014; Jernite et al., 2017: Neil et al., 2016; Campos et al., 2018; Shen et al., 2019; Liu et al., 2018) we impose assumptions of which individual hidden dimensions should update (or not update) together. Instead, we show that using an antirely-learned approach still results in complex task-specific update patterns. On three aublicly-availabbe datasets, show that our low-bias approach achieves higher accuracy with far fewer updates than recent state-of-the-e methods (Koutnik al., 2014; Jernite al., 2017; Neil al., 2016; Campos et al., 2018). These results indicate that predicting RNN update-patterns solely with respect to a task is not only feasible and lia,, but also favorable in a variety of settings.
RELATED WORK
Recurrent neuron update patterns have gained much interest in recent literature (Koutnik et al., 2014; Jernite et al., 2017; Neil et al., 2016; Chung et al., 2017; Shen et al., 2019; Liu et al., 2018). All of these methods boast fewer updates the hidden states than standard RNN architectures. However, there are several limitations of these methods, two of which are summarized as follows.
First, the most popular methods rely on extensively-handerafeed update patterns consisting of periodic neuron activations (Koutnik et al., 2014; Neil et al., 2016; Liu et al., 2018). This requires either prior knowledge of sampling frequencies or seasonal patterns present in the data, reducing the potential extension to many sequential learning problems. Additionally, these input-agnostic periodic updates are fixed prior to learning. The choice of update periods heavily impacts the performance of the model, and sequences with irregular information flow cannot be modeled without massive state representations.
Second, the most recent works allow for data-reactive update patterns (Jernite et al., 2017; Shen et al., 2019; Campos et al., 2018) but assume temporal hierarchies in the input sequences and study settings where this effect is exceedingly obvious (for example, character-level sentence modeling (Chung et al., 2017)). In many real-world settings, temporal hierarchies are often subtle and forcing this assumption into the architectural design may limit its applications.
2

---

Under review as a conference paper at ICLR 2020
Recurrence Function
Update
Copy
ht-1
h
Xt
Coordinator
Figure 1: Overview of SA-RNN. h is the hidden state at timestep 1. Prior to computing ha- the update coordinator decides which hidden dimensions will be updated according 2a and its previous update decisions. According to the decision in this figure, for example, hidden dimension 1 updated while hidden dimension 2 remains unchanged.
Additionally, our approach is related to conditional computation, which predicts subsets of neural networks to activate depending on input data (Bengio et al., 2015; Shazeer et al., 2017; Cheng et al., 2017). In many cases, when a particular concept be represented using only the sub-network of large neural network, computation can preserved by learning the structure of said sub-network (Schmidhuber, 2012) and activating it accordingly.
3 SELECTIVE NEURON ACTIVATION FOR RNNS
We introduce the Selective-Activatte RNN, or SA-RNN, a broadly augmentation to RNNs which minimizes the computation required for RNNs by facilitating unimpeded information- flow across timesteps for individual dimensions of the hidden state. At its core, SA-RNN learns a data-driven strategy for discretely reading and writing information the latent state space through distribution. Despite leaving hidden dimension
the learned parameterization of an update-likelikee update patterns independent from one another, complex strategies still arise naturally depending on the sequential learning task at hand. In this section, we describe the training process of SA-RNN with D-dimensional hidden states on sequences of length T for input data æ with V variables. We omit biases from affine transformation equations and use notation for one training instance for ease of readability. An overview of the forward pass through SA-RNN is shown in Figure
3.1 COMPUTING HIDDEN STATES
RNNs compute sequence of hidden states one timestep at a time (Elman, 1990), each computed by parametric recurrence function R(-)): h R(h--1, (0,). The result is sequence of vector representations = (hi....,hy where each ht e I represents temporal dynamics of the time series up to timestep é with respect to task, preserving not only temporal dependencies but also the ordering the inputs.
A popular and powerful augmentation to the RNN, as it originally proposed, is the Gated Recurrent Unit (GRU) (Cho et al., 2014), which adds a series of gates between h4-1 and h2 to alleviate the vanishing gradient problem (Bengio al., 1994):
r2 OWWhu- 1 + UT.r))
(1)
21 a aWah, + Ugat)
S: d(Waz + Uc(rt O h2-1))
(3)
h (1 21) h 24
3

---

Under review as a conference paper at ICLR 2020
where Ws and Us are matrices of learnable parameters of shape D x D and D x V respectively, Iy E RY is the input data at timestep t. @ represents the element- wise multiplication, o represents the sigmoid function, and & represents a non-linearity (traditionally the hyperbolic tangent function). Its design is motivated heavily by the LSTM (Hochreiter & Schmidhuber, 1997). The GRU performs soft read/write operations, recomputing the entire vector h each timestep since gate E [0, 1]2, the space of vectors with values inclusively between 0 and 1. Instead, we propose that all dimensions do not need to be updated at each timestep, as the position of the hidden state in many dimensions may often encode enough of the modeled input. Note that the output of the recurrence function is referred to as h4. In the next section, we describe how to compute h1, the final hidden state for timestep which is subsequently used for computing h4+1 or the task.
3.2 SELECTIVE NEURON ACTIVATION
To reduce computation required to generate state representations, we assume updating representations to be a sequence of binary decisions at each timestep a neuron will either be updated or not. Thus, we propose learned update coordinator, which generates binary mask for each hidden dimension, forecasting which dimensions need to be updated at the next timestep. First, an update- likelihood d is computed for each neuron, informed by both the data observed the current timestep and the previous
Ut = ((W.ha- + W,r+) where W., E RDD D is a diagonal matrix of trainable parameters which dictate the linear relationship between ht- and ūt. W. is kept diagonal to maintain relationships between update-decisions of the same dimension while avoiding the extensive computation of fully-connected layer, similar the hidden state decay in Che et al. (2018). W; E IR PxV encodes the influence of the input data on the current update-likellhood likelihood and ( represents the hard sigmoid function. bounding ū according to a slope a. Thus ūn E [o, 1]" with one update-
per dimension of the hidden state.
To discretize üt allowing information to flow unimpeded, sement-wiise binarization is applied:
Ut binarize (Q)). where
(5)
a > 0.5,
binarize(a) () otherwise.
(6)
We apply this final discrete update decision as a binary gating mechanism since un E {0, P:
hr un he (1 we) h4-1
As written, this equation requires the pre-computation of heg However, through masking the computa- tion can be directed at only the needed updates upon calculation of u, Thus when ūf" the update decision for the n-th dimension in h, is 1, he is updated according to the new information present in hy. We note that this update-decision strategy does not impose the inter-neuron assumptions of Jernite et al. (2017); Shen et al. (2019); Koutnik et al. (2014) while still allowing such strategies to be learned if they are found to be optimal by the model since decisions are made with respect to previous decisions, similar to Campos et al. (2018). We hypothesize that updating neurons together may generally be beneficial since complex temporal dependencies often require representations evolving in blocks of multiple neurons, as discussed in Koutnik et al. (2014).
Since binary-output neurons are inherently non-differentiable. barring the direct use of back- propagation, we approximate the gradient of the binarization function using the straight-through gradient estimator (Bengio et al., 2013) trained with slope-annealing (Chung et al., 2017):
Abinarize(z) Ox
1.
(8)
By estimating the gradient in this way we avoid additional loss terms and end up with empirically- reasonable approximations in comparison to other high-variance methods, such as REINFORCE (Williams, 1992; Chung et al., 2017; Campos et al., 2018). After computing the sequence of state representations H, they projected into the output space depending the task at hand.
3.3 TRAINING
All weights of SA-RNN are updated together using preepppppagttion to minimize one loss function. For readability we gather all weights into one parameter matrix 0. Our loss function [()) consists of
4

---

Under review as a conference paper at ICLR 2020
two parts: task-driven loss (denoted as Lusk) and update- budget. The task component may be be cross entropy for classification or possibly mean squared error for regression. The update- budger encourages sparser updates the hidden dimensions, as shown in Equation 9 where N is the number of training examples, ÿ is the model's prediction, and y is the label.
T
Crask(V'. Σ ( N 2=1
(9)
À tunes the emphasis on the minimization of u, the update probability, and in practice it is reasonable set À = 0, encouraging the model to make update decisions solely with respect to the learning task. As À is increased and update likelihoods decrease, the hidden dimension is update fewer times until eventually hg = hur where the hidden state not updated all.
EXPERIMENTS
4.1 DATASETS
We conduct our evaluation using three classification tasks on the following datasets, each being publicly-availabe.
Sei zeres's 1 (Andrzejak et al., 2001): From 11,800 178-timestep time series, the task is to detect which EEGs contain evidence of epileptic seizure activity. Since there are only 2,300 cases of such activity. we down-sample an equal number from the negative class, resulting in a balanced dataset with 4,600 time series. Finally, we center the time series around zero and compute the mean value of every 10-timestep chunk, summarizing each series into 17 final timesteps.
Twi TwitterRuzz? (Kawala et al., 2013): To predict buzz events on Twitter, we work with 77- dimensional time series with labels indicating whether or not spike in tweets on a particular topic is observed. Starting with over 1 140,000 timesteps, we compute the mean of every five steps, center the time series around zero, and break the resulting 28,000 timesteps into 2,800 length- 15 sequences. We then extract the 776 time series containing any buzz events and balance the dataset by randomly selecting equal number of no-buzz time series, resulting in 1552 labeled time series.
Yahoo:: We re-frame this outlier detection dataset as a classification problem: whether or not a sequence contains anomaly. We begin by chunking the time series into subsequences of length 25. Then, we create a balanced dataset by selecting all subsequences with anomalies present along with an equal number of andomly-selecteed subsequences with anomalies to serve our negative class. Thus we end up with a dataset containing 418 length-25 time series.
4.2 SETTINGS
Baselines.
To evaluate the performance of SA-RNN, we compare with five recent state-of-the-ar related methods:
Random Skips: This method is effectively the random version of proposed method. At each step, random hidden dimensions are updated. This is similar to Zoneout (Krueger et al., 2017) however we maintain random updating during testing.
Clockwork RNN (Koutnik et al., 2014): Hidden dimensions are updated in groups at pre- determined "clock" rates. For example, the first five dimensions in the hidden state may update every step while the second five neurons update every 3 steps.
Phased LSTM (Neil et al., 2016): Hidden dimensions are updated independently at sampled "clock" rates where the user defines the distribution from which sample. Each hidden dimension has its own update pattern.
VC-GRU (Jernite al., 2017): A value p E [0, 1] is predicted each step indicating the proportion of the representation to update. Then, the first p D dimensions are updated, imposing hierarchical structure to the update patterns.
5

---

Under review as a conference paper at ICLR 2020
Nourons
Neurons
Neurons
Neurons
Neurons
Neurons
Timesteps
Timesteps
immestess
Timesteps
Timesteps
Timesteps
(a) Random
(b) CW-RNN
(c) Phased LSTM
(d) SkipRNN
(e) VC-GRU
(i SA-RNN
Figure 2: Sample skipping patterns from compared methods for the seizures task with 50- dimensional state representations. Black squares indicate update while white squares indicate skip.
SkipRNN (Campos et al., 2018): Hidden dimensions update in loek-step with one another the entire hidden state is either modified or left unchanged at each step. Additionally, the update likelihoods increase monotonically, regardless of input data.
Implementation Details.
For all experiments, we use an 80% training, 10% validation, and 10% testing dataset split. The training data used
the parameters of the models; the validation data used to validate hyperparameter selection; the testing data are used to report final performances. We randomly repeat this process ten times compute confidence intervals for performance metrics. Across all models we fix the size of state representations to be fifty neurons. Keeping this number fixed allows us to purely compare performance of the update-pattes patttess observed in alternative algorithms. For selection in SkipRNN and our proposed method, SA-RNN, we search in a log-space ranging from 0.0 to 0.1 in 11 steps. For all methods, we choose the same learning rate le -03 after log-space search ranging from -e to le 1e-01 likely due to similarities behind the core of the sequential learning (RNNs with equal state representation sizes). We optimize all models using Adam (Kingma & Ba, 2014). While describe our method in the case of the GRU, may also be directly applied to other gating mechanisms such as the LSTM. We implement slope annealing following the setting described in Chung et al. (2017). The code for method is available at https: / //ii ieiddddfff revveiieee com.
4.3 EXPERIMENTAL. RESULTS
Contrasting update patterns of alternative algorithms. First, we inspect the opdate-pattemn generated by each baseline algorithm, as shown in Figure 4. Both PhasedLSTM and VC-GRU use partial updates, and do not make fully-binary update decisions. For this visualization we binarize their update patterns using ceiling function on non-zero update decisions since the neurons still updated. Importantly, all algorithms are subject to update-budgets, which clearly effect the observed patterns. For example, since the SkipRNN updates all neurons at the same time, deciding to update has a large cost, eating through the update budget quickly. Meanwhile, other methods such as our own SA-RNN and the SSaMedL.STMM take much smaller bites into the update budget since the neurons are updated independently. From these visuals, it clear that ours the only method which can adaptively learn update independent neurons for many steps at time, according to the data. Thus, some neurons may update a few times in the middle of the sequence instead of the beginning end, decision which is driven directly by the data. This allows method to spend its computational budget in a more informed way, choosing to activate some neurons many times in row, while leaving others unchanged.
Comparing accuracy and update-frequency across methods. Second, we show results from the three tasks described in Section 4.1. We measure four properties of

---

Under review as a conference paper at ICLR 2020
Method
Acc. x Skip%
Skip(%)
Accuracy (%)
FLOPs
GRU (Cho al., 2014)
0
84.7 (0.8)
257550
CW-RNN (Koutnik et al., 2014)
73.7
81
67.1 (0.4)
16150
PhasedLSTM (Neil et al., 2016)
74.9
69
81.4 (1.4)
106454
VC-GRU (Jemitt al., 2017)
68.7
66
71.6 (3.4)
89284
SkipRNN (Campos et al., 2018)
69.2
82
58.4 (5.5)
48042
Random Skips
62.3
76
51.1 (0.1)
61812
SA-RNN
78.8
76
81.6 (0.6)
63512
Table 1: Performance on the Sei zures task. v Accuuracy x Skip% the geometric mean of Accuracy and Skip Percent. The first section contains the baseline GRU, the second contains non- reactive methods, the third contains learned methods, and the fourth our proposed method and random bascline. For SA-RNN we use À = 2e
Method
V Acc. Skip%
Skip (%)
Accuracy (%)
FLOPs
GRU (Cho et al., 2014)
0
64.8 (1.6)
378750
CW-RNN (Koutnik et al., 2014)
68.2
81
57.4 (1.9)
23750
PhasedI.STM (Neil et al., 2016)
65.3
70
60.9 (4.0)
151500
VC-GRU (Jernite et al., 2017)
62.9
66
59.9 (2.8)
131300
SkipRNN (Campos et al., 2018)
69.2
88
54.4 (8.1)
47925
Random Skips SA-RNN
72.2
89
58.6 (1.9)
41662
75.0
89
63.1 (1.8)
44162
Table 2: Performance the Yahoo task. For SA-RNN we use À 1e-3
each method. 1) Skip Percent - the proportion of neurons which are not updated, computed across all timesteps. To make fair comparison between all methods, we tune their hyperparameters so that their skip percents are as close together as possible, This allows us to better analyze the effects of the differences in update patterns instead of changing the hidden state dimension sizes. Accuracy- the accuracy achieved on the task. For each task we use balanced datasets, so the lower bound is 50%. 3)
/ /Accuracy x Skip% the geometric mean of a model's 's accuracy and skip percent. The measure allows comparison all methods since they do not all update the exact same number of times. Thus, this is the key performance metric, the upper and lower limits of which are 1.0 and 0.0, respectively, 4) FLOPs - as Campos et al. (2018) we compute the FLOPs for each method as a surrogate for wall-clock time, which is hardware- dewendeen and often fluctuates dramatically in practice.
Across all tasks, SA-RNN achieves on average higher accuracy with fewer updates, as shown in Tables 1, and 3. In Yahoo and TwitterBuzze SA-RNN maintains by far the closest accuracy that the baseline GRU, which updates every hidden dimension at every timestep. In Se zu zures, both SA-RNN and PhasedLSTM are similar the GRU, possibly due to periodic dynamics in the data. We also show in Tables 1 and 3, the accuracy of Random Skips is far worse than SA-RNN, indicating that the benefits of our proposed update-strategy comes strongly from the learning. The benefits of adaptive update patterns are not present in the Clockwork RNN or PhasedLSTM.
SA-RNN has eeuril-equivalent FLOPs to the other methods that learn update patterns since each adds another affine transformation to map data to update decisions. As shown in Table 3, adapting the update decisions according to the input data adds significant amount of computation with high- dimensional inputs. To improve this, update patterns may be predicted for multiple steps concurrently, depending on the input data. Given the same number of updates, the FLOPs are roughly equivalent between our method, VC-GRU, and SkipRNN. As in Campos et al. (2018), it may be possible to only observe the previous hidden state, however this results in perpetual lag as information fills the hidden state. CW-RNN consistently has extremely low FLOPs since there is no data-driven decision making in the update patterns, instead hard-coding them beforchand. Additionally, their recurrence function not gated recurrent memory cell.
7

---

Under review as a conference paper at ICLR 2020
Method
v Acc. Skip%
Skip (%)
Accuracy (%)
FLOPs
GRU (Cho et al., 2014)
0
82.8 (2.2)
569250
CW-RNN (Koutnik al., 2014)
72.1
81
64.2 (0.8)
35910
PhasedLSTM (Neil et al., 2016)
70.2
70
70.5 (1.8)
227700
VC-GRU (Jernite et al., 2017)
61.9
66
58.1 (2.2)
197340
SkipRNN (Campos et al., 2018)
72.2
87
60.0 (1.1)
75487
Random Skips
61.2
76
49.4 (0.7)
130927
SA-RNN
76.1
77
75.4 (3.0)
252120
Table 3: Performance on the TwitterBuzz task. For SA-RNN we use X = 2e 2
Accuracy
5 3
Accuracy
Accuracy
(a) Twitter
(b) Seizures
Yahoo
Accuracy
Accuracy
Accuracy
88
0.
6.
30
60
30
40
30
60
40
60
20
90
100
Skip Percent
Skip Percent
Skip Percent
(d) TwitterBuzz
(e) Seizures
(I) Yahoo
Figure 3: Observing the effect of skip percent on accuracy. Accuracy and skip percent contrast one another, resulting in a trade-off.
Effects of budgeting neuron updates.
Finally, assess how the performance of SA-RNN depends its hyperparameter X, which budgets the number of permitted updates. We investigate values from to 0.1 on a log-scale, since empirically updates stopped when > 0.1. Interestingly, the relationship between accuracy and A depends heavily on the task, as demonstrated in in the first row of Figure 3. For example, on the Twi tterBuzz task, we observe smooth transition from random guessing (when no updates are allowed) our peak accuracy (no constraint updates). Meanwhile, on the Sei zures task, there a sharp increase from random predictions to near-peak performance. This could be a feature of the parameter search space, but with already-small changes to À this indicates high-sensitivity. We also investigate how accuracy changes as a function the number of neurons skipped, as shown in the second row of Figure 3. Interestingly, there steep elbows where very few updates needed to observe near-peak accuracy. This bolsters the intuition behind Residual Networks and related methods: many hidden dimensions often capture enough information warrant direct copying.
CONCLUSIONS
In this paper, study the problem of reducing the number of updates the state representations learned by RNNs. This allows for less computation at each timestep. We propose an augmentation to general RNN models, called SA-RNN, which is carefully crafted to skip neurons while maintaining accuracy through the parameterization of distribution of neuron update-likelihock decisions for each neuron each step. We conduct extensive experiments on three real-world aoblicly-availabe datasets and show that our method achieves on average higher accuracy with fewer neuron updates compared to recent state-of-the-as alternatives. Our results demonstrate that updating state representations without imposing high-bias decisions on the update-pattern is not only easier to implement and train, but preferable in terms of performance.
making binary
8

---

Under review as a conference paper at ICLR 2020
REFERENCES
Ralph G Andrzejak, Klaus Lehnertz, Florian Mormann, Christoph Rieke, Peter David, and Christian E Elger. Indications of nonlinear deterministic and inite-dimensional structures time series of brain electrical activity: Dependence on recording region and brain state. Physical Review E, 64 (6):061907, 2001.
Dzmitry Bahdanau, Kyunghyun Cho, and Yoshua Bengio. Neural machine translation by jointly learning to align and translate. In International Conference on Learning Representations, 2015.
Emmanuel Bengio, Pierre-Luc Bacon, Joelle Pineau, and Doina Precup. Conditional computation in neural networks for faster models. arXiv preprint arXiv:/511.0629) 2015.
Yoshua Bengio, Patrice Simard, and Paolo Frasconi. Learning long-term dependencies with gradient descent is difficult. IEEE Transactions on Neural Networks, 5(2):157-166, 1994.
Yoshua Bengio, Nicholas Léonard, and Aaron Courville. Estimating or propagating gradients through stochastic neurons for conditional computation. arXiv preprint arXiv:1308..433 2013.
Víctor Campos, Brendan Jou, Xavier Giro-i Nieto, Jordi Torres, and Shih-Fu Chang. Skip rnn: Learning to skip state updates in recurrent neural networks. In International Conference on Learning Representations, 2018.
Zhengping Che, Sanjay Purushotham, Kyunghyun Cho, David Sontag, and Yan Liu. Recurrent neural networks for multivariate time series with missing values. Scientific reports, 8(1):6085, 2018.
Yu Cheng, Duo Wang, Pan Zhou, and Tao Zhang. A survey of model compression and acceleration for deep neural networks. arXiv preprint 17Xiv:/110.000 2017.
Kyunghyun Cho, Bart Van Merriënboer, Caglar Gulcehre, Dzmitry Bahdanau, Fethi Bougares, Holger Schwenk, and Yoshua Bengio. Learning phrase representations using rnn encoder-decoder for statistical machine translation. In Empirical Methods in Natural Language Processing, 2014.
Junyoung Chung, Sungjin Ahn, and Yoshua Bengio. Hicrarchical multiscale recurrent neural networks.
In International Conference on Learning Representations, 2017.
Jeffrey L Elman. Finding structure in time. Cognitive science, 14(2):79-2111, 1990.
Alex Graves. Generating sequences with recurrent neural networks. In arXiv preprint arXiv: 1308. 0850, 2013.
Alex Graves, AbdelRahman Mohamed, and Geoffrey Hinton. Speech recognition with deep recurrent neural networks. In International conference on acoustics, speech and signal processing, pp- 6645-6649, IEEE, 2013.
David Ha and Jürgen Schmidhuber. Recurrent world models facilitate policy evolution. In Advances in Neural Information Processing Systems, pp. 2450-2466 2018.
Kaiming He. Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Deep residual learning for image recognition. In Computer vision and pattern recognition, pp. 770-778, 2016.
Mikael Henaff, Arthur Szlam, and Yann LeCun. Recurrent orthogonal networks and long-memory tasks. 2016.
Sepp Hochreiter and Jürgen Schmidhuber. Long short-term memory. Neural Computation, 9(8): 1735-1780, 1997.
Yacine Jernite, Edouard Grave, Armand Joulin, and Tomas Mikolov. Variable computation in recurrent neural networks. In International Conference on Learning Representations, 2017.
François Kawala, Ahlame Douzal-Chouakria Eric Gaussier, and Eustache Dimert. Prédictions d' d'activité dans les réseaux sociaux en ligne. In 4ième conférence sur les modèles et I l'analyse des réseaux: Approches mathématiques informatiques, pp. 16, 2013.

---

Under review as a conference paper at ICLR 2020
Diederik P Kingma and Jimmy Ba. Adam: A method for stochastic optimization. arXiv preprint arXiv:1412.6980, 2014.
Jan Koutnik, Klaus Greff, Faustino Gomez, and Juergen Schmidhuber. A clockwork mn. In International Conference Machine Learning, pp. 1863-1871, 2014.
David Krueger, Tegan Maharaj, János Kramár, Mohammad Pezeshki, Nicolas Ballas, Nan Rosemary Ke, Anirudh Goyal, Yoshua Bengio, Aaron Courville, and Chris Pal. Zoneout: Regularizing mns by randomly preserving hidden activations. In International Conference on Learning Representations, 2017.
Luchen Liu, Jianhao Shen, Ming Zhang, Zichang Wang, and Jian Tang. Learning the joint represen- tation of heterogeneous temporal events for clinical endpoint prediction. In Thirty-Second AAAI Conference Artificial Intelligence, 2018.
Daniel Neil, Michael Pfeiffer, and Shih-Chii Liu. Phased Istm: Accelerating recurrent network training for long or event-based sequences. In Advances in Neural Information Processing Systems, pp. 3882-3890, 2016.
Jürgen Schmidhuber. Self-delimiting neural networks. arXiv preprint arXiv: 2012.
Noam Shazeer, Azalia Mirhoseini, Krzysztof Maziarz, Andy Davis, Quoe Le, Geoffrey Hinton, and Jeff Dean. Outrageously large neural networks: The sparsely -attd mixture-of-expeen layer. arXiv preprint arXiv: 1701006888, 2017.
Yikang Shen, Shawn Tan, Alessandro Sordoni, and Aaron Courville. Ordered neurons: Incorpo- rating tree structures into recurrent neural networks. International Conference on Learning Representations, 2019.
Rupesh Kumar Srivastava, Klaus Greff, and Jürgen Schmidhuber. Highway networks. In Advances in Neural Information Processing Systems, 2015.
Yiren Wang and Fei Tian. Recurrent residual learning for sequence classification. In Empirical methods in natural language processing, pp. 938 943, 2016.
Ronald J Williams. Simple statistical gradient- algorithms for connectionist reinforcement learning. Machine learning, 8(3-4):229-25) 1992.
Kelvin Xu, Jimmy Ba, Ryan Kiros, Kyunghyun Cho, Aaron Courville, Ruslan Salakhudinov, Rich Zemel, and Yoshua Bengio. Show, attend and tell: Neural image caption generation with visual attention. In International Conference Machine Learning. pp. 2048-2057.2015
Julian Georg Zilly, Rupesh Kumar Srivastava, Jan Koutník, and Jürgen Schmidhuber. Recurrent highway networks. In International Conference on Machine Learning volume 70, pp. 4189-4198, 2017.
10

---

Under review as a conference paper at ICLR 2020
APPENDIX
6.1 ADDING TASK
In this experiment, the network must learn use a binary mask sum the corresponding values in real-valued sequence. This task was classically used to validate the LSTM's 's effectiveness and is now commonly used to evaluate the robustness of memory in RNNS the presence of extremely long-term dependencies (Hochreiter & Schmidhuber, 1997; Neil et al., 2016; Campos et al., 201 8). The task is as follows: given a data sequence of T values sampled uniformly between and and binary masking sequence containing T 2 zeros and 2 ones which are located at indices and j. the ground truth y is computed as y = I2 + zy- Given a new data sequence x and a masking sequence m, the mean squared error between y and fe (z, m) should be approximately O.
We set T = 500 to stress-test long-term dependencies and use 128-dimensional hidden states, as suggested in Henaff et al. (2016).
Method
Task solved
Skip Percent
FLOPs (x10%)
GRU
Yes
49.7
Random Skips
No
25.0
24.9
Random Skips
No
50.0
12.4
Random Skips
No
90.0
4.97
SkipRNN (A = 0)
Yes
2.1 (3.3)
44.8
SkipRNN (A 77
Yes
21.6 (39.7)
39.6
SA-RNN (A 0)
Yes
25,2 (5.1)
37.5
SA-RNN (A le 5)
Yes
49.6 (9.6)
25.3
SA-RNN (A = 4)
Yes
90.0 (3.9)
15.3
Table 4: Adding task with 500 timesteps.
As shown in Table 4, SA-RNN consistently solves the adding task with far higher skip percenluge and lower FLOPs than the baseline GRU and the SkipRNN. Even though SkipRNN theoretically can and should find the proper timesteps observe given the mask, it did not solve the problem consistently, only performing well under a couple of choice settings which updated the vast majority of the hidden states. However, we note that the sequence- T used in this experiment is ten times greater than was originally explored in Campos et al. (2018).
6.2 HYPERPARAMETER SELECTION FOR COMPARED METHODS
We employ the validation set select hyperparameters for compared models described in Section 4.2.
Random Updates: When training Random Updates, the one hyperparameter to tune is the probubility of updating euch hidden dimension. Our goal to match the number updates in Random Updates to the number observed in proposed method. SA-RNN. So after observing how many times SA-RNN updated, we simply create random binary masks with the same update proportions.
Clockwork RNN: This method relies hand-crafted update patterns. In order to have roughly 20% of the updates (to be similar to the other methods) with 50-dimension state representations,
use block-sizes of 5 (the number of dimensions whose updates tied together) with poooneniilly-incceaaett
clock rates as proposed in the original paper: use of
{1, 4, 16, 32, 64, 128, 264, 512). We choose this it is the originally-intende the model and resulted in the proper number of updates. There is no variance this method does not react to the input data.
PhasedLSTM: This method also hand-crafted update patterns, sampling update periods for individual hidden dimensions. The distribution from which to sample update periods is left up the user (along with the parameters of such distribution). As proposed in the paper, we sample update periods from uniform distribution 4. To determine the lower and upper bounds of the distribution, tried sampling update patterns from uniform distribution of
11

---

Under review as a conference paper at ICLR 2020
all combinations of integers between 0 and 6, finally choosing (1, We sample D values from this distribution, where D is the dimension of the state representation. We choose the shift described in the original PhasedLSTM paper, sampling value with upper limit of the period for each neuron. These two settings, paired with Ton 0.3 led to a comparable number of updates.
This method predicts proportions of the state representation to update at each timestep. During the optimization, there is a loss which adds "target" proportion, penalizing deviations from this target value. As suggested in the original paper, we tried values of 0.1, 0.2, and 0.5 and selected 0.1, which resulted in comparable number of updates.
VC-GRU:
SkipRNN: This method predicts likelihoods of state updates at each timestep. In the loss function, there is one hyperparameter, X, which penalizes the number of updates. We use log-space search, ranging from 0.0 to 0.1 1I steps, settling on - 05 for the Twitter task, and le 04 for the Sei zures and Yahoo tasks. We found the number of updates to extremely sensitive, skipping from roughly 13% to 100% between single log-space steps.
Neurons
Neurons
Timesteps
Timesteps
(a) PhasedLSTM
(b) VC-GRU
Figure 4: Raw update patterns. Each column is state representation. White boxes indicate Skip, darker boxes indicate the degree to which neuron is updated with darker being more updated. A black box indicates that neuron is fully-updated.
6.3 VISUALIZING UPDATE PATTERNS
In Section 4.3 we visualize and contrast the update patterns between all described methods. Phas- edL.TMM and VC-GRU, however, do not propose fully-binary update patterns. PhasedL.STM softly opens and closes neurons, and VC-GRU approximates binary update-decisions using soft mask, changing the proportion updated-neurons at each timestep. order to fairly compare them to all other methods, we employ ceiling functions raise their update predictions to 1 (prior to this, their updates are between 0 and 1, similar to LSTM and GRU). In Figure 4, we display their update originally intended. We believe that this
patterns prior to this ceiling function, to show their use of the ceiling function is fair, since such soft updates are still updates, which is the focus of our work.
12

---

Under review as a conference paper at ICLR 2020
6.4 IMPLEMENTING SA-RNN
We implement our method (and all other methods) in PyTorch 1.0. Below, we provide some pseu- docode give taste of how approach implementing SA-RNN (at high level). The pseudocode is loosely formatted similar to PyTorch for readability. In the pseudocode, Discrim imii nator is simply network which maps the hidden state the latent space for the final prediction. Upon acceptance of the paper, the full code will be released along with our entire training process and many examples. In practice the next state does not need be fully computed once the update decisions are computed.
def Forward
u_likelihoods
zeros # Initialize update likelihoods as zeros Create the initial state for t in range (len (sequence)): # Loop through sequence. sequence # Extract one timestep of data
state
u_likelihoods = fcordinatoorforrarddd (x, u_likelihoods)
u_decisions Binarize. forward took)
state_tilde fNN.forward state)
state __Lecisions-sttte__iide + (l-u_decisions) *state prediction Discriminator. return prediction
forward [
13


Reviews:
[{"review_id": "S1xB6zspFr", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": null, "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": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "A main problem with RNN is to update all hidden dimensions in each time step. The authors proposed selective-activation RNN (SA-RNN), which modifies each state of RNN by adding an update coordinator which is modeled as a lightweight neural network. The coordinator, based on the incoming data, makes a discrete decision to update or not update each individual hidden dimension. A multi-objective optimization problem is defined to both solving a sequential learning task and minimizing the number of updates in each time step. The authors evaluated their networks on three public benchmark datasets and achieved good results compared to the state-of-the-art ones.\nThe papers is well-written. The idea proposed in this paper is interesting and it is presented very well. There is also an extensive evaluation.\n", "extra_scores": {"experience_assessment": "I have published one or two papers in this area.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper at least twice and used my best judgement in assessing the paper.", "review_assessment:_checking_correctness_of_experiments": "I carefully checked the experiments.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I carefully checked the derivations and theory."}, "extra_text": {}}, {"review_id": "Byxm0iP5KH", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": null, "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": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "Summary: This paper proposes selective activation RNN (SA-RNN), by using an update coordinator to determine which subset of the RNN’s hidden state dimensions should be updated at a given timestep. The proposed loss term is then a sum of the original objective (e.g. classification) and a weighted sum of the probability that each dimension will be updated for each timestep. The method is evaluated on 3 time series datasets: Seizures, TwitterBuzz, Yahoo. \n\nDecision: Weak Reject. Although the authors tackle a challenging problem, their empirical results are lacking to provably demonstrate that their approach outperforms existing baselines.\n\nSupporting Arguments/Feedback: The authors compare SA-RNN to 5 baselines: random updates, clockwork RNN, phased LSTM, Skip RNN, and VC-GRU. Although I appreciated the authors’ comparison across the suite of methods with respect to various metrics (e.g. # FLOPS, proportion of neurons that weren’t updated, etc.), the experiments were conducted on datasets that were relatively simple. For example, in prior work, the empirical evaluations were on much larger-scale datasets such as Wikipedia [Shen et. al 2019], real clinical data sources [Liu et. al 2018], and Charades videos [Campos et. al 2018], among others. I would be very interested to see how this training procedure fairs when evaluated on much more complex tasks, and would make the results about computational speedups at train/test time much more convincing.\n\nQuestions:\n- I’m curious if you tried different types of gradient estimators to get around the non-differentiability rather than the straight-through estimator. Also how was the slope-annealing conducted (e.g. annealing schedule)?\n", "extra_scores": {"experience_assessment": "I do not know much about this area.", "review_assessment:_checking_correctness_of_experiments": "I assessed the sensibility of the experiments.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper at least twice and used my best judgement in assessing the paper.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory."}, "extra_text": {}}, {"review_id": "BJecY0BnFr", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": null, "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": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This paper attempts to reduce computation in recurrent neural networks. Instead of artificially determining the update pattern for updating the states, the authors propose SA-RNN to predict discrete update patterns automatically through optimization driven entirely by the input data. Experiments on publicly-available datasets show that the proposed method has competitive performance with even fewer updates.\n\nPros:\nOverall, I think the idea of this paper is clear and the whole paper is easy to follow. The experiments clearly show the advantage of the proposed method claimed by the authors.\n\nCons:\n1.\tSome expressions need to be improved. For example, in “This way, representations can be learned while solving a sequential learning task while minimizing the number of updates, subsequently reducing compute time.” two “while”s are not elegant and there should be an “In” before “this way”. In “We augment an RNN with an update coordinator that adaptively controls the coordinate directions in which to update the hidden state on the fly”, the usage of “in which to” is not right. I suggest the authors to thoroughly proofread the whole paper and improve the presentation.\n2.\tSince this paper focuses on the efficiency of RNN, I suggest the authors could provide the time complexity comparisons. Merely the comparisons on skip of neurons cannot show the advantage on the efficiency.\n", "extra_scores": {"experience_assessment": "I have published one or two papers in this area.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I carefully checked the derivations and theory.", "review_assessment:_checking_correctness_of_experiments": "I carefully checked the experiments.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper thoroughly."}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper introduces a new RNN architecture which uses a small network to decide which cells get updated at each time step, with the goal of reducing computational cost.  The idea makes sense, although it requires the use of a heuristic gradient estimator because of the non-differentiability of the update gate.

The main problem with this paper in my view is that the reduction in FLOPS was not demonstrated to correspond to a reduction in wallclock time, and I don't expect it would, since the sparse updates are different for each example in each batch, and only affect one hidden unit at a time.  The only discussion of this problem is "we compute the FLOPs for each method as a surrogate for wall-clock time, which is hardware-dependent and often fluctuates dramatically in practice."  Because this method reduces predictive accuracy, the reduction in FLOPS should be worth it!

Minor criticism:
1) Figure 1 is confusing, showing not the proposed architecture in general but instead the connections remaining after computing the sparse updates.

Decision: Reject