论文笔记 memory networks

Memory Networks 相关论文笔记。

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

Paper reading 1: Memory Networks, Jason Weston

Motivation

RNNs 将信息压缩到final state中的机制,使得其对信息的记忆能力很有限。而memory work的提出就是对这一问题进行改善。

However, their memory (encoded by hidden states and weights) is typically too small, and is not compartmentalized enough to accurately remember facts from the past (knowledge is compressed into dense vectors). RNNs are known to have difficulty in performing memorization.

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

Memory Networks

four components:

  • I:(input feature map)

把输入映射为特征向量,可以包括各种特征工程,比如parsing, coreference, entity resolution,也可以是RNN/LSTM/GRU。通常以句子为单位,将sentence用向量表示,一个句子对应一个sparse or dense feature vector.

  • G:(generalization)

使用新的输入数据更新 memories

  • O:(output feature map)

给定新的输入和现有的 memory state,在特征空间里产生输出

  • R:(response)

将输出转化为自然语言

详细推导过程

1.I component: :encode input text to internal feature representation.

可以选择多种特征,比如bag of words, RNN encoder states, etc.

2.G component: generalization 就是结合 old memories和输入来更新 memories. \(m_i=G(m_i, I(x),m), ∀i\)

最简单的更新memory的方法是 \(m_{H(x)}=I(x)\), \(H(x)\) 是一个寻址函数slot selecting function,G更新的是 m 的index,可以把新的memory m,也就是新的输入 I(x) 保存到下一个空闲的地址 \(m_n\) 中,并不更新原有的memory. 更复杂的 G 函数可以去更新更早的memory,甚至是所有的memory.

这里的新的input,如果在QA中就是question 和 old memmory的组合 \([I(x), m_i]\).

3.O component: reading from memories and performing inference, calculating what are the relevant memories to perform a good response. 给定新的输入和memory,在memories中寻找最相关的k个记忆

如果k=2:

\[o_1=O_1(q,m)=argmax_{i=1,2,..,N}s_O(q,m_i)\]

\[o_2=O_2(q,m)=argmax_{i=1,2,..,N}s_O([q,o_1],m_i)\]

output: \([q,o_1, o_2]\) 也是module R的输入.

\(s_O\) is a function that scores the match between the pair of sentences x and mi. \(s_O\) 用来表征 question x 和 记忆 \(m_i\) 的相关程度。

\[s_O=qUU^Tm\]

\(s_O\) 表示问题q和当前memory m的相关程度

U:bilinear regression参数,相关事实的 \(qUU^Tm_{true}\) 的score高于不相关事实的分数 \(qUU^Tm_{random}\)

4.R component : 对 output feature o 进行解码,得到最后的response: r=R(o)

\[r=argmax_{w\in W}s_R([q,m_{o_1},m_{o_2}],w)\]

W 是词典,\(s_R\) 表示与output feature o 最相关的单词。

\(s_R\)\(s_O\) 的形式是相同的。 \[s(x,y)=xUU^Ty\]

Huge Memory 问题

如果memory太大,比如 Freebase or Wikipedia,

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

损失函数

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

多类支持向量机损失:

minimize: \(L_i = \sum_{j\ne y_i}max(0,s_j - s_{y_i}+\Delta)\)

其中 \(\overline f, \overline f',\overline r\) 表示负采样。比如(8)式中r表示 true response, 而 \(\overline r\) 表示随机抽样词典中的其他词。

QA实例:

  1. 有没有挑选出正确的第一句话

  2. 正确挑选出了第一句话后能不能正确挑出第二句话

(6)+(7) 合起来就是能不能挑选出正确的语境,用来训练 attention 参数

  1. 把正确的 supporting fact 作为输入,能不能挑选出正确的答案,来训练 response 参数

Paper reading 2 End-To-End Memory Networks

motivation

上一篇paper中的缺陷:

The model in that work was not easy to train via backpropagation, and required supervision at each layer of the network.

这篇论文可以看作是上一篇论文memory networks的改进版。

Our model can also be seen as a version of RNNsearch with multiple computational steps (which we term “hops”) per output symbol.

也可以看做是将multiple hops应用到RNNsearch这篇论文上 Neural Machine Translation by Jointly Learning to Align and Translate

Model architecture

Single layer

输入:

  • input: \(x_1,...,x_i\)
  • query: q
  • answer: a

对于单层网络,主要分为以下几个步骤:

1.将input和query映射到特征空间

  • memory vector {\(m_i\)}: \(\{x_i\}\stackrel A\longrightarrow \{m_i\}\)
  • internal state u: \(q\stackrel B \longrightarrow u\)

2.计算attention,也就是query的向量表示u,和input中各个sentence的向量表示 \(m_i\) 的匹配度。compute the match between u and each memory mi by taking the inner product followed by a softmax.

\[p_i=softmax(u^Tm_i)\]

p is a probability vector over the inputs.

3.得到context vector

  • output vector: \(\{x_i\}\stackrel C\longrightarrow \{c_i\}\)

The response vector from the memory o is then a sum over the transformed inputs ci, weighted by the probability vector from the input: \[o = \sum_ip_ic_i\]

和 Memory Networks with Strong Supervision 版本不同,这里的 output 是加权平均而不是一个 argmax

4.预测最后答案,通常是一个单词 \[\hat a =softmax(Wu^{k+1})= softmax(W(o^k+u^k))\] W可以看做反向embedding,W.shape=[embed_size, V]

5.对 \(\hat a\) 进行解码,得到自然语言的response \[\hat a \stackrel C \longrightarrow a\]

其中:

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

单层网络实例:

这里的 memory {\(m_i\)} 直接用于输出向量 \(c_i\). 其实我也疑惑,为啥要重新用一个output embedding C,直接用 \(m_i\) 不好吗。其实这些小tricks也说不准好不好,都是试出来的吧,因为怎么说都合理。。。

Multiple Layers/ Multiple hops

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

\[u_{k+1}=u^k+o^k\]

对比上一篇paper来理解

多层网络也可以看做是四个组件构成的:

  • input components: 就是将query和sentences映射到特征空间中
  • generalization components: 更新memory,这里的memory也是在变化的,\(\{m_i\}=AX\), 但是embedding matrix A 是逐层变化的
  • output components: attention就是根据inner product后softmax计算memory和query之间的匹配度,然后更新input,也就是[u_k,o_k], 可以是相加/拼接,或者用RNN. 区别是,在上一篇论文中是argmax,\(o_2=O_2(q,m)=argmax_{i=1,2,..,N}s_O([q,o_1],m_i)\), 也就是选出匹配程度最大的 memory \(m_i\), 而这篇论文是对所有的memory进行加权求和
  • response components: 跟output components类似啊,上一篇论文是与词典中所有的词进行匹配,求出相似度最大的 \(r=argmax_{w\in W}s_R([q,m_{o_1},m_{o_2}],w)\),而这篇论文是 \(\hat a=softmax(Wu^{k+1})=softmax(W(u^k+o^k))\) 最小化交叉熵损失函数训练得到 answer prediction matrix W.

Overall, it is similar to the Memory Network model in [23], except that the hard max operations within each layer have been replaced with a continuous weighting from the softmax.

一些技术细节

每一层都有 mebedding matrices \(A^k, C^k\),用来embed inputs {\(x_i\)},为了减少训练参数.作者尝试了以下两种情况:

  1. Adjacent
  • 上一层的output embedding matrix 是下一层的 input embedding matrix, 即 \(A^{k+1}=C^k\)
  • 最后一层的output embedding 可用作 prediction embedding matrix, 即 \(W^T=C^k\)
  • question embedding matrix = input embedding matrix of the first layer, \(B=A^1\)
  1. Layer-wise (RNN-like)
  • \(A^1=A^2=...=A^k, C^1=C^2=...C^k\)
  • \(u^{k+1} = Hu^k+o^k\)

Experiments

Dataset

数据集来源:Towards AI-complete question answering: A set of prerequisite toy tasks

总共有 20 QA tasks,其中每个task有 \(I(I\le 320)\) 个sentence {\(x_i\)}, 词典大小 V=170, 可以看做这是个玩具级的任务。每个task有1000个problems

Modle details

Sentence representations

也就是将input和query映射到特征空间,有两种方式:

1.Bag of words(BOW) representation

\[m_i=\sum_jAx_{ij}\] \[c_i=\sum_jCx_{ij}\] \[u=\sum_jBq_j\]

分别对每个词embed,然后sum,缺点是没有考虑词序

2.encodes the position of words within the sentence 考虑词序的编码 \[m_i=\sum_jl_j\cdot Ax_{ij}\] i表示第i个sentence,j表示这个sentence中的第j个word

\[l_{kj}=(1-j/J)-(k/d)(1-2j/J)\]

查看源码时发现很多代码的position encoder与原paper不一样,比如domluna/memn2n中公式是: \[l_{kj} = 1+4(k- (d+1)/2)(j-(J+1)/2)/d/J\]

原本词 \(x_{ij}\) 的向量表示就是embeded后的 \(Ax_{ij},(shape=[1, embed_size])\), 但现在要给这个向量加一个权重 \(l_j\),而且这个权重不是一个值,而是一个向量,对 \(Ax_{ij}\) 中每一个维度的权重也是不一样的。

令J=20, d=50. 具体两个公式的差别可以查看

wolframalpha1

wolframalpha2

也就是说不仅跟word在sentence中的位置有关,还和embed_size中的维度有关。这就很难理解了。。。

好像跟句子的结构相关,北大有篇相关的论文A Position Encoding Convolutional Neural Network Based on Dependency Tree for Relation Classification

其中 J 表示sentence的长度,d表示 dimension of the embedding. 这种sentence representation称为 position encoding(PE).也就是词序会影响memory \(m_i\).

position encoding 代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
def position_encoding(sentence_size, embedding_size):
"""
Position Encoding described in section 4.1 [1]
"""
encoding = np.ones((embedding_size, sentence_size), dtype=np.float32)
le = embedding_size+1
ls = sentence_size + 1
for k in range(1, le):
for j in range(1, ls):
# here is different from the paper.
# the formulation in paper is: l_{kj}=(1-j/J)-(k/d)(1-2j/J)
# here the formulation is: l_{kj} = 1+4(k- (d+1)/2)(j-(J+1)/2)/d/J,
# 具体表现可查看 https://www.wolframalpha.com/input/?i=1+%2B+4+*+((y+-+(20+%2B+1)+%2F+2)+*+(x+-+(50+%2B+1)+%2F+2))+%2F+(20+*+50)+for+0+%3C+x+%3C+50+and+0+%3C+y+%3C+20
encoding[k-1, j-1] = (k - (embedding_size+1)/2) * (j - (sentence_size+1)/2)
encoding = 1 + 4 * encoding / embedding_size / sentence_size
# Make position encoding of time words identity to avoid modifying them
encoding[:, -1] = 1.0 # 最后一个sentence的权重都为1
return np.transpose(encoding) # [sentence_size, embedding_size]
Temporal Encoding

将memory改进为: \[m_i=\sum_jAx_{ij}+T_A(i)\] 其中 \(T_A(i)\) is the ith row of a special matrix \(T_A\) that encodes temporal information. 用一个特殊的矩阵 \(T_A\) 来编码时间信息。\(T_A(i)\) i表示第i个sentence的包含时间信息??

同样的output embedding: \[c_i=\sum_jCx_{ij}+T_C(i)\]

Learning time invariance by injecting random noise

we have found it helpful to add “dummy” memories to regularize TA.

Training Details

1.learning rate decay
2.gradient clip
3.linear start training
4.null padding, zero padding

完整代码实现

https://github.com/PanXiebit/text-classification/blob/master/06-memory%20networks/memn2n_model.py

Paper reading 3 Ask Me Anything: Dynamic Memory Networks for Natural Language Processing

Motivation

Most tasks in natural language processing can be cast into question answering (QA) problems over language input.

大部分的自然语言处理的任务都可以看作是QA问题,比如QA, sentiment analysis, part-of-speech tagging.

Model Architecture

可以分为以下4个模块:

  • Input Module: 将输入文本编码为distribution representations
  • Question Module: 将question编码为distribution representations
  • Episodic Memory Module: 通过attention机制选择focus on输入文本中的某些部分,然后生成memory vector representation.
  • Answer Module: 依据the final memory vector生成answer

Detailed visualization:

Input Module

主要分为两种情况:

1.输入是single sentence,那么input module输出的就是通过RNN计算得到的隐藏状态 \(T_C= T_I\), \(T_I\) 表示一个sentence中的词的个数。

2.输入是a list of sentences,在每个句子后插入一个结束符号 end-of-sentence token, 然后每个sentence的final hidden作为这个sentence的representation. 那么input module输出 \(T_C\), \(T_C\)等于sequence的sentence个数。

然后RNN使用的是GRU,作者也尝试过LSTM,发现效果差不多,但LSTM计算量更大。

Question Module

同样的使用GRU编码,在t时间步, 隐藏状态 \[q_t=GRU(L[w_t^Q],q_{t-1})\] L代表embedding matrix.

最后输出 final hidden state. \[q=q_{T_Q}\] \(T_Q\) 是question的词的个数。

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。

1.Needs for multiple Episodes: 通过迭代使得模型具有了传递推理能力 transitive inference.

2.Attention Mechanism: 使用了一个gating function作为attention机制。相比在 end-to-end MemNN 中attention使用的是linear regression,即对inner production通过softmax求权重。 这里使用一个两层前向神经网络 G 函数.

\[g_t^i=G(c_t,m^{i-1},q)\]

\(c_t\) 是candidate fact, \(m_{i-1}\) 是previous memory, question q. t 表示sentence中的第t时间步,i表示episodic的迭代次数。

这里作者定义了 a large feture \(z(c,m,q)\) 来表征input, memory, question之间的相似性。

\[z_t^i=[c_t, m^{i-1},q, c_t\circ q,c_t\circ m^{i-1},|c_t-q|,|c_t-m^{i-1}|, c_t^TW^{(b)}q, c_t^TW^{(b)}m^{i-1}]\]

总的来说,就是根据向量内积,向量相减来表示相似度。 跟cs224d-lecture16 dynamic Memory networkRichard Socher本人讲的有点区别,不过这个既然是人工定义的,好像怎么说都可以。

然后通过G函数,也就是两层前向神经网络得到一个scale score.

\[G = \sigma(W^{(2)}tanh(W^{(1)}z_i^t+b^{(1)})+b^{(2)})\]

\(c_t\), \(m^{i-1}, q 带入到G函数,即可求得\)\(g_i^t\),也就是candidate fact \(c_i\) 的score.

计算完每一次迭代后的分数后,来更新episode \(e^i\), 相当于 context vector,

soft attention

在之前的attention机制中,比如cs224d-lecture10-机器翻译和注意力机制介绍的attention得到的context vector,在end-to-end MemNN中attention也是fact representation的加权求和。

attention based GRU

但这篇论文中应用了GRU,对fact representation c 进行处理,然后加上gate

\[h_t^i=g_t^iGRU(c_t,h_{t-1}^i)+(1-g_t^i)h_{i-1}^t\]

所以这里的GRU应该是 \(T_C\)步吧??

每次迭代的context vector是对 input module 的输出进行 attention-based GRU编码的最后的隐藏状态:

\[e^i=h_{T_C}^i\]

总结一下:

这部分attention mechanism目的就是生成episode \(e^i\),\(e^i\) 是第i轮迭代的所有input相关信息的summary.也就是 context vector,将input text压缩到一个向量表示中,end-to-end MemNN用了soft attention,就是加权求和。而这里用了GRU,各个时间步的权重不是直接相乘,而是作为一个gate机制。

3.Memory Update Mechanism 上一步计算的episode \(e^i\) 以及上一轮迭代的memory \(m^{i-1}\) 作为输入来更新memory \(m_i\) \[m_i=GRU(e^i,m^{i-1})\] \(m^0=q\), 所以这里的GRU是单步的吧

经过 \(T_M\) 次迭代: \(m=m^{T_M}\), 也就是episodic memory module的输出,即answer module的输入。

在end-to-end MemNN的memory update中,\(u_{k+1}=u^k+o^k\), 而在这篇论文中,如果也采用这种形式的话就是 \(m^{i}=e^i+m^{i-1}\),但作者采用了 RNN 做非线性映射,用 episode \(e_i\) 和上一个 memory \(m_{i−1}\) 来更新 episodic memory,其 GRU 的初始状态包含了 question 信息,\(m_0=q\)

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

Answer Module

使用了GRU的decoder。输入是question module的输出q和上一个时刻的hidden state \(a_{t-1}\),初始状态是episodic memory module的输出 \(a_0=m^{T_M}\). \[y_t=softmax(W^{(a)}a_t)\] \[a_t=GRU([y_{t-1},q],a_{t-1})\] 这里应该就是单步GRU吧,毕竟question的向量表示q只有一个呀。

Train

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

总结:对比上一篇论文End-to-end memory networks

  • input components: end2end MemNN 采用embedding,而DMN使用GRU
  • generalization components: 也就是memory update,End2End MemNN采用线性相加 \(u^{k+1}=u^k+o^k\),其中的 \(o^k\) 就是经过attention之后得到的memory vector
  • output components: end2end MemNN采用的是对比memory和query,用内积求相似度,然后softmax求权重,最后使用加权求和得到context vector. 而DMN采用的是人工定义相似度的表示形式,然后用两层前向神经网络计算得到score,再对score用softmax求权重,再然后把权重当做gate机制,使用GRU求context vector

  • response components: end2end MemNN 直接使用最后的 top memory layer 预测,而DMN是把top memory 当做init hidden state

总之,DMN实在是太太太复杂了。。每一个module都用到了RNN

Paper reading 4 DMN+

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

Motivate

提出了DMN+,是DMN的改进版,同时将其应用到 Visual Question Answering 这一任务上。

However, it was not shown whether the architecture achieves strong results for question answering when supporting facts are not marked during training or whether it could be applied to other modalities such as images.

这段话是描述DMN的缺点的,在没有标注 supporting facts的情况下表现不好。但是DMN貌似也并不需要标注 supporting facts啊。。。

Like the original DMN, this memory network requires that supporting facts are labeled during QA training. End-toend memory networks (Sukhbaatar et al., 2015) do not have this limitation.

Based on an analysis of the DMN, we propose several improvements to its memory and input modules. Together with these changes we introduce a novel input module for images in order to be able to answer visual questions.

这篇文章对DMN中的 input module进行了修改,并且提出了新的模型架构适用于图像的。

DMN 存在的两个问题:

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

总的来说这篇文章贡献主要还是在应用到图像上了,至于作者所说的 input module的改进,只是为了减少计算量,而且改进版中的 bi-RNN 和 position encoding 都是在别人的论文中出现了的。

Model Architecture

同DMN一样,也分为 input module, question module, episodic module 和 answer module.

Input Module

input module for text QA

主要分为两个组件: sentence reader 和 input fusion layer.

sentence reader: 用encoding position代替RNN对单个sentence进行编码。用 positional encoding 的原因是在这里用 GRU/LSTM 编码句子计算量大而且容易过拟合(毕竟 bAbI 的单词量很小就几十个单词。。),这种方法反而更好。

input fusion layer: 使用 bi-directional GRU 来得到context 信息,兼顾过去和未来的信息。

总的来说: DMN+ 把 single GRU 替换成了类似 hierarchical RNN 结构,一个 sentence reader 得到每个句子的 embedding,一个 input infusion layer 把每个句子的 embedding 放入另一个 GRU 中,得到 context 信息,来解决句子远距离依赖的问题。

input module for VQA

1.Local region feature extraction:

获取局部特征信息,使用VGG预训练得到的特征。局部特征 feature vector 通过一个linear layer 和 tanh activation 得到 feature embedding.

2.Input fusion layer:

将 feature embedding 放入到 bi-GRU 中。

Without global information, their representational power is quite limited, with simple issues like object scaling or locational variance causing accuracy problems. 强调了为什么要使用 input fusion layer.

Question Module

这部分跟DMN是一样的, question 都是文本,用RNN编码。

Episodic Module

score mechanism

input module 的输出是: \[\overleftrightarrow F=[\overleftrightarrow f_1, ...,\overleftrightarrow f_N]\]

同DMN一样,作者也是用了人工特征,相比DMN简化一点: \[z_i^t=[\overleftrightarrow f_i\circ q,\overleftrightarrow f_i\circ m^{t-1},|\overleftrightarrow f_i-q|,|\overleftrightarrow f_i-m^{i-1}|]\]

这里与前面DMN的公式有点区别,就是这里的i表示input module中的时间步, t 表示episodic迭代次数。

同样使用一个两层前向神经网络: \[G = W^{(2)}tanh(W^{(1)}z_i^t+b^{(1)})+b^{(2)}\]

但是这里不是使用 sigmoid 函数来求的 score,而是使用softmax 来求score \(g_i^t\).

\[g_i^t=\dfrac{Z_i^t}{\sum_{k=1}^{M_i}exp(Z_k^t)}\]

attention mechanism

比较了 soft attention 和 attention-based-GRU.相比DMN那篇论文,这里给出了详细的比较。

soft attention, 就是简单的加权求和。

\[c^t=\sum_{i=1}^Ng_i^t\overleftrightarrow f_i\] 其缺点在于丢失了位置信息和词序信息。

感觉简单的attention已经很好了吧。。前面 \(\overleftrightarrow f_i\) 不就是考虑了词序信息的么,然后再用GRU对 \(\overleftrightarrow f_i\) 处理不会过拟合吗???

attention based GRU

使用attention gate \(g_i^t\) 代替 update gate \(u_i\). 我们知道 \(u_i\) 是通过 current input 和 previous hidden state得到的。 而使用 attention gate \(g_i^t\) 能够考虑到 question 和 previous memory. 因为我们这里是要更新memory, 所以这样很合理呀。。厉害了 \[h_i=g_i^t\circ \tilde h_i+(1-g_i^t)\circ h_{i-1}\]

memory update mechanism

在DMN中,更新memory在基于 previous memory 和 当前的 context vector 的GRU编码得到的。 DMN+采用的是将 previous memory \(m^{t-1}\), 当前 context \(c^t\),和question q 拼接起来,然后通过全连接层,以及relu激活函数得到的: \[m_t = ReLU(W^t[m^{t-1},c^t,q]+b)\] 使用relu的全连接层能提升0.5%的准确率。

Answer Module

同DMN.

reference: