神经网络图灵机的通俗解释和详细过程及应用？
转载：https://www.zhihu.com/question/42029751/answer/109995246
神经网络图灵机的通俗解释和详细过程及应用？
神经图灵机的本质是一个使用外部存储矩阵进行attentive interaction机制的RNN，由于定义的RNN各个部分都是可导的，使得输入训练数据通过机器学习（bp加gd）训练“程序”成为了可能。
论文原文：https://arxiv.org/abs/1410.5401
“”””””””””””””””””””””””””
首先简要说说背景。
图灵机
图灵机作为数学模型的定义如下：
给定无限长纸带，读写头和一个存储状态、动作的集合且设为有穷集合，函数，三元组(d,p,s)构成一个图灵机，称D为M的论域DOM(M)，函数d为M的“印-抹”函数，p为M的位置函数，s为M的状态函数。
直白地说图灵机程序的功效叫“建立一个输入纸带到输出纸带的映射”。而神经图灵机就是使用神经网络的方法来“建立从输入纸带到输出纸带的映射”代替了人工编写的自动机（程序）。
在神经网络的模型提出伊始就陆续出现了论证各种神经网络模型的图灵完备性（计算能力等效图灵机）的论文：
Siegelmann, H. T. and Sontag, E. D. (1995). On the computational powerof neural nets.
Graves在论文中说明了为什么用RNN：1:因为目标纸带的映射长度是训练前不确定的，而RNN作为时序模型可以更好地模拟纸带序列的处理；2:图灵机的自动机程序通过当前输入和机器状态决定动作，这和RNN使用输入加隐层状态决定当前状态有共性，而且RNN隐层状态完全可以模拟自动机状态。
图灵完备性的论证提供了神经网络用于实现图灵机的理论合理性：因此传统图灵机输入纸带-->自动机-->输出纸带 就李菊福地变成了 输入纸带-->神经网络-->输出纸带
RNN Attention model
这里的RNN是recurrent neural network。RNN作为一个时序模型，传统应用上就相当于对时序上的输入进行编码，最后得到输出时刻的定长的特诊向量。但是经典的RNN模型如此做法最大的缺陷就是在处理长序列输入时面临长距离记忆问题。打个比方：高考听力考试，要你靠蛮力记忆和听力来处理一个句子，对于你的脑子而言就是越近时刻的内容你越有可能记住，这对RNN也是一样，RNN的编码过程对于较远时刻的编码内容越容易被较近时刻的内容覆盖掉。还有就是RNN训练中的梯度弥散和梯度爆炸，这里不赘述。
为了处理长距离依赖各路大师也提出了相应的单元模型来克服：比如著名的LSTM单元，就是建立了forget机制来建立对于旧时刻输入和新时刻输入的权衡机制：但是这种模型的本质依然是“根据训练目标，调整出记忆的重点和整串编码”，对于长距离记忆的处理能力依然有较大局限。
在这个背景下，就有了在RNN网络内记忆的基础上增强记忆的想法：好记忆不如烂笔头，加一个额外的数据来表示记忆的重点：“记下”哪些对于“整个序列对生成指定目标”是重要的。下面用NLP方面的应用来解读。
Neural machine translation by jointlylearning to align and translate
这里的weighted combination作者提出了一个“对齐模型”来描述：即位置j的输入和目标输出位置i的匹配程度作为权重（这种类似softmax的表示其实是一个soft alignment，而不像传统SMT由latent variable定义的对齐，保证bp传播）。最后得到的加权组合被作者叫做context vector。
神经图灵机
上面说过了RNN attention model，然后这里详细介绍NTM的构成及其流程。
组成是一个表示memory的矩阵，读写头，及RNN作为控制器，上图是Grave提出的架构。另外提一下，NTM的具体细节Grave的论文中只有读写头和memory的交互，至于RNN controller的部分是没有提及的。controller部分的内容是Grave的另一篇论文提及的：
Generating Sequences With Recurrent Neural Network此文的内容是RNN如何用于产生手写内容，用到了一个mixture density output，意思是RNN输出的output作为模型参数使用（这里是RNN controller的输出作为读写头的w，erase，add向量）所以读写头（是一体的，可以有多个读写头，但是必须有固定的读写先后顺序）本质上是个单层的神经网络，将RNN的输出处理成对应的三个向量。
http://arxiv.org/abs/1308.0850
1：初始化内存矩阵，读写头向量。得到前时刻读取内容r_t-1
2：此时刻的输入内容input_t，r_t-1通过输入门得到RNN的输入。
3：运行得RNN的输出y。y通过输出门（或另一层神经网络）得到输出output_t，同时y作为mixture density output，更新读写头向量。使用读写头向量更新内存矩阵。
4：重复以上步骤到最终时刻输出。
使用读写头更新内存矩阵的过程，可以具体参考Grave的论文：概括为读写头查找内存中和当前状态相近的内存向量，设置类似于LSTM的forget的erase向量和add向量对指定的内容进行修改。而这个过程本质就是加了一个外部的attention model。
其中值得一提的是，NTM的交互权重有一个sharpen的过程，就是一个可训练的softmax（想象一下softmax的形式改成alpha的n次方，其中次数n是一个NN的输出），这么做是因为NTM的读写同步训练较难，特别是由于权重如果太分散会导致memory大范围改写，导致系统的不稳定。
添加了外部的attention机制的好处在于此时的网络对于长度的泛化能力得到了质的提升。传统神经网络的问题在于训练数据和实际数据的序列长度有针对性，即在特定长度下训练的网络应用于相近序列长度的任务上还有较好的表现，但这个问题神经图灵机找到了解决，Grave给出的性能对比就能看出很大的差距：对象是NTM和LSTM进行的copy任务（输入序列等于输出序列的任务），训练序列长度为20，NTM可以将其泛化到序列长120的任务中依然保持很好的准确率，但是传统LSTM超出训练长度的部分表现就显得非常糟糕了。
实验序列长度分别为10，20，30，50，120。每个序列位为一个8位的二进制数
NTM的实验结果：
LSTM的实验结果：
NLP上已经有了相关的应用，比如华为诺亚方舟提出的deep memory model：
http://lanl.arxiv.org/abs/1506.06442
大意是多层的multi-scale NTM encoder模型。但是由于NTM的训练难度，让这种多层模型很难训练得能捕获足够的feature.
不过比较有效的并不是直接套用NTM的框架，而是套用了NTM添加外存的思路：
两个论文的BLEU提升都有3点以上！这在传统深度学习普遍只有1点左右的提升上已经可以说是非常惊艳的了。