# Big picture
Basically Transformer builds a graph network where a node is a position-encoded token in a sequence.
During training:
1. Get un-connected tokens as a sequence (e.g. sentence).
2. Wires connections among tokens by having looked at the co-occurrences of them in billions of sequences.
What roles ```Q``` and ```K``` will play to build this graph network? You could be ```Q``` in your society trying to build the social graph network with other people. Each person in the people is ```K``` and you will build the connections with them. Eventually by having billions of interactions with other people, the connections become dependent on the contexts even with the same person ```K```.
You may be superior to a person K at work, but you may be a master of martial art to K. As you remember such connections/relations with others based on the contexts, Transformer model (trained on a specific dataset) figures out such context dependent connections from Q to K (or from you to other person(s)), which is a **memory** that it offers.
If the layers go up higher, your individual identity as K will be blended into larger parts via going through the BoW process which plays the role.
With regard to the Markov Chain (MC), there is only one static connection from Q to K as ```P(K|Q)``` in MC as MC does not have the context **memory** that Transformer model offers.
# First, understand ```Q``` and ```K```
First, focus on **the objective of ```First MatMul```** in the [Scaled dot product attention][1] using ```Q``` and ```K```.
[![enter image description here][2]][2]
## Intuition on what is ```Attention```
For the sentence **"jane** visits africa".
When your eyes see ***jane***, your brain looks for **the most related word** in the rest of the sentence to understand what **jane** is about (query). Your brain focuses or attends to the word **visit** (key).
This process happens for each word in the sentence as your eyes progress through the sentence.
## First MatMul as Inquiry System using Vector Similarity
The first ```MatMul``` implements an inquiry system or question-answer system that imitates this brain function, using Vector Similarity Calculation. Watch [CS480/680 Lecture 19: Attention and Transformer Networks][3] by professor Pascal Poupart to understand further.
> Think about the attention essentially being some form of approximation of SELECT that you would do in the database.<br>
> [![enter image description here][4]][4]
[![enter image description here][5]][5]
Think of the MatMul as an inquiry system that processes the inquiry: "For the word **```q```** that your eyes see in the given sentence, what is the most related word **```k```** in the sentence to understand what **```q```** is about?" The inquiry system provides the answer as the probability.
| q | k | probability |
| ------------- |-------------| -----|
| jane | visit | 0.94 |
| visit | africa| 0.86 |
| africa | visit | 0.76|
Note that the softmax is used to normalize values into probabilities so that their sum becomes 1.0.
[![enter image description here][6]][6]
There are multiple ways to calculate the similarity between vectors such as cosine similarity. Transformer attention uses simple **dot product**.
## Where are ```Q``` and ```K``` from
The transformer encoder training builds the weight parameter matrices ```WQ``` and ```Wk``` in the way ```Q``` and ```K``` builds the Inquiry System that answers the inquiry "**What is ```k``` for the word ```q```**".
The calculation goes like below where ```x``` is a sequence of position-encoded word embedding vectors that represents an input sentence.
1. Picks up a word vector (position encoded) from the input sentence sequence, and transfer it to a vector space **Q**. This becomes the **q**uery.<br>
$Q = X \cdot W_{Q}^T$
2. Pick all the words in the sentence and transfer them to the vector space **K**. They become keys and each of them is used as **k**ey.
$K = X \cdot W_K^T$
3. For each (**q**, **k**) pair, their relation strength is calculated using dot product.
$q\_to\_k\_similarity\_scores = matmul(Q, K^T)$
4. Weight matrices $W_Q$ and $W_K$ are trained via the back propagations during the Transformer training.
We first needs to understand this part that involves **Q** and **K** before moving to ***V***.
[![enter image description here][7]][7]
Borrowing the code from [Let's build GPT: from scratch, in code, spelled out.][8] by Andrej Karpathy.
```
def calculate_dot_product_similarities(
query: Tensor,
key: Tensor,
) -> Tensor:
"""
Calculate similarity scores between queries and keys using dot product.
Args:
query: embedding vector of query of shape (B, h, T, d_k)
key: embedding vector of key of shape (B, h, T, d_k)
Returns: Similarities (closeness) between q and k of shape (B, h, T, T) where
last (T, T) represents relations between all query elements in T sequence
against all key elements in T sequence. If T is people in an organization,
(T,T) represents all (cartesian product) social connections among them.
The relation considers d_k number of features.
"""
# --------------------------------------------------------------------------------
# Relationship between k and q as the first MatMul using dot product similarity:
# (B, h, T, d_k) @ (B, hH, d_k, T) ---> (B, h, T, T)
# --------------------------------------------------------------------------------
similarities = query @ key.transpose(-2, -1) # dot product
return similarities # shape:(B, h, T, T)
```
# Then, understand how ```V``` is created using ```Q``` and ```K```
## Second Matmul
Self Attention then generates the embedding vector called **attention value** as a bag of words (BoW) where each word contributes proportionally according to its relationship strength to **q**. This occurs for each **q** from the sentence sequence. The embedding vector is encoding the relations from **q** to all the words in the sentence.
Citing the [words][9] from Andrej Karpathy:
> What is the easiest way for tokens to communicate. The easiest way is just average.
He makes it simple for the sake of tutorial but the essence is BoW.
[![enter image description here][10]][10]
```
def calculate_attention_values(
similarities,
values
):
"""
For every q element, create a Bag of Words that encodes the relationships with
other elements (including itself) in T, using (q,k) relationship value as the
strength of the relationships.
Citation:
> On each of these projected versions of queries, keys and values we then perform
> the attention function in parallel, yielding d_v-dimensional output values.
```
bows = []
for row in similarities: # similarity matrix of shape (T,T)
bow = sum([ # bow:shape(d_v,)
# each column in row is (q,k) similarity score s
s*v for (s,v) in zip(row,values) # k:shape(), v:shape(d_v,)
= ])
bows.append(bow) # bows:shape(T,d_v)
```
Args:
similarities: q to k relationship strength matrix of shape (B, h, T, T)
values: elements of sequence with length T of shape (B, h, T, d_v)
Returns: Bag of Words for every q element of shape (B, h, T, d_v)
"""
return similarities @ values # (B,h,T,T) @ (B,h,T,d_v) -> (B,h,T,d_v)
```
# References
There are multiple concepts that will help understand how the self attention in transformer works, e.g. embedding to group similars in a vector space, data retrieval to answer query Q using the neural network and vector similarity.
* [CS25 I Stanford Seminar - Transformers United 2023: Introduction to Transformers w/ Andrej Karpathy][21]: Andrej Karpathy explained by regarding a sentence as a graph.
* [Transformers Explained Visually (Part 2): How it works, step-by-step][11] give in-detail explanation of what the Transformer is doing.
* [CS480/680 Lecture 19: Attention and Transformer Networks][12] - This is probably the best explanation I found that actually explains the attention mechanism from the database perspective.
* [Illustrated Guide to Transformers Neural Network: A step by step explanation][13] <br>
* [Distributed Representations of Words and Phrases and their Compositionality][15] - It helps understand how word2vec works to group/categorize words in a vector space by pulling similar words together, and pushing away non-similar words using negative sampling.
* [Generalized End-to-End Loss for Speaker Verification][16] - Continuation to understand embedding to pull together siimilars and pushing away non-similars in a vector space.
* [Transformer model for language understanding][17] - TensorFlow implementation of transformer
* [The Annotated Transformer][18] - PyTorch implementation of Transformer
[1]: https://www.tensorflow.org/text/tutorials/transformer#scaled_dot_product_attention
[2]: https://i.sstatic.net/MJIyF.png
[3]: https://youtu.be/OyFJWRnt_AY?t=704
[4]: https://i.sstatic.net/nVvt9m.png
[5]: https://i.sstatic.net/bgwSb.png
[6]: https://i.sstatic.net/rQhuQ.jpg
[7]: https://i.sstatic.net/DWNTr.jpg
[8]: https://www.youtube.com/watch?v=kCc8FmEb1nY
[9]: https://youtu.be/kCc8FmEb1nY?t=2625
[10]: https://i.sstatic.net/TBpsF.png
[11]: https://towardsdatascience.com/transformers-explained-visually-part-2-how-it-works-step-by-step-b49fa4a64f34
[12]: https://www.youtube.com/watch?v=OyFJWRnt_AY
[13]: https://www.youtube.com/watch?v=4Bdc55j80l8
[14]: https://i.sstatic.net/xALqg.png
[15]: https://arxiv.org/abs/1310.4546
[16]: https://arxiv.org/abs/1710.10467
[17]: https://www.tensorflow.org/text/tutorials/transformer
[18]: http://nlp.seas.harvard.edu/2018/04/03/attention.html
[19]: https://peltarion.com/blog/data-science/self-attention-video
[20]: https://i.sstatic.net/ksCex.png
[21]: https://youtu.be/XfpMkf4rD6E?t=1395
[22]: https://i.sstatic.net/TZnox.png
[23]: https://i.sstatic.net/ibvMv.jpg