Recurrent Neural Networks

A recurrent neural network allows us to process variable-length sequences. This is good for something like next-word prediction in a sentence.

RNNs’ key strength is their a hidden state, which acts as a memory of previous inputs. This allows the network to capture temporal dependencies and make information predictions based on past information.

• Increasing the size of ${\vec{h}}^i$ (larger number of hidden units) enhances the ability to store and process long-term dependencies, but is more computationally expensive.

RNNs suffer from the Vanishing + Exploding Gradient Problem, making it difficult to learn dependencies over long timespans. More advanced architectures such as LSTM and GRU address these issues.

Vanilla RNN Formulation

RNNs process sequences by maintaining a hidden state that carries information from previous timesteps.

At each time step $i$, the hidden state is updated using the previous hidden state and the current input.

$$\begin{array}{rl}{s}^i& =U{x}^i+W{h}^{i-1}+b\\ h^i& =\sigma (s^i)\end{array}$$

• ${\vec{h}}^i$ is the hidden state at time step $i$
• ${\vec{x}}^i$ is the input at time step $i$
• $U$ is the input-to-hidden transformation weight matrix
• $W$ is the hidden-to-hidden transformation weight matrix (allows information to persist over time)
• $\vec{b}$ is the bias term
• $a$ is a non-linear activation function

The output at each timestep is computed as

$$\begin{array}{rl}{z}^i& =V{h}^i+c\\ y^i& =\sigma (z^i)\end{array}$$

• ${\vec{y}}^i$ is the output at time step $i$
• $V$ is the hidden-to-output transformation weight matrix
• $\vec{c}$ is the bias term
• The softmax function ensures that the output represents probabilities or conditional probabilities

Unrolled through time:

Backpropagation Through Time

The total loss function $L$ over a sequence of timesteps is computed as the sum of individual losses at each step:

$$E(y^1,\dots ,y^N,t^1,\dots ,t^N)=\sum _{i=1}^N{\alpha }_{i}L(y^i,t^i)$$

• $y^i$ is the predicted output at each time step $i$
• $t^i$ is the target/ground truth output at time step $i$
• $N$ is the sequence length
• $L(y^i,t^i)$ represents the loss function measuring the error between prediction and target at a given timestep. This could be a cross-entropy or MSE loss depending on the task.
• ${\alpha }_i$ are weights for different timesteps
• The total loss $E$ is accumulated over all timesteps, ensuring that all predictions contribute to the optimization process.

Then, the training objective is to minimize the expected loss over the entire dataset:

$${\theta }^{\ast }=\underset{\theta }{\mathrm{argmin}}{\mathbb{E}}_{y,t}[E(y^1,\dots ,y^N,t^1,\dots ,t^N)]$$

After the forward pass, we can propagate the error gradients through the network.

Let us first consider the output pre-activation, $z^k=V{h}^i+c$.

$$\begin{array}{rlr}{\nabla }_{z^k}E& ={\nabla }_{z^k}\left(\sum _{i=1}^{T}L(y^i,t^i)\right)& \\ & =\sum _{i=1}^T{\nabla }_{z^k}L(y^i,t^i)& \\ & ={\nabla }_{z^k}L(y^k,t^k)& [\text{Only }{y}^k\text{ depends on }{z}^k,\text{ all other }{y}^i\text{ are 0}]\\ & ={\nabla }_{y^k}L(y^k,t^k)\odot {\sigma }^{\prime }(z^k)& \end{array}$$

With this we can get the gradient for the hidden-to-output weight matrix $V$:

$$\begin{array}{rl}{\nabla }_{V}E& =\sum _{i=1}^T{\nabla }_{V}L(y^i,t^i)\\ & =\sum _{i=1}^T{\nabla }_{z^i}L(y^i,t^i){\nabla }_V{z}^i\\ & =\sum _{i=1}^T{\nabla }_{z^i}L(y^i,t^i)(h^i{)}^T\end{array}$$

Hidden layers: Descending down to the hidden layer, it gets more interesting because each unrolled hidden layer depends on the one before it. So, we start at the final timestep $\tau$ and work our way back in time.

Define the “future-from-$k$” loss as:

$$E^k=\sum _{i=k}^{\tau }L(y^i,t^i)$$

and consider ${\nabla }_{h^z}E$.

The variables before timestep $k$ do not depend on the variables after $k$; $h^k$ depends on $h^{k-1}$ but not $h^{k+1}$.

• $j=\tau$ here?

Therefore:

$${\nabla }_{h^k}E={\nabla }_{h^k}\sum _{i=k}^{\tau }L(y^i,t^i)={\nabla }_{h^k}{E}^k$$

Thus, for the final hidden layer we have ${\nabla }_{h^{\tau }}E={\nabla }_{h^{\tau }}{E}^{\tau }$. This can be written as:

$$\underset{H}{\underbrace{{\nabla }_{h^{\tau }}E}}=\underset{Y}{\underbrace{{\nabla }_{z^{\tau }}E}}\underset{Y\times H}{\underbrace{\frac{\partial z^{\tau }}{\partial h^{\tau }}}}={\nabla }_{z^{\tau }}E{V}^T$$

• Recall that $z=hV+C$

Note: All the backprop paths from $E^k$ to the variables $x^i,s^i,h^i$ must pass through $h^k$ for $i\le k$.

Suppose that we have already comptued ${\nabla }_{h^{i+1}}E$. We we would like to compute ${\nabla }_{h^i}E$:

$$\begin{array}{rl}{\nabla }_{h^i}E& ={\nabla }_{h^i}{E}^i\\ & ={\nabla }_{h^i}(L(y^i,t^i)+E^{i+1})\\ & ={\nabla }_{h^i}L(y^i,t^i)+{\nabla }_{h^{i+1}}E\frac{\partial h^{i+1}}{\partial h^i}\\ & =\underset{Y}{\underbrace{[{\nabla }_{y^i}L(y^i,t^i)\odot {\sigma }^{\prime }(z^i)}}\underset{Y\times H}{\underbrace{]V^T}}+\underset{H}{\underbrace{[{\nabla }_{h^{i+1}}E\odot {\sigma }^{\prime }(s^{i+1})]}}\underset{H\times H}{\underbrace{W^T}}\end{array}$$

Once you have ${\nabla }_{h^i}E$, $i=1,\dots ,\tau$, you can compute the gradient with respect to the deeper weights and biases ${\nabla }_{W}E,{\nabla }_{U}E,{\nabla }_{b}E$.