当前位置:   article > 正文

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

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),这样来看,它甚至无法识别正则语言,远远未达到我们的预期。

e12c8959ef24c41e04ac2e28effb844d.jpeg

比例不变性证明

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

如何证明图灵完备性?

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

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

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

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

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

2f711e7c2823498eb0a401577b315b3a.jpeg

证明框架

0f76ebe4f1357242a394efc42e29e008.jpeg

思路细节

对精度的进一步探索

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

若考虑精度会怎么样呢?会限制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

  1. 多模态和Transformer交流群成立
  2. 扫描下方二维码,或者添加微信:CVer333,即可添加CVer小助手微信,便可申请加入CVer-多模态或者Transformer 微信交流群。另外其他垂直方向已涵盖:目标检测、图像分割、目标跟踪、人脸检测&识别、OCR、姿态估计、超分辨率、SLAM、医疗影像、Re-ID、GAN、NAS、深度估计、自动驾驶、强化学习、车道线检测、模型剪枝&压缩、去噪、去雾、去雨、风格迁移、遥感图像、行为识别、视频理解、图像融合、图像检索、论文投稿&交流、PyTorch、TensorFlow和Transformer等。
  3. 一定要备注:研究方向+地点+学校/公司+昵称(如多模态或者Transformer+上海+上交+卡卡),根据格式备注,可更快被通过且邀请进群
  4. ▲扫码或加微信号: CVer333,进交流群
  5. CVer学术交流群(知识星球)来了!想要了解最新最快最好的CV/DL/ML论文速递、优质开源项目、学习教程和实战训练等资料,欢迎扫描下方二维码,加入CVer学术交流群,已汇集数千人!
  6. ▲扫码进群
  7. ▲点击上方卡片,关注CVer公众号
整理不易,请点赞和在看
声明:本文内容由网友自发贡献,不代表【wpsshop博客】立场,版权归原作者所有,本站不承担相应法律责任。如您发现有侵权的内容,请联系我们。转载请注明出处:https://www.wpsshop.cn/w/我家自动化/article/detail/652805
推荐阅读
相关标签
  

闽ICP备14008679号