Title: A COMPARE-AGGREGATE MODEL FOR MATCHING TEXT SEQUENCES

Abstract: Many NLP tasks including machine comprehension, answer selection and text entailment require the comparison between sequences. Matching the important units between sequences is a key to solve these problems. In this paper, we present a general "compare-aggregate" framework that performs word-level matching followed by aggregation using Convolutional Neural Networks. We particularly focus on the different comparison functions we can use to match two vectors. We use four different datasets to evaluate the model. We find that some simple comparison functions based on element-wise operations can work better than standard neural network and neural tensor network.

1. 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 Plot: ... Aragorn is crowned King of Gondor and taking Arwen as his queen before all present at his coronation bowing before Frodo and the other Hobbits . The Hobbits return to the Shire where Sam marries Rosie Cotton . ...

Qustion::

Where does Sam marry Rosie?

Candidate answers: 0) Grey Havens. 1) Gondor.

2) The Shire. 3) Erebor. 4) Mordor.

Question: can i have auto insurance without a car:

Ground-truth answer: yes, it be possible have auto insurance without own a vehicle. you will purchase what be call a name ... Another candidate answer: insurance not be a tax or merely a legal obligation because auto insurance follow a car... Table 1 : The example on the left is a machine comprehension problem from MovieQA, where the correct answer here is The Shire. The example on the right is an answer selection problem from InsuranceQA.

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-ofthe-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.1 

2. 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 elementwise operations can indeed perform very well on a number of sequence matching problems.

2.1. PROBLEM DEFINITION AND MODEL OVERVIEW:

The general setup of the sequence matching problem we consider is the following. We assume there are two sequences to be matched. We use two matrices Q ∈ R d×Q and A ∈ R d×A to represent the word embeddings of the two sequences, where Q and A are the lengths of the two sequences, respectively, and d is the dimensionality of the word embeddings. In other words, each column vector of Q or A is an embedding vector representing a single word. Given a pair of Q and A, the goal is to predict a label y. For example, in textual entailment, Q may represent a premise and A a hypothesis, and y indicates whether Q entails A or contradicts A. In question answering, Q may be a question and A a candidate answer, and y indicates whether A is the correct answer to Q.

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

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

1. Preprocessing: We use a preprocessing layer (not shown in the figure) to process Q and A to obtain two new matrices Q ∈ R l×Q and A ∈ R l×A . The purpose here is to use some gate values to control the importance of different words in making the predictions on the sequence pair. For example, q i ∈ R l , which is the i th column vector of Q, encodes the i th word in Q.

2.. Attention::

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

3.. Comparison::

We use a comparison function f to combine each pair of a j and h j into a vector t j .

4.. Aggregation::

We use a CNN layer to aggregate the sequence of vectors 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 some uncommon ones based on elementwise 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.2. PREPROCESSING AND ATTENTION:

Inspired by the use of gates in LSTM and GRU, we preprocess Q and A with the following formulas:

EQUATION

where is element-wise multiplication, and W i , W u ∈ R l×d and b i , b u ∈ R l are parameters to be learned. The outer product (• ⊗ e X ) produces a matrix or row vector by repeating the vector or scalar on the left for X times. Here σ

(W i Q + b i ⊗ e Q ) and σ(W i A + b i ⊗ e A )

act as gate values to control the degree to which the original values of Q and A are preserved in Q and A. For example, for stop words, their gate values would likely be low for tasks where stop words make little difference to the final predictions.

In this preprocessing step, the word order does not matter. Although a better way would be to use RNN such as LSTM and GRU to chain up the words such that we can capture some contextual information, this could be computationally expensive for long sequences. In our experiments, we only incorporated LSTM into the formulas above for the SNLI task.

The general attention (Luong et al., 2015) layer is built on top of the resulting Q and A as follows:

EQUATION

where W g ∈ R l×l and b g ∈ R l are parameters to be learned, G ∈ R Q×A is the attention weight matrix, and H ∈ R l×A are the attention-weighted vectors. Specifically, h j , which is the j th column vector of H, is a weighted sum of the column vectors of Q and represents the part of Q that best matches the j th word in A. Next we will combine h j and a j using a comparison function.

2.3. COMPARISON:

The goal of the comparison layer is to match each a j , which represents the j th word and its context in A, with h j , which represents a weighted version of Q that best matches a j . Let f denote a comparison function that transforms a j and h j into a vector 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:

NEURALNET (NN):

EQUATION

where matrix W ∈ R l×2l and vector b ∈ R l are parameters to be learned.

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

NEURALTENSORNET (NTN):

EQUATION

where tensor T [1...l] ∈ R l×l×l and vector b ∈ R l are parameters to be learned.

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 a j is to h j . For this reason, a more natural choice used in some previous work is Euclidean distance or cosine similarity between a j and h j . We therefore consider the following definition of f : EUCLIDEAN+COSINE (EUCCOS):

EQUATION

Note that with EUCCOS, the resulting vector 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 a j and 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 a j and h j .

To use something that is a good compromise 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 Mou et al. (2016) .

SUBTRACTION (SUB):

EQUATION

MULTIPLICATION (MULT):

EQUATION

Note that the operator is element-wise multiplication. For both comparison functions, the resulting vector t j has the same dimensionality as a j and 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 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:

SUBMULT+NN:

EQUATION

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.

2.4. AGGREGATION:

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

EQUATION

r ∈ R nl is then used for the final classification, where n is the number of windows in CNN. 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 and the ablation study shown in Table 4 .

3. EXPERIMENTS:



3.1. TASK-SPECIFIC MODEL STRUCTURES:

In all these tasks, we use matrix Q ∈ R d×Q to represent the question or premise and matrix

A k ∈ R d×A k (k ∈ [1, K]

) to represent the k th answer or the hypothesis. For the machine comprehension task MovieQA (Tapaswi et al., 2016) , there is also a matrix P ∈ R d×P that represents the plot of a movie. Here Q is the length of the question or premise, A k the length of the k th answer, and P the length of the plot.

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 r k to represent the resulting vector produced by Eqn. 9 for the k th answer. In order to select one of the K answers, we first define R = [r 1 , r 2 , . . . , r K ]. We then compute the probability of the k th answer to be the correct one as follows:

EQUATION

where

W s ∈ R l×nl , w ∈ R l , b s ∈ R l , b ∈ R are parameters to be learned.

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 P, the question Q and the answer A k . For each k, we first match Q and P and refer to the matching result at position j as t q j , as generated by one of the comparison functions f . Similarly, we also match A k with P and refer to the matching result at position j as t a k,j . We then define

t k,j = t q j t a k,j

, and

r k = CNN([t k,1 , . . . , t k,P ]).

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

The implementation details of the modes are as follows. 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 β 1 = 0.9 and β 2 = 0.999 to optimize the model. We do not use L2regularization. The main parameter we tuned is the dropout on the embedding layer. For WikiQA, which is a relatively small dataset, we also tune the learning rate and the batch size. For the others, we set the batch size to be 30 and the learning rate 0.002.

3.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::

• W-by-W Attention: The model by Rocktäschel et al. (2015) , who first introduced attention mechanism into text entailment. • match-LSTM: The model by Wang & Jiang (2016b) , which concatenates the matched words as the inputs of an LSTM. MovieQA: All the baselines we consider come from Tapaswi et al. (2016) 's work: • 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. • Cosine TFIDF: This model is similar to the previous method but uses bag-of-word with tf-idf scores to compute similarity. • SSCB TFIDF: Instead of using the sliding window method, a convolutional neural network is built on the sentence level similarities.

3.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 4) We find the preprocessing layer and the attention layer for word selection to be important in the "compare-aggregate" structure through the experiments of removing these two layers separately. We also see that for sequence matching with big difference in length, such as the MovieQA and InsuranceQA tasks, the attention layer plays a more important role. For sequence matching with smaller difference in length, such as the WikiQA and SNLI tasks, the pre-processing layer plays a more important role. (5) For the MovieQA, InsuranceQA and WikiQA tasks, our preprocessing layer is order-insensitive so that it will not take the context information into consideration during the comparison, but our model can still outperform the previous work with order-sensitive preprocessing layer. With this finding, we believe the word-by-word comparison part plays a very important role in these tasks. We will further explore the preprocessing layer in the future.

3.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 datasets 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.

4. 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; Luong et al., 2015) 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; Wan et al. , 

:

https://github.com/shuohangwang/SeqMatchSeq

CONCLUSIONSIn 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.

Figures and Tables:

Figure 1: The left hand side is an overview of the model. The right hand side shows the details about the different comparison functions. The rectangles in dark represent parameters to be learned. × represents matrix multiplication.

Figure 2: An visualization of the largest value of each dimension in the convolutional layer of CNN. The top figure is an example from the dataset MovieQA with CNN window size 5. The bottom figure is an example from the dataset InsuranceQA with CNN window size 3. Due to the sparsity of the representation, we show only the dimensions with larger values. The dimensionality of the raw representations is 150.



Table content: <table/>



Table content: <table/>

• LSTMN: Long short-term memorynetworks proposed byCheng et al. (2016). • Decomp Attention: Another "compare-aggregate" model proposed by Parikh et al. (2016). • EBIM+TreeLSTM: The state-of-the-art model proposed by Chen et al. (2016) on the SNLI dataset. InsuranceQA: • IR model: This model by Bendersky et al. (2010) learns the concept information to help rank the candidates. • 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. • 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. • IARNN-Occam: This model by Wang et al. (2016) adds regularization on the attention weights. • 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: • IARNN-Occam and IARNN-Gate as introduced before. • CNN-Cnt: This model by Yang et al. (2015) combines sentence representations built by a convolutional neural network with logistic regression. • ABCNN: This model is Attention-Based Convolutional Neural Network proposed by Yin et al. (2015). • CubeCNN proposed by He & Lin (2016) builds a CNN on all pairs of word similarity.

Table content: <table/>

) Overall, we can find that our general "compareaggregate" 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 dataset. (

Table content: <table/>

Peer review (iclr2017):
This paper proposes a compare-aggregate framework that performs word-level matching followed by aggregation with convolutional neural networks. It compares six different comparison functions and evaluates them on four datasets. Extensive experimental results have been reported and compared against various published baselines. The paper is well written overall. A few detailed comments: * page 4, line5: including a some -> including some * What*s the benefit of the preprocessing and attention step? Can you provide the results without it? * Figure 2 is hard to read, esp. when on printed hard copy. Please enhance the quality.