1. Redo Midterm
2. Hand-Design Transformers
Please follow the instructions in this notebook. You will implement a simple transformer model (with a single attention head) from scratch and then create a hand-designed the attention heads of the transformer model capable of solving a basic problem. Once you finished with the notebook,
• Download submission_log.json and submit it to “Homework 8 (Code)” in Gradescope.
• Answer the following questions in your submission of the written assignment:
(a) Design a transformer that selects by contents. Compare the variables of your hand-designed Transformer with those of the learned Transformer. Identify the similarities and differences between the two sets of variables and provide a brief explanation for each difference.
(b) Design a transformer that selects by positions. Compare the variables of your hand-designed Transformer with those of the learned Transformer. Identify the similarities and differences between the two sets of variables and provide a brief explanation for each difference.
3. Kernelized Linear Attention (Part II)
This is a continuation of “Kernelized Linear Attention” in HW 7. Please refer to this part for notation and context. In Part I of this problem, we considered ways to efficiently express the attention operation when sequences are long (e.g. a long document). Attention uses the following equation:
. (1)
sim
We saw that when the similarity function is a kernel function (i.e. if we can write sim for some function Φ), then we can use the associative property of matrix multiplication to simplify the formula to
. (2)
If we use a polynomial kernel with degree 2, this gives a computational cost of , which for very large N is favorable to the softmax attention computational cost of is the sequence length, D is the feature dimension of the queries and keys, and M is the feature dimension of the values. Now, we will see whether we can use kernel attention to directly approximate the softmax attention:
. (3)
(a) Approximating softmax attention with linearized kernel attention
i. As a first step, we can use Gaussian Kernel KGaussto rewrite the softmax √
similarity function, where simsoftmax. Assuming we can have σ2 = D, rewrite the softmax similarity function using Gaussian Kernel.. (Hint: You can write the softmax as the product of the Gaussian Kernel and two other terms. )
ii. However, writing softmax attention using a Gaussian kernel does not directly enjoy the benefits of the reduced complexity using the feature map. This is because the feature map of Guassian kernel usually comes from the Taylor expression of exp(·), whose computation is still expensive . However, we can approximate the Guassian kernel using random feature map and then reduce the computation cost. (Rahimi and Recht, 2007) proposed random Fourier features to approximate a desired shift-invariant kernel. The method nonlinearly transforms a pair of vectors q and k using a random feature map ϕrandom(); the inner product between ϕ(q) and ϕ(k) approximates the kernel evaluation on q and k. More precisely:
⊤
ϕrandom(q) =. random
(4)
Where we have Drandom of D-dimensional random vectors wi independently sampled from N(0,σ2ID),
. (5)
Use ϕrandom to approximate the above softmax similarity function with Gaussian Kernel and derive the computation cost for computing all the V ′ here.
(b) (Optional) Beyond self-attention, an autoregressive case will be masking the attention computation such that the i-th position can only be influenced by a position j if and only if j ≤ i, namely a position cannot be influenced by the subsequent positions. This type of attention masking is called causal masking.
Derive how this causal masking changes equation 1 and 2. Write equation 1 and 2 in terms of Si and Zi, which are defined as:
, (6)
to simplify the causal masking kernel attention and derive the computational complexity of this new causal masking formulation scheme.
4. Homework Process and Study Group
We also want to understand what resources you find helpful and how much time homework is taking, so we can change things in the future if possible.
(a) What sources (if any) did you use as you worked through the homework?
(b) If you worked with someone on this homework, who did you work with?
List names and student ID’s. (In case of homework party, you can also just describe the group.)
(c) Roughly how many total hours did you work on this homework? Write it down here where you’ll need to remember it for the self-grade form.
Contributors:
• CS182 Staff.
• Olivia Watkins.
• Jake Austin.
• Dhruv Shah.
• Anant Sahai.
• Linyuan Gong.
• Sheng Shen.
• Shaojie Bai.
• Angelos Katharopoulos.
• Hao Peng.
