深度学习挑战冯·诺依曼结构

【新智元导读】想挑战冯·诺依曼，就必须从三个要素入手：基本操作，例如加减乘除；逻辑流程控制，例如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 年设计的体系，冯·诺依曼体系有三大要素：

1. 基本操作，例如加减乘除。
2. 逻辑流程控制，例如if-else-then，for，while。
3. 外设存储器，内存和硬盘的寻址。

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

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

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

1. 不能实现 variable binding，也就是说，f() 的内部参数，不能随着输入 x 的不同而改变。
2. 不能实现 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 组成的向量。

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

1. 每个存储单元上，预留足够长的 vector，遇到很短的词，空着的 byte 就全部填 0。
2. 把每个词，无论长短，都转换为词向量，词向量的长度定长。第二个办法就是其它论文中说的 encoding 的办法。

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

寻址机制

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

1. NTM 不能保障多个存储单元之间，不相互重叠，不相互干扰。dynamic memory allocation: allocate a free space
2. NTM 不能释放存储单元，如果处理很长的序列时，譬如处理一部超长的长篇小说，搞不好所有存储都会被占满，导致系统崩溃。dynamic memory allocation: free gates
3. 如果连续做几个读写操作，它们所使用的存储单元的位置，最好是相邻的。但是在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.