\documentclass[11pt]{article}
\usepackage{calc,fancyhdr,lastpage}
\usepackage[hmargin=.75in,vmargin=1in,
            footskip=.55in,headsep=.55in-\headheight]{geometry}
\usepackage{amsmath,amssymb}
\usepackage{graphicx}
\usepackage{url}
\usepackage{listings}

% Formats, symbols, abbreviations.
\let\altemph\textsl
\let\strong\textbf
\let\code\texttt
\let\latinabb\emph
\newcommand*{\etc}{\latinabb{etc}}
\newcommand*{\eg}{\latinabb{e.g.}}
\newcommand*{\ie}{\latinabb{i.e.}}
% To get proper-looking symbols in \texttt.
\newcommand*{\txtbksl} {\symbol{"5C}}% \
\newcommand*{\txtcaret}{\symbol{"5E}}% ^
\newcommand*{\txtunder}{\symbol{"5F}}% _
\newcommand*{\txtlcurl}{\symbol{"7B}}% {
\newcommand*{\txtrcurl}{\symbol{"7D}}% }
\newcommand*{\txttilde}{\symbol{"7E}}% ~

% Commands \question[marks]{title} and \subquestion[marks]{title}.
\newcounter{questionnumber}
\newcommand*{\question}[2][]
   {\refstepcounter{questionnumber}\section*
    {Question \thequestionnumber.\quad
        \ifx\empty#1\empty\else[#1 marks]\quad\fi#2}}
\newcounter{subquestionnumber}[questionnumber]
\renewcommand*{\thesubquestionnumber}{\alph{subquestionnumber}}
\newcommand*{\subquestion}[2][]
   {\refstepcounter{subquestionnumber}\subsubsection*
    {Part (\thesubquestionnumber)\quad
       \ifx\empty#1\empty\else[#1 marks]\quad\fi#2}}

% Redefine `enumerate' to use less vertical space.
\let\etaremune\enumerate
\let\etaremunedne\endenumerate
\renewenvironment{enumerate}
   {\etaremune
    \setlength{\topsep}{.25ex plus .125ex minus .1825ex}%
    \setlength{\itemsep}{\topsep}\setlength{\parsep}{0ex}%
    \setlength{\leftmargin}{1.75em}\setlength{\labelsep}{.5em}%
    \setlength{\labelwidth}{1.75em}\ignorespaces}
   {\etaremunedne}

% Redefine `itemize' to use less vertical space.
\let\ezimeti\itemize
\let\ezimetidne\enditemize
\renewenvironment{itemize}
   {\ezimeti
    \setlength{\topsep}{.25ex plus .125ex minus .1825ex}%
    \setlength{\itemsep}{\topsep}\setlength{\parsep}{0ex}%
    \setlength{\leftmargin}{1.75em}\setlength{\labelsep}{.5em}%
    \setlength{\labelwidth}{1.75em}\ignorespaces}
   {\ezimetidne}

%% A heading in the instructions.
\newcommand*{\heading}[1]{\subsubsection*{#1}}

% Headings.
\pagestyle{fancy}
\let\headrule\empty
\let\footrule\empty
\lhead{{\bfseries CSC321H1S}}
\chead{Tutorial: Backprop in RNN  (Last update: \today)}
\rhead{{\bfseries }}
\lfoot{{Dept. of Computer Science, University of Toronto}}
\cfoot{{}}
\rfoot{{Page \thepage\ of \pageref{LastPage}}}


\begin{document}
\noindent First, let's write down the forward pass. The variables are:

\begin{itemize}
\item \verb;xs; the input sequence, encoded using one-hot encoding. Denote it by $x_t$.

\item \verb;hs; the hidden state (a vector), at each time step. Denote it by $h_t = \tanh(W^{xh}x_t + W^{hh}h_{t-1}$)

\item \verb;ys; the output layer. Denote it by $y_t = W^{hy}h_t + b^{y}$

\item \verb;ps; the output of the softmax. Denote it by $\hat{y}_t = softmax(y_t)$

\item \verb;loss; the cost/loss function. $Cost = -\sum_t \log(\sum_k \hat{y}_t^{k} x_t^{k})$
\end{itemize}


Now, let's go line by line and interpret those. We will often use e.g. $\partial Cost_t/\partial h$ to denote the contribution from time-step $t$ to the cost function, with $C = \sum_t C_t$ for 

$$C_ t = \log(\sum_k \hat{y}_t^{k} x_t^{k}).$$


\verb;dy = np.copy(ps[t]);

\verb;dy[targets[t]] -= 1 # backprop into y;

\noindent This is just the derivative of the softmax for $Cost_t$:

$$\frac{\partial Cost_t}{\partial y} = \hat{y} - x$$

Note that $x$ is one-hot encoded, so that it's mostly zeros, with only a single $1$ at coordinate \verb;targets[t];. That's why we first set \verb;dy; to \verb;ps; (i.e., the $\hat{y}$), and then subtract $y$.
\\\\\\

\verb;dWhy += np.dot(dy, hs[t].T);

\verb;dby += dy;

\noindent This corresponds to the $t$-th component of the derivatives wrt $W^{hy}$ and $b^{y}$:

$$\partial Cost_t/\partial W^{hy} = \frac{\partial Cost_t}{\partial y_t} \frac{\partial y_t}{\partial W^{hy}} = \frac{\partial Cost_t}{\partial y_t}h_t^T$$

$$\partial Cost_t/\partial W^{hy} = \frac{\partial Cost_t}{\partial y_t} \frac{\partial y_t}{\partial b^{y}} = \frac{\partial Cost_t}{\partial y_t}1 = \frac{\partial Cost_t}{\partial y_t}$$
\\
\\
\\

\verb;dh = np.dot(Why.T, dy) + dhnext;

\noindent This is tricky. We want to account for the influence of $h_t$ on both $Cost_t$ and $Cost_{(t+1):end}$. 

$$\frac{\partial Cost_{t:end}}{\partial h_t} = \frac{\partial Cost_t}{\partial h_t} + \frac{\partial Cost_{(t+1):end}}{\partial h_t} = \frac{\partial Cost_t }{\partial y}  \frac{\partial y}{\partial h_t} + dhnext$$

\verb;dhraw = (1 - hs[t] * hs[t]) * dh;

$$\frac{\partial Cost_{t:end}}{\partial hraw_t}  = (1-h_t^2) \frac{\partial Cost_{t:end}}{\partial h_t}$$
\\
\\
\\
\noindent The following:

\verb;dbh += dhraw;

\verb;dWxh += np.dot(dhraw, xs[t].T);

\verb;dWhh += np.dot(dhraw, hs[t-1].T);

\noindent are similar to what we already had. Note that 

$$\frac{\partial Cost_{t:end}}{\partial h_t} = \frac{\partial Cost}{\partial h_t}$$

since $h_t$ cannot influence components of the cost that come before it in time.

Finally, we compute \verb;dhnext;, which must be $\frac{\partial Cost_{t:end}}{\partial h_{t-1}}$ in order for our earlier definition to work. Now

$$\frac{\partial Cost_{t:end}}{\partial h_{t-1}} = \frac{\partial Cost_{t:end}}{\partial hraw_{t}}\frac{\partial hraw_{t}}{\partial h_{t-1}}$$

This is exactly what the following line does.

\verb;dhnext = np.dot(Whh.T, dhraw);

The following is self-explanatory:

\verb;  for dparam in [dWxh, dWhh, dWhy, dbh, dby]:;

\verb;    np.clip(dparam, -5, 5, out=dparam) # clip to mitigate exploding gradients;

In the loop, we are adding up all the contributions to the gradients from all the time-steps $t$.


\end{document}