Self-Attention & Transformer pytorch

第一部分，参照Hong-yi Lee youtube视频，记录背景知识和attention的计算原理。
第二部分，按照论文《Attention is all your need》的结构，描述怎么利用第一部分的算法，搭建一个transformer。
第三部分，个人实现过程中遇到的问题，能解释的都回来补充了，也会穿插在正文里。

一、Attention
我们知道，rnn不容易并行计算。因为每一个状态依赖于上一个状态生成的隐向量。
现在的模型做的越来越大，不搞并行计算，根本配不上效率要求。
而cnn是一个易于并行计算的东西，于是很自然的，会有人想用cnn代替rnn。

来看看这件事的可行性。
像传统CNN一样，我们用一个filter扫过一个sequence，产出一排sequence作为结果。
看上去效果会跟rnn类似。
但问题是，filter只有局部视野，每次只能看相邻的有限个元素，不能解决长依赖(long dependency)问题。

图像任务里，做法是搞很多层CNN。
只要CNN的层数足够多，最上层的CNN就会有全局视野。
没什么事情是2层CNN不能解决的，如果有就再加2层。
但是这样开销比较大。

于是出来了self-attention layer。
可以做到RNN能做的事情，还支持并行计算，开销又比多层CNN小。

每个输入，进行一次embd，得到xi。于是有列向量x1,x2,...,xm，组成矩阵X。
设有3个矩阵Wq,Wk,Wv。分别与X做矩阵乘法，得到新矩阵Q,K,V。

文章图片

Q,K,V的每个列向量qi,ki,vi，都是归属于xi的衍生物。

q:query (to match others)
k:key (to be matched)
v:value (information to be extracted)

做矩阵乘法 K^T*Q，得到attention矩阵A。
看下图，以矩阵A的第1列举例。
表示第1个特征x1的querry向量q1，分别去match第1,2,3,4个特征的key向量k1,k2,k3,k4后，得到的match结果（感兴趣程度）alpha1,1；alpha1,2；alpha1,3；alpha1,4。

注意，图里没有表现出来。
实际上的算法
alpha1,i =q1(innerproduct)ki/sqrt(d),d is the dim of q and k
实际上还要除以一个平衡variance的sqrt(d)。d代表q和k的dimension。

文章图片

那么我们对第1列进行softmax，得到的就是x1对(x1,x2,x3,x4)分别的attention比例。
同理，对A矩阵的每一列进行softmax，得到attention矩阵A'。

文章图片

得到了每个xi对其他xj的attention比例之后，就可以计算value了。

令V与A'做矩阵乘法，得到结果矩阵O，O的每一列都是一个列向量。
(b1,b2,b3...,bm)就是self-attention代替RNN跑出来的sequence。

文章图片

上述过程你会发现，似乎跟RNN有一点不同，那就是xi在对xj求attention的时候，并没有考虑xj距离xi有多远。
为了弥补这种距离中蕴含的信息，我们让最初的xi =xi+ei 。
ei是一个位置信息，positional embedding。

为什么用add，不用concatenate(xi,ei)。
李宏毅视频里有一个解释，可以证明如果不去学习这个ei，而是公式法直接给出的话，add是等价的。

二、Transformer

2.1
看完李宏毅视频准备自己写代码的时候发现原来什么都不懂
乖乖虚心地去翻了原论文。

算法这东西还是原作者讲得清楚，别人的解析会自动省略掉他的各种“显然”。
我写的肯定也有残缺。

attention mechanism很早就被提出了(上世纪)，从14年开始谷歌等将它用于RNN等，随后在翻译等许多任务上表现优秀，才真正火起来。
【技术在被发明的时代未必有其价值？】
为什么本文的标题会叫《Attention is all your need》呢？
因为本文首次提出，完全基于attention的序列转化模型transformer。

To the best of our knowledge, however, the Transformer is the first transduction model relying
entirely on self-attention to compute representations of its input and output without using sequencealigned
RNNs or convolution.

在此之前，attention只是一种副产品，类似于dropout或者BN，自然嵌入到其他框架中。
这篇标题的意思就是，可以放弃你们的RNN或者CNN的了，可以使用纯Attention来做seq的特征提取。
第一次看标题就很奇怪为什么要这么起，今天算是弄清楚了。
能写这种自由而随意的风格的标题真是好啊。
一般人只敢规规矩矩的按套路起高大上的名字希望被审稿人捡起来，不是谷歌的话，哪里敢这么浪。
希望有朝一日也能使用自由风格的标题发文章。

2.2 结构

模型整体沿用了最常见的encoder-decoder框架。【这种二元对抗似乎某种意义上反映了宇宙本质？】

文章图片

框架图。
【Lee有句话吐槽的好，大家都经常看见这个框架图，但是不懂的人看了一万次还是不懂它在表达什么。。。】

2.3 Encoder
encoder是a stack of 6 identical encoder layers。
每个encode layer由2个sub-layer组成，分别为multi-head self-attention mechanism，和 position-wise fully connected feed-forward network。
【头疼，问了大神确认了feedforward network跟隔壁CTR喜欢说的MLP基本是同一个东西。但你们为什么要如此张扬写意地搞几个不同的名词。】

文章图片

同时，还在2个sub-layer周围添加了残差连接（residual connection）。
于是每个sub-layer的输出可以被描述为 sub_out = LayerNorm(x + Sublayer(x))。
LayerNorm（https://arxiv.org/abs/1607.06450），跟BatchNorm相比，就是方向不同，一般会在序列模型里面使用。

为了方便残差运算，我们固定embedding、sub_layers的输出维度为d_model = 512。

2.4 Decoder
和encoder相比，唯二的区别是从2个sub-layer变成了3个，以及添加了mask。

文章图片

新增的1个sub_layer，被放在中间，采纳了encoder的输出作为输入。
新增的mask，被放在第一个sub_layer处，保证位置i处，只能得到位置小于i的信息。

2.5 Scaled Dot-Product Attention

本文使用的attention被命名为Scaled Dot-Product Attention。
虽然有特殊名字，但其实没什么特殊算法。

文章图片

不妨设，输入Q与K的dim都是d_k，输入V的dim是d_v。
公式如下，和第一部分讲的attention一样。

文章图片

计算过程：
Q, shape=[m,dk]
K^T ,shape=[dk,m]
V,shape=[m,dv]
A=QK^T,shape=[m,m]
B=softmax(A,dim=0), 按列计算softmax, shape=[m,m]
B=B/sqrt(dk)
B^T,shape=[m,m]，每一行相当于是某一个querry对所有K的attention比例。
out = B^T*V,shape=[m,dv]

整个过程，唯一的创新处在于，对Attention矩阵B除以了sqrt(dk)，也就是名字里scaled的来历。
这是为了防止在使用大dk时，A矩阵数值上过大，使得经过softmax变成B以后，梯度太小。【和sigmoid要0均值化一个道理。】

We suspect that for large values of dk, the dot products grow large in magnitude, pushing the softmax function into regions where it has
extremely small gradients

为什么大dk会导致数值变大呢？原文解释

To illustrate why the dot products get large, assume that the components of q and k are independent random
variables with mean 0 and variance 1. Then their dot product, qk = \sum_{i=1}^{d_k} q_ik_i, has mean 0 and variance dk.

补充:

原文介绍，常见additive attention与dot-product (multiplicative)attention两种机制。
即加性attention和点积attention。
在理论上算法复杂度相近的前提下，后者计算更快而且更省空间，因为矩阵乘法运算可以被专门的GPU等优化加速。

2.6 Multi-Head Attention
这里终于解释了我的一个疑问。
一般的attention文章，似乎为了简便起见，会假设Q,K,V的维度是一致的，即等于d_model。
其实是可以不等的。Q和K的维度要相等，因为需要做矩阵运算。(Q,K)与V的维度却完全可以不同。

原文说，他们实践发现把QKV先映射成不同的维度dk和dv，重复做h次，效果更好。

Instead of performing a single attention function with dmodel-dimensional keys, values and queries,
we found it beneficial to linearly project the queries, keys and values h times with different, learned
linear projections to dk, dk and dv dimensions, respectively.

也就是说，我们拿到QKV之后，做h次线性映射，得到h对dk和dv维度的(Q',K',V')。
然后送入上面说的scaled dot-product attention层。
如下图所示。

文章图片

每一对(Q',K',V')产出一个d_v维度的output。
h对产出h个output。
将h个output拼接在一起，再做最后一次linear变换，得到最终的输出。

最后这一步是为了把h*dv维的变量，映射成d_model维。前面说过，这有利于残差连接的计算。

本论文中h=8。

为了保证使用multi-head的运算量不过分超出原版attention，
我们设置dk = dv = d_model/h = 512/8 = 64。
妙啊，这样一来相比于512维的(Q,K,V)，每一次(Q',K',V')都只有64维，单次复杂度降低，但又要运行8次，最终的复杂度在数量级上不会超过原版太多。

2.7 Applications of Attention in our Model

①
感觉我理解有问题。先放原文，防止我的翻译有误导性。

In "encoder-decoder attention" layers, the queries come from the previous decoder layer,
and the memory keys and values come from the output of the encoder. This allows every
position in the decoder to attend over all positions in the input sequence. This mimics the
typical encoder-decoder attention mechanisms in sequence-to-sequence models such as
[38, 2, 9].

我猜测这个"encoder-decoder attention" layers，指的是decoder中间那个新增的sub_layer。

文章图片

所以，这个sub_layer的querry是前一个【masked multi-head attention】的输出，memory keys和values是encoder的第2个sub_layer的输出。
由上文已知，这些输出都是d_model维的。
送入decoder中间的sub_layer后，先进行8次线性变换成为dk=dv=64维的(Q',K',V')，然后参与8次scaled dot-production attention计算，最后8次dv输出concatenate回512维。
那么问题来了，这个concatenate得到的512维输出，还要不要做linear了？？？
【我看到的一个实现是继续做的，虽然此时h*dv==d_model，但需要兼容不相等的情况。】

文章图片

②在encoder里，每一个self-attention sub-layer的Q,K,V都是上一个encode layer的输出。
意思就是Q,K,V是同一个东西。【decoder里面就不一样了】
换句话来说就是，上一层encode layer的输出【即上一层的第二个sub-layer的输出】，被copy了三次。
这样的好处是，当前encode layer的每一个位置，都可以处理上一层encode layer的每一个位置。

Each position in the encoder can attend to all positions in the previous layer of the encoder.

③解释之前的mask是什么意思。
在decoder里面，我们也很想让当前decode layer的每一个位置，能处理上一层decode layer的每一个位置。
但为了不发生信息穿越，decode layer做self-attention时，不应该注意到自己之后的位置（因为自己之后的位置此时并没有输出任何东西）。
所以我们用mask技术，把上三角遮住了【不给看】！

文章图片

这样，第i行只能看到第(1,2,...,i)列。

具体做法是，直接把蒙版区的attention矩阵的值设为负无穷。表示对该区域的注意力为负无穷!
这样softmax之后，对应区域的权重会趋于0。

pytorch中可以这样写
attention = attention.masked_fill(mask, -np.inf)
【注意，置为负无穷发生在softmax之前】

2.8 Position-wise Feed-Forward Networks 可以简单理解为一个MLP
前面说过，这东西和MLP基本是一个意思。

文章图片

但特别之处在于这一句

each of the layers in our encoder and decoder contains a fully connected feed-forward network, which is applied to each position separately and identically

也就是说，在每个位置上是identically applied。
也就是说，等价于kernel_size=1的Conv1d。

Another way of describing this is as two convolutions with kernel size 1.
The dimensionality of input and output is dmodel = 512, and the inner-layer has dimensionality
dff = 2048.

【提问：size=1的conv1d和fc有什么区别？】

2.9 Embeddings and Softmax 参数共享

we use learned embeddings to convert the input tokens and output tokens to vectors of dimension d_model.
We also use the usual learned linear transformation and softmax function to convert the decoder output to predicted next-token probabilities
In our model, we share the same weight matrix between the two embedding layers and the pre-softmax
linear transformation, similar to [30].
In the embedding layers, we multiply those weights by sqrt(d_model).

input和output共用一份embedding参数。

文章图片

我们知道embd的形状是(n_vocab,d_model)
把长度n的词表，表示为d_model的向量。

这句“pre-softmax linear transformation”是指这个部分。

文章图片

最后这个Linear变换写成代码就是：

a=nn.Linear(d_model, n_vocab, bias=False)
在pytorch中，a.weight的形状恰好是(n_vocab,d_model) ，即(out_dim,in_dim)

发现了吗？
这三个地方的参数形状是一样的，所以可以实现共享。
具体来说分2步。
一步是decoder的embd参数与decoder最后一次线性变换的参数共享。
另一步是decoder的embd参数与 encoder的embd参数共享。

根据下面这篇论文，直接利用embd里训练出来的相似性，可以提高softmax的表现。
[30]Using the Output Embedding to Improve Language Models(Ofir Press and Lior Wolf),https://arxiv.org/pdf/1608.05859.pdf 。

回来补充：

躺在床上思考时忽然头皮发麻。
仔细想一想，在softmax之前，用embedding参数矩阵，作为linear变换的参数，这个操作是不是在哪里看过？
是的，在youtube那篇经典的推荐系统论文里面啊！

文章图片

这篇论文的【Deep candidate generation model】部分，
video vectors由embd给出，经过MLP形成user vector的一部分。
同时在最后一步，video vectors要跟user vector做内积，来计算用户的感兴趣程度。
这个不就等于是user vector拿出来跟整个embedding参数矩阵做矩阵乘法吗？
所以说，transformer这篇论文里的矩阵参数共享，乍一看不好理解，其实可以用youtube这篇论文里面的向量内积理论来解释，本质上还是decoder输出的用户向量与所有词向量的内积，即代表了当前output与所有词向量的“距离”，或者说关系程度。

另外一个疑问：

上一段解释了softmax之前的参数共享，但没有解释为什么inputs和 outputs 两个embedding表可以参数共享。
带着这个问题看老外的实现代码时，读到这么一句话，
If your source and target language share one common vocabulary, use the -embs_share_weight flag to enable the model to share source/target word embedding.
可是，做翻译任务的时候，有可能词表相同吗？
不同语言的词表应该都不一样吧？？？

2.10 Positional Encoding（黑科技）
第一部分提到过，positional encoding被表示为一个和输入xi同为d_model维的向量ei，然后把这两个向量相加。

文章图片

尝试解释一下最后那句linear function。
对固定pos，有一个d_model维的位置向量，写成PE_pos
其第(0,1,2,...,i,...)维度
对应值为[sin(pos/a^h(0)),sin(pos/a^h(1)),...,sin(pos/a^h(i)),...]
那么pos+k位置的向量，PE_{pos+k} = [ sin((pos+k)/a^h(0)) ,..., sin((pos+k)/a^h(i)),... ]
而根据sin(a+b)=sin(a)cos(b)+sin(b)cos(a)，当k为常数时
PE_{pos+k}相当于 u*sin(a)+v*cos(a)，其中sin(a) = PE_pos，cos(a)= sqrt(1-PE_pos^2)。
但是，这是线性方程吗？

另外一个问题，为什么不用自己学习的position embedding呢？
作者解释：
其一，试了，效果几乎是一样的，那么还不如使用固定的position向量，减少参数。
其二，使用正弦曲线可以让模型推断的序列长度大于训练时给定的长度。【为什么？？？看不懂！！！】

We chose the sinusoidal version because it may allow the model to extrapolate to sequence lengths longer than the ones encountered during training.

回来补充：
在几篇推荐系统的论文里面，还是有用learned embedding的。
比如这篇《Self-Attentive Sequential Recommendation》。

文章图片

有的人是用时间间隔作为position。【阿里那篇behavior sequence transformer,BST】
有的是用在行为中的相对顺序作为position。
这里展开来呢，有用【被展示-被点击】的时间间隔，也有用【和上一个行为之间】的时间间隔。
但是这些论文都没开源，所以我现在满脑子都是疑问。
你们算的时间间隔，是以秒为单位吗？还是分？
是直接用每一秒当成1个id去查embd吗？还是1~5秒算第一组，5~10秒算第2组这样子按组embd？
还是说？？？

几个疑问

1.decoder的输入是什么？图上写着outputs，可outputs是个啥？
2.怎么自适应输入输出长度？如果翻译任务的话，输入的句子长度不定，输出句子的长度也不定啊。

试图回答：

训练时，decoder用ground_truth作为embd的输入。
测试时，官方实现采用了Beam Search算法，所以第i轮的decoder的输入是上一轮decoder产生的Bm种(i-1)个单词。
这样说可能有点模糊，容我废话一点。
-训练时，target_seq是已知的，长度已知，所以只需要丢进去1次target_seq，跑一次decoder，就能得到长度相同的输出。
输出shape=(batchsize,len_tgt,d_model)，只需要在len_tgt维度上，挨个对每个位置的单词算交叉熵。
-测试时，由于target_seq是未知的，长度未知。所以我们采用逼近求解的思路。
第一次传入一个(xx,1)的0张量，输出一个(xx,1,d_model)的预测结果。在d_model维度上取top Bm个最大概率对应的下标，就是Bm个第1个位置的可能预测值。
第二次，取(xx,2)的张量，其中[:,0]位置由上一轮的输出填充，[:,1]未知，填入0。同样，我们可以算得第二轮的top Bm个结果。
经过N轮之后，检查是否输出【休止符EOS】，若是，则停止。

文章图片

看上面这张图也能明白，相当于每启动一次decoder，都试探性地输出1位，看这1位是不是【休止符EOS】。
当模型认为应该输出休止符时，我们就不再循环。
所以n位输出，会循环调用decoder一共n次。
#问题1,2同时解答完毕。
#关于Beam Search请看这篇，我认为讲得非常好 https://zhuanlan.zhihu.com/p/36029811

代码参考 https://github.com/jadore801120/attention-is-all-you-need-pytorch

这个实现里也有问题

参数共享仅仅在模型的__init__里面进行？
if weight_sharing:
self.fc.weight = self.weight
self.logit_scale = (self.embd_size ** -0.5)
那训练过程中参数就不一样了啊？
这样最后做运算的时候不还是等于没共享吗。
除非每一次 optimizer.step()之后都运行一次另其相等？

---
我又回来补充了！！！
我参考了另外一篇论文的tensorflow实现，Wang-Cheng Kang, Julian McAuley (2018).《 Self-Attentive Sequential Recommendation.》，https://github.com/kang205/SASRec

困扰我多年的一堆问题有了解答！！！
我发现这些人，果然在论文里写的东西，跟代码里的会有区别。

文章不是说，经过一堆transformer之后，最后拿到的hl，做一个线性变换，然后去softmax吗？
youtube那篇推荐系统论文也是这么写的“我们把推荐当成一个超大维度的多分类任务”。
我信了你的邪。

下午老老实实写了一个softmax的版本。
用的天池比赛的数据集，283万个商品。
283万啊，最后输出一个283万维的向量，再softmax？？？
平均每个格子的概率都低到0.0000000001以下了，根本train不动啊！！！
出来的loss都是15这个样子，换算成exp(-15)大概是10^-7这个样子。

然后直到晚上，我发现了这篇SASrec，惊为天人！！！
开源真是好评啊！！！
论文里写的softmax？
呵呵呵，根本不存在的！

训练的时候，比如对前t个序列，预测t+1会点击的物品。
那么正样本的id记为pos_id，同时取n个负样本id构成neg_id。
通过这些id获得对应的embedding向量，pos_embd和neg_embd。
然后用hl去跟pos_embd向量内积，hl跟neg_embd向量内积。
得到的结果sigmoid一下，就可以求负对数似然度了。

写成代码大概是这样。其中user_vec就是我们的transformer在第t个位置的输出值。

pos_embd = self.item_embd(pos_idx)#(bz,1,embdsize) neg_embd = self.item_embd(neg_idx)#(bz,q,embdsize)pos_score = torch.mul(user_vec,pos_embd)#(bz,1,embd_size) pos_score = torch.sum(pos_score,dim=2)#(bz,1)neg_score = torch.mul(user_vec,neg_embd)#(bz,q,embd_size) neg_score = torch.sum(neg_score,dim=2)#(bz,q)loss_1 = -torch.log(F.sigmoid(pos_score)+1e-20).sum() #(bz) loss_2 = -torch.log(1-F.sigmoid(neg_score)+1e-20).sum() #(bz) loss_2 = loss_2*self.alpha #因为negative的数量远大于positive，所以要用一个alpha来平衡。

这个过程我在 (2.9) 解释过了，就是用目标物品的embd向量，和transformer训练出来的表征用户在最后一个时间点兴趣的隐向量，做内积，结果用来表达兴趣（点击概率）。
这才是共享参数的真谛啊，根本不是傻憨憨地令self.fc.weight= self.embd.weight。

以上为训练部分。

预测的时候就更简单了，softmax本来也就是个非递减函数。
我们预测出来的几百万个数字，如果不是为了缩放到(0,1)去算负对数，为什么要softmax呢？
直接在这几百万个数字里面找个最大的当预测值输出不好吗？
是了，一行max搞定的东西。

无数次血泪教训告诉我，没有开源代码的论文，一个字也不要相信！！！
想法很好的模型，实践起来也要做很多工程上的妥协。
对百万维度进行softmax根本不现实的啊，更别提上亿商品的场景了！
【Self-Attention & Transformer】