论文笔记 Pointer Networks and copy mechanism

paper:
- Pointer Networks, NIPS, 2015
- Incorporating Copying Mechanism in Sequence-to-Sequence Learning

Pointer Network

Motivation

We introduce a new neural architecture to learn the conditional probability of an output sequence with elements that are discrete tokens corresponding to positions in an input sequence.
提出来了一种新的架构来学习得到这样的输出序列的条件概率,其中输出序列中的元素是输入序列中离散的 tokens.

Such problems cannot be trivially addressed by existent approaches such as sequence-to-sequence [1] and Neural Turing Machines [2], because the number of target classes in each step of the output depends on the length of the input, which is variable.
这样简单的从输入序列中 copy 输出相关的序列在 seq2seq 或是神经图灵机都很难实现,因为在 decoder 的每一步输出的次的类别依赖于输入序列的长度,这个长度是变化的。

Problems such as sorting variable sized sequences, and various combinatorial optimization problems belong to this class.
和这类问题类似的还有给不定长序列的排序,组合优化等问题。

It differs from the previous attention attempts in that, instead of using attention to blend hidden units of an encoder to a context vector at each decoder step, it uses attention as a pointer to select a member of the input sequence as the output.
同之前的 attention 不同的是,之前的 attention 是 decoder 时每一步计算通过 RNN 编码后的输入序列的隐藏变量与当前向量表示的 attention vector,然后生成当前词。而 Ptr-Net 则是使用 attention 作为指针,从输入序列中选择成员作为输出。

We show Ptr-Nets can be used to learn approximate solutions to three challenging geometric problems – finding planar convex hulls, computing Delaunay triangulations, and the planar Travelling Salesman Problem – using training examples alone.
Ptr-Net 可以用来学习类似的三个几何问题。

Ptr-Nets not only improve over sequence-to-sequence with input attention, but also allow us to generalize to variable size output dictionaries. We show that the learnt models generalize beyond the maximum lengths they were trained on.
Ptr-Net 不仅可以提升 seq2seq with attention,而且能够泛化到变化的 dictionayies.

从摘要以及 Introduction 来说, Ptr-Net 主要是解决两个方面的问题。
- 一是,简单的 copy 在传统的方法中很难实现,而 Ptr-Net 则是直接从输入序列中生成输出序列。
- 而是,可以解决输出 dictionary 是变化的情况。普通的 Seq2Seq 的 output dictionary 大小是固定的,对输出中包含有输入单词(尤其是 OOV 和 rare word) 的情况很不友好。一方面,训练中不常见的单词的 word embedding 质量也不高,很难在 decoder 时预测出来,另一方面,即使 word embedding 很好,对一些命名实体,像人名等,word embedding 都很相似,也很难准确的 reproduce 出输入提到的单词。Point Network 以及在此基础上后续的研究 CopyNet 中的 copy mechanism 就可以很好的处理这种问题,decoder 在各 time step 下,会学习怎样直接 copy 出现在输入中的关键字。

Model Architecture

在介绍 Ptr-Net 之前,作者先回顾了一下基本模型 seq2seq 和 input-attention.

sequence-to-sequence Model

实际上 seq2seq 解决的问题是在当前样本空间里面,给定输入下,使得输出序列的概率最大化。其实类似的 MT,QA,Summarization 都可以看作是这一类问题。只不过根据输入和输出之间的关系,调整相应的模型。
\[p(C^P|P;\theta)=\sum_{i=1}^m(P)p_{\theta}(C_i|C_1,...,C_{i-1},P;\theta)\]

通过训练学习得到参数使得条件概率最大:
\[\theta^* = {argmax}_{\theta}\sum_{P,C^P}logp(C^P|P;\theta)\] 其中类和是在训练样本上。

In this sequence-to-sequence model, the output dictionary size for all symbols \(C_i\) is fixed and equal to n, since the outputs are chosen from the input. Thus, we need to train a separate model for each n. This prevents us from learning solutions to problems that have an output dictionary with a size that depends on the input sequence length.
在 seq2seq 模型中,输出的 dictionary 是固定大小的。因为不能解决 dictionary 是变化的情况。

Content Based Input Attention

在每一个 decoder step,先计算 \(e_{ij}\) 得到对齐概率(或者说 how well input position j matches output position i),然后做一个 softmax 得到 \(a_{ij}\),再对 \(a_{ij}\) 做一个加权和作为 context vector \(c_i\),得到这个 context vector 之后在固定大小的 output dictionary 上做 softmax 预测输出的下一个单词。

This model performs significantly better than the sequence-to-sequence model on the convex hull problem, but it is not applicable to problems where the output dictionary size depends on the input.
Nevertheless, a very simple extension (or rather reduction) of the model allows us to do this easily.

Ptr-Net

seq2seq 模型的输出词是在固定的 dictionary 中进行 softmax,并选择概率最大的词,从而得到输出序列。但这里的输出 dictionary size 是取决于 input 序列的长度的。所以作者提出了新的模型,其实很简单。 \[u_j^i=v^Ttanh(W_1e_j+W_2d_i) ,j\in(1,...,n)\] \[p(C_i|C_1,...,C_{i-1},P)=softmax(u^i)\]

i 表示decoder 的时间步,j 表示输入序列中的index. 所以\(e_j\) 是 encoder 编码后的隐藏向量,\(d_i\) 是 decoder 当前时间步 i 的隐藏向量。跟一般的 attention 基本上一致。只不过得到的 softmax 概率应用在输入序列 \(C_1,...,C_{i-1}\) 上。

Dataset Structure

  • TensorFlow implementation of "Pointer Networks":https://github.com/devsisters/pointer-network-tensorflow

  • Dataset:https://drive.google.com/drive/folders/0B2fg8yPGn2TCMzBtS0o4Q2RJaEU

CopyNet

Motivation

We address an important problem in sequence-to-sequence (Seq2Seq) learning referred to as copying, in which certain segments in the input sequence are selectively replicated in the output sequence. A similar phenomenon is observable in human language communication. For example, humans tend to repeat entity names or even long phrases in conversation.
还是前面提到的问题,seq2seq 很难解决简单的 copy 问题。而在人类的对话中,出现 copy 的现象是很常见的。尤其是 命令实体 或者是长短语。

The challenge with regard to copying in Seq2Seq is that new machinery is needed to decide when to perform the operation.
这也是 seq2seq 模型所需面对的挑战。

For example:

可以看到,对于 Chandralekha 这类实体词,可能是 OOV,也可能是其他实体或者是日期等很难被 decoder “还原” 出来的信息,CopyNet 可以更好的处理这类的信息。

那么问题来了:
- What to copy: 输入中的哪些部分应该被 copy?
- Where to paste: 应该把这部分信息 paste 到输出的哪个位置?

Model Architecture

作者从两个角度来理解 CopyNet:
- From a cognitive perspective, the copying mechanism is related to rote memorization, requiring less understanding but ensuring high literal fidelity. 从认知学角度,copy机制近似于死记硬背,不需要太多的理解,但是要保证文字的保真度。
- From a modeling perspective, the copying operations are more rigid and symbolic, making it more difficult than soft attention mechanism to integrate into a fully differentiable neural model. 从模型的角度,copy 操作更加死板和符号化,这也使得相比 soft attention 机制更难整合到一个完整的可微分的神经模型中去。

整体还是基于 encoder-decoder 模型。

Encoder:
LSTM 将 source sequence 转换为隐藏状态 M(emory) \(h_1,...,h_{T_S}\).

Decoder:
同 cannonical 的 decoder 一样,使用 RNN 读取 encoder 的隐藏状态 M. 但和传统的 decoder 不一样,他有如下区别:

  • Prediction: COPYNET predicts words based on a mixed probabilistic model of two modes, namely the generate-mode and the copymode, where the latter picks words from the source sequence. 下一个词的预测由两种模式混合而成。生成 generate-mode 和 copy-mode. 后者就像前面 Ptr-Net 所说的,在 source sentence 获取词。

  • State Update: the predicted word at time t−1 is used in updating the state at t, but COPYNET uses not only its word-embedding but also its corresponding location-specific hidden state in M (if any). 更新 decoder 中的隐藏状态时,t 时间步的隐藏状态不仅与 t-1 步生成词的 embedding vector 有关,还与这个词对应于 source sentence 中的隐藏状态的位置有关。

  • Reading M: in addition to the attentive read to M, COPYNET also has“selective read” to M, which leads to a powerful hybrid of content-based addressing and location-based addressing. 什么时候需要 copy,什么时候依赖理解来回答,怎么混合这两种模式很重要。

个人思考: 感觉不管要不要 copy 都应该是在基于理解的基础上进行的。但是因为 OOV 或者当前词的 embedding vector 训练的不好,那就无法理解了对吧? 是否可以添加 gate 机制呢? 机器到底还是没理解语言对吧? 貌似是个可以创新的点。

接下来会详细讲解这三个不同之处怎么实现的。

Prediction with Copying and Generation:\(s_t\rightarrow y_t\)

这部分是从 decoder 隐藏状态 \(s_t\) 到输出词 \(y_t\) 的过程。传统的encoder-decoder 是一个线性映射就可以了。

词表 \(\mathcal{V}=\{v_1,...,v_N\}\), 未登录词 OOV(out of vocabulary) 用 UNK 来表示(unk应该也会有对应的 embedding vector). 以及用来表示输入序列中的 unique words \(X=\{x_1,...,x_{T_S}\}\). 其中 X 使得 copynet 输出 OOV.

对于三者有这样的集合关系(先不要看公式,后面会说到):

简而言之(In a nutshell), 对于当前 source sentence X 输出的词表范围 \(\mathcal{V}\cup \text{UNK} \cup X\).

给定 decoder 中当前时间步的隐藏状态 \(s_t\), 以及 encoder 的隐藏状态序列 M.

\[p(y_t|s_t,y_{t-1},c_t,M)=p(y_t,g|s_t,y_{t-1},c_t,M) + p(y_t,c|s_t,y_{t-1},c_t,M)\]

其中 g 代表 generate mode. c 代表 copy mode.

我们知道对于 encoder 部分的输出 \(h_1,...,h_{T_S}\), 记做 M,M 其实同时包含了语义和位置信息。那么 decoder 对 M 的读取有两种形式:

  • Content-base
    Attentive read from word-embedding
  • location-base
    Selective read from location-specific hidden units

两种模式对应的概率计算,以及 score function:

\[p(y_t,g|\cdot)=\begin{cases} \dfrac{1}{Z}e^{\psi_g(y_t)}&y_t\in V\\ 0,&y_t\in X \bigcap \overline V\\ \dfrac{1}{Z}e^{\psi_g(UNK)},&y_t\notin V\cup X \end{cases}\]

\[p(y_t,c|\cdot)=\begin{cases}\dfrac{1}{Z}\sum_{j:x_j=y_t}{e^{\psi_c(x_j)}},&y_t\in X\\0&\text {otherwise}\end{cases}\]

上面两个公式叠加(相加)可以表示为下图(可以将目标词看作类别为 4 的分类。):

其中 \(\psi_g(\cdot)\)\(\psi_c(\cdot)\) 是 generate mode 和 copy mode 的 score function.

Z 是两种模型共享的归一化项,\(Z=\sum_{v\in V\cup\{UNK\}}e^{\psi_g(v)}+\sum_{x\in X}e^{\psi_c(x)}\).

然后对相应的类别计算对应的 score.

Generate-Mode:
\[\psi_g(y_t=v_i)=\nu_i^TW_os_t, v_i\in V\cup UNK\]

  • \(W_o\in R^{(N+1)\times d_s}\)
  • \(\nu_i\)\(v_i\) 对应的 one-hot 向量. 得到的结果是当前词的概率。

generate-mode 的 score \(\psi(y_t=v_i)\) 和普通的 encoder-decoder 是一样的。全链接之后的 softmax.

copy-mode:
\[\psi(y_t=x_j)=\sigma(h_j^TW_c)s_t,x_j\in \mathcal{V}\]

  • \(h_j\) 是 encoder hidden state. j 表示输入序列中的位置。
  • \(W_c\in R^{d_h\times d_s}\)\(h_j\) 映射到跟 \(s_t\) 一样的语义空间。
  • 作者发现使用 tanh 非线性变换效果更好。同时考虑到 \(y_t\) 这个词可能在输入中出现多次,所以需要考虑输入序列中所有的为 \(y_t\) 的词的概率的类和。

state update

上面一部分讲的是怎么从 decoder 中的隐藏状态计算对应的 vocabulary,也就是 \(s_t\rightarrow y_t\). 那么怎么计算当前时间步的隐藏状态呢? 我们知道传统的 encoder-decoder 中隐藏状态就是 content-based atention vector. 但是在 copynet 里面,作者对 \(y_{t-1}\rightarrow s_t\) 这个计算方式做了一定的修改。

先回顾下基本的 attention 模块,decoder 中隐藏状态的更新 \(s_t=f(y_{t-1},s_{t-1},c_t)\), 其中 \(c_t\) 也就是 attention 机制: \[c_t=\sum_{\tau=1}^{T_S}\alpha_{t\tau}\]

\[\alpha_{t\tau}=\dfrac{e^{\eta(s_{t-1},h_{\tau})}}{\sum_{\tau'}e^{\eta(s_{t-1},h_{\tau'})}}\]

CopyNet 的 \(y_{t-1}\) 在这里有所不同。不仅仅考虑了词向量,还使用了 M 矩阵中特定位置的 hidden state,或者说,\(y_{t−1}\) 的表示中就包含了这两个部分的信息 \([e(y_{t−1});\zeta(y_{t−1})]\)\(e(y_{t−1})\) 是词向量,后面多出来的一项 \(\zeta(y_{t−1})\) 叫做 selective read, 是为了连续拷贝较长的短语。和attention 的形式差不多,是 M 矩阵中 hidden state 的加权和.

\[\zeta(y_{t-1})=\sum_{\tau=1}^{T_S}\rho_{t\tau}h_{\tau}\] \[\rho_{t\tau}=\begin{cases}\dfrac{1}{K}p(x_{\tau},c|s_{t-1},M),& x_{\tau}=y_{t-1}\\ 0,& \text{otherwise} \end{cases}\]

  • \(y_{t-1}\) 没有出现在 source sentence中时, \(\zeta(y_{t-1})=0\).
  • 这里的 \(K=\sum{\tau':x_{\tau'}=y_{t-1}}p(x_{\tau'},c|s_{t-1},M)\) 是类和。还是因为输入序列中可能出现多个当前词,但是每个词在 encoder hidden state 的向量表示是不一样的,因为他们的权重也是不一样的。
  • 这里的 p 没有给出解释,我猜跟前面计算 copy 的 score 是一致的?
  • 直观上来看,当 \(\zeta(y_{t-1})\) 可以看作是选择性读取 M (selective read). 先计算输入序列中对应所有 \(y_{t-1}\) 的权重,然后加权求和,也就是 \(\zeta(y_{t-1})\).

Hybrid Adressing of M

包括两种 Addressing 方式: content-based and location-based assressing.

location-based Addressing:

\[\zeta(y_{t-1}) \longrightarrow{update} \ s_t \longrightarrow predict \ y_t \longrightarrow sel. read \zeta(y_t)\]

Learning

最小化概率的负对数:
\[L=-\dfrac{1}{N}\sum_{k=1}^N\sum_{t=1}^Tlog[p(y_t^{(k)}|y_{<t}^{(k)}, X^{(k)})]\]

N 是batch size,T 是 object sentence 长度。