論文
[2009.06732] Efficient Transformers: A Survey
1.Background on Transformers
Dense Attention： encoder和decoder最大的區(qū)別在于掩碼不同搓扯，encoder中的token可以看見所有的襟己，而decoder中的token只能看見它前面的，他后面的token被mask掩掉了假哎，需要預(yù)測出來芒帕。
Transformers是將 Transformer block彼此堆疊形成的多層體系結(jié)構(gòu)歉嗓，Transformer block（基本單元塊）的特點(diǎn)是多頭自注意力機(jī)制（multi-head self-attention mechanism）、位置前饋網(wǎng)絡(luò)（position-wise feed-forward network）背蟆、層歸一化（layer normalization）和殘差連接（residual connectors.）
Transfomers的輸入是tensor鉴分，shape是，B is batch size带膀，N is sequence length志珍。
（1）輸入首先通過embedding layer，embedding layer將每個(gè)one-hot token 表示為d維embedding垛叨，例碴裙，，之后新的tensor與positional encodings相加并通過多頭自注意模塊点额。Positional encodings可以采用正弦輸入的形式或者可訓(xùn)練的embedding舔株。
（2）multi-head self-attention?module的輸入和輸出residual connectors和一層 normalization layer連接。multi-head self-attention?module的輸出傳遞到兩層前饋網(wǎng)絡(luò)还棱，輸入和輸出類似地以殘差方式通過層歸一化連接载慈，表示為。
是sub-layer module珍手，（the multi-headed self-attention或者position-wise 前饋層）
1.1.Multi-Head Self-Attention（多頭注意力機(jī)制）
Transformer模型利用多頭注意力機(jī)制办铡，其背后的機(jī)制是學(xué)習(xí)alignment（對比）辞做，序列中的每個(gè)element學(xué)習(xí)從其他tokens中收集信息。a single head 定義為：
寡具，
秤茅，
，
?是應(yīng)用于輸入序列的時(shí)間維度的線性變換童叠。
框喳，
匹层，
?
是query的權(quán)重矩陣（參數(shù)）亿驾，key和values投影并且將輸入X映射到x維的輸出tensor峭判，
是heads的個(gè)數(shù)宣蠕。
檀训；
?是比例因子 通常設(shè)置為
埋泵。
表示heads的個(gè)數(shù)留夜，heads的輸出
?concatenated together 并且用過一個(gè)dense層包警。輸出Y表示為：
.這里
?是輸出層映射撬碟。注意all heads的線性變換并行計(jì)算诞挨。
.
attention matrix??主要學(xué)習(xí)序列中tokens之間的對比分?jǐn)?shù)（alignment scores），在這個(gè)公式中呢蛤，獲取query（Q）中每個(gè)元素和key（K）之間的點(diǎn)積惶傻。這會推動self-attention中的self-alignment過程，從而使tokens彼此學(xué)習(xí)顾稀。
On the scalability of Self-Attention（自我注意的可擴(kuò)展性）
很明顯輸入sequence 長度為N达罗，the attention matrix A 內(nèi)存和計(jì)算的復(fù)雜性是 N X N。特別的静秆，僅矩陣的乘法運(yùn)算就使用
的時(shí)間和內(nèi)存粮揉。這限制了self-attention在處理長序列的效果。
1.2?Position-wise Feed-forward Layers（位置前饋層）
self-attention的輸出傳遞給具有ReLU激活的兩層前饋網(wǎng)絡(luò)抚笔，該前饋網(wǎng)絡(luò)獨(dú)立的在每個(gè)位置運(yùn)行扶认，因此稱為“position-wise”，表達(dá)式為：
殊橙，F1辐宾、F2 為形式是Wx+b的前饋函數(shù)。
1.3?Putting it all together
每個(gè)Transformer Block 表示為：
?=?
?+?
?=?
?+?
X 是Transformer Block 的輸入膨蛮，是Transformer Block 的輸出叠纹。不管哪一種類型的結(jié)構(gòu)都是由多個(gè)transformer基本單元組成，基本單元包括多頭注意力機(jī)制敞葛、前饋網(wǎng)絡(luò)誉察、層歸一化和殘差連接。多頭注意力機(jī)制主要是將輸入的embedding映射到不同的低維度空間上惹谐，通過內(nèi)積計(jì)算不同token之間的相關(guān)性得分持偏，再將相關(guān)性得分乘以對應(yīng)的token embedding求和得到某一個(gè)token的embedding驼卖，最后把同一token在不同低維度空間上embedding拼接起來得到最終的向量表征。在這里鸿秆，每個(gè)token都與其他的token進(jìn)行一次attention計(jì)算酌畜，如果有序列長度為n，那么時(shí)間復(fù)雜度為o(
),這種attention方式稱之為稠密注意力機(jī)制（dense attention?mechanism）卿叽。
1.4 Transformer Mode
Transformer block的使用差異桥胞，主要有三種使用方式（1）encoder-only（分類），（2）decoder-only（語言模型）（3）encoder - decoder（機(jī)器翻譯）附帽。在encoder - decoder模式下埠戳，通常有多個(gè)multi-headed self-attention 模塊井誉。包括encoder-decoder中的標(biāo)準(zhǔn)self-attention蕉扮。包括encoder-decoder cross attention允許decoder
3. A Survey of Efficient Transformer Models
3.1 Efficient Transformers 的分類
除了基于段的遞歸模型，這些模型的主要目標(biāo)是近似quadratic-cost 注意力矩陣颗圣，每種方法都將稀疏性的概念應(yīng)用稠密的注意力機(jī)制喳钟。
（1）Fixed Patterns (FP)?
通過限制attention的范圍，從全局到局部骄恶，降低計(jì)算復(fù)雜度食铐，包括下述3種方法：
?? ?? ? Blockwise Patterns
??，將輸入序列切成多個(gè)block僧鲁，attention只發(fā)生在block范圍內(nèi)虐呻，所以復(fù)雜度從降低到
,B 是Block size，這種切割會導(dǎo)致序列不連貫寞秃，attention能力受限斟叼，效果應(yīng)該不太行。
????? ??Strided Patterns? 春寿，采用滑動窗口的方法朗涩，每個(gè)token與相鄰幾個(gè)token做attention，相鄰的token范圍就是window size堂淡，這樣是有一定道理的馋缅，因?yàn)樽匀徽Z言在多數(shù)情況下都是局部相關(guān)的扒腕，所以在一個(gè)窗口范圍內(nèi)作attention往往不會丟失太多信息，相比之前的blockwise pattern應(yīng)該好一些萤悴。
? ? ? ?Compressed Patterns? 瘾腰，則通過卷積池化的方式對序列進(jìn)行降采樣，比如用kernel 為2覆履，stride為2的CNN蹋盆，將2個(gè)token表征成一個(gè)向量，然后在做attention硝全，同樣也能降低attention的計(jì)算復(fù)雜度栖雾。其實(shí)就相當(dāng)于通過CNN對序列進(jìn)行n-gram的切分。
（3）Learnable patterns(LP)
learnable patterns是對上文提到的fixed patterns的擴(kuò)展伟众，簡單來說fixed pattern是認(rèn)為規(guī)定好一些區(qū)域析藕，讓該區(qū)域的token進(jìn)行注意力計(jì)算，而learnable patterns則是通過引入可學(xué)習(xí)參數(shù)凳厢，讓模型自己找到劃分區(qū)域账胧。比如reformer引入基于哈希的相似度度量方法將輸入序列切割；routing transformer對token向量進(jìn)行k-means聚類來將整體序列分割成多個(gè)子序列先紫。所以本質(zhì)上說LP與FP是一致的治泥，都是通過將整體序列切分成子序列，attention只在子序列中進(jìn)行遮精，從而降低計(jì)算開銷居夹，只不過LP的區(qū)域劃分是通過模型學(xué)得，而FP則是人為定義本冲。
（4）Memory
memory乍一聽好像有點(diǎn)讓人摸不著頭腦准脂，其實(shí)想法也很簡單。最開始是在19年的set transformer上使用眼俊。一般來說做multihead self-attention時(shí)意狠，Q=K=V=X（X為輸入序列，長度為n）疮胖，而在set transformer中环戈，作者先單獨(dú)設(shè)置了m個(gè)向量（m是超參數(shù)），然后這m個(gè)向量與X做multihead attention澎灸，得到m個(gè)臨時(shí)向量（這些個(gè)臨時(shí)變量我們就稱作“temporary memory”）院塞，接著把X與這m個(gè)臨時(shí)向量再做一次multihead attention得到輸出。這個(gè)過程其實(shí)就是利用這m個(gè)向量將輸入序列X的信息先通過attention進(jìn)行壓縮性昭，再通過attention還原拦止，達(dá)到抽取輸入序列的特征的目的。但是在壓縮編碼解碼的過程中肯定會有信息損失，所以后來的改進(jìn)方法是引入全局記憶汹族，即設(shè)置一些token萧求，它們可以與所有的token進(jìn)行注意力交互，比如bert的[CLS]顶瞒，由于這些token的數(shù)目遠(yuǎn)小于序列長度夸政，因此也不會給計(jì)算帶來負(fù)擔(dān)，而且往往攜帶了整個(gè)輸入序列的信息榴徐，這就是我們可以在bert上用[CLS]作文本分類任務(wù)的原因守问。
（4）Low rank methods（低秩方法）
使用self-attention matrix的leveraging low-rank 近似，方法的關(guān)鍵是采用矩陣的low-rank 結(jié)構(gòu)坑资，Linformer耗帕，簡單來說，經(jīng)過softmax的
矩陣不是滿秩的袱贮，這意味著我們不需要計(jì)算一個(gè)完整的注意力矩陣仿便，因此我們可以將
維（n表示序列長度，d表示模型向量維度）的K字柠，V映射到
維空間探越。
(5)?Kernels
以核函數(shù)變換的新形式取代原有的softmax注意力矩陣計(jì)算常柄，將計(jì)算復(fù)雜度降至? 范圍內(nèi)，比較代表的有Linear Transformers搀擂，下文有介紹西潘。
(6)?Recurrence
recurrence實(shí)際上也是上文提到的fixed patterns中blockwise的一種延伸。本質(zhì)上仍是對輸入序列進(jìn)行區(qū)域劃分哨颂，不過它進(jìn)一步的對劃分后的block做了一層循環(huán)連接喷市，通過這樣的層級關(guān)系就可以把一個(gè)長序列的輸入更好的表征。以recurrence為代表的就是Transformer-XL威恼。
