Memory Networks经典论文阅读笔记，会包括Vanilla Memory Networks及其各种变形以及在NLP领域的应用。主要涉及一下论文：

• Memory Networks (Facebook AI Research/2015)
• End-To-End Memory Networks(2015)
• Key-Value Memory Networks for Directly Reading Documents（2016）
• Ask Me Anything: Dynamic Memory Networks for Natural Language Processing (2016)
• Dynamic Memory Networks for Visual and Textual Question Answering (2016)

1、Memory Networks

Memory Networks提出的最大卖点就是具备长期记忆（long-term memory），虽然当时RNN在文本处理领域十分有效，但是其对信息的长期记忆能力并不理想。Memory Networks的长期记忆思路其实也非常简单暴力，直接采用额外的记忆模块来保存之前的信息，而不是通过cell之间的hidden state传递。

框架

Memory Networks主要由一个记忆模块 \(m\) 和四个组件 \(I, G, O, R\) 构成

I: (input feature map)

用于将输入转化为网络里内在向量表示。（可以利用标准预处理，例如，文本输入的解析，共参考和实体解析。 还可以将输入编码为内部特征表示，例如，从文本转换为稀疏或密集特征向量）

G: (generalization)

用于更新记忆。简单的可以直接插入记忆数组中，复杂的可以将当前的记忆用于更新先前的记忆

O: (output feature map)

从记忆里结合输入，把合适的记忆抽取出来，返回一个向量。每次获得一个向量，代表了一次推理过程。

R: (response)

将上述向量转化回所需的格式，比如文字或者answer。

流程

考虑问答任务，Memory network的工作流程为：

1. 给定一段输入x，通过组件I将x映射到向量空间

2. 通过组件G更新记忆。论文中只是简单地将输入的向量插入到记忆槽中去。\(m_{i}=G\left(m_{i}, I(x), m\right), \forall i\)

3. 利用组件O计算output feature。\(\mathrm{o}=\mathrm{O}(\mathrm{I}(\mathrm{x}), \mathrm{m})\)计算所求问题与记忆槽中的元素的相似度，可以返回一条或多条最相似的记忆

   \[o_{1}=O_{1}(x, \mathbf{m})=\underset{i=1, \ldots, N}{\arg \max } s_{O}\left(x, \mathbf{m}_{i}\right)\\
   o_{2}=O_{2}(x, \mathbf{m})=\underset{i=1, \ldots, N}{\arg \max } s_{O}\left(\left[x, \mathbf{m}_{o_{1}}\right], \mathbf{m}_{i}\right)
   \]

4. 对output feature进行解码，返回输出。

   \[r=\operatorname{argmax}_{w \in W} s_{R}\left(\left[q, o_{1}, o_{2}\right], w\right)
   \\s_{R}(x, y)=x U U^{T}y
   \]

损失函数

采用margin ranking loss，这个与支持向量机的损失函数类似。

QA 问题

作者试图解决的 QA 问题是针对一段给出的文本，回答关于文本的问题，如下图所示。

因此在本例中，I 阶段输入的输入序列是句子序列 \(x_i\)，本文并没有对输入处理成中间表示形式，而是直接将原始文本存储在内存中。对 O 阶段和 R 阶段，本文采用了相同的打分函数。在 O 阶段，通过比较 memory 和 query 的 embedding 相似度，输出一个 memory （输入文本中的一个句子）；在 R 阶段，将 O 阶段的输出（句子） embedding 与词典中的 word embedding 进行相似度比较，选取最相似的词作为 R 阶段输出（ QA 的结果）。

基础的打分函数定义如下：

其中 \(\mathrm{x}\) 和 \(\mathrm{y}\) 分别指 query 和 memory 句子， \(\phi\) 函数将句子转化成 \(\mathrm{BOW}\) 向量，U 指 embedding 矩阵。

一些扩展

使用word-level的输入

如果输入不是句子级别的而是词语级别的，我们需要另外增加一个分词组件。

该分词函数是可以在训练过程中学习得到的

Huge Memory处理

如果需要处理的memory太大：

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

处理未登录词

使用语言模型，通过上下文词语来预测未登录词位置的词，然后就可以认为未登陆词与预测出的词的意思相近

小结

记忆网络是一个组件形式的模型，每个模型相互对立又相互影响。每个组件没有固定的模型，可以是传统的模型，也可以是神经网络

Loss2 无法 backpropagate 到模型的左边部分，BP 过程到 m 就停了，并不能 end-to-end 进行训练

2、End-To-End Memory Networks

上一节提到原始记忆网络受限于反向传播不能实现端到端的训练，因此在本文中改进提出了一种端到端的记忆网络。其主要思想跟attention mechanism很像。论文中提出了单层和多层两种架构，多层其实就是将单层网络进行stack。我们先来看一下单层模型的架构

模型主要的参数包括A,B,C,W四个矩阵，其中A,B,C三个矩阵就是embedding矩阵，主要是将输入文本和Question编码成词向量，W是最终的输出矩阵。从上图可以看出，对于输入的句子s分别会使用A和C进行编码得到memory和Output的记忆模块，memory用来跟Question编码得到的向量相乘得到每句话跟q的相关性，Output则与该相关性进行加权求和得到输出向量。然后再加上q并传入最终的输出层。

Single Layer

上图左边是a模型的单层结构，输入Sentence \(\left\{x_{i}\right\}\)，Question \(q\)，Answer \(a\)，计算过程：

输入模块

首先是输入模块（对应于Memory Networks那篇论文的I和G两个组件），这部分的主要作用是将输入的文本转化成向量并保存在memory中，本文中的方法是将每句话压缩成一个向量对应到memory中的一个slot（上图中的蓝色或者黄色竖条）。其实就是根据一句话中各单词的词向量得到句向量。论文中提出了两种编码方式，BoW和位置编码。BoW就是直接将一个句子中所有单词的词向量求和表示成一个向量的形式，这种方法的缺点就是将丢失一句话中的词序关系，进而丢失语义信息；而位置编码的方法，不同位置的单词的权重是不一样的，然后对各个单词的词向量按照不同位置权重进行加权求和得到句子表示。位置编码公式如下：lj就是位置信息向量。

此外，为了编码时序信息，比如Sam is in the bedroom after he is in the kitchen。我们需要在上面得到\(m_i\)的基础上再加上个矩阵对应每句话出现的顺序，不过这里是按反序进行索引。将该时序信息编码在\(T_A\)和\(T_C\)两个矩阵里面，所以最终每句话对应的记忆mi的表达式如下所示：

算法流程

1. 映射到向量空间:

1. 计算attention distribution

1. 计算context vector

1. 预测答案

1. 计算损失以及更新参数直到收敛

口述一下流程，即输入的序列 \(\{x\}\) 被转化成两个 embedding，一个是 memory embedding \(m_{i},\) 用于存入内存并和 query 进行相似度比较; 一个是 output embedding \(c_{i},\) 用 于生成输出的 output vector \(o\)。模型首先计算 query embedding \(u\) 与所有 memory 的相似 度, 然后使用 softmax 计算在整个 memory 上的概率分布，最后对 \(c_{i}\) 加权求和得到 \(o\)， 将 o 与\(\mathbf{u}\) 加和后在词典上做线性映射，可得到最后的结果。 上述的单层结构并没有实现如上文所述的迭代计算所能实现的多跳推理，在本文中，作者使用多层上述结构来实现多跳推理。

Multiple Layer

上图右边是b模型是多层结构。理解了上述单层框架之后，多层结构也很简单，相当于做多次attention操作，不过注意上层的query向量是由下层的输出向量 \(o\) 和query向量\(u\)得到的（可以简单地拼接，求和，也可以用MLP、RNN）。

对比之前的 memory networks 使用的迭代计算，每一轮都将上一轮产生的 o 与 query 一起与其他 memory 计算打分函数。其本质是一样的。

网络参数设置细节

对于多层网络参数设置问题，文章中提出两种思路：

Adjacent： 这种方法让相邻层之间的A=C。也就是说\(A^{k+1}=C^k\)，此外W等于顶层的C，B等于底层的A，这样就减少了一半的参数量。

Layer-wise（RNN-like)​： 与RNN相似，采用完全共享参数的方法，即各层之间参数均相等。Ak=…=A2=A1,Ck=…=C2=C1。由于这样会大大的减少参数量导致模型效果变差，所以提出一种改进方法，即令\(u^{k+1}=Hu^k+o^k\)，也就是在每一层之间加一个线性映射矩阵H。

QA 问题

下图是本文所述的 memory networks 在 QA 任务上的结果示例：

在本文中，hop 即指多层 memory networks 的层。左下角的例子形象的展示了 memory networks 通过叠加层实现的多跳推理过程。

此外，文章还介绍了将 memory networks 用作 language model 的方法。将输入的句子序列改为单词序列\(w_i\)，由于 language model 不需要 query ，因此在将 memory network 用作 language model 时只需固定 query 为一个常数，最终的输出也不再是 answer 而是单词序列的下一个单词的预测值。

3 Key-Value Memory Networks

本篇文章提出了一个全新的数据集movieQA，同时提供了基于知识库和wiki文章还有IE数据库三种先验知识支撑，以便大家对不同知识源的效果进行比较。首先比较一下基于知识库KB和wiki文章的问答系统的区别和各自的优缺点：

• 基于KB的QA，优点是KB具有高度的结构化组织并且有人工构建，所以便于机器处理。缺点是知识的覆盖面不全，会有遗漏和缺失，也就是有些问题在KB中本身就找不到答案，也就是其稀疏性，此外三元组中的实体可能会有变种表示，但KB中也为包含等各种问题。
• 基于wiki 文章的QA，优点是覆盖面广，基本上所有的问题都能从中找到答案。缺点是非结构化、不直接、有歧义、可能需要多个文档经过复杂的推理才能找出答案等，也就是直接从文档中检索出问题的答案是一个很困难的问题。

基于这些，作者提出了一个新的数据集MovieQA，因为他觉得要想弥补wiki文章和KB系统之间的差距，应该先从一个简单领域（电影）开始，如果二者的gap被填上之后在推广到开放域即可。本数据集包含十万+的QA对覆盖了电影领域的，而且同时可以以KB、wiki文章、IE三种知识源为背景进行问答。接下来我们看一下论文提出的Key-Value MemNN模型，其结构如下图所示：

从上图可以看出来key embedding和value embedding两个模块跟end-to-end模型里面input memory和Output memory两个模块是相同的，不过这里记忆是使用key和value进行表示，而且每个hop之间有R矩阵对输入进行线性映射的操作。此外，求每个问题会进行一个key hashing的预处理操作，从knowledge source里面选择出与之相关的记忆，然后在进行模型的训练。在这里，所有的记忆都被存储在Key-Value memory中，key负责寻址lookup，也就是对memory与Question的相关程度进行评分，而value则负责reading，也就是对记忆的值进行加权求和得到输出。二者各自负责自己的功能，相互配合，使得QA过程的记忆和推理各司其职。接下来从细节的角度上描述一下模型：

key hashing：首先根据输入的问题从知识源中检索（知识图谱，*等）出与问题相关的facts，并且要求选中的key中至少有一个词和问题中的相同（利用倒排索引的方法检索）。也就是上图中下面的绿色部分，相当于一个记忆的子集。这部分工作可以在与处理数据的时候进行。然后将其作为模型输入的一部分训练的时候输入模型即可。

key addressing：寻址，也就是对memory进行相关性评分。用key memory与输入的Question相乘之后做softmax得到一个概率分布。概率大小就表明了相关程度。Qx与Qk都是embedding模型，对输入问题和key进行编码得到其向量表示。

Value Reading：有了相关性评分，接下来就对value memory进行加权求和即可，得到一个输出向量。

这样就完成了一个hop的操作，接下来将输出向量o与输入问题的向量表示q相加，经过Ri矩阵进行映射，在作为下一层的输入，重复循环这个过程即可。每一层都会离答案更进一步，这里可以类比CNN模型进行理解，CNN处理图片时，第一层可以得到一些边缘特征，第二层得到车轮、车门等特征，最后一层得到车，同样，这里第一层可能得到与问题相关的一些答案，第二层得到具体的答案。最后，我们在使用一个答案的预测层即可。

yi可以理解为所有的KB中的实体或者候选的答案句子（使用wiki文章时）。并且使用交叉熵作为损失函数即可，然后就可以端到端的对模型进行反向传播训练。整个过程看下来其实跟end-to-end模型很相似，那么最关键的地方加在于Key-Value的memory如何进行表示，这也是本模型的创新所在，接下来我们就看一下： Key-Value memory的好处在于可以方便的对先验知识进行编码，这样就可以让每个领域的人都方便的将本领域内的一些背景知识编码进记忆中，从而训练自己的QA系统，相比于end-to-end模型将相同的输入经过不同的矩阵分别编码到Input memory和Output memory，Key-Value则选择对输入首先进行一个（key， value）形式的表示，然后再分别编码进入key和value两个memory模块，这样就有了更多的变化和灵活性。我们可以按照自己的理解对数据进行key索引和value记忆，而不需要完全依赖于模型的embedding矩阵，这样也可以使模型更方便的找到相关的记亿并产生与答案最相近的输出。然后论文根据不同形式的输入（KB或者wiki文章），提出了几种不同的编码方式：

1. KB Triple：由于知识库是以三元组的形式构成，所以很方便的就可以表示为（key， value）的形式。这里首先将KB进行double，也就是将主谓宾反过来变成宾谓主，这样使得有些问题可以很方便的被回答。然后将每个三元组的主+谓作为key，宾作为value即可（可以想象，一般的问题都是主语干了什么事之类的，所以主+谓作为key可以更好的跟Question进行匹配，而宾语往往是答案，那么根据key找到相应的答案也就与想要的结果更相似，所以这样的组合很完美==）
2. Sentence Level：以句子为单位进行存储的时候，与end-to-end模型一样，都直接将句子的BOW表示存入memory即可，也就是key和value一样。每个memory slot存储一个句子。
3. Window Level：以窗口长度W对原始wiki文章进行切分（只取以实体作为窗口中心的样本），然后将整个窗口的BoW表示作为key，该实体作为value。因为整个窗口的模式与问题模式更像，所以用它来对问题相关性评分可以找到最相关的memory，而答案往往就是实体，所以将窗口中心的实体作为value对生成答案更方便。
4. Window + Center Encoding：将字典double，使用第二个字典对窗口中心进行编码，这样能更精确的找到中心词。也会跟答案最相关。
5. Window + Title：仍然使用窗口的BoW表示作为key，但是使用wiki文章的标题title作为value，因为对于电影信息而言，文章标题往往就意味这电影名称，所以更贴近问题的答案。这里还会同时保持Center Encoding的方式同时作为value进行训练。

4 Dynamic Memory Networks

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

本文提出的DMN网络模型包含输入、问题、情景记忆、回答四个模块，架构图如下所示。模型首先会计算输入和问题的向量表示，然后根据问题触发Attention机制，使用门控的方法选择出跟问题相关的输入。然后情景记忆模块会结合相关的输入和问题进行迭代生成记忆，并且生成一个答案的向量表示。最只答案模块结合该向量以及问题向量，生成最终的答案。从整个框架上看跟MemNN十分相似，也是四大模块，而且各模块的功能都很像。

接下来我们看一个各个模块的细节是如何实现的，这也是其区别与MemNN的地方。首先结合实例和细节模型图了解一下模型的原理：

如上图所示，假设我们的输入就是Input模块中的8句话，问题是“Where is the football？”首先，模型会将相应的输入都编码成向量表示（使用GRU），如图中的S1~S8和问题向量q。接下来q会触发Attention机制，对输入的向量进行评分计算，如上图中在计算第一层的memory时，只选择了S7（因为问题是足球在哪，而S7是jhon放下了足球，与问题最为相关）。然后q作为第一层GRU的初始隐层状态进行迭代计算得到第一层的记忆m1；之后因为第一层选择出了john这个关键词，所以在第二层memory计算时，q会选择出S2和S6（其中S2属于干扰信息，权重较小），同样结合m1进行迭代计算得到第二层的记忆m2，然后将其作为输出向量传递给Answer模块，最终生成最后的答案hallway。这就是整个模型直观的解释，然后我们在对每个模块一一介绍。

Input Module

使用GRU对输入进行编码

当输入不通时应该如何区别对待。

• 输入是一个句子时，直接输入GRU，步长就是句子的长度。最终也会输出句长个向量表示(隐层状态),对应S1~S8,这是Attention机制用来选与Question最相关的单词；
• 输入是一堆句子时，将句子连接成一个长的单词序列，然后每个句子之间使用end-of-sentence的特殊标志进行分割，然后将每个end-of-sentence处的隐层状态输出即可，这时Attention机制选择的就是与Question相关的句子表示；

Question Module

这部分与Input Module一样，就是使用GRU将Question编码成向量。

不同的是，最后只输出最后的隐层向量即可，而不需要像Input模块那样（输入是句子时，会输出句长个向量）。而且，q向量除了用于Attention外，还会作为Memory模块GRU的初始隐层状态.

Episodic Memory Module

本模块主要包含Attention机制、Memory更新机制两部分组成，每次迭代都会通过Attention机制对输入向量进行权重计算，然后生成新的记忆。

Attention mechanism

首先看一下Attention机制，这里使用一个门控函数作为Attention。输入是本时刻的输入c，前一时刻的记忆m和问题q。首先计算相互之间的相似度作为特征向量传入一个两层的神经网络，最终计算出来的值就是门控函数的值\(G\)，也就是该输入与问题之间的相似度。

其中G是一个两层dense网络

相互之间的相似度

Memory Update Mechanism：记忆更新

计算出门控函数的值之后，根据其大小对记忆进行更新。更新方法就是GRU算出的记忆乘以门控值，再加上原始记忆乘以1-门控值。

Answer Module

使用GRU最为本模块的模型，根据memory模块最后的输出向量（将其作为初始隐层状态），然后输入使用的是问题和上一时刻的输出值连接起来（每个时刻都是用q向量）。并使用交叉熵损失函数作为loss进行反向传播训练。

模型扩展

以上就是DMN的模型架构及细节介绍，可以看得出来，其每个模块都使用GRU作为编码/记忆的基础模型，而且模型性能很依赖于Attention机制的效果。所以可以从以上两个方面对DMN进行改进，接下来我们就参考两篇论文来说一下他们对DMN作出的改进：

5 DMTN

这是论文“Ask Me Even More: Dynamic Memory Tensor Networks (Extended Model)”所提出的改进模型，DMN在用于bAbI数据集时，和MemNN一样，需要对答案所依赖的事实进行监督训练。而本文所提出的模型由于改进了Attention机制，所以可以自己学习到这个点。本文提出的模型叫做Dynamic Memory Tensor Network（DMTN），主要的改进点就是DMN的Attention机制，其他地方未做改动。

原始的Attention机制，首先根据c，m，q三个向量构造一个相似度的特征向量，然后通过一个二层神经网络计算门控值g（见上图）。而DMTN中，作者认为上面那种人工构造特征向量计算相似度的方法存在某种局限，所以推广到让模型自己学习参数构造该特征向量，最后仍适用一个二层神经网络计算门控值g。如下图所示，其实就是将原来的内积、|~|距离替换成使用矩阵参数学习两个向量之间的相似度而已

然后作者有尝试了另外一种方案，令z=（c,m,q），然后使用下面的公式直接进行计算，而不再使用上面的几个变量连接的方法，这样可以减少参数量的同时保持比较高的准确度：

6 DMN+

这是论文“Dynamic Memory Networks for Visual and Textual Question Answering”提出的改进模型。上面的DMTN改动较小，仅仅是对特征向量表示方法的一些尝试。而本篇论文所提出的改进就相对较多，而且还把模型运用到了visual QA的任务上面并取得了较好地成果。其改进点主要集中在对Input module、Attention机制和Memory更新三个地方，是结合了End-to-End MemNN和DMN两个模型的优点作出的改进，可以说是比较完善的解决方案，下面我们看一下改进的点：

1，Input Module的改进：考虑到DMN的强监督性，作者认为是由两点导致的，一是输入模块采用单向GRU，所以只能记住前向的上下文，而无法get到后向上下文的相关信息。二是答案的依据可能距离问题较远，单词水平的GRU无法记忆这么远的信息。所以模型无法自己学习到所以来的句子，而要靠监督学习辅助。因此本文提出了Input Fusion Layer来解决这个问题。

该模型分为两部分，首先将句子采用positional Encoding的方法编码成一个向量（这部分可以参考End-to-End那篇论文，其实就是对句子中每个单词进行位置编码，然后加权求和。这部分主要是解决上面第二个问题，也就是从句子层面编码，然后再输入GRU，以减小文体之间的距离。而且，根据要解决的任务，问题总是于某个句子相关，所以从句子层面进行建模更合理），这部分就是论文所说的sentence reader。这里作者说也尝试了使用GRU或者LSTM进行句子编码，然后回过拟合，而且计算量较大。所以直接使用这种位置编码的方法效果反而会更好。

接下来将所有句子表示输入一个双向GRU模型进行学习，得到其表示，也就是Input Fusion Layer。这部分主要是让句子之间进行信息的交互，学习到前后上下文的信息并进行编码。从而解决上面提出的第一个问题。

2，Attention机制的改进：这部分与DMN思想一样，但是细看会发现有一定区别。这里把一开始简单的门控值作为Attention的方法替换成了使用GRU来产生一个中间输出c。而这个c就相当于End-to-End模型中的softmax的评分向量。

首先同样是使用特征向量来构造门控值，但是这里作者有省去了两项含有参数的部分，一方面是为了减少计算量，另一方面作者认为并不需要这些项，简直与上面那篇论文完全相反的思路，这里在特征向量的构造上做了尽可能的简化。

有了门控值之后就是计算Attention。这里作者提出两种方案，一是soft Attention，也就是直接加权求和，这样做好处是简单，而且在可微的情况下仅选择出一个与答案相关的依赖项。缺点是丢失了位置和顺序关系的信息==BOW就这个缺点。另外一种是Attention based GRU。其实我感觉这里就是DMN的Memory更新部分所采用的模型，及使用门控值g来控制h隐层值的更新。其与标准GRU的区别如下图所示，

这样我们就可以对所有的事实通过Attention机制得到一个中间变量c，恩，其实可以看成是一种f的加权求和~~然后基于c在对记忆进行更新。

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

\(\hat{h}\) 是更新的 state, \(h_{i-1}\) 是传入的上一时刻的 state, \(g_{i}\) 是 attention value，是一个由 softmax 产生的标量（scalar）而不是 sigmoid 激活产生的 vector \(u_{i}\), context vector 是 GRU 的 final hidden state \(_{\text {。 }}\)

3，Memory更新机制的改进：DMN中memory的更新采用以q向量为初始隐层状态的GRU进行更新。而这里作者参考End-to-End模型提出了一种ReLU的单层神经网络用于记忆更新。而记忆m就是上层的输出。

这样做的好处应该是在于简化模型吧，毕竟Attention哪里已经用了GRU，产生的c相对来说已经拥有了比较精准的信息量（猜测），所以这里的模型就不用很复杂了。

参考

记忆网络

Memory Networks (Facebook AI Research/2015)

End-To-End Memory Networks(2015)

Key-Value Memory Networks for Directly Reading Documents（2016）

Ask Me Anything: Dynamic Memory Networks for Natural Language Processing (2016)

Dynamic Memory Networks for Visual and Textual Question Answering (2016)