Intro

Previous Approaches for NLP:

1. Recurrent Neural Networks

A Recurrent Neural Network (RNN) processes a sequence one token at a time while maintaining a hidden state that acts a summary of the preceding context.

For a token sequence $x_1,x_2,x_3,\dots ,x_T$ the basics RNN recurrence is:

$h_t=\varphi (W_x{x}_t+W_h{h}_{t-1}+b_h)$

$x_t$: representation of the current token
$h_t$: hidden state at time $t$
$W_x$: input to hidden weight matrix
$w_h$: recurrent/hidden-to-hidden weight matrix
$\varphi$: nonlinear activation function (tanh,ReLU etc.)

For language modeling, we map the hidden vocabulary to a distribution over the vocabulary: $p(x_t+1|x_1,\dots ,x_t)=softmax(W_y{h}_t+b_y)$

The same recurrent parameters $W_h$ are reused at every time step. This is what allows the model to process sequence of arbitrary length.

Problems with RNNs:

• Vanishing Gradient

During backpropagation, the gradient from a later time step has to propagate through many recurrent transformations which makes it very difficult for the information from distant tokens/words to influence the parameters through gradient updates. Due to this model weights are updated with only near/local relations and not the long-term ones.

• Exploding Gradient

If the recurrent Jacobians have magnitude greater than 1 then repeated multiplication can then make the gradients grow rapidly: $||\nabla ||\to \infty$. This can be fixed with gradient clipping

• Long-distance Dependencies

An RNN has a theoretical recurrent memory extending over the entire sequence - $h_t=f(x_t,h_{t-1})$ Its ability to use distant context is limited because all previous information must be compressed into a fixed-dimensional state $h_t$ and the learning signal must pass through many recurrent steps.

• Lack of Parallelizability

Because $h_t=f(x_t,h_{t-1})$ we cannot directly compute it unless we know $h_{t-1}$ and hence we have dependency: $h_1\to h_2\to h_3\to \cdots \to h_T$ which can not be computed in parallel rather only sequentially.

2. Long Short-Term Memory (LSTM)

LSTM is a recurrent neural network architecture primarily addressed to overcome the vanishing-gradient problem of vanilla RNNs and to improve performance on long-term dependencies.

Modification in LSTM is that it maintains 2 states: $h_t-hiddenstate$ and $c_t-cell/memorystate$
The cell/memory state provides a relatively direct path through time while gates control what information is forgotten, added and exposed.
(not going in depth for now - [TODO])

Attention

Bahdanu Attention

[TODO]

Self-Attention

$\text{Attention(Q,K,V)}=\text{softmax}(\frac{Q{K}^T}{d_K^{1/2}})V$

It is called self-attention because the queries, keys and values originate from the same sequence.

Query - What kind of information am I (token) looking for from the other tokens?
Key - What kind of information I (token) can provide
Value - The actual information retrieved

We use Query and Key to find the relevance between two tokens, and based on that relevancy score we do weighted sum of the value vectors for that token.

$$\begin{gathered} Q=X{W}_Q,(N\times d_{embed})\ast (d_{embed}\times d_k)=(N\times d_k) \\ K=X{W}_K,(N\times d_{embed})\ast (d_{embed}\times d_k)=(N\times d_k) \\ V=X{W}_V,(N\times d_{embed})\ast (d_{embed}\times d_k)=(N\times d_k) \end{gathered}$$ $Q{K}^T(N\times d_k)\ast (d_k\times N)=(N\times N)$

and $d_k$ is the dimensionality of the key/query vectors

$Q{K}_{ij}^T=q_i{k}_j^T$ measures how strongly token $i^{\prime }s$ query relates to token $j^{\prime }s$ key.

$i$-th row of $Q{K}^T$ gives us the relevancy of each token w.r.t $i$-th token.

We apply $softmax$ over the calculated attention scores $q_i{k}_j^T$ before multiplying them with $v_j$: ${\alpha }_{1j}=\frac{exp(q_1{k}_j^T/d_K^{1/2})}{{\sum }_{m=1}^{n}exp(q_1{k}_m^T/d_K^{1/2})}$ Output for 1 token: $t_1={\sum }_{j=1}^n{\alpha }_{1j}{v}_j$ where ${\sum }_j{\alpha }_{1j}=1$

Question

Why divide by $d_k^{1/2}$?
$q_i{k}_j^T={\sum }_{y=1}^{d_k}{q}_{iy}{k}_{jy}\to \text{sum of }{d}_k\text{ terms}$ Assuming components of $q$ and $k$ are independent and have: $\mathbb{E}[q_l]=\mathbb{E}[k_l]=0$ and $Var(q_l)=Var(k_l)=1$ then a single product will be: $a_l=q_l{k}_l$ with $\mathbb{E}[a_l]=0$ and $Var(a_z)\approx 1$
Now the dot product is: $q{k}^T={\sum }_{y=1}^{d_k}{a}_l$ For independent terms the $Var$ will add up and therefore $Var(q{k}^T)\approx d_k$, hence its standard deviation: $std(q{k}^T)\approx d_k^{1/2}$

Dividing by the standard deviation makes the logits independent of the key/query dimension.
Also, large scores makes distribution of attention extremely peaked and a only few (or even just one) token might get the whole score which may lead to small gradient updates and unstable optimization. (softmax saturation)

Problems with Self-Attention:

• No word position- self-attention is positional invariant (add positional encoding - Positional Embedding)
• No Non-linearity (add FFN - FFNN)
• Looks at future words (add Causal Masking - Decoder)

Transformer

Gains:

• Parallel Processing
• Semi-supervised Learning
• Transfer Learning
• Knowledge-stores
• Reasoning

Drawbacks:

• Quadratic computation $O(N^2)$ in self-attention
• Position Representation