2
$\begingroup$

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)

$\endgroup$
2
3
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.