---
title: 目前進度報告0317
---

### Linformer: Self-Attention with Linear Complexity(2020 FBAI)

#### 與其他Transformer差異

### 概念

基於self-attention是Low-rank的理論，利用linear將原始的attention matrix project 成一個Low-rank matrix，簡單說就是一個高維空間中的點集，可以被線性地嵌到低維空間中，且其結構只遭受較小的變化

### transformer

### Multi-head Attention


$(Q、K、V)$都是輸入的嵌入矩陣， $n$是序列長度， $d_k$是嵌入維度， $h$是Head的數量，每個head的計算方式如下：


其中， $W^Q_i、W^K_i∈R^{d_m×d_k}、W^V_i∈R^{d_m×d_v}、W^O_i∈R^{d_m×d_k}$ 都為待訓練學習到的參數。 $d_k、d_v$都是隱維度的投射空間。 $P$部分計算的成本是非常高的。它需要把序列中每個位置的 token 都兩兩組合，即需要將兩個$n×d$的矩陣相乘，時間空間複雜度都是 $O(n^2)$。這部分計算成為了 Transformer 的瓶頸。

### 還沒很懂的

基於上面的式子，$D_A$ 是一個 $n \times n$ 的對角矩陣。該證明的主要思路是Johnson–Lindenstrauss theorem。由$N(0,\frac {1}k)$建立一個Low-rank的近似矩陣$\tilde P$


因JL定理得出，對於矩陣$VW^v_i$中的任意向量$\omega∈R$
當$k=5 log(n)/(\epsilon^2-\epsilon^3)$時，會產生:

當$P$有了low-rank性質後，用
singular value decomposition (SVD)去將$P$轉換成近似的$P_{low}$ :

### model
### attention