Transformer：一种图灵完备的神经网络

点击下方卡片，关注“CVer”公众号

AI/CV重磅干货，第一时间送达

点击进入—>【Transformer】微信技术交流群

作者：张晨珩（北京大学23级博士生）已授权

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

论文: Attention is Turing Complete, Author: Perez et al.

Transformer是一种非常火的模型，特别是在chatgpt问世之后，已经显露出一统NLP领域的趋势。

这篇文章提供了一种崭新的视角去理解transformer，一个单层encoder、三层decoder的小transformer竟然就能几乎完美地模拟一台图灵机。某种程度上说，它拥有至少和现代计算机一样的计算潜力。近期，另一篇脑洞大开的工作甚至用少于13层的looped transformer，就成功地实现了绝大部分基本的计算操作。

这里记录几个自认为有趣的insight

为什么需要位置编码？

众所周知，transformer采用注意力机制，能够识别各单词之间的相关性，但对词序并没有要求。也就是说，在它看来，我爱你、我你爱，这两句话没有区别。因此，需要对输入的序列进行位置编码。

本文从计算理论的角度思考了这个问题。如果将transformer看成一个自动机，那么输入的序列就相当于待识别的语言。如果不进行位置编码，他就无法分辨两种仅有位置不同的语言。更进一步，还可以证明，只要两种语言的各字母比例相同，它就已然无法分辨。

于是这就要求transformer识别的语言集合一定具有比例不变性（proportion invariance），这样来看，它甚至无法识别正则语言，远远未达到我们的预期。

然而，当加入了合适的位置编码以后，我们甚至能使transformer模拟任意一台图灵机。足可见，位置编码有多重要。

如何证明图灵完备性？

这里采用了直接模拟图灵机的方法。对于任意一台图灵机，其核心是，每个格局下的操作以及操作之后的状态转换。因此，我们只需要模拟出他的完整状态表，就可以重现其计算过程，也就证明了等效性。

令人惊叹的是，decoder部分的自回归过程很适合模拟图灵机的每一步操作。

如果按照机器翻译任务来理解，这里就是对于任一输入的语言，通过encoder将之编码，再由decoder将至翻译成图灵机的每一步操作。而自回归也恰恰对应这一步步的顺序操作。

于是，我们要做的事就变成了，如何设置网络参数，让他能够成功翻译。这部分技术性很强，就不在此多说了。

下面总结了整体证明框架和思路：

对精度的进一步探索

证明过程中需要用到一个不现实的假定：无限精度。

若考虑精度会怎么样呢？会限制Transformer能识别语言的复杂度。

首先我们记一个语言被TM识别的操作步数，也就是时间复杂度为T(n)。那么图灵机读写头的移动距离也最多为T(n)。

因此我们编码时最多只需要logT(n)比特（好像Tengyu Ma组有文章说只需要loglogT(n)），同时自回归的规模也最多只需要T(n)。

其实咱们也可以从自回归规模考虑这一问题，毕竟现实中除了精度限制也还有算力限制。

btw，文章中用的是hard attention，那是否可以用soft呢？也可以，但softmax不是有理函数，如果考虑soft，肯定就得将精度纳入考虑范围了。

点击进入—>【计算机视觉】微信技术交流群

最新CVPP 2023论文和代码下载

后台回复：CVPR2023，即可下载CVPR 2023论文和代码开源的论文合集

后台回复：Transformer综述，即可下载最新的3篇Transformer综述PDF

多模态和Transformer交流群成立
扫描下方二维码，或者添加微信：CVer333，即可添加CVer小助手微信，便可申请加入CVer-多模态或者Transformer 微信交流群。另外其他垂直方向已涵盖：目标检测、图像分割、目标跟踪、人脸检测&识别、OCR、姿态估计、超分辨率、SLAM、医疗影像、Re-ID、GAN、NAS、深度估计、自动驾驶、强化学习、车道线检测、模型剪枝&压缩、去噪、去雾、去雨、风格迁移、遥感图像、行为识别、视频理解、图像融合、图像检索、论文投稿&交流、PyTorch、TensorFlow和Transformer等。
一定要备注：研究方向+地点+学校/公司+昵称（如多模态或者Transformer+上海+上交+卡卡），根据格式备注，可更快被通过且邀请进群
 
▲扫码或加微信号: CVer333，进交流群
CVer学术交流群（知识星球）来了！想要了解最新最快最好的CV/DL/ML论文速递、优质开源项目、学习教程和实战训练等资料，欢迎扫描下方二维码，加入CVer学术交流群，已汇集数千人！
 
▲扫码进群
▲点击上方卡片，关注CVer公众号

整理不易，请点赞和在看