# How to derive BPTT algorithm

To gain an understanding of BPTT, I'm attempting to derive the formulas for BPTT by hand, but keep getting stuck. Here's what I have so far.

Forward Pass 1

$a_0 = x_0 * u_0$

$b_0 = s_{-1} * w_0$

$z_0 = a_0 + b_0$

$s_0 = func_0(z_0)$ (where $func_0$ is sig, or tanh)

Foward Pass 2

$a_1 = x_1 * u_1$

$b_1 = s_0 * w_1$

$z_1 = a_1 + b_1$

$s_1 = func_1(z_1)$ (where $func_1$ is sig, or tanh)

$q = s_1 * v_1$

Output pass

$o = func_2(q)$ (where $func_2$ is softmax)

$E = func_3(o)$ (where $func_3$ is x-entropy)

Now, attempting to hand-bomb back prop, for U (by working backwards through the above network).

$\partial E/\partial u = \partial E/\partial u_1 + \partial E/\partial u_0$

$\partial E/\partial u_1 = \partial E/\partial o * \partial o/\partial q * \partial q/\partial s_1 * \partial s_1/\partial z_1 * \partial z_1/\partial a_1 * \partial a_1/\partial u_1$

$\partial E/\partial u_0 = \partial E/\partial o * \partial o/\partial q * \partial q/\partial s_1 * \partial s_1/\partial z_1 * \partial z_1/\partial b_1 * \partial b_1/\partial s_0 * \partial s_0/dz_0 * \partial z_0/\partial a_0 * \partial a_0/\partial u_0$

Gathering like terms

$\partial E/\partial u = \partial E/\partial o * \partial o/\partial q * \partial q/\partial s_1 * \partial s_1/\partial z_1 * ((\partial z_1/\partial a_1 * \partial a_1/\partial u_1) + (\partial z_1/\partial b_1 * \partial b_1/\partial s_0 * \partial s_0/\partial z_0 * \partial z_0/\partial a_0 * \partial a_0/\partial u_0))$

Making substitutions

$\partial E/\partial u = \partial E/\partial o * \partial o/\partial q * v_1 * \partial s_1/\partial z_1 * ((1 * x_1) + (1 * w_1 * \partial s_0/\partial z_0 * 1 * x_0))$

Ending with a nice, clean formula.

$\partial E/\partial u = \partial E/\partial o * \partial o/\partial q * v_1 * \partial s_1/\partial z_1 * (x_1 + w_1 * \partial s_0/\partial z_0 * x_0)$

And similarly

$\partial E/\partial w = \partial E/\partial o * \partial o/\partial q * v_1 * \partial s_1/\partial z_1 * (s_0 + w_1 * \partial s_0/\partial z_0 * s_{-1})$

The problem I face here is one of dimensionality. My gut says w1 should not be in here. Does this formula make sense to anyone? Where have I gone wrong?

Thanks

It's the right idea, but the RNN update equations in the question are non-standard. Generally the hidden state is computed as a linear combination of the previous hidden state and the input at that time. I will go through and replace the equations, but I think that your formulation is not wrong:

Just for the forward pass:

Forward Pass 1

$a_0 = x_0 * u_0$

Assuming that the input for time $t$ is $x_t$ and that we are dealing with scalar inputs and parameters (as opposed to vectors)

$b_0 = s_{-1} * w_0$

Assuming $s$ is the state

$z_0 = a_0 * b_0$

Generally, $z_0 = a_0 + b_0 + k$ for some constant k. Intuitively, this is because the hidden state is then a combination of the input at time $t$ and the hidden state from the previous time $t-1$. In this way, they both contribute to the hidden state, but not synergistically. For many applications of RNN, this seems to be a good assumption (they work well). I am not sure whether the optimization of a network that uses products of the previous hidden state with the current input would be stable in optimization.

$s_0 = func_0(z_0)$ (where $func_0$ is sig, or tanh)

$s_0 = func(z_0)$ --- no need to index the activation function by time step.

Also, there is no real need to index the parameters $u_0, w_0$, although it does help because ultimately when we derive the gradient of the parameters, we sum over time steps. Really, though, in describing the forward pass you can just say

$z_0 = u*x_0 + w*s_{-1} + k$

$s_0 = funct(z_0)$

or

$z_t = u*x_t + w*s_{t-1} + k$

$s_t = func(z_t)$

Foward Pass 2

$a_1 = x_1 * u_1$

$b_1 = s_0 * w_1$

$z_1 = a_1 * b_1$

$s_1 = func_1(z_1)$ (where $func_1$ is sig, or tanh)

$q = s_1 * v_1$

$z_1 = u*x_1 + w*s_{0} + k$

$s_1 = funct(z_1)$

$q = s_1*v1+c$

Note that what you've defined here is actually not a standard RNN, but a many-to-one RNN:

For more detail on this and RNNs in general, I would definitely recommend Goodfellow et al RNN chapter and Andrej Karpathy's post and minimal character RNN implementation.

Output pass

$o = func_2(q)$ (where $func_2$ is softmax)

$E = func_3(o)$ (where $func_3$ is x-entropy)

$o = soft(q)$ (where $soft$ is softmax)

$E = L(o)$ (where $L$ is x-entropy)

Now, attempting to hand-bomb back prop, for U (by working backwards through the above network). $\partial E/\partial u = \partial E/\partial u_1 + \partial E/\partial u_0$

$\partial E/\partial u_1 = \partial E/do * \partial o/\partial q * \partial q/\partial s_1 * \partial s_1/\partial z_1 * \partial z_1/\partial a_1 * \partial a_1/\partial u_1$

$\partial E/\partial u_0 = \partial E/\partial o * \partial o/\partial q * \partial q/\partial s_1 * \partial s_1/\partial z_1 * \partial z_1/\partial b_1 * \partial b_1/\partial s_0 * \partial s_0/dz_0 * \partial z_0/\partial a_0 * \partial a_0/\partial u_0$

Gathering like terms

$\partial E/\partial u = \partial E/\partial o * \partial o/\partial q * \partial q/\partial s_1 * \partial s_1/\partial z_1 * ((\partial z_1/\partial a_1 * \partial a_1/\partial u_1) + (\partial z_1/\partial b_1 * \partial b_1/\partial s_0 * \partial s_0/\partial z_0 * \partial z_0/\partial a_0 * \partial a_0/\partial u_0))$

Making substitutions

$\partial E/\partial u = \partial E/\partial o * \partial o/\partial q * v_1 * \partial s_1/\partial z_1 * ((1 * x_1) + (1 * w_1 * \partial s_0/\partial z_0 * 1 * x_0))$

Ending with a nice, clean formula.

$\partial E/\partial u = \partial E/\partial o * \partial o/\partial q * v_1 * \partial s_1/\partial z_1 * (x_1 + w_1 * \partial s_0/\partial z_0 * x_0)$

For u, the derivative is

$\dfrac{\partial{L}}{\partial{u}}=\sum_t \dfrac{\partial{L}}{\partial{u_t}} = \dfrac{\partial L}{\partial o} \dfrac{\partial o}{\partial s_1} \dfrac{\partial s_1}{\partial u_1}+\dfrac{\partial L}{\partial o} \dfrac{\partial o}{\partial s_1}\dfrac{\partial s_1}{\partial s_0}\dfrac{\partial s_0}{\partial u_0}$

And similarly

$\partial E/\partial w = \partial E/\partial o * \partial o/\partial q * v_1 * \partial s_1/\partial z_1 * (s_0 + w_1 * \partial s_0/\partial z_0 * s_{-1})$

For w:

$\dfrac{\partial{L}}{\partial{w}}=\sum_t \dfrac{\partial{L}}{\partial{w_t}} = \dfrac{\partial L}{\partial o} \dfrac{\partial o}{\partial s_1} \dfrac{\partial s_1}{\partial w_1}+\dfrac{\partial L}{\partial o} \dfrac{\partial o}{\partial s_1}\dfrac{\partial s_1}{\partial s_0}\dfrac{\partial s_0}{\partial w_0}$

• Thanks for the response. I noticed a typo, my z formula should have been addition, not multiplication. Regarding your final formula, Can you please explain how you were able to eliminate so many terms in your last step, and what ds1/ds0 actually means? – 1point8zero61 May 31 '17 at 20:38
• Since s1=ux1+ws0, ds1/ds0=w is the partial derivative of ds1/ds0. There are fewer terms partly because the equation for z has an addition rather than a multiplication, so there is no need for the product rule and partly because, for example, do/ds1=do/dq*dq/ds1 and partly because I didn't define a new function a = uxt as, for example, but instead just wrote s explicitly as a function of u and xt. – user0 May 31 '17 at 21:15