Can someone please explain the truncated back propagation through time algorithm?

Question

I am reading about RNNs and how to train them and I understood how back propagation works. I have the following model: $$ h_t=f(Ah_{t-1}+ B x_t),\\ \hat{y}_t=g(C h_t). $$ For a given sample $(x_1^T,y_1^T)$, my loss function is $L_2$-loss given by $L=\frac{1}{2} \sum_{t=1}^T \|\hat{y}_t-y_t\|^2$. My understanding of back propagation through time(BPTT) is that we can compute the gradients $\frac{\partial{L}}{\partial h_t}$ recursively as follows: \begin{align*} \frac{\partial{L}}{\partial h_T}=C^\top((\hat{y}_t-y_t)\odot g'(Ch_T) ),\\ \frac{\partial{L}}{\partial h_{T-1}}=C^\top((\hat{y}_{t-1}-y_{t-1})\odot g'(Ch_{T-1}) )+\frac{\partial{L}}{\partial h_T} \frac{\partial{h_T}}{\partial h_{T-1}}. \end{align*} Thus proceeding backwards in time one can compute $\frac{\partial{L}}{\partial h_t}$ in terms of $\frac{\partial{L}}{\partial h_{t+1}}$ for all $t=1,\ldots,T-1$. We can find the parameter gradients using: $$ \frac{\partial{L}}{\partial A}=\sum_{t=1}^T \frac{\partial{L}}{\partial h_t} \frac{\partial{h_t}}{\partial A}=\sum_{t=1}^T (\frac{\partial{L}}{\partial h_t} \odot f'(Ah_{t-1}+Bx_t) )h_{t-1}^T. $$

How does the truncated backpropagation algorithm fit into this framework? Can anyone explain it clearly?

Answer 1

I am sure you have found your answer by now, but for others. The truncated part of Truncated Backpropagation through Time simply refers to at which point in time to stop calculating the gradients for the backpropagation phase.

Lets say you truncate after $k$ steps then the difference is you calculate the below instead.

$$ \frac{\partial{L}}{\partial A}\approx\sum_{t=T-k}^{T}\frac{\partial{L}}{\partial h_{t}}\frac{\partial^{+}{h_{t}}}{\partial A}=\sum_{t=T-k}^{T}(\frac{\partial{L}}{\partial h_{t}}\odot f'(Ah_{t-1}+Bx_{t}))h_{t-1}^{T}. $$

Where $\frac{\partial^{+}}{\partial{A}}$ is the "immediate" partial wrt A, i.e. the one that assumes all terms other than an explicit A are constant. Essentially you are truncating the sum in Equation (4) of Pascanu, Mikolov, and Bengio.

At least this is my understanding of it judging from Ilya Sutskever's psuedo-code in his thesis.

Truncated BPTT is given below:
 1: for t from 1 to T do
 2:   Run the RNN for one step, computing ht and zt
 3:   if t divides k1 then
 4:     Run BPTT (as described in sec. 2.5), from t down to t − k2
 5:   end if
 6: end for