My LSTM can't reduce error down to zero, when overfitting

Question

I have implemented LSTM in c++ which steadily decreases in error, but slows down at the certain error value. It also seems to predict most of the characters, but gets stuck and not able to correct some mistakes (or will correct them very slowly), even after 5000 backprop iterations. For example, asking it to predict character one by one might result in

abcdefgjffklmnopqrstuxwxyz

or something similar. Notice, the network almost gets things right. Also, it never 'gets lost' after making a mistake, for instance in the above example, after jff it produces k and gets back on track as if it had never made that mistake. The results are always different - sometimes network learns all the letters. However, the error still plateaus at the same value.

The error starts from around 7.0 and decreases down to 2.35 after which it slows down with every iteration, which seems like it's hitting a plateau.

If my alphabet consists only from a,b, then network almost instantly realises it should be producing abababababab, however the error starts at 0.8 and now always plateas at around 0.2 to 0.28

If with a,b, we set 4 timesteps, network learns to produce abab, but after 50 000 back-props (being well-stuck even after 25 000) it predicts 'a' only with 85%-ish certainty, even though I would expect it to be 99.999%; Similar value when 'b' has to be predicted. Once it gets stuck it maintains values similar to these. So it could keep guessing the same value over and over again when working with the a,b dataaset;

Strangelly, when working with that a,b dataset most of the time, I observe the final learnt probabilities to be:

• a=[0.68, 0.31] b=[0.15, 0.85]
• and sometimes, after re-initializing the network it learns the final probabilities as a=[0.8205, 0.1794] and b=[0.1795, 0.8205]

Disabling momentum (previous frame's grads times zero) still has same effect on a,b

The network doesn't explode, but its gradients seem to vanish.

Question:

Is it usual to get stuck at those values? Back-propping after 26 timesteps, done 200 000 times, and by that time the changes get turtle slow. The error sits at around 2.35 and is not worth the wait for another 0.000001 change in error.

Experimenting with a smaller learning rate (0.0004) allows the error to get down to 2.28 -that's the best I've got. Also, using a momentum coefficient with 0.2; It's applied to the previous frame's gradient. I don't increase momentum while the program executes, but keep it at a constant 0.2;

newgradient = newgradientMatrix + prevFrameGradientMatrix*0.2

I am not using any form of dropout etc. I just want the network to overfit, but it's getting stuck at 2.35 for 26-char aphabet.

I am only getting 0 error when an entire alphabet consists of a single character. In that case, the NN will predict aaaaaaaaaaaaaaaaa and error will be 0

Forward prop:

All is done on a single thread, in CPU. Using 'float' for the components of vectors.

• Tanh on dataGate and after the 'cell' is constructed (before the 'cell' is multiplied by an output gate)

• Sigmoid on Input, Forget and Output gate

• Each gate has Matrix of weights where each column is weights from neuron in current LSTM unit to all neurons in previous LSTM unit. Last column is ignored because nothing should feed into our bias. Also, bias value (but not the weights from it!) is set manually to 1.0 just to be sure.

• Each gate has a separate NxN matrix with recurrent weights (U-matrix) operating on the results of the current LSTM unit at [time-1]

• Both W and U keep the last row, so they both sample bias of lower-LSTM. This shouldn't create issues, granted that both of biases are back-propagated properly. In fact, last row was removed from U-Matrix altogether - just to be sure, but the error still plateaus at the same 2.35 quantity regardless.

Weight initialization: Xavier-Benjio with a uniform distribution page 253, bottom right. Boundaries of the uniform distrib are defined as mentioned here, like this:

low = -4*np.sqrt(6.0/(fan_in + fan_out)); // use |4| for sigmoid gates, |1| for tanh gates 
high = 4*np.sqrt(6.0/(fan_in + fan_out));

Cost function

Result of LSTM unit are softmaxed (bias is ignored), then passed through cross-entropy function to get a single float value.

Cross entropy is the correct one, for multi class classification.

float cost = 0;
for(each vector component){
    if(predictedVal == 0){  continue;  }
    cost += -(targetVec[i])*naturalLog(predictedVec[i]);
}
return cost;

The cost is then summed up across all timesteps and its average is returned right before we do the backprop. This is where I am getting plateaus at 2.3 for 26-character alphabet

By the way, the Cell (aka c) and Result (aka h) are cached after the last (26th timestep). After back-propagation they are used by timestep0. This could be (and was for some time) disabled, but the results are similar.

Backpropagation

Will list a couple of important gotchas & keypoints that I took care of:

1. de_dh is simply (targetVec - predictedVec), in that order. That's because the gathered gradient will be subtracted from the W and U matrices. This is due to derivatives cancelling out nicely when the softmax & crossEntropy are used together during forward prop.

2. To de_dh an extra gradient is added from t+1. That added quantity is sum from all 4 gates. To explain better, recall that one of such gates was forward-propping as follows:

   dataGate = tanh(W * incomingVal + U * lstmResultPrevT + bias_ComesFrom_W_and_U); //one of the 4 gates

   In the above formula, the bold represents the quantity from where the gradient is taken of one of such four gates at [t+1]. Such a gradient is then summed up across those 4 gates and added to de_dh, as stated originally. It's necessary to be done because during forward prop, 'H' of [t] has affected all 4 gates of [t+1]

3. When computing the gradient for Cell at [t], the cell's gradient from [t+1]is added. Afterwards, we compute a gradient for C of [t-1], to be able to repeat this process when we arrive to the earlier timestep.

4. The gradient for the U-weights leading to bias at [t-1] is computed with remembering that the bias's original value was 1.0; Also, it's double-checked to ensure gradient doesn't flow from our bias at [t] to the neurons at [t-1]. That's because nothing fed into our bias originally. As follows, the entire last column of U-gradient matrix is always 0.0;

   Similar thing is done for such a bias-column of the W matrix too - that entire column is zero.

5. Finally, the gradient is computed for each H of [t-1] for each of the four gates. This is done so that the '2. key-point' is possible (adding the 4-grads to de_dh), when we get to the earlier timestep in this back-prop.

Unit Tests & debugging:

after 20 000 backprops (done every 26 timesteps) a file is collected. it was observed that gradients were very small on all 4 gates, especially after being passed through the activation function at each gate. This is one of the reasons why Xavier init (above) was introduced, to prevent weights from being too large (shrinks grad after pushing-back through activation) or being too small (shrinks grad after pushing-back through weights).

A significant improvement was observed after 'norm clipping' was used, allowing my LSTM to seemingly learn a correct sequence even when 56 unique characters were used and backprop was done after 56 timesteps. Similar to the original example (with the 26 chars) only a couple of characters were predicted incorrectly. However the error still always plateaus, at a higher value (around 4.5)

Once again, is this traditional behavior, and I just have to rely on the things like dropout and averaging the results of multiple networks? However it seems that my network isn't even capable of overfitting...

---

Edit:

I've discovered one thing - the result of LSTM is vector, whose components cannot be less than -1 or greater than 1 (curtesy of tanh and sigmoid) As a result, $e^x$ cannot be smaller than ~0.36 or greater than ~2.71

So the probabilities always have some 'precipitation' dangling, and network always 'worries' that it can't reach 100% confidence? Tried to get clarification on that here

Answer 1

As stated in the last edit of my question, the issue indeed was to do with the softmax function.

As clarified here We shouldn't apply softmax directly to the result of the last LSTM. Notice, LSTM will produce a vector of values, each of which is bounded between -1 and 1 (due to the tanh squashing function that's applied to the Cell).

Instead, I've created a traditional fully-connected layer (just additional weight matrix), and feed result of LSTM to that layer. This "output" layer isn't activated - it feeds into a softmax function, which actually serves as an activation instead.

I modified the back-prop algorithm to supply the gradient generated by the softmax to the Output layer. Of course, if you used a cross entropy Cost function originally, then such a gradient will remain $(predicted - expected)$. It's then pushed through the weights of that Output Layer, to get the gradient w.r.t. LSTM. After this the backprop is applied as usual and the network finally converges.

Edit: There is slight improvement to momentum.

Also, using a momentum coefficient with 0.2; It's applied to the previous frame's gradient. I don't increase momentum while the program executes, but keep it at a constant 0.2;

newgradient = newgradientMatrix + prevFrameGradientMatrix*0.2

That's fine, but changing the momentum-coefficient will require us to also re-adjust learning rate. A cleaner version will be:

newgradient = newgradientMatrix*(1-0.9) + prevFrameGradientMatrix*0.9

Which is an exponential moving average, that remembers roughly $\frac{1}{0.1} = 10$ days.

On the 10th day, the coefficinet will be $$\frac{(1-\epsilon)^{\frac{1}{\epsilon}}}{0.9} = \frac{(1-0.1)^\frac{1}{0.1}}{0.9} = \frac{0.9^{10}}{0.9} \approx 0.387 \approx \frac{1}{e}$$ of the peak; Because 9 newer days have larger coefficients (larger than 0.387), their avearge really makes 10th day and older be negligible

Any older days will have even less contribution

Also, don't forget about the bias correction, - which helps get a better estimate when we are "just starting" to compute the average. Without the bias correction it would start very low, and will take some time to catch-up with the expected "exponential moving average"

newval = curval*(1-0.9) + prevVal*0.9
newval /= 1-(0.9)^t  //where t is timestep

However, in practice, it will be fine after approximately 10 timesteps - and so there is no real need for the bias correction in Momentum, but it should be done if we are using combination of Adam (a combination of Momentum & RMSProp)