ACV-tree: A New Method for Sentence Similarity Modeling

1 Introduction

Sentence similarity is a fundamental metric to measure the degree of likelihood between a pair of sentences [Mikolov et al., 2013; Kenter et al., 2016; Conneau et al., 2017], and plays an important role for many applications [Pilehvar and Navigli, 2015; Iyyer et al., 2015; Jiang and Wu, 2017; Jiang et al., 2015]. Measuring sentence similarity is challenging due to the ambiguity and variability of linguistic expression, and thus has received much attention in recent years [Wieting et al., 2016; Pennington et al., 2014; Yu and Dredze, 2015]. A large number of prior works focused on feature engineering, and several types of sparse features have been shown to be useful, such as knowledge-based [Fellbaum, 1998] and corpus-based [Guo and Diab, 2012].

∗means the corresponding author.

Some methods also used the combination of various features and multi-task learning [Xu et al., 2014].

Recently, owing to the success of word embeddings [Bengio et al., 2003; Mikolov et al., 2013], researchers have attempted to study sentence similarity modeling via sentence embeddings. This approach has become a successful paradigm in natural language processing (NLP) community [Kenter et al., 2016; Wang et al., 2017]; and particularly some studies have used the attention weight mechanism to further enhance the performance [Wang et al., 2017; Arora et al., 2017]. In this line of works, most previous studies focused on learning semantic information and modeling it as a continuous vector, while the syntactic information of sentences are not fully exploited. On the other hand, prior works have shown the benefits of structured trees that include syntactic information [Croce et al., 2011; Severyn et al., 2013]. Yet, few works in this branch utilized the advantages of word embeddings and the attention weight mechanism.

Inspired by the above observations, in this paper we attempt to absorb the advantages of the above mentioned techniques, and develop a more efficient method. In a nutshell, our model uses a structured manner for sentence similarity modeling. It seamlessly integrates semantic information, syntactic information, and the attention weight mechanism. To measure similarity, we develops a new tree kernel, known as the ACVT kernel, that is tailored for our proposed structure and is designed for high operability. Our model can be used as a general framework, since one can view word embedding and attention weight as the building blocks of the framework, allowing users to replace them using other on-shelf (or more powerful, developed in the future) word embedding techniques and attention weight schemes. Besides, unlike most of sentence embedding-based models, our model can be free from time-consuming learning/training, once word embeddings are available. In this regard, it is the same as the methods in [Wieting et al., 2015; 2016], which are word embedding-based models. Nevertheless, our model can achieve better performance on almost all datasets used in our experiments, compared against the wordembedding based models.

To summarize, the main contributions of this paper are:

• We propose a new structure for sentence similarity modeling. Our model wisely combines syntactic informa-

tion, semantic features, and attention weight mechanism together, absorbing the merits of various techniques. Our model is easily understood and implemented, but without loss of effectiveness (Section 3.1).

• We developed the ACVT kernel that can allow us to efficiently perform similarity measure based on the proposed structure (Section 3.2).
• We conduct extensive experiments based on widely-used benchmark datasets (Section 4). The experimental results consistently demonstrate the superiorities and competitiveness of our proposed model.

2 Background

In this section we review several main techniques, for ease of understanding our proposed model.

Constituency-based parse tree: It is known as the constituency tree. The interior nodes are labelled by non-terminal categories of the grammar, while the leaf nodes are labelled by terminal categories [Carnie, 2012]. Each node in the tree is either a root node, a branch node, or a leaf node. A root node doesn't have any branches on top of it. Within a sentence, there is only ever one root node. A branch node is a parent node that connects to two or more child nodes. A leaf node, however, is a terminal node that does not dominate other nodes in the tree. The fundamental trait of the constituency tree is that we view sentence structure in terms of the constituency relation. Consider a sentence "Love makes man grow up" as an example, the constituency tree that represents the syntactic structure of this sentence is shown in Figure 1. Note that, by convention, the constituency tree usually uses some abbreviations. For example, "S for sentence", "N for noun", "NP for noun phrase", "V for verb", "VP for verb phrase", and so on.

Word embedding: Recently, a popular framework can allow users to represent words as continuous vectors that capture lexical and semantic properties of words [Bengio et al., 2003; Mikolov et al., 2013]. Usually, this technique is known as word embedding (a.k.a., distributed vector representation of words). Figure 2 shows an example of this framework (notice: for ease of understanding, the readers can rotate the figure 90 degrees). In brief, in this framework every word is mapped to a unique vector that is represented by a column in a matrix W. The column is indexed by position of the word in the vocabulary. The concatenation or sum of the vectors is then used as features for prediction of the next word in a sentence. More formally, given a sequence of training words w1,w2,w3, ...,wT , the objective of the word vector model is to maximize the average log probability 1 T ∑T -k t=k log p(wt|wt-k, ...,wt+k). The neural network based word embeddings are usually trained using stochastic gradient descent where the gradient is obtained via backpropagation. After the training converges, words with similar meaning are mapped to a similar position in the vector space. For example, "pretty" and "beautiful" are close to each other, whereas "beautiful" and "cup" are more distant. The prediction task is typically done via a multiclass classifier, such as softmax. It can be formulated as p(wt|wt-k, ...,wt+k) = eywt ∑t eyi . Each of yi is un-normalized log probability for each output word i, and it is computed as y = b + Uh(wt-k, ...,wt+k;W), where U, b are the softmax parameters, and h is constructed by a concatenation or average of word vectors extracted from matrix W.

Attention weight mechanism: Most of neural network based sentence representation models treat each word in sentences equally [Le and Mikolov, 2014; Kiros et al., 2015; Wieting et al., 2016]. This mechanism could be ineffective since it is inconsistent with the way that human read and understand sentences (i.e., reading some words superficially and paying more attention to others). So far, extensive studies have proven that word attributes, as represented by frequency, POS tag, length, Surprisal, etc., are all correlated with human reading time [Barrett et al., 2016]. Thereby, researchers have considered to assign words with different weights (known as attention weight mechanism), and there are many schemes to assign attention weights to words, such as smooth inverse frequency (SIF), term frequency-inverse document frequency (TF-IDF), Surprisal (SUR), POS tag (POS), CCG supertag (CCG) [Wang et al., 2017; Arora et al., 2017].

Tree kernel: Tree kernel is used to compute the similarity between structured trees. The main idea of tree kernels is to compute the number of common substructures between two trees T1 and T2 without explicitly considering the whole fragment space [Moschitti, 2006]. A tree kernel function over T1 and T2 is defined as

where NT1 and NT2 denote the set of nodes in T1 and T2, respectively. Note that, the ∆(·) function determines the richness of the kernel space and thus can yield different tree kernels. A representative tree kernel, known as partial tree kernel (PTK) [Moschitti, 2006], is highly related to our proposed tree kernel. Specifically, the ∆(·) function of PTK is computed as

where µ and λ are two decay factors: µ for the height of the tree, and λ for the length of the child sequences; cn1 (resp., cn2 ) refers to the list of children nodes of n1 (resp., n2); lm = min{length(cn1 ), length(cn2 )}; and ∆p(·) refers to the number of common subsequence whose length is p.

3 Model

In this section, we first cover the proposed structure, and then expatiate the new tree kernel tailored for computing similarity based on our structure.

3.1 ACV-tree

At a high level, the ACV-tree (Attention Constituency Vectortree) is similar to the so-called constituency tree, since (1) it is also tree-like structure with only a root denoting the sentence; (2) the internal nodes are some abbreviations for various constituencies such as NP and VP; and (3) the leaf nodes contain also the words. A major difference is that, the leaf nodes of ACV-tree contain also two other elements besides the words: one is a vector storing the semantic information of the corresponding word, the other is a real number denoting the weight of the corresponding word. In what follows, we address how to construct the ACV-tree in detail.

To construct the ACV-tree, one can follow several steps below. First, we determine "part of speech" for each word in the sentence. Second, we associate each word with (1) the word vector, which can be trained from unlabelled texts in large corpus, and (2) the attention weight, which can distinguish the contribution of different words to the semantic meaning of sentences. Third, we find the modification relations of each word in the sentence (e.g., in the sentence "a beautiful girl is over there", the word beautiful modifies the word girl). Finally, we link items according to the modification relation found by the previous step, until all the modifiers are attached to the modified constituents. Note that, in the process of "linking", different rules shall be used (e.g., when a modifier (or word) modifies a noun, the NP rule is to be used). As such, we obtain our ACV-tree as shown in Figure 3.

3.2 ACVTKernel

As mentioned before, tree kernel is used to compute similarity between structured trees. Yet, few existing tree kernels consider both the semantic information and the attention weight. To alleviate this issue, we develop a new tree kernel known as ACVT kernel (Attention Constituency Vector Tree kernel). Our tree kernel is tailored for computing similarity based on the proposed ACV-tree.

As same as almost all existing tree kernels, our ACVT kernel uses also the general framework. That is, Equation 1 is also used. The major difference between our tree kernel and existing tree kernels is the ∆(·) function. Let vec1 and wt1 (resp., vec2 and wt2) be the word vector and attention weight of node n1 (resp., n2). Our ∆(n1, n2) function is inspired by that of PTK (recall Section 2). Specifically, it is defined as

where cn1 , cn2 , lm, µ and λ have the same meaning as mentioned in Section 2; vec1 and vec2 are the word vector of n1 and n2, respectively; SIM(·, ·) is a function to measure the cosine similarity between vectors; Attweight = wt1 × wt2.

It remains to explain how to compute ∆p(·) as far as our tree kernel. To understand, consider cn1 = s1a and cn2 = s2b (a and b are the last children, s1 and s2 are subsequences of cn1 and cn2 , respectively), then one can solve ∆p(cn1 , cn2 ) by constructing a "recursive" function as follows.

where s1[1 : i] (resp., s2[1 : r]) is the subsequence of s1 (resp., s2) ranging from 1 to i (resp., from 1 to r); |s1| (resp., |s2|) is the length of s1 (resp., s2). Note that, here ∆(a, b) is computed using Equation 3, while ∆p-1(·) is recursively computed using Equation 4, and the recursive process stops when it reaches at the leaf node.

Algorithm 1 COMPSIM(T1,T2)

1: for each node ni in T1 do 2: if isLeaf(ni) = true then 3: for each node nj in T2 do 4: if isLeaf(nj) = true then 5: K[ni][nj ] ← Attweight × SIM(vec1, vec2); 6: else 7: K[ni][nj ] ← 0; 8: else 9: for each node nj in T2 do 10: if isLeaf(nj) = true then 11: K[ni][nj ] ← 0; 12: else 13: if ni has the same structure with nj then 14: K[ni ][nj ] ← COMPSIM(ni , nj ); 15: else 16: K[ni][nj ] ← 0; 17: ST1T2 ←compute the sum of K and normalize it; 18: return ST1T2

Algorithm: The pseudo-codes of our algorithm for computing similarity score between two trees T1 and T2 are shown in Algorithm 1. Our algorithm follows the paradigm in [Moschitti, 2006]. In a nutshell, it works as follows. First, it constructs a matrix K, and then compute the similarity of each node pair based on the rules in Equation 3. Note that, for the case of "otherwise" mentioned in Equation 3, our algorithm treats these two nodes as two new trees and compute their similarity (see Line 14). The final step is the same as that in [Moschitti, 2006], namely, we compute the sum of all values in K and normalize it, obtaining the similarity score.

4 Experiments

This section covers our experimental results. Our codes are available at the open-source code repository (https://github. com/yuquanle/Sentence-similarity-modeling.git).

4.1 Datasets and Experimental Settings

Datasets: Following prior works, we conduct experiments on 19 textual similarity datasets (http://ixa.si.ehu.eus/) that contain all the datasets from Semantic Textual Similarity (STS) tasks (2012-2015), except the SMT dataset in 2013 due to no permission. Each dataset contains many pairs of sentences (e.g. MSRvid dataset contains 750 pairs of sentences). These datasets cover a wide range of domains such as news, web forum, images, glosses, twitter. Table 1 summarizes these datasets (grouped by year). Please note that datasets with the same name in different years include different data.

Compared methods: In our experiments, we compare two sets of baselines (note that, most of models in the second category are classic and earlier than those in the first category):

(1) The models that use word embedding and/or sentence embedding techniques, including Glove [Pennington et al., 2014], PSL [Wieting et al., 2015], ST [Kiros et al., 2015], SCBOW [Kenter et al., 2016], PROJ [Wieting et al., 2016], PP-tfidf [Wang et al., 2017], DAN [Iyyer et al., 2015], LSTM [Gers and Schraudolph, 2002], RNN and iRNN [Wieting et al., 2016]. The results of the above methods are collected from [Wieting et al., 2016] except SCBOW from [Kenter et al., 2016] and PP-tfidf from [Wang et al., 2017].

(2) The models that are developed based on other techniques, including WUP [Wu and Palmer, 1994], RES [Resnik, 1995], LIN [Lin and others, 1998], JCN [Jiang and Conrath, 1997], and LCH [Leacock and Chodorow, 1998], ESA [Gabrilovich and Markovitch, 2007], ADW [Pilehvar and Navigli, 2015]. For ESA and ADW, they have many variants, we choose the best of them for comparison. The results of these classic methods are collected from [Pilehvar and Navigli, 2015].

Other settings: In our paper we use the Pearson's correlation between the predicted scores and the ground-truth scores as the evaluation criterion, which is the same as that in [Pilehvar and Navigli, 2015; Wang et al., 2017; Kenter et al., 2016]. The similarity score of sentence pair is from 0 to 5, where a scale of 5 means semantically equivalence, whereas 0 means complete unrelated. In our experiments, the hyperparameters µ=[0.1,0.2,...,0.9,1.0], and λ =[0.1,0.2,...,0.9,1.0], where the numbers in bold denote the default settings, unless otherwise stated. In our experiments, we implement our ACV-tree by using the Stanford Parser [Manning et al.,

2017] to generate the constituency tree of the sentence, and then attach the word vectors (i.e., lexical vectors) and the attention weights to the words in leaf nodes, for the sake of simplicity. Following prior works [Arora et al., 2017; Wang et al., 2017], we use the term frequency-inverse document frequency (TF-IDF) scheme to generate the attention weights. In the computation, we view each sentence as a document. The lexical vectors we used are provided by PARAGRAM-SL999 vectors, which is learned by PPDB and is the 300 dimensional Paragram embeddings tuned on SimLex999 dataset [Wieting et al., 2015].

4.2 Experimental Results

In what follows, we first compare with the methods that used word/sentence embedding techniques, since these methods are closest to our proposed model. Then, we check whether our model can beat classic methods. Finally, we study the impact of important parameters.

Word/sentence embedding-based methods: Table 2 shows the comparison results. It can be seen from this table that our proposed method (shorted as ACVT) gets favourable performance. Specifically, ACVT achieves the best performance on 12 out of 19 datasets (notice: in NLP community "12 out of 19" is an attractive result [Wieting et al., 2016]). Besides, we observe that for some datasets, although our method is not the best one, it is close to the best result (e.g., 12' OnWN, 14' tweet-news, 15' images). These evidences demonstrate that our proposed model is effective and competitive. Essentially, it implies that a combination of syntax, semantics and word attention mechanism could be a good choice for sentence similarity modeling. Nevertheless, we find that, on several datasets including 12' SMTeuroparl, 12' SMTnews, 14' deft-forum, and 15' belief, our method is inferior than the strongest competitor and the performance gap is larger than 0.05. It is interesting to understand why our method cannot performs well on these datasets.

As for 12' SMTeuroparl and 12' SMTnews datasets, it could be due to that some particular properties such as a large number of numerical items or special characters in these datasets weaken the performance of our model. For example, in the 12' SMTeuroparl dataset items like "5.30pm" and "(A5-0323/2000)" account for around 10% of the total test sample; in the 12' SMTnews dataset, items like "5.2%" and "24 May" account for around 8% of the total test sample. Note that, our model currently lacks for the strong ability to model numerical items and special characters (e.g., the sentence pair for phone numbers and email addresses).

Meanwhile, we find that the 14' deft-forum dataset contains the forum post sentences, and the 15' belief dataset contains the Belief pairs for which their source documents are English Discussion Forum data. It is easy to understand that people usually write sentences in forums without using rigorous syntactic format, and so the grammars used in these sentences could be not guaranteed; and particularly sentences are also doped with a large number of colloquial terms and network abbreviations. These factors lead to the construction of syntactic structure inaccurate, weakening the performance of our model.

Classic methods: As same as to [Pilehvar and Navigli, 2015], we here also use the SemEval-2012 Semantic Similarity task to compare these classic methods. Table 3 lists the compared results. It can be seen from the table, our method beats all these methods for almost all these datasets. This further demonstrates the competitiveness of our model. Note that, as for the SMTeuroparl dataset, our model is significantly inferior than ADW (i.e., the performance gap is about 0.12). The reason is the same as our previous analysis. That is, this dataset contains much more numerical items and special characters for which our model lacks for the strong ability to model.

Impact of parameters: Recall Section 3.2, our model is involved with two important parameters µ and λ, where µ is a decay factor for the height of the tree, and λ is a decay factor for the length of the child sequences. We here study the impact of these two parameters on the accuracy of our model. Note that, in this set of experiments, we also test two other methods: one is known as CT which did not incorporate the word embedding technique and the attention weight mechanism; the other is known as CVT, which did not incorporate the attention weight mechanism. This way, it might be helpful for us to study the effectiveness of various techniques used in our model. To compute the similarity, CT uses PTK, while CVT uses the simple version of ACVT kernel in which the "weight" part is removed by setting "Attweight = 1 in Equation 3". Next, we use the representative results to analyze the performance. Specifically, Figure 4 shows the compared results, these results are obtained by using the 13' OnWN dataset.

It can be seen from Figure 4 that ACVT basically outperforms CVT, and CVT basically outperforms CT. This demonstrates that the word embedding technique and the attention weight mechanism are useful when we combine them together. As for ACVT, we can see from Figure 4(a) that, it has the best performance when we set µ = 0.2 or 0.1 (compared to other settings such as µ = 0.9). On the other hand, from Figure 4(b) we can see that our model can obtain best performance when we set λ = 0.1. These facts justify our default settings for parameter µ and λ, recall Section 4.1.

One could be curious why the curve of ACVT goes down when µ (resp., λ) increases. The main reason could be the followings. When the parameter µ (resp., λ) turns smaller, nodes near to the leaf level (resp., nodes with long child sequences) shall be penalized much more. This way, it makes our model pay more attention to the key information of sentences, which usually located at the upper layers of the ACV-tree. As such, it has higher probability to match people's reading habit (i.e., when people compare two complex sentences, most of people tend toward comparing the main components and essential meaning of the sentences), and thus improves the accuracy.

5 RelatedWork

As mentioned before, own to the success of word embeddings [Bengio et al., 2003; Mikolov et al., 2013; Pennington et al., 2014; Wieting et al., 2015], much attention has been devoted to sentence similarity modeling via sentence embeddings in NLP community. For example, [Yu and Dredze, 2015] used the simple additional composition of the word vectors to achieve sentence embeddings. [Arora et al., 2017] obtained the sentence embeddings by a weighted average of the word vectors. [Kiros et al., 2015] proposed an encoderdecoder method that can reconstruct the surrounding sentences of an encoded passage. [Wieting et al., 2016] studied the general-purpose sentence embeddings by using the supervision from paraphrase databases. [Le and Mikolov, 2014; Wang et al., 2016] focused on learning "extra" sentence embeddings. [Wang et al., 2017] introduced the attention mechanism to improve sentence embeddings. [Kenter et al., 2016] presented the Siamese CBOW model for efficiently obtaining the high-quality sentence embeddings. In this line of works, complex nonlinear functions like convolutional neural networks [Kalchbrenner et al., 2014; Gan et al., 2017], and recurrent neural networks [Tai et al., 2015] were already widely used. Compared to this line of works, our work shares several common features with theirs: (1) our work is also attributed to the development of word embeddings, and (2) our work also addresses the issues related to sentence similarity. Nevertheless, our work is different from theirs in several features at least: (1) most of these works focused on learning semantic information and did not fully take the syntactic information of sentences into account, and (2) tree kernels are not covered in these works. In this paper we take full use of the syntactic information (besides the semantic information). Our model uses a structured manner for sentence similarity modeling; it integrates semantic information by word embeddings and syntactic information by constituency trees, and develops the ACV-tree kernel to measure similarity, achieving favourable performance (as shown in our experiments).

Another line of works that discussed syntactic and semantic kernels are also related to our work, since our work also encodes syntactic/semantic information represented by means of tree structures [Wu and Lowery, 2006; Moschitti, 2006; Severyn et al., 2013]. For example, [Moschitti, 2006] proposed a new tree kernel, namely the partial tree kernel; their method encodes syntactic parsing information represented by tree structures. [Collins and Duffy, 2001] discussed kernel methods for various natural language structures such as strings, trees, graphs or other discrete structures. [Croce et al., 2011] proposed efficient and powerful kernels for measuring the similarity between dependency structures. [Severyn et al., 2013] proposed a powerful feature-based model that relies on the kernel-based learning and simple tree structures. Compared with this line of works, although our work also uses tree structures, our work is different from theirs, since (1) word embeddings are not used in these works, and (2) the attention weight mechanism is not covered in these works. In our paper, the ACV-tree and the corresponding tree kernel are designed to address these issues.

6 Conclusions

This paper proposed a new method for sentence similarity modeling. The central idea of the proposed model is to combine syntactic information, semantic features, and attention weight mechanism together, absorbing the merits of various techniques. We compared our model with classic and state-of-the-art models on multiple STS tasks, and the results demonstrated that our model can achieve favourable performance. The major merits of our model are: (1) it can be used as a general framework, since techniques integrated in our model can be viewed as building blocks, allowing users to replace them using other on-shelf techniques or more powerful techniques developed in the future; and (2) unlike most of sentence embedding-based models, our model can be free from time-consuming learning/training, once word embeddings are available; some existing models essentially have also this merit, yet our model outperforms them in terms of performance, further reflecting the superiorities of our model.

Acknowledgments

This work was supported by the National Key Research and Development Program of China (No. 2016YFB0201900), and the NSFC (No. 61602166, 61772183, and 61572179).