Transformer/CNN/RNN的对比（时间复杂度，序列操作数，最大路径长度）

AINLP 原创 · 作者 | redoragd

研究方向 | 自然语言处理

---

• Maximum path lengths：序列中两个元素进行交互所需经过的最大路径长度

• per-layer complexity：每层的时间复杂度

• minimum number of sequential operations：最少需要的序列操作数

计算效率

一个形状为   的矩阵，与另一个形状为   的矩阵相乘，其运算复杂度来源于乘法操作的次数，时间复杂度为 

Self-Attention

• 相似度计算  ：  与  运算，得到  矩阵，复杂度为 

• softmax计算：对每行做softmax，复杂度为  ，则n行的复杂度为 

• 加权和：  与  运算，得到  矩阵，复杂度为 

故最后self-attention的时间复杂度为 

对于受限的self-attention，每个元素仅能和周围  个元素进行交互，即和  个  维向量做内积运算，复杂度为  ，则  个元素的总时间复杂度为 

Multi-Head Attention

对于multi-head attention，假设有  个head，这里  是一个常数，对于每个head，首先需要把三个矩阵分别映射到  维度。这里考虑一种简化情况：  。(对于dot-attention计算方式，  与  可以不同)。

• 输入线性映射的复杂度：  与  运算，忽略常系数，复杂度为  。

• Attention操作复杂度：主要在相似度计算及加权和的开销上，  与  运算，复杂度为 

• 输出线性映射的复杂度：concat操作拼起来形成  的矩阵，然后经过输出线性映射，保证输入输出相同，所以是  与  计算，复杂度为 

故最后的复杂度为： 

注意：多头的计算并不是通过循环完成的，而是通过 transposes and reshapes，用矩阵乘法来完成的。假设有  个head，则新的representation dimension：  。因为，我们将  的矩阵拆为  的张量，再利用转置操作转为  的张量。故  的计算为：  与  做计算，得到  的张量，复杂度为  ，即  。注意，此处  实际是一个常数，故  复杂度为  。

Recurrent

•  ：  与  运算，复杂度为  ，  为input size

•  ：  与  运算，复杂度为 

故一次操作的时间复杂度为  ，  次序列操作后的总时间复杂度为 

Convolution

注: 这里保证输入输出都是一样的，即均是 

• 为了保证输入和输出在第一个维度都相同，故需要对输入进行padding操作，因为这里kernel size为  ，（实际kernel的形状为  ）如果不padding的话，那么输出的第一个维度为  ，因为这里stride是为1的。为了保证输入输出相同，则需要对序列的前后分别padding长度为  。

• 大小为  的卷积核一次运算的复杂度为：  ，一共做了  次，故复杂度为 

• 为了保证第二个维度在第二个维度都相同，故需要  个卷积核，所以卷积操作总的时间复杂度为 
  

序列操作数

• 表明三种模型的并行程度：从计算方式上看，只有RNN才需要串行地完成  次序列操作，而self-attention和convolution的n次序列操作均可以并行完成。因为RNN还需要依赖于上一个时间步的隐藏层输出，而其他模型仅仅依赖于输入。

最大路径长度

• 最大路径长度即距离为  的两个结点传递信息所经历的路径长度，表征了存在长距离依赖的结点在传递信息时，信息丢失的程度，长度越长，两个节点之间越难交互，信息丢失越严重

• RNN：长度为  的序列中，节点之间的最大路径长度为  ，即  。第一个token的信息需要经过  次迭代才能传到最后一个时间步的状态中，信息丢失严重，很难建立节点间的长距离依赖。

• CNN：通过convolution layer来捕捉局部依赖，扩大层数来扩大视野。对每个节点来说，能够“看到”的local context的大小取决于卷积核的大小和层数。在一个卷积核大小为  , 层数为  的CNN中，能看到最大的local context的大小为  ，最大路径长度为  ，例如图(b)中是一个两层的卷积核大小为3的CNN，顶层节点能看到的最大local context为2*2+1=5个token的输入。粗略来看，上图可以看作一个  叉树，深度为  的树，叶子节点个数为  ，解得最大路径长度为  ，即 

• Self-attention：任意两个结点都可以直接相连，即任意两个结点之间的距离为1，故最大路径长度为1

• 受限的self-attention：类似于卷积核大小为  的CNN，最大路径长度为 

参考资料

https://tobiaslee.top/2018/12/13/Start-from-Transformer/
https://arxiv.org/abs/1808.08946
https://www.reddit.com/r/LanguageTechnology/comments/9gulm9/complexity_of_transformer_attention_network/
https://zhuanlan.zhihu.com/p/132554155

---

本文由作者授权AINLP原创发布于公众号平台，欢迎投稿，AI、NLP均可。原文链接，点击"阅读原文"直达：

https://zhuanlan.zhihu.com/p/264749298

由于微信平台算法改版，公号内容将不再以时间排序展示，如果大家想第一时间看到我们的推送，强烈建议星标我们和给我们多点点【在看】。星标具体步骤为：

（1）点击页面最上方"AINLP"，进入公众号主页。

（2）点击右上角的小点点，在弹出页面点击“设为星标”，就可以啦。

感谢支持，比心。

欢迎加入AINLP技术交流群

进群请添加AINLP小助手微信 AINLPer（id: ainlper)，备注NLP技术交流

推荐阅读

这个NLP工具，玩得根本停不下来

征稿启示| 200元稿费+5000DBC（价值20个小时GPU算力）

完结撒花！李宏毅老师深度学习与人类语言处理课程视频及课件（附下载）

从数据到模型，你可能需要1篇详实的pytorch踩坑指南

如何让Bert在finetune小数据集时更“稳”一点

模型压缩实践系列之——bert-of-theseus，一个非常亲民的bert压缩方法

文本自动摘要任务的“不完全”心得总结番外篇——submodular函数优化

Node2Vec 论文+代码笔记

模型压缩实践收尾篇——模型蒸馏以及其他一些技巧实践小结

中文命名实体识别工具（NER）哪家强？

学自然语言处理，其实更应该学好英语

斯坦福大学NLP组Python深度学习自然语言处理工具Stanza试用

关于AINLP

AINLP 是一个有趣有AI的自然语言处理社区，专注于 AI、NLP、机器学习、深度学习、推荐算法等相关技术的分享，主题包括文本摘要、智能问答、聊天机器人、机器翻译、自动生成、知识图谱、预训练模型、推荐系统、计算广告、招聘信息、求职经验分享等，欢迎关注！加技术交流群请添加AINLPer(id：ainlper)，备注工作/研究方向+加群目的。

阅读至此了，分享、点赞、在看三选一吧🙏