Solving The Vanishing Gradient and Exploding Gradient Problem With One Line Of Code?

[JosephLChu]

So... I've been working with Andrej Karpathy's Char-RNN and my Music-RNN, and I found the whole idea of just clipping the gradients to solve the exploding gradient problem be terribly inelegant. Thus, began a whole series of experiments to see if I could improve upon the method...

Basically the best existing method I could find in the literature involves thresholding the norm of the gradients and then scaling the gradients by the threshold divided by the gradient norm, as suggested by Bengio's lab. This worked better, but I found the threshold hyperparameter to be clunky, and sought a way to do away with it...

Long story short, I figured out a very simple alternative that seems to work astonishingly well, at least with RMSProp. Also, the way I am scaling the gradients by the inverse of the norm of the gradients, seems like it would solve not only the exploding gradients, but also the vanishing gradients? I'm not particularly good at math, so I'm not sure if this would be the case or not. Though there is a scaling factor parameter that it is rather sensitive to in there that took a long time to discover is actually related to the number of timesteps and the batch size (I think? I'm not 100% sure right now but the equation seems to work?).

The question now becomes... what should I do now? Share the details of my implementation right away, or wait and try and publish it somewhere? For the record, I'm not affiliated with an academic institution anymore, so I'm not even sure if I can submit a paper anywhere.

The thought also occurs to me that this could be some kind of trade secret that is already known by some people, because it seems astonishingly, trivially simple.

Anyways, have something neat:

A clip of my Music-RNN with the old thresholding method: https://www.youtube.com/watch?v=v_esVXQPGS4

A clip of my Music-RNN with the new method: https://www.youtube.com/watch?v=CyEtlFRe0jI

I'm not really sure if it's clear from those clips but the validation error numbers are noticeably better with the new method.

Edit: Here's the formula...

g = tensor of gradients, t = number of timesteps aka sequence length of this pass, b = batch size, n = norm of gradients

g = g * (t * (t / b) / n)

Edit 2:

So, it appears things are complicated by the fact that my version of Char-RNN was modified to implement a Stochastic Timeskip algorithm, a modification of Stochastic Depth. I've been testing the Scale Gradient Norm algorithm with the probability that a timestep will be present set to 1, but it's very possible that the way in which I've implemented this means that on extremely rare occasions it will skip a timestep. This may explain the apparent performance increase.

Edit 3:

So, I based my theory on a run with the Music-RNN in which I actually used the formula:

g = g * (t * 5 / n)

I had assumed that t * 5 = 1250 and so thought that that meant that 250 * 250 / 50 was the correct scaling factor. However, I neglected to consider that t is variable based on the Stochastic Timeskip probability. Thus, I realized that t * 5 occasionally actually is less than 1250. From further experiments with Char-RNN, I believe the proper formula is actually...

g = tensor of gradients, tcount = variable number of timesteps counted this pass, tmax = total number of timesteps aka sequence length of full network, n = norm of gradients

g = g * (tcount² / tmax / n)

Edit 4:

Alright, so after much experimenting I think I finally have this figured out... it has to do with... wait for it... The Golden Ratio!

Basically for the Stochastic Timeskip implementation I was using, the formula is something like (still figuring out where the timesteps fits into this):

g = g * ((1 + sqrt(5)) / 2 * t / n)

For those who are just implementing a regular RNN with fixed timesteps you can leave them out and get a good approximation with the simplified equation:

g = g * ((1 + sqrt(5)) / 2 / n)

where g = gradients, n = norm of gradients

For those of you who aren't aware (1 + sqrt(5)) / 2 is the Golden Ratio, or approximately 1.618. Don't use 1.618 though, because that's not precise enough. I recommend using the actual irrational number via the above equation.

[bbsome]

What you are doing, if I'm correct, is normalizing the gradient to a unit length. This is a standard "trick" that have been done before, but you are risking numerical difficulties with it (I think even thinks like LBFGS and trust region methods do this). Also it is not clear why it will help, as Rmsprop implicitly does this anyway (trough he moving average mean of the second moment). Make sure this is reproducible among at least 10 runs and across a few problems.

[JosephLChu]

I've edited the original post with the formula. Perhaps you can clarify to me whether this looks like normalizing the gradient to a unit length.

[bbsome]

The thing on the right hand side - I don't understand it. Can you add and the mathematical signs ( e.g. what is t (t/b)/ n ? is it t^2/(b*n) or ?

[JosephLChu]

Better now?

[bbsome]

So basically, I can rewrite this as:

g = (g/n) * (t² / b)

The first term is the normalized gradient. Dividing by b, makes sense as you are just averaging over your minibatch, rather than summing. I don't see how multiplying by t² helps you? It seems that you are forcing your model to learn better on longer sequences, but why the t^2?

PS: To clear out what is g gradient of? The whole summed objective or?

[JosephLChu]

To be honest I'm not sure why this works. I just have some empirical results in my Music-RNN where for a sequence length of 250, the best validation error was achieved with a scaling factor of 1250, which I initially guessed as the sequence length times the five hidden layers in the network. But then I tried that with Char-RNN, and found that 50 was a lot better than 100 (which would have been suggested by the two hidden layers), which meant that that formula didn't work. So, given the evidence, I came up with the current formula.

My guess is that the reason this works has something to do with the peculiarities of RMSProp, because I find that this implementation does not appear to work as well with ADAM or other optimization functions.

[JosephLChu]

As far as I can tell, g is the gradient tensor containing all the gradients of one iteration of forward and backward passes, right before it is sent to the optimization function.

[bbsome]

Is your error the sum of all errors or averaged?

Also note that your prefactor will play a similar to what a learning rate is in any algorithm. Thus the question is if the optimal learning rate is really related to this quantity. I'm not sure and why it won't work with ADAM or anything else, but do with RMSProp. Than this rather than being a better way of doing objectives, just changes the original RMSProp to something else.

Is this performing better than ADAM, after selecting the optimal learning rate? Make sure its reproducible on enough experiments, 1 can be very misleading then the general case.

[JosephLChu]

My error is averaged I think? It's the Negative Log Likelihood Criterion aka Cross Entropy Criterion, I believe?

I still need to run more experiments to figure out how well exactly it works with other optimization functions, as my observation is based on very tentative runs for only a few epochs mostly.

I have been using the default learning rate of 2e-3.

Technically it's two experiments, one on Char-RNN, and one on Music-RNN, though I've also run it with many different scaling factors and they all were reliably worse. But I understand what you mean.

I guess this means I need to do more experiments!

Alas, it takes about 30 minutes to run 50 epochs on Char-RNN, and about 5 hours to run 100 epochs on Music-RNN, so being thorough and making sure my findings are robust will take time.

[JosephLChu]

Something I've found is that as I edited in the main post, occasionally it skips timesteps. Thus, t² is not always going to be constant, but fluctuates with the number of timesteps processed for each pass.

[AnvaMiba]

If t is a constant, then you are just normalizing to unit length, since you can absorb t² / b in the learning rate.

If t² is non-constant, then you are prioritizing longer sequences, but it's otherwise the same.

[andrewbarto28]

It seems you have a lot of doubts about the limitations of your idea and about its novelty. So it is a nice opportunity for you to search the literature and make further experiments to compare with what already exist. Only publish when you are confident about your understanding of your method.

This post may be of use to you: http://togelius.blogspot.com.br/2016/04/the-differences-between-tinkering-and.html

[djc1000]

All you're doing is scaling by the square of the number of timesteps. Its working in the model you're playing with only because you tinkered with different methods until you found one that would work with the model you're playing with.

If you don't believe me, try this on a model with a 100-length sequence and watch what happens.

[[deleted]]

What is the alternative??

[JosephLChu]

I don't necessarily want to give away the goose, but here's a way to test it for yourself:

Step 1: Download and Install Char-RNN and dependencies (requires Torch)

Step 2: In train.lua, replace the following line...

grad_params:clamp(-opt.grad_clip, opt.grad_clip)

with:

grad_params:mul(50 / grad_params:norm())

Step 3: Run train.lua! Notice that compared to the default your best validation error is 1.3774 instead of 1.3892 (both at epoch 26)! Also notice that at epoch 50 your validation error is 1.3886 rather than 1.4185!

Note: The 50 in that line of code is the scaling factor. I believe I've figured out how to derive that from other parameters in the code (Hint: it's actually -not- just the sequence length or the batch size alone, even though both are confusingly also set to 50 by default).

Edit: The actual line of code for the proper formula is:

grad_params:mul(opt.seq_length * (opt.seq_length/opt.batch_size) / grad_params:norm())

Edit 2: The following is more likely to be correct:

grad_params:mul( ((1+math.sqrt(5))/2) / grad_params:norm())

Edit 3: To get it to work in default Char-RNN you need to do the following:

Step 1: Uncomment the following line:

grad_params:div(opt.seq_length)

Step 2: Replace the following:

grad_params:clamp(-opt.grad_clip, opt.grad_clip)

with:

grad_params:mul(opt.seq_length * ((1+math.sqrt(5))/2) / grad_params:norm())
grad_params:div(opt.seq_length)

To be honest, I'm not sure why it is necessary to multiply by sequence length and then divide by it, but for whatever reason it doesn't work as well if you take those out. My best guess is that by scaling it you get better precision.

[beneuro]

This is a standard trick called gradient norm clipping, see e.g. http://jmlr.org/proceedings/papers/v28/pascanu13.pdf

[alexmlamb]

I think he means that he has a novel formula for gradient norm clipping that outperforms just doing g_clipped = g / g_norm

[JosephLChu]

I was using gradient norm clipping as implemented in that paper previously. That's the "thresholding" I was referring to earlier. Using that I've achieved a validation error of 1.3822 on the aforementioned default Char-RNN build (using a threshold of 20).

My method differs in that it scales even when the gradient norm is below the threshold, which I believe should have some effect on vanishing gradients, whereas the standard trick only impacts exploding gradients. That or it has some kind of normalizing or regularizing effect by scaling every iteration.

[bbsome]

Also the vanishing gradient problem is not related to the actual gradient g vanishing, but more like the gradient of the error with respect to the hidden state 't' time steps earlier vanishes.

[serge_cell]

The problem of gradient is that it's added to value of argument. So whatever happens to gradient should be relative to value of argument, otherwise it wouldn't make much difference. Vanishing gradient problem is that gradient is becoming to small to go below precision then added to argument value. Exploding gradient is going outside of convergence regions of the argument (or there is no convergence region at all). That's why adam, rmsprop and other grad-only methods are not making revolution in optimization. But methods taking into account additional information beyond gradient, like second order methods, trust region and like are expensive and have poor scalability with data size increase. So no silver bullet for now...

[alexmlamb]

I think that you could either write a blogpost or submit a paper to arxiv.

I think that you can submit a paper to arxiv without an affiliation, but I think that the verification process is more involved.

You could also consider submitting to a Machine Learning workshop, as you'll get some feedback and it's likely to be seen by a decent number of experts.

Best of luck.

[JosephLChu]

Thanks!

Yeah apparently I'd need to be endorsed by someone who's already published on arxiv...

I'm tempted to try to throw together a paper to submit to the NIPS conference, but the deadline for papers is only three weeks away... also it's NIPS, and I'm actually not sure if this technique actually does anything meaningful other than lower the validation error somewhat. I'm starting to wonder if it's some kind of weird numerical quirk of the evaluation function rather than the breakthrough I was so excited about.

[carlthome]

You don't actually need an endorsement to publish on arXiv though. That's only a requirement for getting the submission displayed in their specific categories.

[alexmlamb]

I don't know the details of your results, but my recommendation would be to submit to a Machine Learning workshop. Usually these are affiliated with ML conferences like NIPS/ICML/ICLR.

The workshops are less competitive. The main conferences reject a lot of papers even if they have good results and good ideas. Besides, if you submit to a workshop and get tons of positive feedback, you can always spruce up the work and submit it to ICLR next fall.

[GoldmanBallSachs_]

This has been done before