###### tags: `Paper Notes`
# Performer
* 原文：[Rethinking Attention with Performers](https://arxiv.org/abs/2009.14794)
* 機構：Google、University of Cambridge、DeepMind、Alan Turing Institute
* 時間：2020 年

### Introduction
* 原本的 Transformer 在做計算時，其 time complexity 會隨著 input sequence length $L$ 增加而成平方被增長。這樣就會導致我們的 input sequence 不能調很大。
* Transformer 原始公式如下：
$$
Attention(Q, K, V) = softmax(\frac{QK^{T}}{\sqrt{d}})V = D^{-1}AV \\
A = exp(\frac{QK^{T}}{\sqrt{d}}),\ D = diag(A1_{L})
$$
* 由於 $Q, K, V \in R^{L \times d}$ 因此 $QK^{T}$ 矩陣乘法的 time complexity 為 $L \times d \times L = L^{2}d$。
* $d$：dimension of the latent representation
* $exp(\cdot)$：applied elementwise
* $diag(\cdot)$：diagonal matrix with the input vector as the diagonal
* $1_L$：all-ones vector of length $L$
* $D$ 中的對角項即為 softmax 裡的分母。複習：對角矩陣的反矩陣為對角項做倒數。
* 如果我們能讓 $K^{T}V$ 先乘，再乘以 $Q$，那麼 time complexity 將可以變成 $d \times L \times d = Ld^{2}$。如此一來便只跟 $L$ 成線性（一次方）關係。但因為 $QK^{T}$ 前面有一個 $exp$ 運算，所以不能直接這樣換。
* 本文在做的，就是利用 kernel 找出 $Q', K'$，使得 $Q'(K')^{T} \approx exp(\frac{QK^{T}}{\sqrt{d}}) = A$。如此一來，便能讓 $K^{T}V$ 先乘。
* 具體來說 Performer 是透過名為 Fast Attention Via positive Orthogonal Random features (FAVOR+) 的機制來去逼近 softmax 與 Gaussian kernels。

### Generalized Kernelizable Attention (==FA==VOR+)
* 定義 kernel $K : R^{d} \times R^{d} \to R_{+}$
$$
K(x, y) = E[\phi(x)^{T}\phi(y)]
$$
* $E$：期望值
* $\phi(x) : R^{d} \to R^{r}_{+}$：random feature map for $ x\in R^{d}$
* $A(i, j) = K(q_{i}^{T}, k_{j}^{T})$。其中，$q_i$ 與 $k_j$ 分別是 $Q$ 與 $K$ 的第 $i、j$ 個 row。
* $Q', K' \in R^{L \times r}$ 的第 $i$ 個 row 即為 $\phi(q_{i}^{T})^{T}$ 與 $\phi(k_{i}^{T})^{T}$。
* 新的 attention 公式如下：
$$
\widehat{Attention}(Q, K, V) = \hat{D}^{-1}(Q'((K')^{T}V))\\
\hat{D}^{-1} = diag(Q'((K')^{T} 1_{L}))
$$
* 此時 time complexity 為 $O(Lrd)$。
<center><img src ="https://i.imgur.com/XLTrGlV.png" width=650></center>

### How and How Not to Approximate Softmax Kernels for Attention (FAVO==R+==)
* 事實證明，將 $\phi$ 定義成以下形式可以讓 kernel 適用於大部分的場景：
$$
\phi(x) = \frac{h(x)}{\sqrt{m}}[f_1(w_{1}^{T}x), ..., f_1(w_{m}^{T}x), ... f_l(w_{1}^{T}x), ..., f_l(w_{m}^{T}x)]
$$
* $f_1,...,f_l : R \to R$
* $h : R^{d} \to R$
* $w_1, ..., w_m \overset{iid}{\sim} D$ for some distribution $D \in P(R)^{d}$。(iid：independent and identically distributed)
* 對於 $x, y \in R^{d}, z = x + y$，softmax-kernel for matrix $A$ 可以寫成以下形式 (證明見原文第三節)：
$$
SM(x, y) = E_{w \sim N(0, I_d)} [exp(w^{T}x - \frac{||x||^{2}}{2})exp(w^{T}y - \frac{||y||^{2}}{2})] \\
= \Lambda E_{w \sim N(0, I_d)} cosh (w^{T}, z)
$$
* $\Lambda = exp(- \frac{||x||^2 + ||y||^2}{2})$
* $cosh$：hyperbolic cosine
* 因此，可定義 $\phi$ 的參數如下（共有兩種定義方式）：
* 第一種：
* $h(x) = exp(- \frac{||x||^2}{2})$
* $l = 1$
* $f_1 = exp$
* $D = N(1, I_d)$。$N$ 表示常態分佈。
* 第二種：
* $h(x) = \frac{1}{\sqrt{2}} exp(- \frac{||x||^2}{2})$
* $l = 2$
* $f_1(x) = exp(x),\ f_2(x) = exp(-x)$
* $D = N(1, I_d)$。$N$ 表示常態分佈。

### Orthogonal Random Features (ORF) (FAV==O==R+)
* 如果 $w_1, ..., w_m$ 兩兩正交，那麼就可以減少逼近時的 variance。這樣一來，我們就可以用更小的 $r$ 去逼近。
* 可以用 Gram-Schmidt renormalization 對 $w_1, ..., w_m$ 做正規化。(忘記的回去複習線代)

### Experiments & Results
* Figure 3 展示了 Performer (實線) 與 Transformer (虛線) 在做 forward 與 backward 時所花費的時間。除了 attention 方式不一樣以外，其它配置都相同。
* 可以看到隨著 $L$ 增加，Performer 推論的時間成線性增長，而 Transformer 成平方倍成長。
* 但要注意的點是，當 $L$ 小於 $2^{8} = 256$ 時，Transformer 的效能是比 Performer 好的。當 $L$ 很大時，才能體現出 Performer 的價值。
* Performer 適用的領域：生物醫療、環境工程。
<center><img src ="https://i.imgur.com/4Eiee8J.png" width=650></center>

### References
* [Yannic Kilcher - Performer](https://www.youtube.com/watch?v=xJrKIPwVwGM&ab_channel=YannicKilcher)

### Others
* [知乎](https://zhuanlan.zhihu.com/p/280864164)上有人對 Performer 做了速度測試，測試結果如下：
<center><img src ="https://i.imgur.com/DIdiBFO.pngg" width=600></center>