Recurrent Neural Networks

Introduces the concept of feedback with Neural networks from past states and the notion of timestep. RNNs are represented as computational DAGs.

Adds a state variable h (hidden unit), and the operation of the layer depends on its state. State is updated at every time step. $f,g$ can be arbitrary differentiable functions (required for backpropagation).

$$\begin{array}{rl}{h}_t& =f(h_{t-1},x_{\text{in}}[t])\\ x_{\text{out}}[t]& =g(h_t)\end{array}$$

Backpropagation through time: our goal is to compute MLE of the parameters by solving ${\theta }^{\ast }=\arg {\max }_{\theta }p(y_{1:T}|x_{1:T},\theta )$. To compute the MLE, we need the gradients of the loss wrt parameters. Consider a general parameterized RNN model

$$\begin{array}{rlr}{h}_t& =W_{hx}{x}_t+W_{hh}{h}_{t-1}& =f(x_t,h_t,w_h)\\ o_t& =W_{ho}{h}_t& =g(h_t,w_o)\end{array}$$

• Loss can be written as: $L=\frac{1}{T}{\sum }_{t=1}^T\ell (y_t,o_t)$ and we need to compute $\frac{\partial L}{\partial W_{hx}},\frac{\partial L}{\partial W_{hh}},\frac{\partial L}{\partial W_{ho}}$, and $w_h$ is just flattened version of $W_{hx},W_{hh}$.
• $\frac{\partial L}{\partial w_h}=\frac{1}{T}{\sum }_{t=1}^T\frac{\partial \ell (y_t,o_t)}{\partial w_h}$
• Using chain rule, this can be calculated, and takes $\mathcal{O}(T^2)$ to compute overall and thus, need to truncated at some time step to maintain computable tracatability.
• Exploding and vanishing gradients: We are multiplying by the jacobian to compute backpropagation at each time step (consider the gradient of $\frac{\partial x_{\text{out}}[t]}{\partial x_{in}[0]}=\frac{\partial x_{out}[t]}{\partial h_t}\frac{\partial h_t}{\partial h_{t-1}}\dots \frac{\partial h_0}{\partial x_{\text{in}}[0]}$ and $\frac{\partial h_t}{\partial h_{t-1}}={\sigma }^{\prime }W$ where ${\sigma }^{\prime }$ is gradient of the nonlinearity). If the gradients are high or low, it can result in exploding and vanishing gradients respectively.

LSTM

Much better introduction by Chris Olah.

• Avoids the vanishing/exploding gradient problem.
• LSTM adds a memory cell $C_t$ that is controlled using three gates output gate $O_t$, Input gate $I_t$, and forget gate $F_t$. Each serves a specific purpose:
  • Output: determines what gets reads out from the input and hidden state.
  • Input: determines what gets reads in.
  • Forget: determines when to reset the cell.
  • Each gate is composed of a sigmoid NN and a pointwise multiplication. Sigmoid controls when to switch something on and off, and pointwise multiplication uses the sigmoid output for switching operation. A “1” keeps something, and “0” corresponds to removing it.
• Let’s first write the computation equations, and then understand them:

$$\begin{array}{rl}{O}_t& =\sigma (W_o[H_{t-1},X_t]+b_o)\\ I_t& =\sigma (W_i[H_{t-1},X_t]+b_i)\\ F_t& =\sigma (W_f[H_{t-1},X_t]+b_f)\end{array}$$

• At the first step, $C_t=C_{t-1}{F}_t$. This means, we use the forget gate output to forget some of the information from the cell state.
• At the second step $C_t=C_{t-1}{F}_t+I_t{\tilde{C}}_t$, we use the output from input gate $I_t$ which scales the information as per its importance, and use the candidate memory ${\tilde{C}}_t=\text{tanh}(W_c[H_{t-1},X_t]+b_c)$ to select the new candidate values that could be added to the state.
• Our memory is updated at this point, and LSTM now decides what to output.
• Output gate $O_t$ decides what gets read out from the input and hidden state, and is transformed with the cell state to compute the next hidden state: $H_t=O_t\cdot \text{tanh}(C_t)$

GRU

GRU combines forget and input gate into a single “update” gate $Z_t\in {\mathbb{R}}^{N\times H}$. And also merges cell and hidden state.

$$\begin{array}{rl}{R}_t& =\sigma (W_r[H_{t-1},X_t]+b_r)\\ Z_t& =\sigma (W_z[H_{t-1},X_t]+b_z)\\ \tilde{H}\ast t& =\text{tanh}(W\ast h[R\ast t\odot H_{t-1},X_t]+b_h)\\ H_t& =Z_t\odot H_{t-1}+(1-Z_t)\odot \tilde{H}\ast t\end{array}$$

Beam search

Compute top K candidate outputs at each step, and expand each one in V possible ways, to generate VK candidates. Select top K again.

• Stochastic beam search samples top K without replacement, i.e. pick the top one, renormalize, and pick the new top one.