原文

这一篇会覆盖下面三个版本的 Memory Networks

• Memory Network with strong supervision
• End-to-End Memory Network
• Dynamic Memory Network

涉及下面一些论文：

• Memory Networks (2015)
• End-To-End Memory Networks (2015)
• Ask Me Anything: Dynamic Memory Networks for Natural Language Processing (2016)
• Dynamic Memory Networks for Visual and Textual Question Answering (2016)

首先要明确的是，Memory Networks 只是一种思想或者说一个框架，像一个 base class，里面的各个 module 都可以自己定制。其中基本的一些思路：

• 分层 RNN 的 context RNN
  与 context RNN 类似，Memory Network 同样以句子为单位来提取、保存语境信息
• Attention 原理
  使用多个 state vector 来保存信息，并从中寻找有用的记忆，而不是寄希望于 final state 存储的信息
• Incorporate reasoning with attention over memory(RAM): Memory Network
  使用记忆以及记忆上的 attention 来做推理

Memory Networks (2015)

对应论文：Memory Networks (2015)

Memory Networks 提出的基本动机是我们需要 长期记忆（long-term memory）来保存问答的知识或者聊天的语境信息，而现有的 RNN 在长期记忆中表现并没有那么好。

组件

4 个重要组件：

• I: input feature map
  把输入映射为特征向量（input -> feature representation）
  通常以句子为单位，一个句子对应一个向量
• G: generalization
  使用新的输入数据更新 memories
• O: output
  给定新的输入和现有的 memory state，在特征空间里产生输出
  类比 attention RNN decoder 产生 outputs/logits
• R: response
  将输出转化为自然语言

流程

上面的 4 个 component 就对应了整个工作流程：

1. 把输入 x 映射为特征向量 I(x)
   可以选择多种特征，如 bag of words, RNN encoder states, etc.
   如果用 embedding model 来表达文本的话，一个郁闷的地方是 embdding 的参数在不断变化，所以训练时保存的 vector 也要变化……当然这在测试时就成了优势，因为测试时 embedding 参数就固定啦
2. 更新 memory mi，mi=G(mi,I(x),m),∀i.mi=G(mi,I(x),m),∀i.
   将输入句子的特征 x 保存到下一个合适的地址 mnmn，可以简单的寻找下一个空闲地址，也可以使用新的信息更新之前的记忆
   简单的函数如 mH(x)=I(x)mH(x)=I(x)，H(x) 是一个寻址函数（slot choosing function），G 更新的是 m 的 index，可以直接把新的输入 I(x) 保存到下一个空闲的地址 mnmn，并不更新原有的 memory，当然更复杂的 G 函数可以去更新更早的 memory 甚至是所有的 memory
3. 给定新的输入和 memory，计算 output feature o: o=O(I(x),m)
   Addressing，寻址，给定 query Q，在 memory 里寻找相关的包含答案的记忆
   qUUTmqUUTm： 问题 q 和事实 m 的相关程度，当然这里的 q，m 都是特征向量，可以用同一套参数也可以用不同的参数
   U：bilinear regression 参数，相关事实的 qUUTmtrueqUUTmtrue 分数高于不相关事实的分数 qUUTmrandomqUUTmrandom
   n 条记忆就有 n 条 bilinear regression score
   回答一个问题可能需要寻找多个相关事实，先根据 query 定位到第一条最相关的记忆，再用第一条 fact 和 query 通过加总或拼接等方式得到 u1 然后一起定位第二条
   o1=O1(q,m)=argmaxi=1,…N so(q,mi)o1=O1(q,m)=argmaxi=1,…N so(q,mi)
   o2=O2(q,m)=argmaxi=1,…N so([q,o1],mi)o2=O2(q,m)=argmaxi=1,…N so([q,o1],mi)
4. 对 output feature o 进行解码，得到最后的 response: r=R(o)
   将 output 转化为自然语言的 response
   r=argmaxw∈W sR([q,o1,o2],w)r=argmaxw∈W sR([q,o1,o2],w)
   sR(x,y)=xUUTysR(x,y)=xUUTy
   可以挑选并返回一个单词比如说 playground
   在词汇表上做一个 softmax 然后选最有可能出现的单词做 response，也可以使用 RNNLM 产生一个包含回复信息的句子，不过要求训练数据的答案就是完整的句子，比如说 football is on the playground

Huge Memory 问题

如果 memory 太大怎么办？

1. 可以按 entity 或者 topic 来存储 memory，这样 G 就不用在整个 memories 上操作了
2. 如果 memory 满了，可以引入 forgetting 机制，替换掉没那么有用的 memory，H 函数可以计算每个 memory 的分数，然后重写
3. 还可以对单词进行 hashing，或者对 word embedding 进行聚类，总之是把输入 I(x) 放到一个或多个 bucket 里面，然后只对相同 bucket 里的 memory 计算分数

损失函数

损失函数如下，选定 2 条 supporting fact (k=2)，response 是单词的情况：

(6) 有没有挑选出正确的第一句话
(7) 正确挑选出了第一句话后能不能正确挑出第二句话
(6)+(7) 合起来就是能不能挑选出正确的语境，用来训练 attention 参数
(8) 把正确的 supporting fact 作为输入，能不能挑选出正确的答案，来训练 response 参数

Performance

在 bAbI QA 部分数据集上的结果

部分 QA 实例：

局限

1. 需要很强的标记信息
   bAbI 提供了 supporting fact 的 ID，但对大多数 QA 数据而言，并不存在明确的 supporting fact 标记
2. Loss2 无法 backpropagate 到模型的左边部分，BP 过程到 m 就停了，并不能 end-to-end 进行训练
   这相当于一个链状的贝叶斯网络，考虑 A->B->C 的有向图，B 对应 m，B 不确定的时候，C 依赖于 A，但是当 B 确定的时候，C 就不依赖于 A 了。 也就是说，在给定 m 的情况下，loss2 和前面的参数是独立的，所以优化 loss2 并不能优化左边的参数

End-to-End learning

对应论文：End-To-End Memory Networks (2015)

End-to-End learning 用了 soft attention 来估计每一个 supporting fact 的相关程度，实现了端到端的 BP 过程。

Single Layer

一张图就解决了：

模型输入:

• Input: x1,…,xnx1,…,xn，会被存储到 memory 中
• Query: q
• Answer: a

具体过程（以单层为例）：

1. 映射到特征空间
   {xixi} −→A→A {mimi}
   q−→Buq→Bu
2. 计算 attention，得到 query 和 memory 的匹配度，有多少个 memory 就有多少个 pipi
   pi=Softmax(uTmi)pi=Softmax(uTmi)
3. 得到 context vector
   o=∑ipicio=∑ipici
   和 Memory Networks with Strong Supervision 版本不同，这里的 output 是加权平均而不是一个 argmax
4. context vector 和 query 一起，预测最后答案，通常是一个单词
   a^=Softmax(W(o+u))a^=Softmax(W(o+u))
5. 对 a^a^ 进行解码，得到自然语言的 response
   a^−→Caa^→Ca

其中，
A: intput embedding matrix
C: output embedding matrix
W: answer prediction matrix
B: question embedding matrix

损失函数是交叉熵，用 SGD 训练。

Multi-hop Architecture

多层结构（K hops）也很简单，相当于做多次 addressing/多次 attention，每次 focus 在不同的 memory 上，不过在第 k+1 次 attention 时 query 的表示需要把之前的 context vector 和 query 拼起来，其他过程几乎不变。
uk+1=uk+okuk+1=uk+ok

一些技术细节

通常来说 encoding 和 decoding 的词向量参数是不一样的，因为一个是单词-词向量，一个是 隐状态-词向量。

• Adjacent
  前一层的输出是这一层的输入
  Ak+1=CkAk+1=Ck
  WT=CLWT=CL
  B=A1B=A1
• Layer-wise(RNN-like)
  不同层之间用同样的 embedding
  A1=A2=…=AKA1=A2=…=AK
  C1=C2=…=CKC1=C2=…=CK
  可以在 hop 之间加一层线性变换 H 来更新 μμ
  uk+1=Huk+okuk+1=Huk+ok

Dynamic Memory Networks

对应论文：Ask Me Anything: Dynamic Memory Networks for Natural Language Processing (2016)

Input Module

这一部分像是一个 semantic memory。输入可以是一个/多个句子，一篇/几篇文章，包含语境信息和知识库等，使用 RNN 进行 encoding，每一个句子编码成固定维度的 state vector。
具体做法是把句子拼到一起（每个句子结尾加标记符 EOS），用 GRU-RNN 进行编码，如果是单个句子，就输出每个词的 hidden state；如果是多个句子，就输出每个句子 EOS 标记对应的 hidden state，其实相当于分层 RNN 的下面一层。

 

ht=GRU(L[wt],ht−1)ht=GRU(L[wt],ht−1)

L[wt]L[wt] 是 word embedding。

Question Module

输入是 question 对应的词序列，同样用 GRU-RNN 进行编码。

 

qt=GRU([L[wQt],qt−1)qt=GRU([L[wtQ],qt−1)

同样的，L 是词向量参数，和 input module 的 L 相同。输出是 final hidden state

Episodic Memory Module

由 internal memory, attention mechansim, memory update mechanism 组成。 输入是 input module 和 question module 的输出。

把 input module 中每个句子的表达（fact representation c）放到 episodic memory module 里做推理，使用 attention 原理从 input module 中提取相关信息，同样有 multi-hop architecture。

Attention Mechanism

觉得论文里的 attention mechanism 和 memory update mechanism 描述的有点问题，个人以为 attention mechanism 的目的还是生成 context vector，memory update mechanism 的目的是更新 memory，所以把部分公式按自己的理解移动了下，便于理解。

计算 query 和 fact 的分数，query 和上一个 memory mi−1mi−1 作为输入产生输出 episode eiei。要注意的是，End-to-End MemNN 的 attention 用的是 linear regression，DMN 用的是 gating function，一个两层的前向神经网络。

在每一轮迭代中，都有输入：

1. ctct（input module 中第 t 个位置的 fact vector)
2. 上一轮迭代得到的 memory mi−1mi−1
3. question q

利用 gating function 计算第 t 个位置的得分 git=G(ct,mi−1,q)gti=G(ct,mi−1,q)。G 是一个两层的前向神经网络的 score function，不过描述 input, memory, question 相似度的 feature vector z(c,m,p) 是人工定义的，这也成为了之后 DMN+ 的一个优化点。

计算完每一次迭代每一个位置的分数后，来更新 episode eiei，或者说产生 context vector。输入是 c1,…,cTCc1,…,cTC，和它们的 gate score gitgti。

 

hit=gitGRU(ct,hit−1)+(1−git)hit−1hti=gtiGRU(ct,ht−1i)+(1−gti)ht−1i

 

ei=hiTCei=hTCi

总结一下，这部分 attention mechanism 的目的是生成 episode eiei，eiei 是第 t 轮迭代的所有相关 input 信息的 summary。与 End-to-End MemNN 不同的是，End-to-End 用了 soft attention，也就是加权和来计算 context，而这里用了 GRU。

Memory Update Mechanism

上一步算的 episode eiei 以及上一轮迭代的 memory mi−1mi−1 作为输入 来更新 episodic memory mimi。

 

mi=GRU(ei,mi−1)mi=GRU(ei,mi−1)

输出是最后一次迭代的 m=mTMm=mTM

End-to-End MemNN 的 memory update 过程里，第 k+1 次 query vector 直接是上一个 context vector 和 query 的拼接，uk+1=uk+okuk+1=uk+ok。而 DMN 里，采用了 RNN 做非线性映射，用 episode eiei 和上一个 memory mi−1mi−1 来更新 episodic memory，其 GRU 的初始状态包含了 question 信息，m0=qm0=q。

Episodic Memory Module 需要一个停止迭代的信号。一般可以在输入中加入一个特殊的 end-of-passes 的信号，如果 gate 选中了该特殊信号，就停止迭代。对于没有显性监督的数据集，可以设一个迭代的最大值。

总结一下，这部分 memory update mechanism 的目的是生成 t 时刻的 episode memory mtmt，最后一个 pass 的mTmT将包含用于回答问题 q 的所有信息。

Example Understanding

来用例子解释下 Episodic Memory Module 上面那张图，question 是 where is the football? 第一次迭代找到的是第 7 个句子，John put down the football，第二次找到第 6 个句子 John went to the hallway，第三次找到第 2 个句子 John moved to the bedroom。

多次迭代第一次找到的是字面上最相关的 context，然后一步步迭代会逐渐定位到真正语义相关的 context，这感觉上就是一个推理的过程。

Answer Module

使用了 GRU-RNN 作为 decoder。输入是 question module 的输出 q 和上一时刻的 hidden state at−1at−1，初始状态是episode memory module 的输出 a0=mTMa0=mTM

 

yt=Softmax(W(a)at)at=GRU([yt−1,q],at−1) 

训练

使用 cross-entroy 作为目标函数。如果数据集有 gate 的监督数据，还可以将 gate 的 cross-entroy 加到总的 cost上去，一起训练。训练直接使用 backpropagation 和 gradient descent 就可以。

小结

总的来说，DMN 在 addressing，memory 提取，query/memory update 部分都用了 DL 手段，相比于 End-to-End MemNN 更为复杂。

DMN+

对应论文：Dynamic Memory Networks for Visual and Textual Question Answering (2016)

DMN 存在的两个问题：

1. 输入模块只考虑了过去信息，没考虑到将来信息
2. 只用 word level 的 GRU，很难记忆远距离 supporting sentences 之间的信息

这一部分重点讲与 DMN 不同的地方。

Input Module

DMN+ 把 single GRU 替换成了类似 hierarchical RNN 结构，一个 sentence reader 得到每个句子的 embedding，一个 input infusion layer 把每个句子的 embedding 放入另一个 GRU 中，得到 context 信息，来解决句子远距离依赖的问题。HRED 相关思路见 论文笔记 - HRED 与 VHRED。这里还做了一些微调，sentence reader 用的是 positional encoding，input fusion layer 用了双向 GRU，兼顾了过去和未来的信息。

用 positional encoding 的原因是在这里用 GRU/LSTM 编码句子计算量大而且容易过拟合（毕竟 bAbI 的单词量很小就几十个单词。。），这种方法反而更好。

除了处理文本信息，作者也提出了图像信息的方案，CNN+RNN，把局部位置的图像信息当做 sentence 处理，在这不多介绍。

Episodic Memory Module

Attention Mechanism

仍然是人工构造特征向量来计算 attention，但与之前版本的 DMN 相比更为简化，省去了两项含有参数的部分，减少了计算量。另外与 DMN 不同的是，gate 值不是简单的二层前馈网络的结果，而是接着计算了一个 sofmax 评分向量。

也就是说，从公式上看，相对于 DMN，式 8 更为简洁，式 9 不变（结果就是 DMN 的 gate 值），增加了式 10。

进行到下一步关于 context vector 的计算，两种方案，一种是 soft attention，简单的加权求和，另一种是 attention based GRU。

AttnGRU 考虑了输入 facts 的位置和顺序信息（position and ordering），或者说是时序信息。在得到 attenion 后，把 attention 作为 gate，如上图，把传统 GRU 中的 update gate uiui 替换成了 attention 的输出 gtigit，这样 gate 就包含了 question 和前一个 episode memory 的知识，更好的决定了把多少 state 信息传递给下一个 RNN cell。同时这也大大简化了 DMN 版本的 context 计算。

h^h^ 是更新的 state，hi−1hi−1 是传入的上一时刻的 state，gtigit 是 attention value，是一个由 softmax 产生的标量（scalar）而不是 sigmoid **产生的 vector ui∈RnHui∈RnH，context vector 是 GRU 的 final hidden state。

AttnGRU 要优于 weighted sum，因为使用了一些时间上的关系，比如小明在操场，小明回了家，小明进了卧室，这些事实实际上有先后关系，而 weighted sum 不一定能反映这种时序关系。

Memory Update Mechanism

DMN 中 memory 更新采用以 q 向量为初始隐层状态的 GRU 进行更新，用同一套权重，这里替换成了一层 ReLU 层，实际上简化了模型。

 

mt=ReLU(Wt[mt−1;ct;q]+b)mt=ReLU(Wt[mt−1;ct;q]+b)

其中 ; 表示拼接，这能进一步提高近 0.5% 的准确率。

Performance

最后上一个不同模型的 performance 比较图。