# Backpropagation Through Time Error Computation

I'm attempting to work through the backpropagation through time terms using this source:

http://www.deeplearningbook.org/contents/rnn.html

The final formulas are given on pages 385 and 386, but I wanted to work through the algebra to get a better understanding for them. I've computed the first two error terms but my solutions do not match 100% what's presented. The network is characterized as follows:

I'm basing my work on the following

\begin{align} \mathbf{a}^{(t)} &= \mathbf{b} + \mathbf{W}\mathbf{h}^{(t-1)} + \mathbf{U}\mathbf{x}^{(t)}\\ \mathbf{h}^{(t)} &= \tanh(\mathbf{a}^{(t)})\\ \mathbf{o}^{(t)} &= \mathbf{c} + \mathbf{V}\mathbf{h}^{(t)}\\ \hat{\mathbf{y}}^{(t)} &= \text{softmax}(\mathbf{o}^{(t)}) \end{align}

where $\mathbf{b}$ and $\mathbf{c}$ are the biases for there respective neurons. $\mathbf{W}$ is the weight matrix from the previous activation $\mathbf{h}^{(t-1)}$, $\mathbf{U}$ is the weight matrix for the input vector $\mathbf{x}^{(t)}$, and $\mathbf{V}$ is the weight matrix for our current activations vector $\mathbf{h}^{(t)}$. The Loss function is the negative log likelihood and the softmax function is used for output activations to obtain a vector $\hat{\mathbf{y}}^{(t)}$ of probabilities over the output.

I have the following example to help with the understanding of the network. Let the inputs $\mathbf{x}^{(t)} \in \mathbb{R}^4$, the outputs $\mathbf{o}^{(t)} \in \mathbb{R}^3$ and the actual values $\mathbf{y}^{(t)} \in \mathbb{R}^3$, furthermore we let the weights $\mathbf{U} \in \mathbb{R}^{5\times 4}, \mathbf{W} \in \mathbb{R}^{5\times 5}$ and $\mathbf{V} \in \mathbb{R}^{3\times 5}$, and finally the biases $\mathbf{b} \in \mathbb{R}^5$, and $\mathbf{c} \in \mathbb{R}^3$. Written out fully we would have:

$$\begin{pmatrix} a_1^{(t)}\\ a_2^{(t)}\\ a_3^{(t)}\\ a_4^{(t)}\\ a_5^{(t)} \end{pmatrix} = \begin{pmatrix} b_1^{(t)}\\ b_2^{(t)}\\ b_3^{(t)}\\ b_4^{(t)}\\ b_5^{(t)} \end{pmatrix} + \begin{pmatrix} w_{11} & w_{12} & w_{13} & w_{14} & w_{15}\\ w_{21} & w_{22} & w_{23} & w_{24} & w_{25}\\ w_{31} & w_{32} & w_{33} & w_{34} & w_{35}\\ w_{41} & w_{42} & w_{43} & w_{44} & w_{45}\\ w_{51} & w_{52} & w_{53} & w_{54} & w_{55} \end{pmatrix} \begin{pmatrix} h_1^{(t-1)}\\ h_2^{(t-1)}\\ h_3^{(t-1)}\\ h_4^{(t-1)}\\ h_5^{(t-1)} \end{pmatrix} + \begin{pmatrix} u_{11} & u_{12} & u_{13} & u_{14}\\ u_{21} & u_{22} & u_{23} & u_{24}\\ u_{31} & u_{32} & u_{33} & u_{34}\\ u_{41} & u_{42} & u_{43} & u_{44}\\ u_{51} & u_{52} & u_{53} & u_{54} \end{pmatrix} \begin{pmatrix} x_1^{(t)}\\ x_2^{(t)}\\ x_3^{(t)}\\ x_4^{(t)} \end{pmatrix}$$ Which we can write a little more compactly as \begin{align} a_1^{(t)} &= b_1^{(t)} + \sum\limits_{i=1}^5 w_{1i}h_i^{(t-1)} + \sum\limits_{j=1}^4 u_{1j}x_j^{(t)}\\ a_2^{(t)} &= b_2^{(t)} + \sum\limits_{i=1}^5 w_{2i}h_i^{(t-1)} + \sum\limits_{j=1}^4 u_{2j}x_j^{(t)}\nonumber\\ a_3^{(t)} &= b_3^{(t)} + \sum\limits_{i=1}^5 w_{3i}h_i^{(t-1)} + \sum\limits_{j=1}^4 u_{3j}x_j^{(t)}\nonumber\\ a_4^{(t)} &= b_4^{(t)} + \sum\limits_{i=1}^5 w_{4i}h_i^{(t-1)} + \sum\limits_{j=1}^4 u_{4j}x_j^{(t)}\nonumber\\ a_5^{(t)} &= b_5^{(t)} + \sum\limits_{i=1}^5 w_{5i}h_i^{(t-1)} + \sum\limits_{j=1}^4 u_{5j}x_j^{(t)}\nonumber \end{align} We could do the same for the output so that we arrive at $$\label{o_vector} \begin{pmatrix} o_1^{(t)}\\ o_2^{(t)}\\ o_3^{(t)} \end{pmatrix} = \begin{pmatrix} c_1^{(t)}\\ c_2^{(t)}\\ c_3^{(t)}\end{pmatrix} + \begin{pmatrix} v_{11} & v_{12} & v_{13} & v_{14} & v_{15}\\ v_{21} & v_{22} & v_{23} & v_{24} & v_{25}\\ v_{31} & v_{32} & v_{33} & v_{34} & v_{35} \end{pmatrix} \begin{pmatrix} \tanh\big(a_1^{(t)}\big)\\ \tanh\big(a_2^{(t)}\big)\\ \tanh\big(a_3^{(t)}\big)\\ \tanh\big(a_4^{(t)}\big)\end{pmatrix}$$ Which can also be rewritten as: \begin{align} o_1^{(t)} &= c_1^{(t)} + \sum\limits_{i=1}^5 v_{1i}h_i^{(t)}\\ o_2^{(t)} &= c_2^{(t)} + \sum\limits_{i=1}^5 v_{2i}h_i^{(t)}\nonumber\\ o_3^{(t)} &= c_3^{(t)} + \sum\limits_{i=1}^5 v_{3i}h_i^{(t)}\nonumber \end{align}

and the softmax outputs: $$\begin{pmatrix} \hat{y}_1^{(t)}\\ \hat{y}_2^{(t)}\\ \hat{y}_3^{(t)} \end{pmatrix} = \frac{1}{\sum\limits_{i=1}^3 \exp\big(o_i^{(t)}\big)}\begin{pmatrix} \exp\big(o_1^{(t)}\big)\\ \exp\big(o_2^{(t)}\big)\\ \exp\big(o_3^{(t)}\big) \end{pmatrix}$$ In the derivation of the backpropagation through time we assume that the outputs $\mathbf{o}^{(t)}$ are used as the argument to the softmax function to obtain the vector $\hat{\mathbf{y}}$ of the probabilities over the output. It is also assumed that the loss is the negative log-likelihood of the true target $y^{(t)}$ given the input so far. We start the recursion with the nodes immediately preceding the final loss so that: $$\frac{\partial L}{\partial L^{(t)}} = 1$$

For the example the loss is expressed as: \begin{align} L &= -\sum\limits_{i=1}^3 y_i^{(t)}\ln\big(\hat{y}_i^{(t)}\big)\\ &= -\bigg( y_1^{(t)}\ln\big(\hat{y}_1^{(t)}\big) + y_2^{(t)}\ln\big(\hat{y}_2^{(t)}\big) + y_3^{(t)}\ln\big(\hat{y}_3^{(t)}\big)\bigg)\\ &= -\Bigg[y_1^{(t)}\ln\begin{pmatrix} \frac{\exp\big(o_1^{(t)}\big)}{\sum\limits_{i=1}^3 \exp\big(o_i^{(t)}\big)}\end{pmatrix} + y_2^{(t)}\ln\begin{pmatrix} \frac{\exp\big(o_2^{(t)}\big)}{\sum\limits_{i=1}^3 \exp\big(o_i^{(t)}\big)}\end{pmatrix} + y_3^{(t)}\ln\begin{pmatrix} \frac{\exp\big(o_3^{(t)}\big)}{\sum\limits_{i=1}^3 \exp\big(o_i^{(t)}\big)}\end{pmatrix} \Bigg]\\ &= -\Bigg[y_1^{(t)}\bigg(o_1^{(t)} - \ln\Big(\sum\limits_{i=1}^3 \exp\big(o_i^{(t)}\big)\Big)\bigg) + y_2^{(t)}\bigg(o_2^{(t)} - \ln\Big(\sum\limits_{i=1}^3 \exp\big(o_i^{(t)}\big)\Big)\bigg) \nonumber\\ & \ \qquad + y_3^{(t)}\bigg(o_3^{(t)} - \ln\Big(\sum\limits_{i=1}^3 \exp\big(o_i^{(t)}\big)\Big)\bigg)\Bigg] \end{align} When computing the gradient $\nabla_{\mathbf{o}^{(t)}} L$ on the outputs at time step $t$ for all $i, t$, I get: \begin{align} \frac{\partial L}{\partial o_1^{(t)}} = \frac{\partial L}{\partial L^{(t)}}\frac{\partial L^{(t)}}{\partial o_1^{(t)}} &= - \Bigg[ y_1^{(t)} \begin{pmatrix}1 - \frac{\exp(o_1^{(t)})}{\sum\limits_{i=1}^3 \exp\big(o_i^{(t)}\big)}\end{pmatrix} + y_2^{(t)} \begin{pmatrix} - \frac{\exp(o_1^{(t)})}{\sum\limits_{i=1}^3 \exp\big(o_i^{(t)}\big)}\end{pmatrix} \\ & \ \qquad + y_3^{(t)} \begin{pmatrix} - \frac{\exp(o_1^{(t)})}{\sum\limits_{i=1}^3 \exp\big(o_i^{(t)}\big)}\end{pmatrix} \Bigg]\nonumber \end{align} which can be simplified to \begin{align} \frac{\partial L}{\partial o_1^{(t)}} = \frac{\partial L}{\partial L^{(t)}}\frac{\partial L^{(t)}}{\partial o_1^{(t)}} &= -\Bigg[y_1^{(t)} \Big(1 - \hat{y}_1^{(t)}\Big) + y_2^{(t)}\Big(-\hat{y}_1^{(t)}\Big)+ y_3^{(t)}\Big(-\hat{y}_1^{(t)}\Big) \Bigg] \end{align} distributing the minus sign and writing this in matrix form we have: $$\begin{pmatrix} \Big(\hat{y}_1^{(t)}-1\Big) & \hat{y}_1^{(t)} & \hat{y}_1^{(t)}\\ \hat{y}_2^{(t)} & \Big(\hat{y}_2^{(t)}-1\Big) & \hat{y}_2^{(t)}\\ \hat{y}_3^{(t)} & \hat{y}_3^{(t)} & \Big(\hat{y}_3^{(t)}-1\Big) \end{pmatrix} \begin{pmatrix}y_1^{(t)} \\y_2^{(t)}\\y_3^{(t)}\end{pmatrix}$$

Yet this is calculated to be: $$\big(\nabla_{\mathbf{o}^{(t)}} L\big)_i = \frac{\partial L}{\partial o_i^{(t)}} = \frac{\partial L}{\partial L^{(t)}}\frac{L^{(t)}}{\partial o_i^{(t)}} = \hat{y}_i^{(t)} - \mathbf{1}_{i, y^{(t)}}$$ Where $\mathbf{1}_{\text{condition}} = 1$ if the condition is true, else is zero. (I'm relatively certain that my calculations are correct and it's just a notation issue between what I have and what's presented in the book)

Moving on, we take a look at $\nabla_{h^{(\tau)}}L$ at the final time step $\tau$ and begin by computing $\frac{\partial \hat{y}_1^{(\tau)}}{\partial h_1}$ \begin{align} \hat{y}_1^{(\tau)} &= \frac{\exp(o_1^{(\tau)})}{\sum\limits_{i=1}^3 \exp\big(o_i^{(\tau)}\big)}\\ &= \frac{\exp\bigg(c_1^{(\tau)} + \sum\limits_{i=1}^5 v_{1i}h_i^{(\tau)}\bigg)}{\sum\limits_{k=1}^3 \exp\bigg(c_k^{(\tau)} + \sum\limits_{l=1}^5 v_{kl}h_l^{(\tau)}\bigg)} \end{align} For simplicity we let $$S=\sum\limits_{k=1}^3 \exp\bigg(c_k^{(\tau)} + \sum\limits_{l=1}^5 v_{kl}h_l^{(\tau)}\bigg)$$ then the partial derivative with respect to $h_1$ is: \begin{align} \frac{\partial \hat{y}_1^{(\tau)}}{\partial h_1} =\Bigg[ v_{11}\exp\bigg(c_1^{(\tau)} + \sum\limits_{i=1}^5 v_{1i}h_i^{(\tau)}\bigg) \times S - \Bigg(&v_{11}\exp\bigg(c_1^{(\tau)} + \sum\limits_{i=1}^5 v_{1i}h_i^{(\tau)}\bigg) \\ & \ + v_{21}\exp\bigg(c_2^{(\tau)} + \sum\limits_{i=1}^5 v_{1i}h_i^{(\tau)}\bigg)\nonumber\\ & + v_{31}\exp\bigg(c_3^{(\tau)} + \sum\limits_{i=1}^5 v_{1i}h_i^{(\tau)}\bigg)\Bigg)\nonumber\\ & \ \times \exp\bigg(c_1^{(\tau)} + \sum\limits_{i=1}^5 v_{1i}h_i^{(\tau)}\bigg)\Bigg]\nonumber\\ \Bigg/ S^2\nonumber \end{align} written a little more compactly we would have \begin{align} \frac{\partial \hat{y}_1^{(\tau)}}{\partial h_1} &= \frac{v_{11}\exp(o_1^{(\tau)})\times S - \bigg( v_{11}\exp(o_1^{(\tau)}) + v_{21}\exp(o_2^{(\tau)}) + v_{31}\exp(o_3^{(\tau)})\bigg) \times \exp(o_1^{(\tau)})}{S^2}\\ &= v_{11} \hat{y}_1^{(\tau)} - v_{11} \hat{y}_1^{(\tau)} \hat{y}_1^{(\tau)} - v_{21} \hat{y}_2^{(\tau)} \hat{y}_1^{(\tau)} - v_{31} \hat{y}_3^{(\tau)} \hat{y}_1^{(\tau)}\\ &= -\hat{y}_1^{(\tau)}\bigg[v_{11}\Big( \hat{y}_1^{(\tau)}-1\Big) + v_{21} \hat{y}_2^{(\tau)} + v_{31} \hat{y}_3^{(\tau)}\bigg] \end{align} We could do the same for $\frac{\partial \hat{y}_1^{(\tau)}}{\partial h_2}, \frac{\partial \hat{y}_1^{(\tau)}}{\partial h_3}, \frac{\partial \hat{y}_1^{(\tau)}}{\partial h_4}$ and $\frac{\partial \hat{y}_1^{(\tau)}}{\partial h_5}$ to yield:

\begin{align} \frac{\partial \hat{y}_1^{(\tau)}}{\partial h_2} &= -\hat{y}_1^{(\tau)}\bigg[v_{12}\Big( \hat{y}_1^{(\tau)}-1\Big) + v_{22} \hat{y}_2^{(\tau)} + v_{32} \hat{y}_3^{(\tau)}\bigg]\\ \frac{\partial \hat{y}_1^{(\tau)}}{\partial h_3} &= -\hat{y}_1^{(\tau)}\bigg[v_{13}\Big( \hat{y}_1^{(\tau)}-1\Big) + v_{23} \hat{y}_2^{(\tau)} + v_{33} \hat{y}_3^{(\tau)}\bigg]\\ \frac{\partial \hat{y}_1^{(\tau)}}{\partial h_4} &= -\hat{y}_1^{(\tau)}\bigg[v_{14}\Big( \hat{y}_1^{(\tau)}-1\Big) + v_{24} \hat{y}_2^{(\tau)} + v_{34} \hat{y}_3^{(\tau)}\bigg]\\ \frac{\partial \hat{y}_1^{(\tau)}}{\partial h_5} &= -\hat{y}_1^{(\tau)}\bigg[v_{15}\Big( \hat{y}_1^{(\tau)}-1\Big) + v_{25} \hat{y}_2^{(\tau)} + v_{35} \hat{y}_3^{(\tau)}\bigg] \end{align} for $\hat{y}_1^{(\tau)}$ this can be written as: $$-\hat{y}_1^{(\tau)} \begin{pmatrix} v_{11} & v_{21} & v_{31}\\ v_{12} & v_{22} & v_{32}\\ v_{13} & v_{23} & v_{33}\\ v_{14} & v_{24} & v_{34}\\ v_{15} & v_{25} & v_{35} \end{pmatrix} \begin{pmatrix} \hat{y}_1^{(\tau)}-1\\ \hat{y}_2^{(\tau)}\\ \hat{y}_3^{(\tau)} \end{pmatrix}$$ If we were to compute $\hat{y}_2^{(\tau)}$ and $\hat{y}_3^{(\tau)}$ we would have something resembling $\mathbf{V}^T\nabla_{o^{(t)}} L$. We would have:

$-\begin{pmatrix} \hat{y}_1^{(\tau)} & 0 & 0\\ 0 & \hat{y}_2^{(\tau)} & 0\\ 0 & 0 & \hat{y}_3^{(\tau)}\end{pmatrix}\begin{pmatrix} v_{11} & v_{21} & v_{31}\\ v_{12} & v_{22} & v_{32}\\ v_{13} & v_{23} & v_{33}\\ v_{14} & v_{24} & v_{34}\\ v_{15} & v_{25} & v_{35} \end{pmatrix}\begin{pmatrix} \hat{y}_1^{(\tau)}-1 & \hat{y}_1^{(\tau)} & \hat{y}_1^{(\tau)}\\ \hat{y}_2^{(\tau)} & \hat{y}_2^{(\tau)}-1 & \hat{y}_2^{(\tau)}\\ \hat{y}_3^{(\tau)} & \hat{y}_3^{(\tau)} & \hat{y}_3^{(\tau)}-1 \end{pmatrix}$

I'm unsure whether I have made an error or if there is a problem in the source material. My computations show that the matrices would be multiplied by $-\hat{y}_i^{(\tau)}$ which is nowhere to be found in the source material, and I'm unsure whether the mistake is no my part or I'm missing something.

Tex file for the above

PDF file for the above

• Welcome to CV. Where is your question? In other words, what do you hope to learn from your fellow CVers? – DJohnson Aug 2 '16 at 22:19
• I'm unsure if my results pertaining to the error terms for BPTT is correct since it differs slightly from those found in the source that I'm using. I'm unsure whether there is an error in my work or if I'm simply missing something. I've tried to make my issues a little more visible by making the statement bold and highlighting them in gray, since it is a long derivation. – Lukasz Aug 2 '16 at 23:32

Your derivation is indeed correct. You should have the component $-\hat{y}_1^{(\tau)}$ in the formular of $\frac{\partial \hat{y}_1^{(\tau)}}{\partial h_1}$. However, these components $-\hat{y}_i^{(\tau)}$'s will be cancelled out when you compute $\nabla_{h^{(\tau)}}L$. For example:
\begin{aligned} \nabla_{h^{(\tau)}_1}L &= -\sum_{i=1}^3 \nabla_{\hat{y}^{(\tau)}_i}L \nabla_{h^{(\tau)}_1}\hat{y}^{(\tau)}_i \\ &= -\sum_{i=1}^3 y_i^{(\tau)}\frac{1}{\color{red}{\hat{y}_i^{(\tau)}}} \nabla_{h^{(\tau)}_1}\hat{y}^{(\tau)}_i\end{aligned}