# 論文筆記：Efficient Transformers: A Survey
# Efficient Transformers: A Survey
PART 3-2-13~3-2-17

## 13. linear transformer

#### 1. source:
[Transformers are RNNs:
Fast Autoregressive Transformers with Linear Attention](https://arxiv.org/pdf/2006.16236.pdf)

---

#### 2. background
一般的transformer複雜度都是O(N^2)，對於資源的要求高並導致對長度的擴展有限制。

---

#### 3. 原理
##### 3-1. dot product attention
* 步驟:
1. attention model需要去算下一層序列和上一層序列之間的正交矩陣，然後用softmax得到各個權重
2. 將第一步的權重去乘下一層序列向量加權的總和，得到下一層序列對應的結果
3. 加權算總和的softmax可以用sim來取代一般化
* 公式:

##### 3-2. linear attention
* 簡述:
根據dot product attention，只要將sim去掉，再根據矩陣乘法的結合律，就可以成功的減少運算量。因為先算KT會得到一個d*d的矩陣，Q在乘以這個矩陣就會講O(n^2)的複雜度變成O(d*n)，因為d<<n，所以就是O(n)
* 要求:
和softmax相比，sim需要(1)normalization(2)非負
* 方法:
1. kernel function
將sim轉換成縣normalization的非負函數，在論文裡面，兩個kernel函數是一樣ㄉ

3. softmax
Q在d那個維度是normalized的，K在n那個維度也是~ 所以QK就滿足了都norm!

##### 3-3. transformers are RNN!
* 簡述:
linear attention 可以將attention model傳換成RNN的模型，如果要mask未來的資訊，算總和的時候把n換成i

* 方法:
1. 原本的表示式
計算上一層i步的結果，需要加權求和算i步到第i步前的結果，當使用kernel函數就可以把q_i提取出來(因為不會變~)

3. 轉換後的表示式
設定S和z，然後S就是下層各個step K的加權求和結果，S就是下層各個step V的加權求和結果。以transformer可以表示為RNN那樣的前一步狀態+當前狀態的形式，也就是RNN的形式。

## 14. performer

#### 1. source:
[Rethinking Attention with Performers](https://arxiv.org/pdf/2009.14794.pdf)

---

#### 2. background
Performer是一個具有注意力線性擴展機制的Transformer架構，可以使模型在處理更長序列的同時實現更快的訓練，這是對於特定的圖像數據集如 ImageNet64和文本數據集如 PG-19所必需的。
Performer框架中使用不同的相似度計算方法（各種核方法）來完成attention機制。這個框架由FAVOR+(Fast Attention Via Positive Orthogonal Random Features，透過正交隨機特徵來完成快速的attention)，這個方法提供了高度可擴展性的attention機制。一方面確保了線性空間和複雜度，另一方面也保有準確度。

---

#### 3. FAVOR+

透過上述的分解可以得到線性(而非二次)的複雜度注意力矩陣。同樣，透過分解可以獲得線性時間的注意力機制。原有的方式是注意力矩陣與value输入相乘得到最终结果，但在**分解注意力矩陣**之後，可以重新排列矩陣乘法来近似常规注意力機制的结果，而不需要建立二次方的注意力矩陣。最终生成了新算法 FAVOR+。



---

## 15. synthesizers

#### 1. source:
[Synthesizer: Rethinking Self-Attention in Transformer Models](https://arxiv.org/pdf/2005.00743.pdf)

---

#### 2. background
dot product self attention提供了強大的建模能力，但同时作者提出了質疑，它的計算可能是不必要的。

dot product的基本作用是確定一個token對於序列中所有其他token的相對重要性。key、query、value 暗指self attention模擬一个基于内容的檢索過程，過程的核心是 pairwise 的交互作用。論文對整整個過程進行了反思。

---

#### 3. 原理
##### 3-1. 簡述
Synthesizer 對 Transformer 最重要的dot product attention提出修改。這篇論文提出的 Synthesizer 假设我们不僅可以不需要dot product attention，還可以完全不需要有關内容的memorized self attention。

傳統的transformer，注意力權重是在實例或樣本學習的，其中的權重是由實例層面通过 pairwise 交互所產生的。因此，這些特定在實例當中的交互往往在不同的實例之間自由波動，因为它们缺乏一致的全局情境。

##### 3-2. 實現方法: Dense Synthesizer
Synthesizer可以理解為一個Transformer，其中自attention模塊被Synthetic Attention模塊替換掉。

上圖為Transformer、Dense Synthesizer 和 Random Synthesizer 的主要概念。

Synthesizer 移除了 query-key-value 的概念，而直接合成一个對齊矩陣。具體就是去除了 K、Q、V，而使用一個行和列大小等同與序列長度l的矩陣B来表示任意token之间的關係。作者提出了两種 synthesizer，分别是Dense Synthesizer和Random Synthesizer。

Dense Synthesizer 给定模型的输入X，表示了l個token，每个token的维度为d，這個方法做以下的變化：

可以理解為兩个Dense層，W和b用在Dense層的计算。而最後模型的输出Y，由表示token間關係的矩陣 B得到。


其中， G(x)可類比當作標準Transformer的V。

##### 3-3. 實現方法: Random Synthesizer

Random Synthesizer Dense Synthesizer 方法實際上是给定每個token，然後投影到l维，而不是如同原生Transformer對token間交互進行建模。Random Synthesizer的方法中，注意力權重的初始化不是受任何输入token的影響，而是完全做隨機初始化。這些隨機初始化的值可以被訓練，或者保持固定。

以R表示一个隨機初始化矩陣，則Random Synthesizer被定義為：

Y = Softmax(R)G(X)

即B初始化的值是R，這個方法不會依賴token對之間的交互或者任何單一token的資訊，而是學習一个能跨實例有效的任務特定的對齊。
換句話說，作者認為，學習一个跨實例有效的模型意味着在初始化时不直接依靠任何token的資訊。

分解模型 Dense Synthesizer為網絡添加了大小為d*l 的參數，用來投影；

而Random Synthesizer 添加了大小为l*l的参数。如果序列很長，將導致很大的參數量。因此，为了可以實踐，作者提出了分解模型，分别針對Dense Synthesizer和Random Synthesizer稱為Factorized Dense Synthesizer 和 Factorized Random Synthesizer。该方法的作用是减少參數量，以防止過度擬合。

---

## 16. transformer-XL

#### 1. source:
[Transformer-XL: Attentive Language Models Beyond a Fixed-Length Context](https://arxiv.org/pdf/1901.02860.pdf)

---

#### 2. background
將一個完整的段落一次性輸入，進行特徵提取了。但是現實是殘酷的，這麼大的Transformer，內存是消耗不起的。所以現有的做法是，對段落按照segment進行分隔。在訓練時，當輸入segment序列比sequence length短時，就做padding；當輸入segment序列比sequence length長時就做切割。

這種做法顯然是一種權宜之計，它有這麼兩個缺點：
(1)長句子切割必然會造成語義的殘破，不利於模型的訓練。
(2)segment的切割沒有考慮語義，也就是模型在訓練當前segment時拿不到前面時刻segment的信息，造成了語義的分隔。

---

#### 3. 原理
##### 3-1. vanilla
Transformer的限制會固定上下文的長度，就是會將一個長的的文本序列截斷為幾百个字符的固定長度片段(segment)，然後再分别去計算每个片段，片段之间沒有任何的信息交互。例如BERT，序列长度的限制通常都在512，所以對於長篇的文本效果差。
另外，因為要把處理的文本分割成等長的片段，通常不會考慮句子通順（語意），導致上下文碎片化(context fragmentation)。可能會讓一個完整的句子在分割之後，一半在前面的片段，一半在後面的片段。

##### 3-2 XL 原理
* 提出片段遞迴機制(segment-level recurrence mechanism)，引入一個memory模組（類似cache或cell），遞迴用来建模片段之间的聯繫，使得長距离depedency的建模成为可能；使得片段之間產生交互，解决上下文碎片化问题。
* 提出相對位置嵌入机制(relative position embedding scheme)，代替絕對位置嵌入。
在memory的遞迴運算中，避免時序混淆，位置嵌入可重用。

##### 3-3 和transformer比較
普通的Transformer是如何encode的？下圖顯示每個segment分别encode，相互之间不產生任何交互。

而論文中提出的segment-level recurrence mechanism為了解决長距離相依性，引入一个memory狀態。
在计算片段的表示时，用memory缓存片段層的隱層狀態，這樣就给下一個片段同個上文，長距離相依性也透過memory保存下来。並且，最大可能的依賴長度線性增長，達到N*L。

## 17. compressive transformers

#### 1. source:
[Compressive Transformers for Long-Range Sequence Modelling](https://arxiv.org/pdf/1911.05507.pdf)

---

#### 2. 原理
##### 3-1. 概念

為了增加Transformer可以學習到的語意長度，Compressive Transformer在原Transformer的結構上增加了一個記憶模塊和一個壓縮記憶模塊。

每一個序列計算後其隱藏的狀態被放入記憶模塊中，然后記憶模塊中的部分原有記憶会被壓縮然後放入壓缩記憶模塊中，這時候壓縮記憶模塊中的部分記憶則會被丟掉。

如下圖所示，壓縮記憶模塊和記憶模塊维度皆為6，而序列長度為3。箭投和f表示对記憶模塊中的記憶進行壓縮並放入壓縮記憶模塊中。

Compressive Transformer具體的方法如下，其中m表示記憶模塊，cm表示壓縮記憶模塊，h為隱藏狀態，d為Embedding维度，为壓縮記憶模塊長度，为記憶模塊長度，c為壓縮長度，l為層數。


##### 3-1. 圖解原理
下圖為一個簡易圖解，红色表示計算的注意力，藍色表示將計算過的序列存入記憶模塊和壓縮記憶模塊過程。


在論文中作者嘗試了如下幾個不同的壓縮函数：(1)max/mean pooling； (2)Dconvolution；(3)dialated convolutions；(4)most-used。實驗表明在 WIKITEXT-103數據集中 1D convolution表現最好。

同时為了更好的學習壓縮函数的參數，模型訓練时使用了一个輔助的損失函數（因為若是依賴模型的損失函数，則梯度需要經過很長的时序才能傳到儲存的老的記憶，類似RNN裡梯度消失的問題）。

這個損失涵數為注意力重建損失函數，只在測量透過更新後的記憶計算的注意力和使用原本記憶計算的注意力之間的差距。透過最小化該差距來確保有效的壓縮資訊。