Advances in Optimizing Recurrent Networks

Introduction

Machine learning algorithms for capturing statistical structure in sequential data face a fundamental problem , called the difficulty of learning long-term dependencies. If the operations performed when forming a fixed-size summary of relevant past observations (for the purpose of predicting some future observations) are linear, this summary must exponentially forget past events that are further away, to maintain stability. On the other hand, if they are non-linear, then this non-linearity is composed many times, yielding a highly non-linear relationship between past events and future events. Learning such non-linear relationships turns out to be difficult, for reasons that are discussed here, along with recent proposals for reducing this difficulty.

Recurrent neural networks can represent such non-linear maps ($F$, below) that iteratively build a relevant summary of past observations. In their simplest form, recurrent neural networks (RNNs) form a deterministic state variable $h_{t}$ as a function of the present input observation $x_{t}$ and the past value(s) of the state variable, e.g., $h_{t}=F_{\theta}(h_{t-1},x_{t})$, where $\theta$ are tunable parameters that control what will be remembered about the past sequence and what will be discarded. Depending on the type of problem at hand, a loss function $L(h_{t},y_{t})$ is defined, with $y_{t}$ an observed random variable at time $t$ and $C_{t}=L(h_{t},y_{t})$ the cost at time $t$. The generalization objective is to minimize the expected future cost, and the training objective involves the average of $C_{t}$ over observed sequences. In principle, RNNs can be trained by gradient-based optimization procedures (using the back-propagation algorithm to compute a gradient), but it was observed early on that capturing dependencies that span a long interval was difficult, making the task of optimizing $\theta$ to minimize the average of $C_{t}$’s almost impossible for some tasks when the span of the dependencies of interest increases sufficiently. More precisely, using a local numerical optimization such as stochastic gradient descent or second order methods (which gradually improve the solution), the proportion of trials (differing only from their random initialization) falling into the basin of attraction of a good enough solution quickly becomes very small as the temporal span of dependencies is increased (beyond tens or hundreds of steps, depending of the task).

These difficulties are probably responsible for the major reduction in research efforts in the area of RNNs in the 90’s and 2000’s. However, a revival of interest in these learning algorithms is taking place, in particular thanks to and . This paper studies the issues giving rise to these difficulties and discusses, reviews, and combines several techniques that have been proposed in order to improve training of RNNs, following up on a recent thesis devoted to the subject . We find that these techniques generally help generalization performance as well as training performance, which suggest they help to improve the optimization of the training criterion. We also find that although these techniques can be applied in the online setting, i.e., as add-ons to stochastic gradient descent (SGD), they allow to compete with batch (or large minibatch) second-order methods such as Hessian-Free optimization, recently found to greatly help training of RNNs .

Learning Long-Term Dependencies and the Optimization Difficulty with Deep Learning

There has been several breakthroughs in recent years in the algorithms and results obtained with so-called deep learning algorithms (see and for reviews). Deep learning algorithms discover multiple levels of representation, typically as deep neural networks or graphical models organized with many levels of representation-carrying latent variables. Very little work on deep architectures occurred before the major advances of 2006 , probably because of optimization difficulties due to the high level of non-linearity in deeper networks (whose output is the composition of the non-linearity at each layer). Some experiments showed the presence of an extremely large number of apparent local minima of the training criterion, with no two different initializations going to the same function (i.e. eliminating the effect of permutations and other symmetries of parametrization giving rise to the same function). Furthermore, qualitatively different initialization (e.g., using unsupervised learning) could yield models in completely different regions of function space. An unresolved question is whether these difficulties are actually due to local minima or to ill-conditioning (which makes gradient descent converge so slowly as to appear stuck in a local minimum). Some ill-conditioning has clearly been shown to be involved, especially for the difficult problem of training deep auto-encoders, through comparisons of stochastic gradient descent and Hessian-free optimization (a second order optimization method). These optimization questions become particularly important when trying to train very large networks on very large datasets , where one realizes that a major challenge for deep learning is the underfitting issue. Of course one can trivially overfit by increasing capacity in the wrong places (e.g. in the output layer), but what we are trying to achieve is learning of more powerful representations in order to also get good generalization.

The same questions can be asked for RNNs. When the computations performed by a RNN are unfolded through time, one clearly sees a deep neural network with shared weights (across the ’layers’, each corresponding to a different time step), and with a cost function that may depends on the output of intermediate layers. Hessian-free optimization has been successfully used to considerably extend the span of temporal dependencies that a RNN can learn , suggesting that ill-conditioning effects are also at play in the difficulties of training RNN.

An important aspect of these difficulties is that the gradient can be decomposed into terms that involve products of Jacobians $\frac{\partial h_{t}}{\partial h_{t-1}}$ over subsequences linking an event at time $t_{1}$ and one at time $t_{2}$: $\frac{\partial h_{t_{2}}}{\partial h_{t_{1}}}=\prod_{\tau=t_{1}+1}^{t_{2}}\frac{\partial h_{\tau}}{\partial h_{\tau-1}}$. As $t_{2}-t_{1}$ increases, the products of $t_{2}-t_{1}$ of these Jacobian matrices tend to either vanish (when the leading eigenvalues of $\frac{\partial h_{t}}{\partial h_{t-1}}$ are less than 1) or explode (when the leading eigenvalues of $\frac{\partial h_{t}}{\partial h_{t-1}}$ are greater than 1 Note that this is not a sufficient condition, but a necessary one. Further more one usually wants to operate in the regime where the leading eigenvalue is larger than 1 but the gradients do not explode.). This is problematic because the total gradient due to a loss $C_{t_{2}}$ at time $t_{2}$ is a sum whose terms correspond to the effects at different time spans, which are weighted by $\frac{\partial h_{t_{2}}}{\partial h_{t_{1}}}$ for different $t_{1}$’s:

where $\frac{\partial h_{t_{1}}}{\partial\theta^{(t_{1})}}$ is the derivative of $h_{t_{1}}$ with respect to the instantiation of the parameters $\theta$ at step $t_{1}$, i.e., that directly come into the computation of $h_{t_{1}}$ in $F$. When the $\frac{\partial h_{t_{2}}}{\partial h_{t_{1}}}$ tend to vanish for increasing $t_{2}-t_{1}$, the long-term term effects become exponentially smaller in magnitude than the shorter-term ones, making it very difficult to capture them. On the other hand, when $\frac{\partial h_{t_{2}}}{\partial h_{t_{1}}}$ “explode” (becomes large), gradient descent updates can be destructive (move to poor configuration of parameters). It is not that the gradient is wrong, it is that gradient descent makes small but finite steps $\Delta\theta$ yielding a $\Delta C$, whereas the gradient measures the effect of $\Delta C$ when $\Delta\theta\rightarrow 0$. A much deeper discussion of this issue can be found in , along with a point of view inspired by dynamical systems theory and by the geometrical aspect of the problem, having to do with the shape of the training criterion as a function of $\theta$ near those regions of exploding gradient. In particular, it is argued that the strong non-linearity occurring where gradients explode is shaped like a cliff where not just the first but also the second derivative becomes large in the direction orthogonal to the cliff. Similarly, flatness of the cost function occurs simultaneously on the first and second derivatives. Hence dividing the gradient by the second derivative in each direction (i.e., pre-multiplying by the inverse of some proxy for the Hessian matrix) could in principle reduce the exploding and vanishing gradient effects, as argued in .

Advances in Training Recurrent Networks

To address the exploding gradient effect, recently proposed to clip gradients above a given threshold. Under the hypothesis that the explosion occurs in very small regions (the cliffs in cost function mentioned above), most of the time this will have no effect, but it will avoid aberrant parameter changes in those cliff regions, while guaranteeing that the resulting updates are still in a descent direction. The specific form of clipping used here was proposed in and is discussed there at much greater length: when the norm of the gradient vector $g$ for a given sequence is above a $threshold$, the update is done in the direction $threshold\frac{g}{||g||}$. As argued in , this very simple method implements a very simple form of second order optimization in the sense that the second derivative is also proportionally large in those exploding gradient regions.

2 Spanning Longer Time Ranges with Leaky Integration

An old idea to reduce the effect of vanishing gradients is to introduce shorter paths between $t_{1}$ and $t_{2}$, either via connections with longer time delays or inertia (slow-changing units) in some of the hidden units , or both . Long-Short-Term Memory (LSTM) networks , which were shown to be able to handle much longer range dependencies, also benefit from a linearly self-connected memory unit with a near 1 self-weight which allows signals (and gradients) to propagate over long time spans.

A different interpretation to this slow-changing units is that they behave like low-pass filter and hence they can be used to focus certain units on different frequency regions of the data. The analogy can be brought one step further by introducing band-pass filter units or by using domain specific knowledge to decide on what frequency bands different units should focus. shows that adding low frequency information as an additional input to a recurrent network helps improving the performance of the model.

In the experiments performed here, a subset of the units were forced to change slowly by using the following “leaky integration” state-to-state map: $h_{t,i}=\alpha_{i}h_{t-1,i}+(1-\alpha_{i})F_{i}(h_{t-1},x_{t})$. The standard RNN corresponds to $\alpha_{i}=0$, while here different values of $\alpha_{i}$ were randomly sampled from $(0.02,0.2)$, allowing some units to react quickly while others are forced to change slowly, but also propagate signals and gradients further in time. Note that because $\alpha<1$, the vanishing effect is still present (and gradients can still explode via $F$), but the time-scale of the vanishing effect can be expanded.

3 Combining Recurrent Nets with a Powerful Output Probability Model

One way to reduce the underfitting of RNNs is to introduce multiplicative interactions in the parametrization of $F$, as was done successfully in . When the output predictions are multivariate, another approach is to capture the high-order dependencies between the output variables using a powerful output probability model such as a Restricted Boltzmann Machine (RBM) or a deterministic variant of it called NADE . In the experiments performed here, we have experimented with a NADE output model for the music data.

4 Sparser Gradients via Sparse Output Regularization and Rectified Outputs

hypothesized that one reason for the difficulty in optimizing deep networks is that in ordinary neural networks gradients diffuse through the layers, diffusing credit and blame through many units, maybe making it difficult for hidden units to specialize. When the gradient on hidden units is more sparse, one could imagine that symmetries would be broken more easily and credit or blame assigned less uniformly. This is what was advocated in , exploiting the idea of rectifier non-linearities introduced earlier in , i.e., the neuron non-linearity is $out=\max(0,in)$ instead of $out=\tanh(in)$ or $out={\rm sigmoid}(in)$. This approach was very successful in recent work on deep learning for object recognition , beating by far the state-of-the-art on ImageNet (1000 classes). Here, we apply this deep learning idea to RNNs, using an L1 penalty on outputs of hidden units to promote sparsity of activations. The underlying hypothesis is that if the gradient is concentrated in a few paths (in the unfolded computation graph of the RNN), it will reduce the vanishing gradients effect.

5 Simplified Nesterov Momentum

Nesterov accelerated gradient (NAG) is a first-order optimization method to improve stability and convergence of regular gradient descent. Recently, showed that NAG could be computed by the following update rules:

where $\theta_{t}$ are the model parameters, $v_{t}$ the velocity, $\mu_{t}\in$ the momentum (decay) coefficient and $\epsilon_{t}>0$ the learning rate at iteration $t$, $f(\theta)$ is the objective function and $\nabla f(\theta^{\prime})$ is a shorthand notation for the gradient $\frac{\partial f(\theta)}{\partial\theta}|_{\theta=\theta^{\prime}}$. These equations have a form similar to standard momentum updates:

and differ only in the evaluation point of the gradient at each iteration. This important difference, thought to counterbalance too high velocities by “peeking ahead” actual objective values in the candidate search direction, results in significantly improved RNN performance on a number of tasks.

In this section, we derive a new formulation of Nesterov momentum differing from (3) and (5) only in the linear combination coefficients of the velocity and gradient contributions at each iteration, and we offer an alternative interpretation of the method. The key departure from (1) and (2) resides in committing to the “peeked-ahead” parameters $\Theta_{t-1}\equiv\theta_{t-1}+\mu_{t-1}v_{t-1}$ and backtracking by the same amount before each update. Our new parameters $\Theta_{t}$ updates become:

Assuming a zero initial velocity $v_{1}=0$ and velocity at convergence of optimization $v_{T}\simeq 0$, the parameters $\Theta$ are a completely equivalent replacement of $\theta$.

Note that equation (7) is identical to regular momentum (5) with different linear combination coefficients. More precisely, for an equivalent velocity update (6), the velocity contribution to the new parameters $\mu_{t}\mu_{t-1}<\mu_{t}$ is reduced relatively to the gradient contribution $(1+\mu_{t})\epsilon_{t-1}>\epsilon_{t-1}$. This allows storing past velocities for a longer time with a higher $\mu$, while actually using those velocities more conservatively during the updates. We suspect this mechanism is a crucial ingredient for good empirical performance. While the “peeking ahead” point of view suggests that a similar strategy could be adapted for regular gradient descent (misleadingly, because it would amount to a reduced learning rate $\epsilon_{t}$), our derivation shows why it is important to choose search directions aligned with the current velocity to yield substantial improvement. The general case is also simpler to implement.

Experiments

In the experimental section we compare vanilla SGD versus SGD plus some of the enhancements discussed above. Specifically we use the letter ‘C‘ to indicate that gradient clipping is used, ‘L‘ for leaky-integration units, ‘R‘ if we use rectifier units with L1 penalty and ‘M‘ for Nesterov momentum.

We evaluate our models on the four polyphonic music datasets of varying complexity used in : classical piano music (Piano-midi.de), folk tunes with chords instantiated from ABC notation (Nottingham), orchestral music (MuseData) and the four-part chorales by J.S. Bach (JSB chorales). The symbolic sequences contain high-level pitch and timing information in the form of a binary matrix, or piano-roll, specifying precisely which notes occur at each time-step. They form interesting benchmarks for RNNs because of their high dimensionality and the complex temporal dependencies involved at different time scales. Each dataset contains at least 7 hours of polyphonic music with an average polyphony (number of simultaneous notes) of 3.9.

Piano-rolls were prepared by aligning each time-step (88 pitch labels that cover the whole range of piano) on an integer fraction of the beat (quarter note) and transposing each sequence in a common tonality (C major/minor) to facilitate learning. Source files and preprocessed piano-rolls split in train, validation and test sets are available on the authors’ websitewww-etud.iro.umontreal.ca/~boulanni/icml2012.

We select hyperparameters, such as the number of hidden units $n_{h}$, regularization coefficients $\lambda_{L1}$, the choice of non-linearity function, or the momentum schedule $\mu_{t}$, learning rate $\epsilon_{t}$, number of leaky units $n_{leaky}$ or leaky factors $\alpha$ according to log-likelihood on a validation set and we report the final performance on the test set for the best choice in each category. We do so by using random search on the following intervals:

The cutoff threshold for gradient clipping is set based on the average norm of the gradient over one pass on the data, and we used 15 in this case for all music datasets. The data is split into sequences of 100 steps over which we compute the gradient. The hidden state is carried over from one sequence to another if they belong to the same song, otherwise is set to 0.

Table 1 presents log-likelihood (LL) and expected frame-level accuracy for various RNNs in the symbolic music prediction task.

Results clearly show that these enhancements allow to improve on regular SGD in almost all cases; they also make SGD competitive with HF for the sigmoid recognition layers RNNs.

2 Text Data

We use the Penn Treebank Corpus to explore both word and character prediction tasks. The data is split by using sections 0-20 as training data (5017k characters), sections 21-22 as validation (393k characters) and sections 23-24 as test data (442k characters).

For the word level prediction, we fix the dictionary to 10000 words, which we divide into 30 classes according to their frequency in text (each class holding approximately 3.3% of the total number of tokens in the training set). Such a factorization allows for faster implementation, as we are not required to evaluate the whole output layer (10000 units) which is the computational bottleneck, but only the output of the corresponding class .

In the case of next word prediction, we compute gradients over sequences of 40 steps, where we carry the hidden state from one sequence to another. We use a small grid-search around the parameters used to get state of the art results for this number of classes , i.e., with a network of 200 hidden units yielding a perplexity of 134. We explore learning rate of $0.1,0.01,0.001$, rectifier units versus sigmoid units, cutoff threshold for the gradients of 30, 50 or none, and no leaky units versus 50 of the units being sampled from 0.2 and 0.02.

For the character level model we compute gradients over sequences of 150 steps, as we assume that longer dependencies are more crucial in this case. We use 500 hidden units and explore learning rates of 0.5, 0.1 and 0.01.

In table 2 we have entropy (bits per character) or perplexity for varous RNNs on the word and character prediction tasks. Again, we observe substantial improvements in both training and test perplexity, suggesting that these techniques make optimization easier.

Conclusions

Through our experiments we provide evidence that part of the issue of training RNN is due to the rough error surface which can not be easily handled by SGD. We follow an incremental set of improvements to SGD, and show that in most cases they improve both the training and test error, and allow this enhanced SGD to compete or even improve on a second-order method which was found to work particularly well for RNNs, i.e., Hessian-Free optimization.

References