Incorporating Copying Mechanism in Sequence-to-Sequence Learning

Introduction

Recently, neural network-based sequence-to-sequence learning (Seq2Seq) has achieved remarkable success in various natural language processing (NLP) tasks, including but not limited to Machine Translation [Cho et al. (2014, Bahdanau et al. (2014], Syntactic Parsing [Vinyals et al. (2015b], Text Summarization [Rush et al. (2015] and Dialogue Systems [Vinyals and Le (2015]. Seq2Seq is essentially an encoder-decoder model, in which the encoder first transform the input sequence to a certain representation which can then transform the representation into the output sequence. Adding the attention mechanism [Bahdanau et al. (2014] to Seq2Seq, first proposed for automatic alignment in machine translation, has led to significant improvement on the performance of various tasks [Shang et al. (2015, Rush et al. (2015]. Different from the canonical encoder-decoder architecture, the attention-based Seq2Seq model revisits the input sequence in its raw form (array of word representations) and dynamically fetches the relevant piece of information based mostly on the feedback from the generation of the output sequence.

In this paper, we explore another mechanism important to the human language communication, called the “copying mechanism”. Basically, it refers to the mechanism that locates a certain segment of the input sentence and puts the segment into the output sequence. For example, in the following two dialogue turns we observe different patterns in which some subsequences (colored blue) in the response (R) are copied from the input utterance (I):

Both the canonical encoder-decoder and its variants with attention mechanism rely heavily on the representation of “meaning”, which might not be sufficiently inaccurate in cases in which the system needs to refer to sub-sequences of input like entity names or dates. In contrast, the copying mechanism is closer to the rote memorization in language processing of human being, deserving a different modeling strategy in neural network-based models. We argue that it will benefit many Seq2Seq tasks to have an elegant unified model that can accommodate both understanding and rote memorization. Towards this goal, we propose CopyNet, which is not only capable of the regular generation of words but also the operation of copying appropriate segments of the input sequence. Despite the seemingly “hard” operation of copying, CopyNet can be trained in an end-to-end fashion. Our empirical study on both synthetic datasets and real world datasets demonstrates the efficacy of CopyNet.

Background: Neural Models for Sequence-to-sequence Learning

Seq2Seq Learning can be expressed in a probabilistic view as maximizing the likelihood (or some other evaluation metrics [Shen et al. (2015]) of observing the output (target) sequence given an input (source) sequence.

RNN-based Encoder-Decoder is successfully applied to real world Seq2Seq tasks, first by ?) and ?), and then by [Vinyals and Le (2015, Vinyals et al. (2015a]. In the Encoder-Decoder framework, the source sequence $X=[x_{1},...,x_{T_{S}}]$ is converted into a fixed length vector $\mathbf{c}$ by the encoder RNN, i.e.

where $\{\mathbf{h}_{t}\}$ are the RNN states, $\mathbf{c}$ is the so-called context vector, $f$ is the dynamics function, and $\phi$ summarizes the hidden states, e.g. choosing the last state $\mathbf{h}_{T_{S}}$. In practice it is found that gated RNN alternatives such as LSTM [Hochreiter and Schmidhuber (1997] or GRU [Cho et al. (2014] often perform much better than vanilla ones.

The decoder RNN is to unfold the context vector $\mathbf{c}$ into the target sequence, through the following dynamics and prediction model:

where $\mathbf{s}_{t}$ is the RNN state at time $t$, $y_{t}$ is the predicted target symbol at $t$ (through function $g(\cdot)$) with $y_{<t}$ denoting the history $\{y_{1},...,y_{t-1}\}$. The prediction model is typically a classifier over the vocabulary with, say, 30,000 words.

2 The Attention Mechanism

The attention mechanism was first introduced to Seq2Seq [Bahdanau et al. (2014] to release the burden of summarizing the entire source into a fixed-length vector as context. Instead, the attention uses a dynamically changing context $\mathbf{c}_{t}$ in the decoding process. A natural option (or rather “soft attention”) is to represent $\mathbf{c}_{t}$ as the weighted sum of the source hidden states, i.e.

where $\eta$ is the function that shows the correspondence strength for attention, approximated usually with a multi-layer neural network (DNN). Note that in [Bahdanau et al. (2014] the source sentence is encoded with a Bi-directional RNN, making each hidden state $\mathbf{h}_{\tau}$ aware of the contextual information from both ends.

CopyNet

From a cognitive perspective, the copying mechanism is related to rote memorization, requiring less understanding but ensuring high literal fidelity. 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. In this section, we present CopyNet, a differentiable Seq2Seq model with “copying mechanism”, which can be trained in an end-to-end fashion with just gradient descent.

As illustrated in Figure 1, CopyNet is still an encoder-decoder (in a slightly generalized sense). The source sequence is transformed by Encoder into representation, which is then read by Decoder to generate the target sequence.

Same as in [Bahdanau et al. (2014], a bi-directional RNN is used to transform the source sequence into a series of hidden states with equal length, with each hidden state $\mathbf{h}_{t}$ corresponding to word $x_{t}$. This new representation of the source, $\{\mathbf{h}_{1},...,\mathbf{h}_{T_{S}}\}$, is considered to be a short-term memory (referred to as $\mathbf{M}$ in the remainder of the paper), which will later be accessed in multiple ways in generating the target sequence (decoding).

An RNN that reads $\mathbf{M}$ and predicts the target sequence. It is similar with the canonical RNN-decoder in [Bahdanau et al. (2014], with however the following important differences

Prediction: CopyNet predicts words based on a mixed probabilistic model of two modes, namely the generate-mode and the copy-mode, where the latter picks words from the source sequence (see Section 3.2);

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 $\mathbf{M}$ (if any) (see Section 3.3 for more details);

Reading $\mathbf{M}$: in addition to the attentive read to $\mathbf{M}$, CopyNet also has“selective read” to $\mathbf{M}$, which leads to a powerful hybrid of content-based addressing and location-based addressing (see both Sections 3.3 and 3.4 for more discussion).

2 Prediction with Copying and Generation

We assume a vocabulary $\mathcal{V}=\{v_{1},...,v_{N}\}$, and use unk for any out-of-vocabulary (OOV) word. In addition, we have another set of words $\mathcal{X}$, for all the unique words in source sequence $X=\{x_{1},...,x_{T_{S}}\}$. Since $\mathcal{X}$ may contain words not in $\mathcal{V}$, copying sub-sequence in $X$ enables CopyNet to output some OOV words. In a nutshell, the instance-specific vocabulary for source $X$ is $\mathcal{V}\cup\textsc{unk}\cup\mathcal{X}$.

Given the decoder RNN state $\mathbf{s}_{t}$ at time $t$ together with $\mathbf{M}$, the probability of generating any target word $y_{t}$, is given by the “mixture” of probabilities as follows

where g stands for the generate-mode, and c the copy mode. The probability of the two modes are given respectively by

where $\psi_{g}(\cdot)$ and $\psi_{c}(\cdot)$ are score functions for generate-mode and copy-mode, respectively, and $Z$ is the normalization term shared by the two modes, $Z=\sum_{v\in\cal V\cup\{\textsc{unk}\}}e^{\psi_{g}(v)}+\sum_{x\in X}e^{\psi_{c}(x)}.$ Due to the shared normalization term, the two modes are basically competing through a softmax function (see Figure 1 for an illustration with example), rendering Eq.(4) different from the canonical definition of the mixture model [McLachlan and Basford (1988]. This is also pictorially illustrated in Figure 2. The score of each mode is calculated:

The same scoring function as in the generic RNN encoder-decoder [Bahdanau et al. (2014] is used, i.e.

The score for “copying” the word $x_{j}$ is calculated as

Naturally we let $p(y_{t},\textsf{c}|\cdot)=0$ if $y_{t}$ does not appear in the source sequence, and set $p(y_{t},\textsf{g}|\cdot)=0$ when $y_{t}$ only appears in the source.

3 State Update

CopyNet updates each decoding state $\mathbf{s}_{t}$ with the previous state $\mathbf{s}_{t-1}$, the previous symbol $y_{t-1}$ and the context vector $\mathbf{c}_{t}$ following Eq. (2) for the generic attention-based Seq2Seq model. However, there is some minor changes in the $y_{t-1}\longrightarrow\mathbf{s}_{t}$ path for the copying mechanism. More specifically, $y_{t-1}$ will be represented as $[\mathbf{e}({y_{t-1})};\zeta(y_{t-1})]^{\top}$, where $\mathbf{e}({y_{t-1}})$ is the word embedding associated with $y_{t-1}$, while $\zeta(y_{t-1})$ is the weighted sum of hidden states in $\mathbf{M}$ corresponding to $y_{t}$

where $K$ is the normalization term which equals $\sum_{{\tau^{\prime}}:x_{\tau^{\prime}}=y_{t-1}}p(x_{\tau^{\prime}},c|\mathbf{s}_{t-1},\mathbf{M})$, considering there may exist multiple positions with $y_{t-1}$ in the source sequence. In practice, $\rho_{t\tau}$ is often concentrated on one location among multiple appearances, indicating the prediction is closely bounded to the location of words.

In a sense $\zeta(y_{t-1})$ performs a type of read to $\mathbf{M}$ similar to the attentive read (resulting $\mathbf{c}_{t}$) with however higher precision. In the remainder of this paper, $\zeta(y_{t-1})$ will be referred to as selective read. $\zeta(y_{t-1})$ is specifically designed for the copy mode: with its pinpointing precision to the corresponding $y_{t-1}$, it naturally bears the location of $y_{t-1}$ in the source sequence encoded in the hidden state. As will be discussed more in Section 3.4, this particular design potentially helps copy-mode in covering a consecutive sub-sequence of words. If $y_{t-1}$ is not in the source, we let $\zeta(y_{t-1})=\textbf{0}$.

4 Hybrid Addressing of 𝐌𝐌\mathbf{M}

We hypothesize that CopyNet uses a hybrid strategy for fetching the content in $\mathbf{M}$, which combines both content-based and location-based addressing. Both addressing strategies are coordinated by the decoder RNN in managing the attentive read and selective read, as well as determining when to enter/quit the copy-mode.

Both the semantics of a word and its location in $X$ will be encoded into the hidden states in $\mathbf{M}$ by a properly trained encoder RNN. Judging from our experiments, the attentive read of CopyNet is driven more by the semantics and language model, therefore capable of traveling more freely on $\mathbf{M}$, even across a long distance. On the other hand, once CopyNet enters the copy-mode, the selective read of $\mathbf{M}$ is often guided by the location information. As the result, the selective read often takes rigid move and tends to cover consecutive words, including unks. Unlike the explicit design for hybrid addressing in Neural Turing Machine [Graves et al. (2014, Kurach et al. (2015], CopyNet is more subtle: it provides the architecture that can facilitate some particular location-based addressing and lets the model figure out the details from the training data for specific tasks. Location-based Addressing: With the location information in $\{\mathbf{h}_{i}\}$, the information flow

Learning

Although the copying mechanism uses the “hard” operation to copy from the source and choose to paste them or generate symbols from the vocabulary, CopyNet is fully differentiable and can be optimized in an end-to-end fashion using back-propagation. Given the batches of the source and target sequence $\{X\}_{N}$ and $\{Y\}_{N}$, the objectives are to minimize the negative log-likelihood:

Experiments

We report our empirical study of CopyNet on the following three tasks with different characteristics

A synthetic dataset on with simple patterns;

A dataset for simple single-turn dialogues.

Dataset: We first randomly generate transformation rules with 5$\sim$20 symbols and variables $\mathbf{x}$ & $\mathbf{y}$, e.g.

with {a b c d e f g h m} being regular symbols from a vocabulary of size 1,000. As shown in the table below, each rule can further produce a number of instances by replacing the variables with randomly generated subsequences (1$\sim$15 symbols) from the same vocabulary. We create five types of rules, including “$\mathbf{x}\rightarrow$ $\emptyset$”. The task is to learn to do the Seq2Seq transformation from the training instances. This dataset is designed to study the behavior of CopyNet on handling simple and rigid patterns. Since the strings to repeat are random, they can also be viewed as some extreme cases of rote memorization.

Experimental Setting: We select 200 artificial rules from the dataset, and for each rule 200 instances are generated, which will be split into training (50%) and testing (50%). We compare the accuracy of CopyNet and the RNN Encoder-Decoder with (i.e. RNNsearch) or without attention (denoted as Enc-Dec). For a fair comparison, we use bi-directional GRU for encoder and another GRU for decoder for all Seq2Seq models, with hidden layer size = 300 and word embedding dimension = 150. We use bin size = 10 in beam search for testing. The prediction is considered correct only when the generated sequence is exactly the same as the given one.

It is clear from Table 1 that CopyNet significantly outperforms the other two on all rule-types except “$\mathbf{x}\rightarrow\emptyset$”, indicating that CopyNet can effectively learn the patterns with variables and accurately replicate rather long subsequence of symbols at the proper places.This is hard to Enc-Dec due to the difficulty of representing a long sequence with very high fidelity. This difficulty can be alleviated with the attention mechanism. However attention alone seems inadequate for handling the case where strict replication is needed.

A closer look (see Figure 3 for example) reveals that the decoder is dominated by copy-mode when moving into the subsequence to replicate, and switch to generate-mode after leaving this area, showing CopyNet can achieve a rather precise coordination of the two modes.

2 Text Summarization

Automatic text summarization aims to find a condensed representation which can capture the core meaning of the original document. It has been recently formulated as a Seq2Seq learning problem in [Rush et al. (2015, Hu et al. (2015], which essentially gives abstractive summarization since the summary is generated based on a representation of the document. In contrast, extractive summarization extracts sentences or phrases from the original text to fuse them into the summaries, therefore making better use of the overall structure of the original document. In a sense, CopyNet for summarization lies somewhere between two categories, since part of output summary is actually extracted from the document (via the copying mechanism), which are fused together possibly with the words from the generate-mode.

We evaluate our model on the recently published LCSTS dataset [Hu et al. (2015], a large scale dataset for short text summarization. The dataset is collected from the news medias on Sina Weibowww.sina.com including pairs of (short news, summary) in Chinese. Shown in Table 2, PART II and III are manually rated for their quality from 1 to 5. Following the setting of [Hu et al. (2015] we use Part I as the training set and and the subset of Part III scored from 3 to 5 as the testing set.

Experimental Setting: We try CopyNet that is based on character (+C) and word (+W). For the word-based variant the word-segmentation is obtained with jiebahttps://pypi.python.org/pypi/jieba. We set the vocabulary size to 3,000 (+C) and 10,000 (+W) respectively, which are much smaller than those for models in [Hu et al. (2015]. For both variants we set the embedding dimension to 350 and the size of hidden layers to 500. Following [Hu et al. (2015], we evaluate the test performance with the commonly used ROUGE-1, ROUGE-2 and ROUGE-L [Lin (2004], and compare it against the two models in [Hu et al. (2015], which are essentially canonical Encoder-Decoder and its variant with attention.

It is clear from Table 3 that CopyNet beats the competitor models with big margin. ?) reports that the performance of a word-based model is inferior to a character-based one. One possible explanation is that a word-based model, even with a much larger vocabulary (50,000 words in ?)), still has a large proportion of OOVs due to the large number of entity names in the summary data and the mistakes in word segmentation. CopyNet, with its ability to handle the OOV words with the copying mechanism, performs however slightly better with the word-based variant.

2.1 Case Study

As shown in Figure 4, we make the following interesting observations about the summary from CopyNet: 1) most words are from copy-mode, but the summary is usually still fluent; 2) CopyNet tends to cover consecutive words in the original document, but it often puts together segments far away from each other, indicating a sophisticated coordination of content-based addressing and location-based addressing; 3) CopyNet handles OOV words really well: it can generate acceptable summary for document with many OOVs, and even the summary itself often contains many OOV words. In contrast, the canonical RNN-based approaches often fail in such cases.

It is quite intriguing that CopyNet can often find important parts of the document, a behavior with the characteristics of extractive summarization, while it often generate words to “connect” those words, showing its aspect of abstractive summarization.

3 Single-turn Dialogue

In this experiment we follow the work on neural dialogue model proposed in [Shang et al. (2015, Vinyals and Le (2015, Sordoni et al. (2015], and test CopyNet on single-turn dialogue. Basically, the neural model learns to generate a response to user’s input, from the given (input, response) pairs as training instances. Dataset: We build a simple dialogue dataset based on the following three instructions:

Dialogue instances are collected from Baidu Tiebahttp://tieba.baidu.com with some coverage of conversations of real life， e.g., greeting and sports, etc.

are mined from the set, with possibly multiple responding patterns to one input.

Similar with the synthetic dataset, we enlarge the dataset by filling the slots with suitable subsequence (e.g. name entities, dates, etc.)

To make the dataset close to the real conversations, we also maintain a certain proportion of instances with the response that 1) do not contain entities or 2) contain entities not in the input. Experimental Setting: We create two datasets: DS-I and DS-II with slot filling on 173 collected patterns. The main difference between the two datasets is that the filled substrings for training and testing in DS-II have no overlaps, while in DS-I they are sampled from the same pool. For each dataset we use 6,500 instances for training and 1,500 for testing. We compare CopyNet with canonical RNNSearch, both character-based, with the same model configuration in Section 5.1.

We compare CopyNet and RNNSearch on DS-I and DS-II in terms of top-1 and top-10 accuracy (shown in Table 4), estimating respectively the chance of the top-1 or one of top-10 (from beam search) matching the golden. Since there are often many good responses to an input, top-10 accuracy appears to be closer to the real world setting.

As shown in Table 4, CopyNet significantly outperforms RNNsearch, especially on DS-II. It suggests that introducing the copying mechanism helps the dialogue system master the patterns in dialogue and correctly identify the correct parts of input, often proper nouns, to replicate in the response. Since the filled substrings have no overlaps in DS-II, the performance of RNNSearch drops significantly as it cannot handle words unseen in training data. In contrast, the performance of CopyNet only drops slightly as it has learned to fill the slots with the copying mechanism and relies less on the representation of the words.

As indicated by the examples in Figure 5, CopyNet accurately replicates the critical segments from the input with the copy-mode, and generates the rest of the answers smoothly by the generate-mode. Note that in (2) and (3), the decoding sequence is not exactly the same with the standard one, yet still correct regarding to their meanings. In contrast, although RNNSearch usually generates answers in the right formats, it fails to catch the critical entities in all three cases because of the difficulty brought by the unseen words.

Related Work

Our work is partially inspired by the recent work of Pointer Networks [Vinyals et al. (2015a], in which a pointer mechanism (quite similar with the proposed copying mechanism) is used to predict the output sequence directly from the input. In addition to the difference with ours in application, [Vinyals et al. (2015a] cannot predict outside of the set of input sequence, while CopyNet can naturally combine generating and copying.

CopyNet is also related to the effort to solve the OOV problem in neural machine translation. ?) introduced a heuristics to post-process the translated sentence using annotations on the source sentence. In contrast CopyNet addresses the OOV problem in a more systemic way with an end-to-end model. However, as CopyNet copies the exact source words as the output, it cannot be directly applied to machine translation. However, such copying mechanism can be naturally extended to any types of references except for the input sequence, which will help in applications with heterogeneous source and target sequences such as machine translation.

The copying mechanism can also be viewed as carrying information over to the next stage without any nonlinear transformation. Similar ideas are proposed for training very deep neural networks in [Srivastava et al. (2015, He et al. (2015] for classification tasks, where shortcuts are built between layers for the direct carrying of information.

Recently, we noticed some parallel efforts towards modeling mechanisms similar to or related to copying. ?) devised a neural summarization model with the ability to extract words/sentences from the source. ?) proposed a pointing method to handle the OOV words for summarization and MT. In contrast, CopyNet is more general, and not limited to a specific task or OOV words. Moreover, the softmaxCopyNet is more flexible than gating in the related work in handling the mixture of two modes, due to its ability to adequately model the content of copied segment.

Conclusion and Future Work

We proposed CopyNet to incorporate copying into the sequence-to-sequence learning framework. For future work, we will extend this idea to the task where the source and target are in heterogeneous types, for example, machine translation.

Acknowledgments

This work is supported in part by the China National 973 Project 2014CB340301.

References