写在前面
上一篇 重点在transformer位置信息的改进,这一集挑选了几篇都带有「Sparse」的标签,主要关注点在于transformer结构的复杂度问题。先来看看都有哪些:
「Sparse Transformer from OpenAI,NAACL 2019」 「Adaptively Sparse Transformers,EMNLP2019」 「Explcit Sparse Transformer from PKU」 Generating Long Sequences with Sparse Transformers[1] 来自 OpenAI 的工作,关注于原始 Transformer 的计算复杂度问题,尤其是在面对长序列输入的情况。为此,论文中将 full attention 进行分解,通过多个 sparse attention 来代替,在不牺牲性能的情况下降低复杂度至
O(n \sqrt{n}) 。
下图是三种不同的注意力形式,其中上半部分表示一个 6x6 图像的像素之间相互 attend,下半部分表示对应的 connectivity matrix。
(a)原始 Transformer 的 full attention; (b)「Strided Attention」:这种方式主要应用于图像或者音频,每一个位置通过 attend 其对应的行和列来获取信息,两个 head 的具体表示为:第一个 head 用于 attend 该位置前面的 l 个位置,第二个 head 用于 attend 间隔
l 的位置(如果输入是图像
l 为图像的宽,则 attend 对应的列):
A_{i}^{(1)}=\{t, t+1, \ldots, i\} \text { for } t=\max (0, i-l)
A_{i}^{(2)}=\{j:(i-j) \bmod l=0\}
(c)「Fixed Attention」:这种方式主要应用于像文本
之类没有周期性的数据,首先将文本分成固定长度的块,然后第一个 head 处理该块中该位置之前的所有元素,第二个 head 处理每个块的最后一部分的固定大小的部分。 Other Tricks 上面就是 Attention 主要的改进,文中还涉及了一些其他的 tricks。
「pre-activation residual block」来自Identity mappings in deep residual networks[2]可以使 Transformer 的训练更加容易 \begin{aligned}
H_{0} &=\text { embed }\left(X, W_{e}\right) \\
H_{k} &=H_{k-1}+\text { resblock }\left(H_{k-1}\right) \\
y=& \operatorname{softmax}\left(\operatorname{norm}\left(H_{N}\right) W_{\text {out}}\right)
\end{aligned}
其中 resblock(H)的计算如下
\begin{aligned}
a(H) &=\text { dropout }(\text { attention }(\operatorname{norm}(H))) \\
b(H) &=\operatorname{dropout}(\mathrm{ff}(\operatorname{norm}(H+a(H)))) \\
& \text { resblock }(H)=a(H)+b(H)
\end{aligned}
「Gradient check-pointing」 「Efficient block-sparse attention kernels」 「Mixed-precision training」 reference Code Here[3] openai sparse-transformer blog[4] Adaptively Sparse Transformers[5] 这篇论文也是对 vanilla Transformer 的改进,提出了 Adaptively Sparse Transformers (AST),优化的两个关键就在其名字中:
「Sparse:」 通过替换 Softmax 函数为 \alpha-entmax 达到稀疏注意力;
「Adaptively:」 每个 attention head 都是模型可自动学习的; 作者指出与先前的sparse transformer
(下图sparse transformer就是上一篇论文,adaptive span transformer在本系列第二篇 中介绍过)研究不同的是,他们的这一方法可以关注在不连续的输入集合,如下图:
2.1 Sparse Attention softmax 函数所有结果都不为 0,并且最终所有元素之和为 1,这样的特性决定了相对重要的部分的权值会“缩水”。这一方向的研究很多,作者选用了最近提出的alpha-entmax[6]:
\alpha \text { -entmax }(\boldsymbol{z}):=\underset{\boldsymbol{p} \in \Delta^{d}}{\operatorname{argmax}} \boldsymbol{p}^{\top} \boldsymbol{z}+\mathrm{H}_{\boldsymbol{\alpha}}^{\mathrm{T}}(\boldsymbol{p})
\mathrm{H}_{\alpha}^{\mathrm{T}}(\boldsymbol{p}):=\left\{\begin{array}{ll}
{\frac{1}{\alpha(\alpha-1)} \sum_{j}\left(p_{j}-p_{j}^{\alpha}\right),} & {\alpha \neq 1} \\
{-\sum_{j} p_{j} \log p_{j},} & {\alpha=1}
\end{array}\right.
2.2 AST 对于 Transformer 类模型的功能至关重要的是,不同的 head 会捕获不同的语言现象,这让我们想到对于不同的 head,使用不同的
\alpha 值,使其自适应地让一些 head 稀疏化,一些 head 更接近 softmax。利用上面的
\alpha-entmax 替换原始的 softmax 函数后,将
\alpha 看成是与其他网络参数一样的可学习参数,通过随机梯度进行优化。但是通过梯度方法对其自动优化并不容易,然后作者在下面就开始一系列数学推导。。。
2.3 TODO 实在是看不动了。。。
后面的实验和分析也非常有意思的。。。
大家记得看,我先溜了。。。
PS. 在油管上发现了作者的分享视频,放在 reference 里
2.4 Reference Explicit Sparse Transformer: Concentrated Attention Through Explicit Selection[9] Motivation和上一篇论文一样,如下图,对于文本I thanked him with all my heart, and I asked him, 'why are you helping me?'
,vanilla Transformer(蓝色标记)会对所有元素都有注意,而噪音的注意力会对效果产生影响;新提出的显式稀疏注意力机制(橙色标记)只会关注文本的
topk 个attention score最大的元素,从而移除无关信息。
具体实现也非常简单易于实现,且不会增加额外的内存和计算开销。
沿用vanilla transformer的attention计算公式得到attention score, P=\frac{Q K^{\mathrm{T}}}{\sqrt{d}}
假定分值越大的元素其相关性越大,计算Masking矩阵。找出 P 中每行的
k 个最大元素,记录其位置,并得到一个threshold vector,
t=\left[t_{1}, t_{2}, \cdots, t_{l_{Q}}\right] 将Making矩阵应用到原始 P 矩阵上,
\mathcal{M}(P, k)_{i j}=\left\{\begin{array}{l}
{P_{i j}},ifP_{i j} \geq t_{i}(k \text { -th largest value of row } i) \\
{-\infty},if P_{i j} \leq t_{i}(k \text { -th largest value of row } i)
\end{array}\right.
该步反向传播时
\frac{\partial M_{i j}}{\partial P_{k l}}=0 \quad(i \neq k \text { or } j \neq l)
\frac{\partial M_{i j}}{\partial P_{i j}}=\left\{\begin{array}{ll}
{1} & {\text { if }P_{i j} \geq t_{i}(k \text { -th largest value of row } i)} \\
{0} & {\text { if }P_{i j} \leq t_{i}(k \text { -th largest value of row } i)}
\end{array}\right.
归一化, A=\operatorname{softmax}(\mathcal{M}(P, k))
该步反向传播时,
\begin{aligned}
\frac{\partial A_{i j}}{\partial P_{k l}} &=\sum_{m=1}^{l_{Q}} \sum_{n=1}^{l_{K}} \frac{\partial A_{i j}}{\partial M_{m n}} \frac{\partial M_{m n}}{\partial P_{k l}} \\
&=\frac{\partial A_{i j}}{\partial M_{k l}} \frac{\partial M_{k l}}{\partial P_{k l}} \\
&=\left\{\begin{array}{c}
{\frac{\partial A_{i j}}{\partial M_{k l}}} & {\text { if }P_{i j} \geq t_{i}(k \text { -th largest value of row } i)} \\
{0}& {\text { if }P_{i j} \leq t_{i}(k \text { -th largest value of row } i)}
\end{array}\right.
\end{aligned}
输出表示, C=A V
整体流程如下最右图所示,
另外,参数
k 的选择至关重要,当
k 取与序列长度一致时即为vanilla transformer。作者在NMT实验中发现当
k=8 时效果最好。
reference Code Here[10] Open Review[11] 本集Over~明天要视频毕业答辩就不更了,希望老师轻点怼...轻点... 本文参考资料 [1]
Generating Long Sequences with Sparse Transformers: https://arxiv.org/abs/1904.10509
[2]
Identity mappings in deep residual networks: https://arxiv.org/abs/1603.05027
[3]
Code Here: https://github.com/openai/sparse_attention
[4]
openai sparse-transformer blog: https://openai.com/blog/sparse-transformer/
[5]
Adaptively Sparse Transformers: https://www.aclweb.org/anthology/D19-1223.pdf
[6]
alpha-entmax: http://xxx.itp.ac.cn/pdf/1905.05702v2
[7]
Code Here: https://github.com/deep-spin/entmax
[8]
作者分享视频: https://www.youtube.com/watch?v=HLmPDJh8Fls
[9]
Explicit Sparse Transformer: Concentrated Attention Through Explicit Selection: https://arxiv.org/abs/1912.11637
[10]
Code Here: https://github.com/lancopku/Explicit-Sparse-Transformer
[11]
Open Review: https://openreview.net/forum?id=Hye87grYDH¬eId=rkezjkjniS
- END -