Logic Constrained Pointer Networks for Interpretable Textual Similarity

1 Introduction

Measuring semantic similarity between sentences has been one of the major problems towards text understanding. Many tasks including paraphrase identification [Socher et al., 2011], text entailment recognition [Heilman and Smith, 2010], etc. also utilize sentence similarity. Clearly, it has attracted a lot of attention in the NLP research community [Shao, 2017; Tai et al., 2015]. Semantic textual similarity (STS) dataset from SemEval 2012 [Agirre et al., 2012] has been one of the commonly used benchmark for sentence similarity task, which attempts at measuring the degree of semantic equivalence between two sentences. While recently proposed deep learning methods built on pretrained language models have shown great success for the task [Reimers and Gurevych, 2019], interpretability and explainability of the final scores remains a concern in general. [Agirre et al., 2015] proposed to formalize interpretable semantic textual similarity (henceforth, iSTS) as an alignment between pairs of segments across the two sentences at SemEval 2016. This is also linguistically well motivated because similarity between sentences has been observed to be decomposable [Sultan et al., 2015] over segments and the overall similarity is a combined measure of similarity on parts (words, chunks, etc). The problem of interpretable semantic textual similarity is to provide an interpretation or explanation of semantic similarity between two texts (usually sentences). We consider chunking to be a preprocessing step and assume that the sentences are already chunked. Not all chunks in the sentences may be aligned and number of aligned chunks gives indication to the overall similarity between the sentences. Figure 1 provides an illustrative example.

∗Equal contribution.

†Now at Amazon.

We introduce a novel logic statement constrained gated pointer network model to align constituents of the two sentences, aiding in interpretation of semantic relationships between sentences. Our model uses a pointer network [Vinyals et al., 2015] with a sentinel gating function to align the constituent chunks, which are represented using BERT. We improve this base model with a loss function to equally penalize misalignments in both sentences, ensuring bidirectional alignments. Finally, we introduce first-order logic constraints based on ConceptNet as well as syntactic knowledge to aid in training and inference.

Experiments over two different SemEval datasets indicate that our proposed approach achieves state of the art results on both the datasets. We achieve F1 score of 97.73 on headlines and 96.32 on images, an improvement of 7.8% and 5.6% over the previous best results, respectively. Through ablation studies, we also find that the proposed logical constraints help boost the performance on both the datasets. Further, since getting alignments for training the model is costly, we also perform a cross-domain experiment (training on headlines, testing on images and vice-versa) and find that even in this scenario, we achieve F1 scores of 96.16 and 94.80 on these datasets, comprehensively beating state-of-the-art methods.

2 RelatedWork

Discovering semantic relations in text is a widely studied problem in Natural Language Processing (NLP) with various tasks. One such task is STS which was first introduced as a shared task in [Agirre et al., 2012]. Several approaches to this task have been developed [B¨ar et al., 2012; Jimenez et al., 2012], with deep learning based methods achieving the most success recently [Shao, 2017; Tai et al., 2015; Reimers and Gurevych, 2019]. [Shao, 2017] train a CNNbased sentence encoder on the STS task. [Conneau et al., 2017] and [Pagliardini et al., 2018] train sentence encoders on alternative similar tasks to aid in learning. Many such approaches make use of an alignment (implicitly or explicitly) between parts of sentences (e.g. [H¨anig et al., 2015; Sultan et al., 2015]) with the assumption that composing subsequence alignments can lead to better identification of semantic similarity. Alignments also lend a notion of interpretability of sentence level similarity judgements.

Alignment of parts of sentence pairs is also well studied in domains such as Machine Translation [Koehn et al., 2003] and Paraphrase Recognition [Chang et al., 2010]. The iSTS [Agirre et al., 2015] shared task focuses on predicting chunk alignments as a means to lend interpretability to STS. [Banjade et al., 2015] develop a rule-based alignment system using standard textual features such as parts-of-speech (POS) tags. [Kazmi and Sch¨uller, 2016] realize a similar rule engine in Answer Set Programming, allowing reordering of rules. [Konopik et al., 2016] pose chunk alignment as a binary classification task supported with rules. [Li and Srikumar, 2016] build an alignment model using an integer linear program (ILP), with scoring functions learnt using both alignment and sentence similarity tasks. Chunk alignment is a central piece in this line of work and is also the focus of our work.

Incorporating external information from large labelled or unlabelled corpora into neural models for NLP has been shown to improve task performance. One common way is to use pre-trained word or sentence embeddings. In this work, we experiment with GloVe [Pennington et al., 2014] and BERT [Devlin et al., 2019] based chunk representations and show ablations in model performance. Another external source of information is in the form of structured knowledge from knowledge bases like ConceptNet [Speer et al., 2017] and Pharaphrase Database (PPDB) [Pavlick et al., 2015]. Structured knowledge can be incorporated in the form of firstorder logic statements without expensive direct supervision. Logic rules provide a declarative language to express such structured knowledge and thus have been used to guide neural networks in several ways recently. [Towell et al., 1990] and [Franc¸a et al., 2014] build networks from a rule set expressed in propositional logic. [Hu et al., 2016] make use of teacherstudent network formulation to distill logic rules into network parameters. This approach does not restrict models to specialized networks but requires a specialized training procedure. [Li and Srikumar, 2019] introduce logic statements to constraint labelled neurons (e.g. attention nodes) which can be used in general neural networks. We introduce constraints in the framework which are applicable to the chunk alignment task.

3 Approach

Given two sentences, let us denote these by x = (x1, x2, . . . , xn) and y = (y1, y2, . . . , ym), where xi and yj are chunks (i.e contiguous words) in x and y, respectively. The problem of iSTS is to predict an alignment between chunks zi,j ∈ {0, 1} indicating if xi and yj are aligned. We consider a supervised setting in which the ground truth alignment ai,j ∈ {0, 1} is specified in the training data. Not all chunks in x are aligned to a chunk in y (and vise-versa). We consider these non-aligned chunks to be aligned to a special φ chunk. Therefore, the problem is to generate an alignment from x to y ∪ {φ} and from y to x ∪ {φ}. Figure 2 shows a block level view of our model. Next, we explain each of the individual components in further details.

3.1 Chunk Representation

Given a chunked sentence, we obtain chunk representation from BERT [Devlin et al., 2019] bert-base-uncased variant by concatenation of contextualized embedding of first and last word of a chunk. We use summation of last 4-layers from BERT to represent a word as higher layers of BERT capture semantic features as suggested in [Jawahar et al., 2019]. We use BERT WordPiece model for sub-words representations corresponding to a word which are averaged to realize the word final representation. We also experiment with GloVe where the chunk representation is obtained by averaging the word embeddings, as is common in literature.

3.2 Alignment with Gated Pointer Networks

Extending previous work [Vinyals et al., 2015], we design a pointer network (PN) to model alignment between chunks of sentences x and y. The alignment between chunks xi and yj is modelled as

where W1, W2, W3 and v are model parameters, f is a nonlinearity (we use tanh) and ⊗ is the Hadamard product. The W matrices are of the same dimension and project chunk embeddings to a lower dimension d; v is a d-dimension vector. Thus, the PN 'points' from chunks in x to chunks in y. However, we consider the pointers as unidirectional and interpret Equation (1) as alignment between yj and xi as well. To allow for non-aligned chunks, we consider such chunks to be aligned to a special empty chunk φ and treat its representation as a parameter of the model. Specifically with a little abuse of notation, we model non-aligned chunks xi and yi using bxi,φ and byφ,i , respectively, given by

Using Equations (1) and (2), we define a gating function that models xi's alignment to y and yi's alignment to x,

where c1, c2 and d1, d2 are parameters of the model. Intuitively, gx i captures how well xi is aligned to its best alignment (with high θi,j) in y in comparison to φ. Mathematically, gx i → 1 when xi is better aligned to some yj in comparison to φ. Let zi,j ∈ {0, 1} indicate if xi is aligned to yj (zi,j = 1). Using Equations (3) and (1), we model the probability of the event zi,j as,

Thus, the alignment probability of xi and yj is proportional to product of xi being aligned to some chunk in y, yj being aligned to some chunk in x and xi being aligned to yj .

The probability of non-alignment of xi (aligned to φ) is proportional to 1-gx i and probability of non-alignment of yj is proportional to 1 - gy j . Thus

Equations (4) and (5) are appropriately normalised by passing them through a softmax layer. Mathematically,

where [·; ·] indicates concatenation.

Therefore, the alignment is modeled for every index i in x because p(zi,·) is a distribution for every i. The model is trained by minimizing the categorical cross-entropy loss between correct (ai,j) and predicted alignment (zi,j). However, this loss alone fails to capture the non-alignment for chunks in y because the PN 'points' from x to y and therefore cannot model φ aligning to multiple yj's. We address this separately by binary cross-entropy loss between pφ,j and non-aligned chunks in y indicated by aφ,j . The combined loss is addition of these two losses,

where C1, C2 are positive hyperparameters capturing the relative cost sensitivity between the two loss functions.

3.3 Improving Alignments with Bidirectionality

For a pair of similar sentences, usually a certain part of a sentence is semantically similar to only a particular part of the other sentence. Thus, the alignment is usually one-to-one between chunks in the two sentences. We observed this phenomenon in SemEval 2016 dataset on iSTS, where approximately 85% of alignments between the chunks in the sentence pair are one-to-one. However, the gated PN formulation we developed in Section 3.2 falls short in modelling one-to-one alignments. This is because while alignment for every chunk xi in x is modelled explicitly as a distribution zi,·, thus encouraging a hard alignment to a chunk yj (because of the cross-entropy loss), the alignments for yj are unconstrained (e.g the model might easily choose to align two chunks xi and xk to yj). Therefore, the one-to-one alignment for yj's is violated because it is not being modelled, and is implicitly derived from z·,j's. We illustrate this in Figure 3 with an example from the SemEval dataset.

We address this shortcoming of our gated PN by ensuring bidirectionality, i.e.,both zi,· and z·,j are distributions for all i, j. Moreover, xi's alignment to yj and yj's alignment to xi is modeled by the same event zi,j with probability pi,j. Alignment between two sentences can be viewed as solution to an optimal transport problem where the transportation cost is defined by the activations in Equations (4) and (5). This results in a combinatorial optimization and is difficult to solve in an end-to-end manner with a neural network.

We propose an approximate solution to this problem using Sinkhorn distance [Cuturi, 2013] which is an entropy regularized approximation of optimal transportation problem. Mathematically, Sinkhorn distance is a solution p to,

where p is a distribution, H(p) is the entropy of p, C is a transportation cost matrix and λ is the strength of the entropy regularization. The constraints in Equation (8) ensure that p is a distribution over alignments from x to y and from y to x. We define the cost matrix C as,

In transportation problems, the cost matrix is defined as nonnegative. To ensure non-negativity of the cost matrix we subtract the minimum of each row from the entries of the matrix to define, Ci,j = Ci,j -minj Ci,j ∀i. We use Cuturi's iterative row and column normalization algorithm [Cuturi, 2013] to solve Equation (8). To ensure convergence of Cuturi's algorithm [Cuturi, 2013], a small constant ϵ is added to every entry of the cost matrix. The parameters of the model are learnt in an end-to-end manner. The backward pass to compute gradients differentiates through Cuturi's algorithm. This is achievable with automatic differentiation because the algorithm consists of only multiplication and division steps over differentiable terms.

Now both pi,· and p·,j form distributions and the modified formulation can be viewed as a bidirectional PN which points from both x to y and from y to x. The loss function is categorical cross-entropy on p. The two-way alignment distribution encourages one-to-one alignments for chunks in both x and y,

Equation (9) can be viewed as summation of categorical cross-entropy of distributions pi,· and p·,j. Figure 4 illustrates the improvement in alignment on the example given in Figure 3.

3.4 Side-supervision with FOL

Guiding neural networks with structured external knowledge has been shown to improve predictive performance by complementing powerful data-driven learning. This knowledge provides a mechanism to regulate the learning process by encoding human intention without expensive supervision. A number of techniques have been proposed to incorporate declarative logic statements into networks, such as data augmentation [Collobert et al., 2011], knowledge distillation [Hu et al., 2016], etc. [Li and Srikumar, 2019] propose a promising technique to augment existing networks by constraining activations of named neurons (e.g. attention layer) using declarative rules. Motivated by their approach, in this work, we propose two intuitive rules for the chunk alignment task,

• R1: Two chunks should be aligned if they are related by any of the relations: Synonym, Antonym, IsA, SimilarTo, RelatedTo, DistinctFrom or FormOf. The relational information to realize this rule is obtained from ConceptNet.
• R2: Two chunks should be aligned if they are syntactically similar. This similarity is defined based on overlap of parts-of-speech tags of their ancestor or children nodes in dependency parse trees of the two sentences.

These rules are based on structured knowledge and are expressed as declarative statements. We define predicates Reli,j and SynSimi,j to indicate whether chunk xi is related to chunk yj according to R1 or R2, respectively. Let Ai,j denote the model decision that chunk xi is related to chunk yj. We use the following constraints:

For rule R1, we experiment with two resources, ConceptNet and the paraphrase database (PPDB). In the ConceptNet knowledge base permitted relation types are [Synonym, Antonym, IsA, SimilarTo, RelatedTo, DistinctFrom, FormOf] which closely correspond to the alignment categories specified in the task [Agirre et al., 2015]. We also experiment with PPDB since a large number of alignments are paraphrases. As complete chunks may not always be available, we evaluate using bigram and unigram alignments from these sources as indicators of chunk alignments. We ignore non-content words by restricting the alignment to content words W, identified as having POS tags [ADJ, ADV, INTJ, NOUN, PROPN, VERB, NUM].

We next discuss the details of syntactic similarity measure which constitutes R2. Using the dependency tree of x and y obtained from Spacy [Honnibal and Montani, 2017], we define syntactic similarity measure between two words w1 ∈ xi and w2 ∈ yj as an average of (i). Jaccard similarity between parts-of-speech (POS) tags of ancestor nodes of w1 and w2, (ii). Jaccard similarity between POS tags of children nodes of w1 and w2 and (iii). Boolean to indicate if both w1 and w2 are roots of the corresponding dependency trees. The syntactic similarity between xi and yj is defined as the average syntactic similarity between words in xi to its best aligned word (maximum similarity) in yj. A high value of syntactic similarity between xi, yj indicates a possible alignment.

Using the logic statements from Equation (10) we constraint the pointer network decisions by adding a positive constant mi,j to the activations in Equation (1) if either R1 or R2 is true on (i, j) (i.e. a rule aligns xi and yj),

where mi,j captures whether the antecedent Reli,j or SynSimi,j or both are true. From an implementation perspective, we unroll the FOL statement to propositional statements for all examples. The modified alignment strength θ′ in Equation (11) replaces θ and affects both the gating functions in Equation (3) and combined alignment probability in Equation (4). This saturates the probability of the event zi,j to 1 constraining the network output towards rule predictions. The importance of FOL rules is controlled using the ρ hyperparameter.

4 Experiments

We compare the proposed model against existing work on iSTS. In line with much of previous research on this task, we report experimental results on the SemEval 2016 interpretable textual similarity dataset.

4.1 Dataset Description

We use SemEval 2016 Task 2 dataset for interpretable semantic textual similarity [Agirre et al., 2016]. It consists of examples from two domains; News Headlines and Flickr Images. In both domains, there are 1, 125 sentence pairs, with a 2:1 split between train and test sets. Each sentence pair is annotated with the alignments between the chunks, similar to example in Figure 1. In this work, we focus on predicting the alignment between the chunks. Additionally, the chunking of the sentences is pre-specified in both train and test examples, therefore we directly use the chunking in this work. For more detailed specifications, please refer to [Agirre et al., 2016].

4.2 Baselines &Models

We compare against the best task submissions on the two datasets as well as a followup work achieving SOTA results. Inspire [Kazmi and Sch¨uller, 2016] is a rule-based alignment system extending the earlier NeRoSim [Banjade et al., 2015] rule engine. It introduces Answer Set Programming to build an extended rule set. This model was the winning entry of the SemEval task on the News Headlines dataset. UWB [Konopik et al., 2016] pose alignment as binary classification between all possible chunk pairs using lexical, syntactic, semantic and WordNet-based features, with impossible alignments handled via rules. This model was the winning entry of the SemEval task on the Flickr Images dataset. Lastly, we compare against [Li and Srikumar, 2016] which models chunk alignment using an ILP. Scoring functions for the ILP are calculated using a structured loss to penalize alignments far-off from ground truth along with two additional terms for chunk and sentence similarities. To the best of our knowledge, currently this method achieves SOTA results for the iSTS task on the SemEval dataset.

To thoroughly investigate the proposed approach, we report the experimental results across four different configurations of the proposed model, as described in Table 2. These settings capture the relative merit of each of the model components. The evaluation metric is F1 measure as per the SemEval task description.

4.3 Evaluation

We report F1 measure across the model ablations and baselines discussed in Section 4.2. The results for the baselines are reported from the corresponding papers owing to unavailability of the their code bases. We trained each of the model configurations on train part of the SemEval dataset and did hyperparamter tuning on training set F1. We fixed the entropy regularization strength λ to 0.6 across all experiments and changing it had little effect on results. The embedding dimension for Glove based representations was 300 and for BERT was 768. To avoid over-fitting, we employed early stopping using training set F1 as a metric and stop the training if training set F1 does not improve over 5 successive epochs. In Table 2, we report the average test set F1 over 3 runs for each model configurations (corresponding to the best hyperparameter setting) on news headlines and images dataset. For example, the best identified hyperparameter configuration corresponding to M4 are; ρ = 2 and PN dimension of 100 for experiments on headlines dataset and ρ = 2 and PN dimension of 150 for experiments on images dataset. The results for M4 and M3 in comparison to M2 and M1 indicate that BERT based chunk embeddings are superior to Glove based representation. The constraints improve the performance of the BERT based model as highlighted by superior performance of M4 over M3. The improvements using constraints are much more visible on the images dataset. Both BERT chunk representation based models are significantly better than SOTA results [Li and Srikumar, 2016; Konopik et al., 2016]. We see an improvement of 5.6% on News headlines dataset and 7.8% on Flickr images dataset for M4 over SOTA results. The Glove representation based model even without FOL constraints (M2) is comparable to SOTA method on both the datasets.

4.4 Qualitative Evaluation

We illustrate the qualitative merits of different components of our model on two examples by investigating the alignment produced by the four modelling configurations we introduced in Section 4.2. Figure 5 shows that modelling bidirectionality is important as is evident from large number of alignment errors made by M1 in comparison to M2. However, using BERT based contextual embeddings for chunks in the sentences leads to improved representations for chunks and both M3 and M4 correctly align all the chunks.

Figure 6 shows the effect of including real-world knowledge in the form of FOL statements in the model. The chunks pair "in N Waziristan" and "in Pakistan" are aligned by the FOL statements retrieved from ConceptNet. This is because ConceptNet holds the real-world knowledge that "Waziristan" is a part of "Pakistan" and relates them. BERT embeddings alone may not encode enough information to relate "Waziristan" and "Pakistan" and M3 fails to align both these chunks correctly, while M4 owing to the activated FOL constraint gives the correct alignment.

4.5 Cross-domain Experiments

While the proposed approach achieves significant improvements over the previous baselines, a natural question arises - how would this approach be applicable on a new sentence similarity dataset to provide interpretability, when no chunk alignments are available to train the model in the target domain? To answer this, we attempted a cross-domain experiment, where we train on headlines, test on images, and vice versa (i.e., do not utilize training examples from the target domain). Remarkably, even in this setting, using our best model M4, we achieve F1 scores of 96.16 and 94.80 on headlines and images datasets, respectively, outperforming the previous SOTA results. Note that no hyperparameter tuning was performed on the target domain.

5 Conclusion

We propose a novel pointer network for the task of interpretable sentence similarity along with logic constraints based on ConceptNet and syntactic knowledge. Experiments over benchmark datasets show a large performance improvement for the alignment task, even in the cross-domain setting, proving the general applicability of the proposed approach.

It was encouraging to see that the logical constraints imposed using external knowledge helped the model performance, and it would be interesting to check how the whole framework can be employed to improve performance for the sentence similarity task, while providing interpretability and explanation for the model decision.