Derivation of back propagation though time

There is a wonderful explanation for the implementation of Backpropagation through time in the this article by Denny Britz here:

http://www.wildml.com/2015/10/recurrent-neural-networks-tutorial-part-3-backpropagation-through-time-and-vanishing-gradients/

I would like to find the derivation steps as mathematical equations for dLDU, dLdV and dLDW. I would also like to know the significance of "delta_t" in this code.

def bptt(self, x, y):
T = len(y)
# Perform forward propagation
o, s = self.forward_propagation(x)
# We accumulate the gradients in these variables
dLdU = np.zeros(self.U.shape)
dLdV = np.zeros(self.V.shape)
dLdW = np.zeros(self.W.shape)
delta_o = o
delta_o[np.arange(len(y)), y] -= 1.
# For each output backwards...
for t in np.arange(T)[::-1]:
dLdV += np.outer(delta_o[t], s[t].T)
# Initial delta calculation: dL/dz
delta_t = self.V.T.dot(delta_o[t]) * (1 - (s[t] ** 2))
# Backpropagation through time (for at most self.bptt_truncate steps)
for bptt_step in np.arange(max(0, t-self.bptt_truncate), t+1)[::-1]:
# print "Backpropagation step t=%d bptt step=%d " % (t, bptt_step)
# Add to gradients at each previous step
dLdW += np.outer(delta_t, s[bptt_step-1])
dLdU[:,x[bptt_step]] += delta_t
# Update delta for next step dL/dz at t-1
delta_t = self.W.T.dot(delta_t) * (1 - s[bptt_step-1] ** 2)
return [dLdU, dLdV, dLdW]


You may also provide me a link to any relevant paper that explains these mathematical steps explicitly. (I have been unable to find a relevant paper as most seem esoteric)

• Goodfellow's deep learning has all the steps and free online. Nov 22 '17 at 19:56
• Goodfellows book link -- deeplearningbook.org/contents/rnn.html Oct 22 '19 at 1:28

1 Answer

You may follow the derivation of dLdV in this link: https://github.com/go2carter/nn-learn/blob/master/grad-deriv-tex/rnn-grad-deriv.pdf.

For the derivative w.r.t. $U$ (and similarly $W$):

\begin{aligned} \frac{\partial E_t}{\partial U} &= \sum\limits_{k=0}^{t} \frac{\partial E_t}{\partial z_k}\frac{\partial z_k}{\partial U}\\ &= \sum\limits_{k=0}^{t} x_k \frac{\partial E_t}{\partial z_k}\end{aligned}

in which $z_k = Ux_k + Ws_{k-1}$. This is because of the fact that $U$ contributes to all $z_k$'s up to $k=t$. The second equation is a little subtle; please take a look at this link: https://math.stackexchange.com/questions/1621948/derivative-of-a-vector-with-respect-to-a-matrix.

delta_t in your code is precisely the $\frac{\partial E_t}{\partial z_k}$, which needs to be updated for each decrement of $k$. The trick here is that:

$$\frac{\partial E_t}{\partial z_{k-1}} = \frac{\partial E_t}{\partial z_k} \frac{\partial z_k}{\partial z_{k-1}}$$

So we only need to compute $\frac{\partial z_k}{\partial z_{k-1}}$ for each decrement of $k$ and use it to update delta_t.

Please let me know if it's still confusing.