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{equation} \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} \end{equation} 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 \begin{equation} \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} \end{equation} 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{equation} \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} \end{equation} 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: \begin{equation} \frac{\partial L}{\partial L^{(t)}} = 1 \end{equation}
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{equation} \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} \end{equation}
Yet this is calculated to be:
\begin{equation}
\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)}}
\end{equation}
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 \begin{equation} S=\sum\limits_{k=1}^3 \exp\bigg(c_k^{(\tau)} + \sum\limits_{l=1}^5 v_{kl}h_l^{(\tau)}\bigg) \end{equation} 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: \begin{equation} -\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} \end{equation} 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.
