Sentence Similarity using Recursive Embeddings and Dynamic Pooling

I was watching Richard Socher's lectures on CS224d: Deep Learning for Natural Language Processing at the Deep Learning Enthusiasts meetup at San Francisco couple of weeks ago. In one of the lectures, he describes this really cool idea for paraphrase detection using Dynamic Pooling and Unfolding Recursive Autoencoders. His use case was detecting mutual entailment in sentence pairs, but I figured that it might also be useful for computing sentence similarity, so I decided to try that out.

My data is a tiny corpus of 16 pairs of short sentences. The dataset came from a paper that described a rule-based algorithm that uses Wordnet and the Brown Corpus for its semantic smarts. Here is a link to my implementation of this algorithm. I later used the same dataset to re-implement another algorithm that uses word2vec and Word Mover's Distance. Neither algorithm gives importance to the structure of the sentence, although the second one does bring in some information about the context via word2vec. Socher's algorithm uses the structure of the sentence via its parse tree, and uses word embeddings, so it considers both the sentence structure and word context. So I thought it might be a good idea to see how it stacks up against the previous two.

Socher's algorithm goes something like this. Given a sentence pair, we first construct parse trees for them. The figure below shows the parse trees for a pair of sentences. Embeddings are constructed for each node in each tree using an Unfolding Recursive Autoencoder. The resulting embeddings are compared pairwise to generate a similarity matrix. Since the sentence pairs can be of arbitary length, the similarity matrix is passed through a Dynamic Pooling filter to reduce it to a fixed size square matrix. This matrix is then used as input to a classifier network to predict whether the sentences mutually entail one another.

Since my sentence collection was too small to generate a decent embedding out of, I decided to use the GoogleNews model (word2vec embeddings trained on about 100B words of Google News) to look up the words instead. For non-leaf nodes, I compute the vector as the sum of the vectors for the words in the phrase. I then compute the similarity matrix between the nodes for the two sentences. The similarity matrix for the sentences above looks like this.

I then apply a Dynamic Pooling filter on this matrix to reduce it to a 4x4 pooled similarity matrix. This involves splitting the input matrix into 16 blocks to which the pooling function can be applied. The paper deals with (the very common) situation where the input matrix is not perfecly divisible into 4x4 blocks by assigning the extra blocks to the last block. My approach is slightly different, I pad out the input matrix with the edge values in order to make it perfectly divisible - this allows me to use library functions that assume perfect divisibility. The corresponding pooled similarity matrix looks like this:

Instead of computing a binary label (entailed vs not entailed), I compute the similarity between the sentences as the sum of the elements of the pooled matrix divided by the number of elements (i.e, average pool). The similarity for the example sentence pair works out to 0.5079262884003104.

I now apply this modified algorithm to my small corpus of short sentence pairs. My input data has only 16 sentence pairs, with similarity scores that were provided as part of the original paper.

	lsent	rsent	sim
6	A glass of cider.	A full cup of apple juice.	0.678
11	Canis familiaris are animals.	Dogs are common pets.	0.362
10	Dogs are animals.	They are common pets.	0.738
14	I have a hammer.	Take some nails.	0.508
15	I have a hammer.	Take some apples.	0.121
13	I have a pen.	Where is ink?	0.129
12	I have a pen.	Where do you live?	0.000
0	I like that bachelor.	I like that unmarried man.	0.561
9	It is a dog.	It is a pig.	0.790
7	It is a dog.	That must be your dog.	0.739
8	It is a dog.	It is a log.	0.623
1	John is very nice.	Is John very nice?	0.977
3	Red alcoholic drink.	Fresh orange juice.	0.611
2	Red alcoholic drink.	A bottle of wine.	0.585
5	Red alcoholic drink.	Fresh apple juice.	0.420
4	Red alcoholic drink.	An English dictionary.	0.000

I used the Stanford CoreNLP to generate the nodes in the trees using the following Scala code.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64

package parsing import edu.stanford.nlp.ling.CoreAnnotations.SentencesAnnotation import edu.stanford.nlp.pipeline.StanfordCoreNLP import edu.stanford.nlp.pipeline.Annotation import edu.stanford.nlp.trees.LabeledScoredTreeNode import edu.stanford.nlp.trees.TreeCoreAnnotations.TreeAnnotation import scala.collection.JavaConversions._ import scala.collection.mutable.ArrayBuffer import scala.collection.mutable.LinkedHashSet import scala.io.Source import java.io.FileWriter import java.io.PrintWriter import java.util.Properties object SentenceNodes extends App { val props = new Properties props.put("annotators", "tokenize, ssplit, pos, lemma, ner, parse") val pipeline = new StanfordCoreNLP(props) val idx2sent = scala.collection.mutable.Map[String,String]() val texts = Source.fromFile("/path/to/orig_phrases.tsv") .getLines .zipWithIndex .map(indexedLine => { val Array(lsent, rsent, score) = indexedLine._1.split("\\|") idx2sent(indexedLine._2 + "L") = lsent idx2sent(indexedLine._2 + "R") = rsent List(lsent, rsent).mkString(" ") }) val sentPhrasesOut = new PrintWriter(new FileWriter( "/path/to/sent_phrases.txt")) texts.zipWithIndex.foreach(textIndexed => { val doc = new Annotation(textIndexed._1) pipeline.annotate(doc) val sentences = doc.get(classOf[SentencesAnnotation]) sentences.zipWithIndex.foreach(sentenceIndexed => { val tree = sentenceIndexed._1.get(classOf[TreeAnnotation]) // leaves first, then build up nodes val nodes = tree.postOrderNodeList() val phrases = nodes.map(node => { node.getLeaves( new java.util.ArrayList[LabeledScoredTreeNode]) .map(leaf => leaf.label().value()).mkString(" ") }) // remove terminating period .filter(node => !node.equals(".")) .map(node => node.replace(".", "")) .toList val dedupedPhrases = new LinkedHashSet[String]() dedupedPhrases.addAll(phrases) val sentId = textIndexed._2.toString + (if (sentenceIndexed._2 == 0) "L" else "R") sentPhrasesOut.println("%s\t%s".format( sentId, dedupedPhrases.mkString("|"))) }) }) sentPhrasesOut.flush sentPhrasesOut.close }

This writes out the phrases in the following format. Each sentence is identified by the sentence number and L or R depending on whether it is the first or second sentence in the pair. The second field is a pipe separated list of nodes in the tree. I do a post-order walk of the tree and discard duplicate nodes.

1 2 3 4 5

0L I|like|that|bachelor|that bachelor|like that bachelor|I like that bachelor 0R I|like|that|unmarried|man|unmarried man|that unmarried man|like that unmarried man|I like that unmarried man 1L John|is|very|nice|very nice|is very nice|John is very nice 1R Is|John|very|nice|very nice|?|Is John very nice ? ...

I then use gensim to load up its word2vec model using the GoogleNews data, and generate the word2vec embeddings for each of the nodes. Vectors for non-leaf nodes (containing multiple words) are the sum of the vectors for the constituent words.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22

from gensim.models import Word2Vec model = Word2Vec.load_word2vec_format( "/path/to/GoogleNews-vectors-negative300.bin.gz", binary=True) sent_phrases = open("/path/to/sent_phrases.txt", "rb") phrase_vecs = open("/path/to/phrase_vecs.txt", "wb") for line in sent_phrases: sent_id, phrase_str = line.strip().split("\t") phrases = phrase_str.split("|") for phrase in phrases: words = phrase.lower().split(" ") phrase_vec = np.zeros((1, 300)) for word in words: try: phrase_vec += model[word] except KeyError: continue phrase_vec_str = ",".join(["%.5f" % (float(x)) for x in phrase_vec[0]]) phrase_vecs.write("%s\t%s\t%s\n" % (sent_id, phrase, phrase_vec_str)) sent_phrases.close() phrase_vecs.close()

This produces another file that looks like this. The fields are the sentence ID, the phrase string and the corresponding 300 dimensional word2vec vector as a string.

1 2 3 4 5 6

0L I -0.08574,-0.00742,0.03452,0.09019,... 0L like 0.05687,0.07565,-0.00163,0.09980,... 0L that -0.01236,-0.02223,0.06554,0.03948,... 0L bachelor 0.02234,-0.05067,-0.11133,0.02895,... 0L that bachelor 0.00998,-0.07290,-0.04579,0.06843,... ...

Finally, I compute the similarity matrix for each sentence pair and run it through the Dynamic Pooling filter to produce the pooled similarity matrix, from which I compute the similarity score. I also generated heatmaps of the pooled similarity matrix for visualization.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67

from skimage.measure import block_reduce import matplotlib.pyplot as plt import numpy as np import pandas as pd # Dynamic pooling def dynamic_pool(X, out_dim, func): output_dim = np.ones(2) * out_dim # make sure input dimensions are splittable into output_dim pools xpad = X.shape[0] % out_dim ypad = X.shape[1] % out_dim # if not, pad with edge weights to make it splittable Xpadded = np.pad(X, ((0, out_dim - xpad), (0, out_dim - ypad)), "edge") # recalculate pooling block size xpool = Xpadded.shape[0] // out_dim ypool = Xpadded.shape[1] // out_dim # compute pooled matrix Xpooled = block_reduce(Xpadded, block_size=(xpool, ypool), func=func) return Xpooled # Create a Pandas dataframe for the phrase vectors # This is so we can filter on it for individual sentence pairs phrase_vecs_df = pd.read_csv("/path/to/phrase_vecs.txt", delimiter="\t", index_col=False, header=None, names=["sent_id", "phrase", "phrase_vec"]) results = [] for i in range(len(orig_df)): phrases_left = (phrase_vecs_df[phrase_vecs_df["sent_id"] == str(i) + "L"] ["phrase_vec"].values) Xvecs = np.zeros((phrases_left.shape[0], 300)) for j in range(phrases_left.shape[0]): Xvecs[j] = np.fromstring(phrases_left[j], dtype=float, sep=",") phrases_right = (phrase_vecs_df[phrase_vecs_df["sent_id"] == str(i) + "R"] ["phrase_vec"].values) Yvecs = np.zeros((phrases_right.shape[0], 300)) for j in range(phrases_right.shape[0]): Yvecs[j] = np.fromstring(phrases_right[j], dtype=float, sep=",") # compute similarity between elements from each sentence sims = np.zeros((Xvecs.shape[0], Yvecs.shape[0])) for j in range(Xvecs.shape[0]): for k in range(Yvecs.shape[0]): denom = np.linalg.norm(Xvecs[j], 2) * np.linalg.norm(Yvecs[k], 2) if denom == 0: sims[j, k] = 0 else: sims[j, k] = np.dot(Xvecs[j], Yvecs[k]) / denom pooled_sims = dynamic_pool(sims, 4, np.max) # retrieve original sentence lsent = id2sent[str(i) + "L"] rsent = id2sent[str(i) + "R"] similarity = np.sum(pooled_sims) / 16 results.append({"sent_id": i, "lsent": lsent, "rsent": rsent, "sim": similarity}) print(i, "//", lsent, "//", rsent, "//", "%.5f" % (similarity)) plt.figure(figsize=(1, 1)) plt.xticks([]) plt.yticks([]) plt.pcolor(pooled_sims) plt.show() # populate a Pandas dataframe from the results and display # :NOTE: we manually modified the HTML to add in the heatmaps results_df = pd.DataFrame(results) results_df = results_df.sort_values(["lsent", "sim"], ascending=[1, 0]) results_df.to_html()

The results are shown below. As with the input, I have sorted the resulting sentence pairs by left sentence and score in order to visually verify that the scores match up with intuition.

	lsent	rsent	sent_id	sim	heatmap
6	A glass of cider.	A full cup of apple juice.	6	0.392548
11	Canis familiaris are animals.	Dogs are common pets.	11	0.606134
10	Dogs are animals.	They are common pets.	10	0.734140
14	I have a hammer.	Take some nails.	14	0.409951
15	I have a hammer.	Take some apples.	15	0.347448
13	I have a pen.	Where is ink?	13	0.329194
12	I have a pen.	Where do you live?	12	0.296247
0	I like that bachelor.	I like that unmarried man.	0	0.613622
7	It is a dog.	That must be your dog.	7	0.611811
9	It is a dog.	It is a pig.	9	0.581342
8	It is a dog.	It is a log.	8	0.432356
1	John is very nice.	Is John very nice?	1	0.723129
2	Red alcoholic drink.	A bottle of wine.	2	0.454120
3	Red alcoholic drink.	Fresh orange juice.	3	0.451136
5	Red alcoholic drink.	Fresh apple juice.	5	0.346925
4	Red alcoholic drink.	An English dictionary.	4	0.095906

From the results, it looks like the similarity scores do capture the semantics of the sentences. For example, a dog seems semantically closer to a pig than a log, a hammer closer to nails than apples, and red alcoholic drink closer to wine than apple juice.

That's all I have for today. Hope you enjoyed reading this as much as I enjoyed building it.