AlphaGo开发者欲通过深度学习挑战冯·诺依曼体系

想挑战冯·诺依曼，就必须从三个要素入手：基本操作，例如加减乘除；逻辑流程控制，例如if-else-then，for，while；设存储器，内存和硬盘的寻址。DeepMind团队认为，冯·诺依曼体系中的逻辑流程控制和外设存储器使用，都必须在程序中写死，而不能通过观察范例，自动生成程序。

2016年10月27日 “Nature” 期刊第538卷，发表了Google旗下的DeepMind团队写的人工智能的论文，题目是 “Hybrid compuTIng using a neural network with dynamic external memory” [1]，用配置了动态外部存储的神经网络，实现杂交计算。这篇论文介绍了DifferenTIable Neural Computer的实现细节。

DeepMind团队在伦敦工作，2014年被Google收购。DeepMind开发的AlphaGo，2016年年初战胜了围棋高手李世乭。

早在2014年12月，DeepMind团队发表了一篇论文，“Neural Turing Machines” [2]。后来，他们对Neural Turing Machines （NTM）的存储管理方式做了改进，命名为DifferenTIable Neural Computer（DNC）。DifferenTIable是可训练的意思，尤其是可以用gradient descent的算法来训练。

冯·诺依曼体系

当今世界，所有计算机的体系，都源自于冯·诺依曼于1945年设计的体系，冯·诺依曼体系有三大要素：

基本操作，例如加减乘除。

逻辑流程控制，例如if-else-then，for，while。

外设存储器，内存和硬盘的寻址。

想挑战冯·诺依曼，就必须从这三个要素入手。DeepMind团队认为，冯·诺依曼体系中的逻辑流程控制和外设存储器使用，都必须在程序中写死，而不能通过观察范例，自动生成程序。

如果把程序理解为把输入x转换为输出y的函数f()，y = f(x)，那么neural network就是模拟任何函数的通用模型f^()。

但是早期的neural network有两个软肋：

不能实现variable binding，也就是说，f() 的内部参数，不能随着输入x的不同而改变。

不能实现variable-length structure，也就是说，输入x和输出y的维度都是定长的，不能改变。

早期neural network的这两个软肋，都不难修补。譬如循环神经网络Recurrent Neural Network（RNN），就解决了这两个问题。换而言之，RNN是Turing-complete的，可以用来模拟任何函数，当然也可以模拟任何程序的功能。

既然冯·诺依曼体系的三大要素中的两个，基本操作和逻辑流程控制，都能够被RNN模拟，假如RNN也能够解决存储管理的问题，那么整个冯·诺依曼体系，就都能够被RNN来实现了。所以 Differentiable Neural Computer （DNC）的工作重点，在于存储管理。

[3] 深入浅出地解释了用RNN来管理存储的原理。建议先读 [3]，再读 [2]，最后读 [1]。需要特别注意的，个人体会有几个方面，1. 存储的设置，2. 寻址机制，3. 需要训练哪些参数，4. 如何把DNC应用到Graph操作中。

存储的设置

[3] 把NTM/DNC的存储设置解释为the memory is an array of vectors，也就是一个矩阵，每一行就是一个vector，每行的vector的长度一致，所有行集结起来就是array。在文中的例子中，[3] 把memory简化为an array of scalar, 也就是N行单列的矩阵，每一行只存储一个数值。

什么时候需要存储向量呢？如果存储里存放的是图像，那么每个存储单元上存储的是一个像素（r,g,b），像素就是一个向量，三个bytes组成的向量。

但是如果需要存储的是一篇文章，每个存储单元上需要存储一个词，而每个词的长度不同，怎么办？三篇文章都没有说，但是简单的办法有二。

每个存储单元上，预留足够长的vector，遇到很短的词，空着的byte就全部填0。

把每个词，无论长短，都转换为词向量，词向量的长度定长。第二个办法就是其它论文中说的encoding的办法。

另外要注意的是，存储矩阵的行数可能很多。想象一下，把一部长篇小说存放到存储矩阵里，每个词都占用一行，需要占用存储矩阵的多少行。

寻址机制

DNC改进了NTM的寻址机制。NTM的寻址机制是content-based和location-based的混搭。为什么需要改进呢？原因有三。

NTM不能保障多个存储单元之间，不相互重叠，不相互干扰。dynamic memory allocation: allocate a free space

NTM不能释放存储单元，如果处理很长的序列时，譬如处理一部超长的长篇小说，搞不好所有存储都会被占满，导致系统崩溃。dynamic memory allocation: free gates

如果连续做几个读写操作，它们所使用的存储单元的位置，最好是相邻的。但是在NTM中，一旦某个读写操作，远远跳到其它存储区域，那么后续操作也跟着去其它区域，而且失忆，想不起来原先的存储区域在哪里。temporal link matrix

DNC的寻址机制，把读操作和写操作分开。DNC用content-based和dynamic memory allocation的混搭方式，处理写操作。用content-based和temporal memory linkage的混搭方式，处理读操作。

1. content-based寻址：

比较需要处理的目标vector，与存储矩阵中每一行的vector，用余弦距离来计算两者相似性。取存储矩阵中，与目标vector距离最短的行。

计算余弦距离时，需要一个系数向量，beta，这个系数向量是被训练出来的。

2. dynamic memory allocation存储单元分配：

每一个存储单元，都是等长的vector。当每一个存储单元被free的时候，整个vector中的每一个element，都可以用来写入新数据。但是当一个vector中有若干elements已经被占用时，剩下的elements还可以被写入新数据。

想象一下，如果每个vector的长度是100，又如果某个vector里，已经写入了一个不长的词，但是还有剩余的elements，这些剩余的elements可以用于给这个词做词性标注等等。但是如果剩余的elements不多，那么词性标注只好被写到其它行的vector里。

DNC设计了一个存储单元占用向量u。u(i) = 0时第i行的vector中，所有element都可以被写入新数据，而当u(i) = 1时第i行的vector中所有elements都已经被占用了。

但是如果存储矩阵中有两行，i和j，分别有完全相同的elements可以被写。谁先被写，取决于权重向量wt。wt体现了存储使用的策略，策略既可以是尽可能写入最新释放的存储单元，也可以尽可能写入内容相似，而且没有被完全占用的存储单元。这个权重向量wt，是可以根据被训练出来的。

3. Temporal memory linkage读写时序的关联：

Dynamic memory allocation没有记录历次写操作时，loc(t) 发生在哪个存储单元，以及loc(t+1) 发生在哪个存储单元。而记录历次写操作的存储单元的位置顺序，是有用的。

DNC用N^2的方阵，来记录temporal link，其中L(i, j) 记录着t时写操作发生在存储单元j，而t+1时写操作发生在存储单元i的概率。L(i, j) 可以是简单的统计结果，也可以是加权的统计结果，权重体现了控制策略。权重是可以被训练出来的。

当N很大的时，理论上来说L方阵会占用很多空间。但是鉴于L方阵很稀疏，很多L(i, j) 等于0。根据DeepMind团队的估算，L实际占用空间只有O( N )，计算成本只有O( N * Log N )。

需要训练哪些参数?

除了读写操作、以及寻址操作中的几个权重向量以外，还有作为controller的RNN的参数。RNN可以选择结构比较简单的neuralnet work，也可以选择结构更复杂的LSTM。选用LSTM意味着有更多参数，需要被训练。

训练数据通常不包含读写操作发生在哪个存储空间上的信息。譬如NTM中，Priority Sort实验的训练数据，是一连串（输入，理想输出）pairs。每个pair中的输入，是20个向量，每个向量伴随着priority打分。每个pair中的理想输出，是从输入的20个向量中，挑选出来的16个，并且按priority得分排序。

注意，训练数据中不包含读写操作在哪些存储单元上进行的信息。

把DNC应用到Graph操作中

文中把DNC用于在伦敦地铁中，寻找两站之间最佳路线。坐地铁本身不重要，重要的是如果RNN学会使用Graph以后，能做什么？假如Graph不是地铁，而是social graph呢？又假如是knowledge graph呢？

参考文献：

[1] Graves, Alex, et al. "Hybrid computing using a neural network with dynamic external memory." Nature 538.7626 (2016): 471-476.

[2] Graves, Alex, Greg Wayne, and Ivo Danihelka. "Neural turing machines." arXiv preprint arXiv:1410.5401 (2014).

[3] Chris Olah & Shan Carter, “Attention and Augmented Recurrent Neural Networks”, Distill, 2016.