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.
