3
$\begingroup$

This is a basic recurrent neural network (RNN), and I am trying to figure out the derivation of its backpropagation and all intermediate steps, I encounter 3rd-order tensor, and not sure if I am doing right.

This RNN is designed for a language model, so its purpose is to predict the next word given previous words in a sentence. The input word is represented as a word vector. The cost function is cross-entropy ($CE$).

The definition:

\begin{align*} \underset{1 \times D_h}{h^{(t)}} &= \mathrm{sigmoid}(\underset{1 \times D_h}{z_1^{(t)}}) = \mathrm{sigmoid}\bigg( \underset{1 \times D_h,}{h^{(t - 1)}} \underset{D_h \times D_h}{H} + \underset{1\times d,}{e^{(t)}} \underset{d \times D_h}{I} + \underset{1 \times D_h}{b_1} \bigg) \\ \underset{1 \times \left|V\right|}{\hat y^{(t)}} &= \mathrm{softmax}(\underset{1 \times \left|V\right|}{z_2^{(t)}}) = \mathrm{softmax}\bigg( \underset{1 \times D_h,}{h^{(t)}} \underset{D_h \times \left| V \right |}{U} + \underset{1 \times \left| V \right|}{b_2} \bigg) \\ J^{(t)} &= CE(y^{(t)}, \hat{y}^{(t)}) = \sum_{j=1}^{\left|V\right|}y_j^{(t)}\mathrm{log}(\hat{y}_j^{(t)}) \end{align*}

  • $e^{(t)}$: the input word embedding at $t$th time step.
  • $I$: the input word representation matrix.
  • $H$: the hidden transformation matrix.
  • $U$: the output word representation matrix.

Dimensions:

  • $\left|V\right|$: dimension of vocabulary
  • $D_h$: hidden layer size
  • $d$: size of word embedding

$z_1$ and $z_2$ are intermeidate variables added for convenience.

As seen, I labeled the matrix sizes for each quantity except for scalar.

Here, I am most interested in the derivation of

$$\underset{D_h \times D_h}{\frac{\partial J^{(t)}}{\partial H}\bigg|_t} $$

with emphasis on all the intermediate steps. Here is my attempt:

\begin{align*} \underset{D_h \times D_h}{\frac{\partial J^{(t)}}{\partial H}\bigg|_t} &= \underset{1 \times \left|V\right|,}{\frac{\partial J^{(t)}}{\partial z_2^{(t)}}} \underset{\left|V\right| \times D_h,}{\frac{\partial z_2^{(t)}}{\partial h^{(t)}}} \underset{D_h \times D_h,}{\frac{\partial h^{(t)}}{\partial z_1^{(t)}}} \underset{D_h \times D_h \times D_h}{\frac{\partial z_1^{(t)}}{\partial H}} \\ &= \underset{1 \times \left|V\right|,}{(\hat{y}^{(t)} - y^{(t)})} \underset{\left|V\right| \times D_h,}{U^T} \underset{D_h \times D_h,}{diag\{h^{(t)} \circ (1 - h^{(t)})\}} ? \\ &= \underset{D_h \times 1}{(h^{(t - 1)})^T} \underset{1 \times \left|V\right|,}{(\hat{y}^{(t)} - y^{(t)})} \underset{\left|V\right| \times D_h,}{U^T} \underset{D_h \times D_h,}{diag\{h^{(t)} \circ (1 - h^{(t)})\}} \end{align*}

The parts that I've already figured out:

  • $(\hat{y}^{(t)} - y^{(t)})$ is the derivative of $J$ w.s.t. the input to softmax ($z_2$)
  • $diag\{\cdots\}$ takes advantage of the sigmoid function whose derivative has the form of $\sigma(1 - \sigma)$.

But I am still not sure of the second equality because I don't know how to deal with $\frac{\partial z_1^{(t)}}{\partial H}$ (where I put a question mark), which is the derivative of a vector w.s.t. a matrix, and the result seems to be a 3rd-order tensor ($D_h \times D_h \times D_h$).

I checked the solution and the last equality is likely to be correct. But the transpose and then left multiply of $(h^{(t - 1)})^T$ looks too magical to me. Can anybody shed some light on this part, please?

I also put the graph here in case anyone is interested in looking at it. All quantities are labeled consistently with the above equations.

RNN

$\endgroup$
1
$\begingroup$

There is a single variable in these three equations which carries the $(t-1)$ superscript. Let's rename that variable $$g^{(t)}=h^{(t-1)}$$ Now all of the variables carry the $(t)$ superscript, which is needlessly redundant, and merely creates "visual clutter". So let's drop the superscripts for the purposes of this derivation.

While we're renaming variables, let's use $N$ instead of $I$, and reserve the latter symbol for the identity matrix. Besides, $N$ is an equally good mnemonic for "input".

To avoid all of the decorations (hats, subscripts, etc) on the variables, let's assign each variable a distinct name $$\eqalign{ b &= b_1, &\,\,c = b_2 \cr x &= z_1, &\,\,z = z_2 \cr y &= y, &\,\,w = {\hat y} \cr f &= h^{(t)}, &\,\,g = h^{(t-1)} \cr I &= N \cr }$$ Let's use the convention that an uppercase letter is a matrix, and a lowercase is a column vector. It will also be convenient to use a matrix with the same name as a vector to denote the diagonal matrix formed from that vector, i.e. $$F={\rm Diag}(f)$$ This allows us to replace elementwise/Hadamard multiplication and division with regular matrix operations, e.g. $$\eqalign{ f\circ g &= Gf = Fg \cr f\oslash g &= G^{-1}f \cr }$$ One last notational device is to use a colon for the trace/Frobenius product $$\eqalign{ A:B &= {\rm tr}(A^TB)\cr }$$ So the variables and their differentials are $$\eqalign{ x &= H^Tg +N^Te + b &\implies dx=dH^Tg \cr f &= \sigma(x) &\implies df=(F-F^2)\,dx \cr z &= U^Tf + c &\implies dz=U^T\,df \cr w &= {\rm softmax}(z) &\implies dw=(W-ww^T)\,dz \cr }$$ Let's take the differential of $J$ and successively substitute the others, all the way back to $dH$ $$\eqalign{ J &= y:\log(w) \cr \cr dJ &= y:W^{-1} dw \cr&= W^{-1}y:dw \cr &= W^{-1}y:(W-ww^T)\,dz \cr&= (I-w1^T)y:dz \cr &= (I-w1^T)y:U^T\,df \cr&= U(I-w1^T)y:df \cr &= U(I-w1^T)y:(F-F^2)\,dx \cr&= (F-F^2)U(I-w1^T)y:dx \cr &= (F-F^2)U(I-w1^T)y:dH^T\,g \cr&= (F-F^2)U(I-w1^T)yg^T:dH^T \cr &= gy^T(I-1w^T)U^T(F-F^2):dH \cr \cr \frac{\partial J}{\partial H} &= gy^T(I-1w^T)U^T(F-F^2) \cr &= g(y^T-w^T)U^T(F-F^2) \cr }$$ where in the final step, I have assumed that there is a normalization condition such that $$y^T1=1$$

Substituting the original variable names and reverting back to row vectors (yuk!)   yields $$\eqalign{ \frac{\partial J}{\partial H} &= {h^{(t-1)}}^T\,\Big(y^{(t)}-{\hat y^{(t)}}\Big)\,U^T\,\Big({\rm Diag}(h^{(t)})-{\rm Diag}(h^{(t)})^2\Big) \cr\cr }$$ This result is the negative of yours, because in the problem statement the cost function is defined as $$J = +\sum_k y_k\,\log({\hat y_k})$$ but in your derivation you apparently used $$J = -\sum_k y_k\,\log({\hat y_k})$$

Footnotes
The cyclic properties of the trace give rise to a number of ways to rearrange a Frobenius product. For example $$\eqalign{ A:BC &= AC^T:B \cr&= B^TA:C \cr&= A^T:(BC)^T \cr }$$ As with the Hadamard product, the matrix on each side of the product symbol must be the same size. In fact, the Frobenius product is just the sum over the elements of the Hadamard product $$\eqalign{ A:B = {\rm sum}(A\circ B) \cr\cr }$$ In matrix calculus the chain rule is difficult to use, as you've discovered. This is because the intermediate quantities are often higher order tensors which are awkward to handle.

The virtue of the differential approach is that the differential of a matrix can be handled like an ordinary matrix.

$\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.