A Compare-Aggregate Model for Matching Text Sequences

Introduction

Many natural language processing problems involve matching two or more sequences to make a decision. For example, in textual entailment, one needs to determine whether a hypothesis sentence can be inferred from a premise sentence (Bowman et al., 2015). In machine comprehension, given a passage, a question needs to be matched against it in order to find the correct answer (Richardson et al., 2013; Tapaswi et al., 2016). Table 1 gives two example sequence matching problems. In the first example, a passage, a question and four candidate answers are given. We can see that to get the correct answer, we need to match the question against the passage and identify the last sentence to be the answer-bearing sentence. In the second example, given a question and a set of candidate answers, we need to find the answer that best matches the question. Because of the fundamental importance of comparing two sequences of text to judge their semantic similarity or relatedness, sequence matching has been well studied in natural language processing.

With recent advances of neural network models in natural language processing, a standard practice for sequence modeling now is to encode a sequence of text as an embedding vector using models such as RNN and CNN. To match two sequences, a straightforward approach is to encode each sequence as a vector and then to combine the two vectors to make a decision (Bowman et al., 2015; Feng et al., 2015). However, it has been found that using a single vector to encode an entire sequence is not sufficient to capture all the important information from the sequence, and therefore advanced techniques such as attention mechanisms and memory networks have been applied to sequence matching problems (Hermann et al., 2015; Hill et al., 2016; Rocktäschel et al., 2015).

A common trait of a number of these recent studies on sequence matching problems is the use of a “compare-aggregate” framework (Wang & Jiang, 2016b; He & Lin, 2016; Parikh et al., 2016). In such a framework, comparison of two sequences is not done by comparing two vectors each representing an entire sequence. Instead, these models first compare vector representations of smaller units such as words from these sequences and then aggregate these comparison results to make the final decision. For example, the match-LSTM model proposed by Wang & Jiang (2016b) for textual entailment first compares each word in the hypothesis with an attention-weighted version of the premise. The comparison results are then aggregated through an LSTM. He & Lin (2016) proposed a pairwise word interaction model that first takes each pair of words from two sequences and applies a comparison unit on the two words. It then combines the results of these word interactions using a similarity focus layer followed by a multi-layer CNN. Parikh et al. (2016) proposed a decomposable attention model for textual entailment, in which words from each sequence are compared with an attention-weighted version of the other sequence to produce a series of comparison vectors. The comparison vectors are then aggregated and fed into a feed forward network for final classification.

Although these studies have shown the effectiveness of such a “compare-aggregate” framework for sequence matching, there are at least two limitations with these previous studies: (1) Each of the models proposed in these studies is tested on one or two tasks only, but we hypothesize that this general framework is effective on many sequence matching problems. There has not been any study that empirically verifies this. (2) More importantly, these studies did not pay much attention to the comparison function that is used to compare two small textual units. Usually a standard feedforward network is used (Hu et al., 2014; Wang & Jiang, 2016b) to combine two vectors representing two units that need to be compared, e.g., two words. However, based on the nature of these sequence matching problems, we essentially need to measure how semantically similar the two sequences are. Presumably, this property of these sequence matching problems should guide us in choosing more appropriate comparison functions. Indeed He & Lin (2016) used cosine similarity, Euclidean distance and dot product to define the comparison function, which seem to be better justifiable. But they did not systematically evaluate these similarity or distance functions or compare them with a standard feedforward network.

In this paper, we argue that the general “compare-aggregate” framework is effective for a wide range of sequence matching problems. We present a model that follows this general framework and test it on four different datasets, namely, MovieQA, InsuranceQA, WikiQA and SNLI. The first three datasets are for Question Answering, but the setups of the tasks are quite different. The last dataset is for textual entailment. More importantly, we systematically present and test six different comparison functions. We find that overall a comparison function based on element-wise subtraction and multiplication works the best on the four datasets.

The contributions of this work are twofold: (1) Using four different datasets, we show that our model following the “compare-aggregate” framework is very effective when compared with the state-of-the-art performance on these datasets. (2) We conduct systematic evaluation of different comparison functions and show that a comparison function based on element-wise operations, which is not widely used for word-level matching, works the best across the different datasets. We believe that these findings will be useful for future research on sequence matching problems. We have also made our code available online.https://github.com/shuohangwang/SeqMatchSeq

Method

In this section, we propose a general model following the “compare-aggregate” framework for matching two sequences. This general model can be applied to different tasks. We focus our discussion on six different comparison functions that can be plugged into this general “compare-aggregate” model. In particular, we hypothesize that two comparison functions based on element-wise operations, Sub and Mult, are good middle ground between highly flexible functions using standard neural network models and highly restrictive functions based on cosine similarity and/or Euclidean distance. As we will show in the experiment section, these comparison functions based on element-wise operations can indeed perform very well on a number of sequence matching problems.

We treat the problem as a supervised learning task. We assume that a set of training examples in the form of $(\mathbf{Q},\mathbf{A},y)$ is given and we aim to learn a model that maps any pair of $(\mathbf{Q},\mathbf{A})$ to a $y$.

An overview of our model is shown in Figure 1. The model can be divided into the following four layers:

Attention: We apply a standard attention mechanism on $\overline{\mathbf{Q}}$ and $\overline{\mathbf{A}}$ to obtain attention weights over the column vectors in $\overline{\mathbf{Q}}$ for each column vector in $\overline{\mathbf{A}}$. With these attention weights, for each column vector $\overline{\mathbf{a}}_{j}$ in $\overline{\mathbf{A}}$, we obtain a corresponding vector $\mathbf{h}_{j}$, which is an attention-weighted sum of the column vectors of $\overline{\mathbf{Q}}$.

Comparison: We use a comparison function $f$ to combine each pair of $\overline{\mathbf{a}}_{j}$ and $\mathbf{h}_{j}$ into a vector $\mathbf{t}_{j}$.

Aggregation: We use a CNN layer to aggregate the sequence of vectors $\mathbf{t}_{j}$ for the final classification.

Although this model follows more or less the same framework as the model proposed by Parikh et al. (2016), our work has some notable differences. First, we will pay much attention to the comparison function $f$ and compare a number of options, including a some uncommon ones based on element-wise operations. Second, we apply our model to four different datasets representing four different tasks to evaluate its general effectiveness for sequence matching problems. There are also some other differences from the work by Parikh et al. (2016). For example, we use a CNN layer instead of summation and concatenation for aggregation. Our attention mechanism is one-directional instead of two-directional.

In the rest of this section we will present the model in detail. We will focus mostly on the comparison functions we consider.

2 Preprocessing and Attention

Our preprocessing layer uses a recurrent neural network to process the two sequences. We use a modified version of LSTM/GRU in which we keep only the input gates for remembering meaningful words:

The attention layer is built on top of the resulting $\overline{\mathbf{Q}}$ and $\overline{\mathbf{A}}$ as follows:

3 Comparison

The goal of the comparison layer is to match each $\overline{\mathbf{a}}_{j}$, which represents the $j^{\text{th}}$ word and its context in $\mathbf{A}$, with $\mathbf{h}_{j}$, which represents a weighted version of $\mathbf{Q}$ that best matches $\overline{\mathbf{a}}_{j}$. Let $f$ denote a comparison function that transforms $\overline{\mathbf{a}}_{j}$ and $\mathbf{h}_{j}$ into a vector $\mathbf{t}_{j}$ to represent the comparison result.

A natural choice of $f$ is a standard neural network layer that consists of a linear transformation followed by a non-linear activation function. For example, we can consider the following choice:

Alternatively, another natural choice is a neural tensor network (Socher et al., 2013) as follows:

However, we note that for many sequence matching problems, we intend to measure the semantic similarity or relatedness of the two sequences. So at the word level, we also intend to check how similar or related $\overline{\mathbf{a}}_{j}$ is to $\mathbf{h}_{j}$. For this reason, a more natural choice used in some previous work is Euclidean distance or cosine similarity between $\overline{\mathbf{a}}_{j}$ and $\mathbf{h}_{j}$. We therefore consider the following definition of $f$:

Note that with EucCos, the resulting vector $\mathbf{t}_{j}$ is only a 2-dimensional vector. Although EucCos is a well-justified comparison function, we suspect that it may lose some useful information from the original vectors $\overline{\mathbf{a}}_{j}$ and $\mathbf{h}_{j}$. On the other hand, NN and NTN are too general and thus do not capture the intuition that we care mostly about the similarity between $\overline{\mathbf{a}}_{j}$ and $\mathbf{h}_{j}$.

To use something that is a good compromise between the two extreme cases, we consider the following two new comparison functions, which operate on the two vectors in an element-wise manner. These functions have been used previously by Tai et al. (2015).

Note that the operator $\odot$ is element-wise multiplication. For both comparison functions, the resulting vector $\mathbf{t}_{j}$ has the same dimensionality as $\overline{\mathbf{a}}_{j}$ and $\mathbf{h}_{j}$.

We can see that Sub is closely related to Euclidean distance in that Euclidean distance is the sum of all the entries of the vector $\mathbf{t}_{j}$ produced by Sub. But by not summing up these entries, Sub preserves some information about the different dimensions of the original two vectors. Similarly, Mult is closely related to cosine similarity but preserves some information about the original two vectors.

Finally, we consider combining Sub and Mult followed by an NN layer as follows:

In summary, we consider six different comparison functions: NN, NTN, EucCos, Sub, Mult and SubMult+NN. Among these functions, the last three (Sub, Mult and SubMult+NN) have not been widely used in previous work for word-level matching.

4 Aggregation

After we apply the comparison function to each pair of $\overline{\mathbf{a}}_{j}$ and $\mathbf{h}_{j}$ to obtain a series of vectors $\mathbf{t}_{j}$, finally we aggregate these vectors using a one-layer CNN (Kim, 2014):

Experiments

In this section, we evaluate our model on four different datasets representing different tasks. The first three datasets are question answering tasks while the last one is on textual entailment. The statistics of the four datasets are shown in Table 2. We will fist introduce the task settings and the way we customize the “compare-aggregate” structure to each task. Then we will show the baselines for the different datasets. Finally, we discuss the experiment results shown in Table 3.

For the SNLI (Bowman et al., 2015) dataset, the task is text entailment, which identifies the relationship (entailment, contradiction or neutral) between a premise sentence and a hypothesis sentence. Here $K=1$, and there are exactly two sequences to match. The actual model structure is what we have described before.

For the InsuranceQA (Feng et al., 2015) dataset, the task is an answer selection task which needs to select the correct answer for a question from a candidate pool. For the WikiQA (Yang et al., 2015) datasets, we need to rank the candidate answers according to a question. For both tasks, there are $K$ candidate answers for each question. Let us use $\mathbf{r}_{k}$ to represent the resulting vector produced by Eqn. 9 for the $k^{\text{th}}$ answer. In order to select one of the $K$ answers, we first define $\mathbf{R}=[\mathbf{r}_{1},\mathbf{r}_{2},\ldots,\mathbf{r}_{K}]$. We then compute the probability of the $k^{\text{th}}$ answer to be the correct one as follows:

For the machine comprehension task MovieQA, each question is related to Plot Synopses written by fans after watching the movie and each question has five candidate answers. So for each candidate answer there are three sequences to be matched: the plot $\mathbf{P}$, the question $\mathbf{Q}$ and the answer $\mathbf{A}_{k}$. For each $k$, we first match $\mathbf{Q}$ and $\mathbf{P}$ and refer to the matching result at position $j$ as $\mathbf{t}^{\text{q}}_{j}$, as generated by one of the comparison functions $f$. Similarly, we also match $\mathbf{A}_{k}$ with $\mathbf{P}$ and refer to the matching result at position $j$ as $\mathbf{t}^{\text{a}}_{k,j}$. We then define

To select an answer from the $K$ candidate answers, again we use Eqn. 10 to compute the probabilities.

2 Baselines

Here, we will introduce the baselines for each dataset. We did not re-implement these models but simply took the reported performance for the purpose of comparison.

SNLI: $\bullet$ W-by-W Attention: The model by Rocktäschel et al. (2015), who first introduced attention mechanism into text entailment. $\bullet$ match-LSTM: The model by Wang & Jiang (2016b), which concatenates the matched words as the inputs of an LSTM. $\bullet$ LSTMN: Long short-term memory-networks proposed by Cheng et al. (2016). $\bullet$ Decomp Attention: Another “compare-aggregate” model proposed by Parikh et al. (2016). $\bullet$ EBIM+TreeLSTM: The state-of-the-art model proposed by Chen et al. (2016) on the SNLI dataset.

InsuranceQA: $\bullet$ IR model: This model by Bendersky et al. (2010) learns the concept information to help rank the candidates. $\bullet$ CNN with GESD: This model by Feng et al. (2015) uses Euclidean distance and dot product between sequence representations built through convolutional neural networks to select the answer. $\bullet$ Attentive LSTM: Tan et al. (2016) used soft-attention mechanism to select the most important information from the candidates according to the representation of the questions. $\bullet$ IARNN-Occam: This model by Wang et al. (2016) adds regularization on the attention weights. $\bullet$ IARNN-Gate: This model by Wang et al. (2016) uses the representation of the question to build the GRU gates for each candidate answer.

WikiQA: $\bullet$ IARNN-Occam and IARNN-Gate as introduced before. $\bullet$ CNN-Cnt: This model by Yang et al. (2015) combines sentence representations built by a convolutional neural network with logistic regression. $\bullet$ ABCNN: This model is Attention-Based Convolutional Neural Network proposed by Yin et al. (2015). $\bullet$ CubeCNN proposed by He & Lin (2016) builds a CNN on all pairs of word similarity.

MovieQA: All the baselines we consider come from Tapaswi et al. (2016)’s work: $\bullet$ Cosine Word2Vec: A sliding window is used to select the answer according to the similarities computed through Word2Vec between the sentences in plot and the question/answer. $\bullet$ Cosine TFIDF: This model is similar to the previous method but uses bag-of-word with tf-idf scores to compute similarity. $\bullet$ SSCB TFIDF: Instead of using the sliding window method, a convolutional neural network is built on the sentence level similarities.

3 Analysis of Results

We use accuracy as the evaluation metric for the datasets MovieQA, InsuranceQA and SNLI, as there is only one correct answer or one label for each instance. For WikiQA, there may be multiple correct answers, so evaluation metrics we use are Mean Average Precision (MAP) and Mean Reciprocal Rank (MRR).

We observe the following from the results. (1) Overall, we can find that our general “compare-aggregate” structure achieves the best performance on MovieQA, InsuranceQA, WikiQA datasets and very competitive performance on the SNLI dataset. Especially for the InsuranceQA dataset, with any comparison function we use, our model can outperform all the previous models. (2) The comparison method SubMult+NN is the best in general. (3) Some simple comparison functions can achieve better performance than the neural networks or neural tensor network comparison functions. For example, the simplest comparison function EucCos achieves nearly the best performance in the MovieQA dataset, and the element-wise comparison functions, which do not need parameters can achieve the best performance on the WikiQA data set.

4 Further Analyses

To further explain how our model works, we visualize the max values in each dimension of the convolutional layer. We use two examples shown in Table 1 from MovieQA and InsuranceQA data sets respectively. In the top of Figure 2, we can see that the plot words that also appear in either the question or the answer will draw more attention by the CNN. We hypothesize that if the nearby words in the plot can match both the words in question and the words in one answer, then this answer is more likely to be the correct one. Similarly, the bottom one of Figure 2 also shows that the CNN will focus more on the matched word representations. If the words in one answer continuously match the words in the question, this answer is more likely to be the correct one.

Related Work

We review related work in three types of general structures for matching sequences.

Siamense network: These kinds of models use the same structure, such as RNN or CNN, to build the representations for the sequences separately and then use them for classification. Then cosine similarity (Feng et al., 2015; Yang et al., 2015), element-wise operation (Tai et al., 2015; Mou et al., 2016) or neural network-based combination Bowman et al. (2015) are used for sequence matching.

Attentive network: Soft-attention mechanism (Bahdanau et al., 2014) has been widely used for sequence matching in machine comprehension (Hermann et al., 2015), text entailment (Rocktäschel et al., 2015) and question answering (Tan et al., 2016). Instead of using the final state of RNN to represent a sequence, these studies use weighted sum of all the states for the sequence representation.

Compare-Aggregate network: This kind of framework is to perform the word level matching (Wang & Jiang, 2016a; Parikh et al., 2016; He & Lin, 2016; Trischler et al., 2016). Our work is under this framework. But our structure is different from previous models and our model can be applied on different tasks. Besides, we analyzed different word-level comparison functions separately.

Conclusions

In this paper, we systematically analyzed the effectiveness of a “compare-aggregate” model on four different datasets representing different tasks. Moreover, we compared and tested different kinds of word-level comparison functions and found that some element-wise comparison functions can outperform the others. According to our experiment results, many different tasks can share the same “compare-aggregate” structure. In the future work, we would like to test its effectiveness on multi-task learning.

References

Appendix A appendix

Following are the implementation details. The word embeddings are initialized from GloVe (Pennington et al., 2014). During training, they are not updated. The word embeddings not found in GloVe are initialized with zero.

The dimensionality $l$ of the hidden layers is set to be 150. We use ADAMAX (Kingma & Ba, 2015) with the coefficients $\beta_{1}=0.9$ and $\beta_{2}=0.999$ to optimize the model. The batch size is set to be 30 and the learning rate is 0.002. We do not use L2-regularization. The hyper-parameter we tuned is the dropout on the embedding layer. For WikiQA, which is relatively small dataset, we also tune the learning rate and batch size. For the convolutional window sizes for MovieQA, InsuranceQA, WikiQA and SNLI, we use , , and , respectively.