Accessing ML models in Spark from various NLP toolkits

NLTK users know that a lot of functionality, even seemingly basic ones like sentence and word tokenization, are dependent on machine learning models pre-trained on default corpora. These models are available as a separate download because of their size. Making these models available to your code is simple -- just a single one time nltk.download() command as described on this page.

The situation is slightly more complicated in case of a distributed environment such as Apache Spark. The general idea is that you partition your data processing across multiple nodes in a cluster and then bring back the processed datasets. We use the web-based Databricks analytics platform on top of Spark, which allows us, among other things, a notebook based development environment that hides some of the boilerplate associated with straight Spark code. Databricks notebooks support Python, but NLTK does not come pre-installed.

In order to use NLTK to process text within Databricks, you need to install NLTK on your cluster. That's not too hard as long as you have the necessary permissions, the process is described on this Databricks documentation page. The PyPI package name I used was "nltk==3.2.5". This will make NLTK available to the master node and all the worker nodes in your cluster.

Generally the very first step in analyzing text data is to tokenize it into sentences and words, and as I mentioned earlier, this needs the appropriate ML model to be available on the workers. Back when I first started working on this, a colleague mentioned that he just added the nltk.download() command to the map call, so it was called for each record on the worker. He accompanied this hint with a brilliant peice of insight -- that the nltk.download() call has code to check if the download has already happened, so subsequent calls after the first one are just pass-throughs.

I thought about this a bit, and realized that I could make the process even more efficient, by calling nltk.download() once per partition using mapPartitions instead of once per record using map. So that's what I did, the code below loads the NLTK models once per partition and tokenizes the text into sentences, then words. Also, once loaded, these models are available to subsequent calls made within the same partition, as shown in the POS tagging done in a subsequent map call.

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

def download_and_tokenize(iter): import nltk def tokenize(line): image_id, caption_text = line.split("\t") tokens = [] for sent in nltk.sent_tokenize(caption_text): for word in nltk.word_tokenize(sent): tokens.append(word) return (image_id, tokens) # for each partition nltk.download("all") # for each record within partition for line in iter: yield tokenize(line) def postag(rec): id, tokens = rec tokentags = nltk.pos_tag(tokens) return (id, tokentags) captions_rdd = (sc.textFile("/path/to/input/text/file") .mapPartitions(download_and_tokenize) .map(postag) ) captions_rdd.take(10)

Of late, the SpaCy NLP library has become more popular, and I think for good reason. It is faster and has more functionality, and is being actively developed based on user feedback. Like NLTK, SpaCy does not come pre-installed on Databricks either, you can install it using the PyPI loader using the package name "spacy==2.0.9". The main problem with my trying to use SpaCy in the same way as NLTK was that I did not know of a Python analog to nltk.download(). SpaCy has a set of 2 commands, a "python -m spacy download en" call on the command line followed by a spacy.load("en") Python call as described on the SpaCy Models and Languages page. While this works very nicely in a single user environment, the only way I could think of to do this in Spark was to login separately into each of the workers and download the model on each, obviously not the most desirable approach in an automated notebook environment.

I had some spare cycles, so I went digging in the code, and found that the "python -m spacy ..." call corresponds to identically named functions in the spacy.cli package. So this allowed me to use SpaCy in Databricks using code as shown below. The idea is the same as for NLTK. We download the model and load it into SpaCy once per partition. Just like NLTK, the spacy.cli.download() call checks for the existence of the model and its dependencies using the pip installer. In addition, my code also checks for existence, so it will bypass the download() call altogether after the first time on each worker. Also unlike NLTK, SpaCy batches up basic operations in a single call for performance as shown in SpaCy lightning tour code example, so we don't have a separate POS tagging step here. But the model should be accessible to subsequent map calls similar to the NLTK case here as well.

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

def download_tokenize_and_postag(iter): import os import spacy def tokenize_and_postag(line): image_id, caption_text = line.split("\t") doc = nlp(caption_text) token_tags = [] for token in doc: token_tags.append((token.text, token.pos_)) return (image_id, token_tags) # for each partition model_dir = spacy.util.get_data_path() if not os.path.exists(os.path.join(model_dir.as_posix(), "en")): spacy.cli.download("en") nlp = spacy.load("en", parser=False) # for each record within partition for line in iter: yield tokenize_and_postag(line) captions_rdd = (sc.textFile("/path/to/input/text/file") .mapPartitions(download_tokenize_and_postag) ) captions_rdd.take(10)

Java based toolkits are easier to work with, at least with respect to model files, since they often embed their model into their JARs and access it as a Resource instead of a File. So the models are automatically distributed to workers along with the code by attaching the JAR file to the cluster. So the user of these toolkits does not have to do anything special to use these libraries. As an example, here is some code to do tokenization and POS tagging using the Spark-NLP library from John Snow Labs. The code is based on Spark-NLP 2.11-1.2.3, and is part of the pipeline described on their quickstart page.

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

import com.johnsnowlabs.nlp._ import com.johnsnowlabs.nlp.annotators._ import com.johnsnowlabs.nlp.annotators.sbd.pragmatic.SentenceDetectorModel import com.johnsnowlabs.nlp.annotators.pos.perceptron.PerceptronApproach import org.apache.spark.sql.functions._ import org.apache.spark.ml.Pipeline case class Caption(id: String, text: String) val captionDF = sc.textFile("/path/to/input/text/file") .map(line => { val Array(id, text) = line.split("\t") Caption(id, text) }) .toDF val assembleDoc = new DocumentAssembler() .setInputCol("text") .setOutputCol("document") val sentTokenize = new SentenceDetectorModel() .setInputCols(Array("document")) .setOutputCol("sentence") val wordTokenize = new RegexTokenizer() .setInputCols(Array("sentence")) .setOutputCol("token") .setPattern("[^ \\(\\)\\/%]+") // default pattern is \S+ too loose val posTagger = new PerceptronApproach() .setInputCols(Array("sentence", "token")) .setOutputCol("pos") .setCorpusPath("/anc-pos-corpus/1400.txt") // see spark-nlp issue 41 val finishDoc = new Finisher() .setInputCols("token") .setCleanAnnotations(false) val pipeline = new Pipeline() .setStages(Array( assembleDoc, sentTokenize, wordTokenize, posTagger, finishDoc )) val transformedDF = pipeline.fit(captionDF) .transform(captionDF)

Notice that the sentence tokenizer and POS tagger uses models, but no mention is made of loading them up-front. The POS tagger has to explicitly set the corpus path. If you look at the file in the repository, you will see it's just a POS-tagged dataset, so presumably the tagger trains itself inline on startup. The SentenceModel on the other hand, seems to use a pre-trained model, which is also loaded once on startup. This would happen once per worker JVM as part of the object's initialization, so this mechanism is even more performant than using mapPartitions().

Lastly, I wanted to mention yet another approach to doing NLP tasks on Spark that we use internally. The approach is similar to the one SpaCy uses -- we have a set of annotators, each of which does a set of tasks. For example, our GeniaAnnotator uses models trained against the GENIA corpus, and outputs sentence, phrase and word boundaries, POS tags and lemmas. An example of annotations output by the annotator is shown below.

These annotations convert unstructured text data into structured annotations, and can be consumed by downstream applications in a language agnostic manner. The annotation building framework has too many hooks into internal systems to be effectively open-sourced, but we do plan on providing exemplar output from our annotators for OA-STM-Corpus, our hand-annotated mini-corpus of scientific open access articles. Our team has also open-sourced AnnotationQuery, a framework that allows you to compose interesting queries on these annotations, either locally or on Spark.

Classification with Positive Examples only

I recently came across a problem where I had to identify drug names in text. The drug names could be generic (eg, acetominophen, aspirin, etc) or brand names (Tylenol, Prilosec, etc). The thing about drug names is that they "look" slightly different from normal English words, so I thought that perhaps I could exploit this and build n-gram features for each word in the text and compare it to a model based on n-gram features of known drug names.

For a list of drug names, I used the drugbank.xml file, which contains 7,779 generic and 9,251 brand names. These are my positive examples, ie, I can derive from this set what a drug name should look like. However, I don't have a corresponding list of negative examples. What I do have are the words in the text, which can be thought of as unlabeled examples. The book Web Data Mining by Bing Liu describes several methods to build classifiers out of these inputs - this post describes how I used one of them.

In the past (before I learned of this approach), I would treat this as an unsupervised problem, comparing n-grams of unknown words against the n-gram set I had generated from the drugbank.xml file. Words that had a similarity above some (manually derived) threshold would be considered drugs, others not.

With my newly acquired knowledge, the approach is as follows. First, consider the unlabeled data as negative examples and combine it with the positive examples. Build a classifier, then use the predicted probability of the known positive examples as a lower bound to label the unlabeled examples with predicted probabilities above this lower bound. Repeat until the number of positive examples converge. Finally, use this classifier against another set of data.

The first step is to extract the generic and brand names from the XML file. Because of the size of the file, I decided to use a SAX parser. Here's the code. It parses the generic and drug names out of this file and writes it into a pair of text files.

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

# Source: parse_drugbank.py # -*- coding: utf-8 -*- from sklearn.externals import joblib import drug_ner_utils as dnu import os import xml.sax class DrugXmlContentHandler(xml.sax.ContentHandler): def __init__(self): xml.sax.ContentHandler.__init__(self) self.tags = [] self.generic_names = [] self.brand_names = [] def startElement(self, name, attrs): self.tags.append(name) def endElement(self, name): self.tags.pop() def characters(self, content): breadcrumb = "/".join(self.tags) if breadcrumb == "drugbank/drug/brands/brand": self.brand_names.append(content) if breadcrumb == "drugbank/drug/name": self.generic_names.append(content) def write_list_to_file(lst, filename): fout = open(os.path.join(dnu.DATA_DIR, filename), 'wb') for e in lst: fout.write("%s\n" % (e.encode("utf-8"))) fout.close() source = open(os.path.join(dnu.DATA_DIR, "drugbank.xml"), 'rb') handler = DrugXmlContentHandler() xml.sax.parse(source, handler) source.close() write_list_to_file(handler.generic_names, "generic_names.txt") write_list_to_file(handler.brand_names, "brand_names.txt") generic_fd = dnu.ngram_distrib(handler.generic_names, dnu.GRAM_SIZE) brand_fd = dnu.ngram_distrib(handler.brand_names, dnu.GRAM_SIZE) joblib.dump(generic_fd, os.path.join(dnu.DATA_DIR, "generic_fd.pkl")) joblib.dump(brand_fd, os.path.join(dnu.DATA_DIR, "brand_fd.pkl")) # Plot visualizations dnu.plot_ngram_distrib(generic_fd, 30, "Generic", dnu.GRAM_SIZE) dnu.plot_ngram_distrib(brand_fd, 30, "Brand", dnu.GRAM_SIZE)

This code produces a visualization of the distribution for the top 30 (by frequency) 3-grams, for generic names and brand names. Notice that the distribution is quite different, which is why we used different classifiers to detect each class.


The drug_ner_utils file contain some common functions and constants that are used by multiple processes. They all have fairly descriptive names, so it should be easy to infer what they do. The str_to_ngram function takes a string and the n-gram size to split it into and returns a list of ngrams. The ngram_distrib creates a frequency distribution from a list of tokens, and the plot_ngram_distrib function plots a visualization out of the first (most frequent) n-gram frequencies of the distribution. The truncate_fd is for selecing the first n-gram frequencies, and the vectorize takes a pair of files (positive and unlabeled), where each line corresponds to a single word, represented as a sequence of n-gram "words", and builds the X and y matrices in the format required by the classifier. Here is the 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 65 66 67 68 69

# Source: drug_ner_utils.py # -*- coding: utf-8 -*- from operator import itemgetter from sklearn.feature_extraction.text import CountVectorizer import matplotlib.pyplot as plt import nltk import numpy as np import os import string DATA_DIR = "../../data/drug_ner" GRAM_SIZE = 3 PUNCTS = set([c for c in string.punctuation]) NUMBERS = set([c for c in "0123456789"]) def is_punct(c): return c in PUNCTS def is_number(c): return c in NUMBERS def str_to_ngrams(instring, gram_size): ngrams = [] for word in nltk.word_tokenize(instring.lower()): try: word = "".join(["S", word, "E"]).encode("utf-8") cword = [c for c in word if not(is_punct(c) or is_number(c))] ngrams.extend(["".join(x) for x in nltk.ngrams(cword, gram_size)]) except UnicodeDecodeError: pass return ngrams def ngram_distrib(names, gram_size): tokens = [] for name in names: tokens.extend(str_to_ngrams(name, gram_size)) return nltk.FreqDist(tokens) def plot_ngram_distrib(fd, nbest, title, gram_size): kvs = sorted([(k, fd[k]) for k in fd], key=itemgetter(1), reverse=True)[0:nbest] ks = [k for k, v in kvs] vs = [v for k, v in kvs] plt.plot(np.arange(nbest), vs) plt.xticks(np.arange(nbest), ks, rotation="90") plt.title("%d-gram frequency for %s names (Top %d)" % (gram_size, title, nbest)) plt.xlabel("%d-grams" % (gram_size)) plt.ylabel("Frequency") plt.show() def truncate_fd(fd, nbest): kvs = sorted([(k, fd[k]) for k in fd], key=itemgetter(1), reverse=True)[0:nbest] return {k:v for k, v in kvs} def vectorize(ufile, pfile, max_feats): text = [] labels = [] fno = 0 for fname in [ufile, pfile]: f = open(os.path.join(DATA_DIR, fname), 'rb') for line in f: text.append(line.strip()) labels.append(fno) fno = fno + 1 f.close() vec = CountVectorizer(min_df=0.0, max_features=max_feats, binary=True) X = vec.fit_transform(text) y = np.array(labels) return X, y, vec

The next step is converting the extracted names into corresponding n-grams. We use 3-grams for this experiment. The following code reads the files we had written out in the drugbank.xml parsing step and writes out corresponding files of n-grams. Each word in the input file are converted to a space separated sequence of 3-grams, similar to words in a sentence, and the format the downstream vectorizer expects. This results in 10,000 brand name words, 10,365 generic name words, and 199,018 unlabeled words.

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

# Source: ngram_convert.py # -*- coding: utf-8 -*- import drug_ner_utils as dnu import os def build_ngram_text(infile, outfile): fin = open(os.path.join(dnu.DATA_DIR, infile), 'rb') fout = open(os.path.join(dnu.DATA_DIR, outfile), 'wb') for line in fin: for word in line.strip().split(): ngrams = dnu.str_to_ngrams(word, dnu.GRAM_SIZE) if len(ngrams) > 0: fout.write("%s\n" % " ".join(ngrams)) fin.close() fout.close() build_ngram_text("generic_names.txt", "generic_positive.txt") build_ngram_text("brand_names.txt", "brand_positive.txt") build_ngram_text("raw_data.txt", "unlabeled.txt")

The next step is called cotraining. It uses the unlabeled set as input, setting it to be the negative example set, and adding to it the positive examples, and training a classifier. The hope is that the classifier will separate the unlabeled set into one that is "close" to the positive set and one that is not. The classifier reports, for each row, the probability that it is in the positive class. If we find the minimum probability for the positive examples (minus outliers), we can consider any row in the unlabeled set as positive if its associated prediction probability is higher than this minimum value. We repeat this step multiple times until the number of positive examples plateau. At each step, we feed it the output targets from the previous step. Here is the code to do this.

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

# Source: co_train.py # -*- coding: utf-8 -*- from sklearn.externals import joblib from sklearn.svm import LinearSVC import drug_ner_utils as dnu import matplotlib.pyplot as plt import numpy as np import os MAX_ITERS = 10 EST_POSITIVE = 0.7 MAX_FEATURES = 3000 def conservative_min(xs): # remove outliers q25, q75 = np.percentile(xs, [25, 75]) iqr = q75 - q25 lb = q25 - (1.5 * iqr) ub = q75 + (1.5 * iqr) xs_con = xs[(xs >= lb) & (xs <= ub)] return np.min(xs_con) for borg in ["generic", "brand"]: X, y, vec = dnu.vectorize("unlabeled.txt", "%s_positive.txt" % (borg), MAX_FEATURES) y_pos = y[y == 1] num_positives = [y_pos.shape[0]] clf = LinearSVC() clf.fit(X, y) num_iters = 0 while (num_iters < MAX_ITERS): print("Iteration #%d, #-positive examples: %d" % (num_iters, num_positives[-1])) confidence = clf.decision_function(X) min_pos_confidence = conservative_min(confidence[y_pos]) y_pos = np.where(confidence >= min_pos_confidence)[0] # if y_pos.shape[0] <= num_positives[-1]: # break num_positives.append(y_pos.shape[0]) y = np.zeros(y.shape) y[y_pos] = 1 clf = LinearSVC() clf.fit(X, y) joblib.dump(y, os.path.join(dnu.DATA_DIR, "y_%s_%d.pkl" % (borg, num_iters))) num_iters += 1 # visualize output plt.plot(np.arange(len(num_positives)), num_positives, "b-") plt.plot(np.arange(len(num_positives)), X.shape[0] * EST_POSITIVE * np.ones(len(num_positives)), 'r--') plt.title("Cotraining for %s classifier (%d features)" % (borg.title(), MAX_FEATURES)) plt.xlabel("Iterations") plt.ylabel("#-Positives") plt.show()

The number of positive examples derived from this process is plotted on the charts below, the first for generic names and the second for brand names. Both classifiers plateau at around the Iteration #2. Our code pickles the classifier at each iteration so we can retrieve the one we need later.


Finally, we apply this classifier to actually detect drug names in our text. Based on the charts above, we choose the generic classifier from iteration #3 and the brand classifier from iteration #4, and pass in vectorized strings for classification. The accuracy scores for the generic and brand classifier (on training data) are 88.4% and 89.4% respectively. However, neither classifier works well on the test data. This is because my unlabeled data is very strongly positive - by my rough estimate, the number of words that are either generic or drug name is about 70% - so the classifier tends to mark everything as positive.

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

# Source: apply_model.py from sklearn.externals import joblib from sklearn.feature_extraction.text import CountVectorizer from sklearn.svm import LinearSVC import drug_ner_utils as dnu import numpy as np import os def vectorize_ngrams(ngrams, vocab): vec = np.zeros((1, len(vocab))) for ngram in ngrams: if vocab.has_key(ngram): vec[0, vocab[ngram]] = 1 return vec X, y, generic_vec = dnu.vectorize("unlabeled.txt", "generic_positive.txt", 100) y = joblib.load(os.path.join(dnu.DATA_DIR, "y_generic_4.pkl")) generic_clf = LinearSVC() generic_clf.fit(X, y) print("Score for generic classifier: %.3f" % (generic_clf.score(X, y))) X, y, brand_vec = dnu.vectorize("unlabeled.txt", "brand_positive.txt", 100) y = joblib.load(os.path.join(dnu.DATA_DIR, "y_brand_3.pkl")) brand_clf = LinearSVC() brand_clf.fit(X, y) print("Score for brand classifier: %.3f" % (brand_clf.score(X, y))) fraw = open(os.path.join(dnu.DATA_DIR, "raw_data.txt"), 'rb') i = 0 for line in fraw: line = line.strip().lower() annotated = [] for word in line.split(): ngrams = dnu.str_to_ngrams(word, dnu.GRAM_SIZE) Xgen = generic_vec.transform([" ".join(ngrams)]) Xbrand = brand_vec.transform([" ".join(ngrams)]) is_generic = generic_clf.predict(Xgen) is_brand = brand_clf.predict(Xbrand) if is_generic == 1: annotated.append("<GENERIC>" + word + "</GENERIC>") elif is_brand == 1: annotated.append("<BRAND>" + word + "</BRAND>") else: annotated.append(word) print("Input: %s" % (line)) print("Output: %s" % (" ".join(annotated))) i += 1 if i > 10: break fraw.close()

I attempted to correct for this by co-training with very high number of features (3000), so the classifier would learn to be more conservative in its decisions, and then retraining the test classifiers with much smaller number of features (100 and 50 for generic and brand classifiers respectively). I also tried scaling the data before training the classifiers, that did result in an increase in classifier accuracy (on training data) to 98% and 95%, but the resulting classifiers still marked almost all words as drugs, so it was not very effective.

So I guess its back to the drawing board for this one. However, it was interesting to learn of a method that allows us to build classifiers with no negative examples.

The code for this work is spread out across different files, and correspond to a specific step in the process. Communication is via flat files and pickled objects dropped by the component at the previous step. The code can be found on my GitHub project, the drugbank.xml file can be downloaded, and you will have to supply your own unlabeled data.

Computing Semantic Similarity for Short Sentences

A reader recently recommended a paper for me to read - Sentence Similarity Based on Semantic Nets and Corpus Statistics. I found the algorithm quite interesting and I ended up implementing it. While I was not able to replicate the results exactly, my results did agree with results you would intuitively expect. I describe the algorithm and my implementation in this post.

My implementation is built with Python and Natural Language Tool Kit (NLTK). The Semantic Net referred to in the paper is Wordnet and the Corpus Statistics are from the Brown Corpus, both of which are available using NLTK's corpus API. Here is the complete code, which I explain below.

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 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206 207 208 209 210 211 212 213 214 215 216 217 218 219 220 221 222 223 224 225 226 227 228 229 230 231 232 233 234 235 236 237 238 239 240 241 242 243 244 245 246 247 248 249 250 251 252 253 254 255 256 257 258 259 260 261 262 263 264 265 266 267 268 269 270 271 272 273 274 275 276 277 278 279 280 281 282 283 284 285 286 287 288 289 290 291 292 293 294 295 296 297 298 299 300 301 302

from __future__ import division import nltk from nltk.corpus import wordnet as wn from nltk.corpus import brown import math import numpy as np import sys # Parameters to the algorithm. Currently set to values that was reported # in the paper to produce "best" results. ALPHA = 0.2 BETA = 0.45 ETA = 0.4 PHI = 0.2 DELTA = 0.85 brown_freqs = dict() N = 0 ######################### word similarity ########################## def get_best_synset_pair(word_1, word_2): """ Choose the pair with highest path similarity among all pairs. Mimics pattern-seeking behavior of humans. """ max_sim = -1.0 synsets_1 = wn.synsets(word_1) synsets_2 = wn.synsets(word_2) if len(synsets_1) == 0 or len(synsets_2) == 0: return None, None else: max_sim = -1.0 best_pair = None, None for synset_1 in synsets_1: for synset_2 in synsets_2: sim = wn.path_similarity(synset_1, synset_2) if sim > max_sim: max_sim = sim best_pair = synset_1, synset_2 return best_pair def length_dist(synset_1, synset_2): """ Return a measure of the length of the shortest path in the semantic ontology (Wordnet in our case as well as the paper's) between two synsets. """ l_dist = sys.maxint if synset_1 is None or synset_2 is None: return 0.0 if synset_1 == synset_2: # if synset_1 and synset_2 are the same synset return 0 l_dist = 0.0 else: wset_1 = set([str(x.name()) for x in synset_1.lemmas()]) wset_2 = set([str(x.name()) for x in synset_2.lemmas()]) if len(wset_1.intersection(wset_2)) > 0: # if synset_1 != synset_2 but there is word overlap, return 1.0 l_dist = 1.0 else: # just compute the shortest path between the two l_dist = synset_1.shortest_path_distance(synset_2) if l_dist is None: l_dist = 0.0 # normalize path length to the range [0,1] return math.exp(-ALPHA * l_dist) def hierarchy_dist(synset_1, synset_2): """ Return a measure of depth in the ontology to model the fact that nodes closer to the root are broader and have less semantic similarity than nodes further away from the root. """ h_dist = sys.maxint if synset_1 is None or synset_2 is None: return h_dist if synset_1 == synset_2: # return the depth of one of synset_1 or synset_2 h_dist = max([x[1] for x in synset_1.hypernym_distances()]) else: # find the max depth of least common subsumer hypernyms_1 = {x[0]:x[1] for x in synset_1.hypernym_distances()} hypernyms_2 = {x[0]:x[1] for x in synset_2.hypernym_distances()} lcs_candidates = set(hypernyms_1.keys()).intersection( set(hypernyms_2.keys())) if len(lcs_candidates) > 0: lcs_dists = [] for lcs_candidate in lcs_candidates: lcs_d1 = 0 if hypernyms_1.has_key(lcs_candidate): lcs_d1 = hypernyms_1[lcs_candidate] lcs_d2 = 0 if hypernyms_2.has_key(lcs_candidate): lcs_d2 = hypernyms_2[lcs_candidate] lcs_dists.append(max([lcs_d1, lcs_d2])) h_dist = max(lcs_dists) else: h_dist = 0 return ((math.exp(BETA * h_dist) - math.exp(-BETA * h_dist)) / (math.exp(BETA * h_dist) + math.exp(-BETA * h_dist))) def word_similarity(word_1, word_2): synset_pair = get_best_synset_pair(word_1, word_2) return (length_dist(synset_pair[0], synset_pair[1]) * hierarchy_dist(synset_pair[0], synset_pair[1])) ######################### sentence similarity ########################## def most_similar_word(word, word_set): """ Find the word in the joint word set that is most similar to the word passed in. We use the algorithm above to compute word similarity between the word and each word in the joint word set, and return the most similar word and the actual similarity value. """ max_sim = -1.0 sim_word = "" for ref_word in word_set: sim = word_similarity(word, ref_word) if sim > max_sim: max_sim = sim sim_word = ref_word return sim_word, max_sim def info_content(lookup_word): """ Uses the Brown corpus available in NLTK to calculate a Laplace smoothed frequency distribution of words, then uses this information to compute the information content of the lookup_word. """ global N if N == 0: # poor man's lazy evaluation for sent in brown.sents(): for word in sent: word = word.lower() if not brown_freqs.has_key(word): brown_freqs[word] = 0 brown_freqs[word] = brown_freqs[word] + 1 N = N + 1 lookup_word = lookup_word.lower() n = 0 if not brown_freqs.has_key(lookup_word) else brown_freqs[lookup_word] return 1.0 - (math.log(n + 1) / math.log(N + 1)) def semantic_vector(words, joint_words, info_content_norm): """ Computes the semantic vector of a sentence. The sentence is passed in as a collection of words. The size of the semantic vector is the same as the size of the joint word set. The elements are 1 if a word in the sentence already exists in the joint word set, or the similarity of the word to the most similar word in the joint word set if it doesn't. Both values are further normalized by the word's (and similar word's) information content if info_content_norm is True. """ sent_set = set(words) semvec = np.zeros(len(joint_words)) i = 0 for joint_word in joint_words: if joint_word in sent_set: # if word in union exists in the sentence, s(i) = 1 (unnormalized) semvec[i] = 1.0 if info_content_norm: semvec[i] = semvec[i] * math.pow(info_content(joint_word), 2) else: # find the most similar word in the joint set and set the sim value sim_word, max_sim = most_similar_word(joint_word, sent_set) semvec[i] = max_sim if max_sim > PHI else 0.0 if info_content_norm: semvec[i] = semvec[i] * info_content(joint_word) * info_content(sim_word) i = i + 1 return semvec def semantic_similarity(sentence_1, sentence_2, info_content_norm): """ Computes the semantic similarity between two sentences as the cosine similarity between the semantic vectors computed for each sentence. """ words_1 = nltk.word_tokenize(sentence_1) words_2 = nltk.word_tokenize(sentence_2) joint_words = set(words_1).union(set(words_2)) vec_1 = semantic_vector(words_1, joint_words, info_content_norm) vec_2 = semantic_vector(words_2, joint_words, info_content_norm) return np.dot(vec_1, vec_2.T) / (np.linalg.norm(vec_1) * np.linalg.norm(vec_2)) ######################### word order similarity ########################## def word_order_vector(words, joint_words, windex): """ Computes the word order vector for a sentence. The sentence is passed in as a collection of words. The size of the word order vector is the same as the size of the joint word set. The elements of the word order vector are the position mapping (from the windex dictionary) of the word in the joint set if the word exists in the sentence. If the word does not exist in the sentence, then the value of the element is the position of the most similar word in the sentence as long as the similarity is above the threshold ETA. """ wovec = np.zeros(len(joint_words)) i = 0 wordset = set(words) for joint_word in joint_words: if joint_word in wordset: # word in joint_words found in sentence, just populate the index wovec[i] = windex[joint_word] else: # word not in joint_words, find most similar word and populate # word_vector with the thresholded similarity sim_word, max_sim = most_similar_word(joint_word, wordset) if max_sim > ETA: wovec[i] = windex[sim_word] else: wovec[i] = 0 i = i + 1 return wovec def word_order_similarity(sentence_1, sentence_2): """ Computes the word-order similarity between two sentences as the normalized difference of word order between the two sentences. """ words_1 = nltk.word_tokenize(sentence_1) words_2 = nltk.word_tokenize(sentence_2) joint_words = list(set(words_1).union(set(words_2))) windex = {x[1]: x[0] for x in enumerate(joint_words)} r1 = word_order_vector(words_1, joint_words, windex) r2 = word_order_vector(words_2, joint_words, windex) return 1.0 - (np.linalg.norm(r1 - r2) / np.linalg.norm(r1 + r2)) ######################### overall similarity ########################## def similarity(sentence_1, sentence_2, info_content_norm): """ Calculate the semantic similarity between two sentences. The last parameter is True or False depending on whether information content normalization is desired or not. """ return DELTA * semantic_similarity(sentence_1, sentence_2, info_content_norm) + \ (1.0 - DELTA) * word_order_similarity(sentence_1, sentence_2) ######################### main / test ########################## # the results of the algorithm are largely dependent on the results of # the word similarities, so we should test this first... word_pairs = [ ["asylum", "fruit", 0.21], ["autograph", "shore", 0.29], ["autograph", "signature", 0.55], ["automobile", "car", 0.64], ["bird", "woodland", 0.33], ["boy", "rooster", 0.53], ["boy", "lad", 0.66], ["boy", "sage", 0.51], ["cemetery", "graveyard", 0.73], ["coast", "forest", 0.36], ["coast", "shore", 0.76], ["cock", "rooster", 1.00], ["cord", "smile", 0.33], ["cord", "string", 0.68], ["cushion", "pillow", 0.66], ["forest", "graveyard", 0.55], ["forest", "woodland", 0.70], ["furnace", "stove", 0.72], ["glass", "tumbler", 0.65], ["grin", "smile", 0.49], ["gem", "jewel", 0.83], ["hill", "woodland", 0.59], ["hill", "mound", 0.74], ["implement", "tool", 0.75], ["journey", "voyage", 0.52], ["magician", "oracle", 0.44], ["magician", "wizard", 0.65], ["midday", "noon", 1.0], ["oracle", "sage", 0.43], ["serf", "slave", 0.39] ] for word_pair in word_pairs: print "%s\t%s\t%.2f\t%.2f" % (word_pair[0], word_pair[1], word_pair[2], word_similarity(word_pair[0], word_pair[1])) sentence_pairs = [ ["I like that bachelor.", "I like that unmarried man.", 0.561], ["John is very nice.", "Is John very nice?", 0.977], ["Red alcoholic drink.", "A bottle of wine.", 0.585], ["Red alcoholic drink.", "Fresh orange juice.", 0.611], ["Red alcoholic drink.", "An English dictionary.", 0.0], ["Red alcoholic drink.", "Fresh apple juice.", 0.420], ["A glass of cider.", "A full cup of apple juice.", 0.678], ["It is a dog.", "That must be your dog.", 0.739], ["It is a dog.", "It is a log.", 0.623], ["It is a dog.", "It is a pig.", 0.790], ["Dogs are animals.", "They are common pets.", 0.738], ["Canis familiaris are animals.", "Dogs are common pets.", 0.362], ["I have a pen.", "Where do you live?", 0.0], ["I have a pen.", "Where is ink?", 0.129], ["I have a hammer.", "Take some nails.", 0.508], ["I have a hammer.", "Take some apples.", 0.121] ] for sent_pair in sentence_pairs: print "%s\t%s\t%.3f\t%.3f\t%.3f" % (sent_pair[0], sent_pair[1], sent_pair[2], similarity(sent_pair[0], sent_pair[1], False), similarity(sent_pair[0], sent_pair[1], True))

Proceeding from the top-down (wrt the code, or bottom-up wrt the algorithm), the lowest unit of the algorithm is the semantic similarity between a pair of words. The word similarity is a combination of two functions f(l) and f(h), where l is the shortest path between the two words in Wordnet (our Semantic Network) and h the height of their Lowest Common Subsumer (LCS) from the root of the Semantic Network. The intuition behind these is that l is a proxy for how similar the words are, and d is a proxy for the specificity of the LCS, ie, LCS nodes closer to the root indicate broader/more abstract concepts and less similarity. The functions f(l) and f(h) serve to normalize these values to the range [0,1]. In formulas, then:

sim(w1, w2) = f(l).f(h)

    where:

    f(l) = e-αl
            eβh - e-βh
    f(h) = ------------
            eβh + e-βh

Word similarities between a set of word pairs were reported in the paper. As a test, I computed the similarities between the same word pairs with my code above. The similarity values reported in the paper are shown under Exp.Sim and the ones returned by my code are shown under Act.Sim. As you can see, they are close but not identical - however, note that the computed similarites seem to line up with intuition. For example, sim(autograph, signature) is higher than sim(autograph, shore), sim(magician, wizard) is higher than sim(magician, oracle), etc.

Word #1	Word #2	Exp. Sim	Act. Sim
asylum	fruit	0.21	0.30
autograph	shore	0.29	0.16
autograph	signature	0.55	0.82
automobile	car	0.64	1.00
bird	woodland	0.33	0.20
boy	rooster	0.53	0.11
boy	lad	0.66	0.82
boy	sage	0.51	0.37
cemetery	graveyard	0.73	1.00
coast	forest	0.36	0.36
coast	shore	0.76	0.80
cock	rooster	1.00	1.00
cord	smile	0.33	0.13
cord	string	0.68	0.82
cushion	pillow	0.66	0.82
forest	graveyard	0.55	0.20
forest	woodland	0.70	0.98
furnace	stove	0.72	0.17
glass	tumbler	0.65	0.82
grin	smile	0.49	0.99
gem	jewel	0.83	1.00
hill	woodland	0.59	0.36
hill	mound	0.74	0.99
implement	tool	0.75	0.82
journey	voyage	0.52	0.82
magician	oracle	0.44	0.30
magician	wizard	0.65	1.00
midday	noon	1.00	1.00
oracle	sage	0.43	0.37
serf	slave	0.39	0.55

One thing I did differently from the paper is to select the most similar pair of synsets instead of just picking the first noun synset for each word (see the function get_best_synset_pair). This is because a word can map to multiple synsets, and finding the most similar pair mimics the human tendency to maximize pattern seeking (ie see patterns where there are none).

Sentence similarity is computed as a linear combination of semantic similarity and word order similarity. Semantic Similarity is computed as the Cosine Similarity between the semantic vectors for the two sentences. To build the semantic vector, the union of words in the two sentences is treated as the vocabulary. If the word occurs in the sentence, its value for that position is 1. If it doesn't, the similarity for the word is computed against all the other words in the sentence. If it happens to be above a threshold φ, then the value of the element is φ, else it is 0. This value is further attenuated by the information content for the word as found in the Brown corpus. In equations:

s1 • s2
    Ss = -----------------
          ||s1|| * ||s2||

    where:

    si = s * I(wi) * I(wj)

                log(n + 1)
    I(w) = 1 - ------------
                log(N + 1)

    where:
      n = number of times word w occurs in corpus
      N = number of words in the corpus

The word order similarity attempts to correct for the fact that sentences with the same words can have radically different meanings. This is done by computing the word order vector for each sentence and computing a normalized similarity measure between them. The word order vector, like the semantic vector is based on the joint word set. If the word occurs in the sentence, its position in the joint word set is recorded. If not, the similarity to the most similar word in the sentence is recorded if it crosses a threshold η else it is 0. In equations:

||r1 - r2||
    Sr = 1 - --------------
              ||r1 + r2||

    where:
      r1 = word position vector for sentence 1
      r2 = word position vector for sentence 2

The similarity between two sentences are modeled as a linear combination of their semantic similarity and word order similarity, ie:

S = δSs + (1 - δ)Sr

Similar to word similarities, the paper also lists some sentence similarities computed with their algorithm. I tried these same sentences through my code, and as expected, got slightly different results (since the sentence similarity is dependent on word similarities). Here they are. Exp.Sim are the values reported in the paper, Act.Sim (w/o IC) are computed similarities without Information Content normalization and Act.Sim (w/IC) are computed similarities with Information Content normalization. As you can see the Exp.Sim and Act.Sim (w/IC) values are quite consistent.

Sentence #1	Sentence #2	Exp.Sim	Act.Sim (w/o IC)	Act.Sim (w/IC)
I like that bachelor.	I like that unmarried man.	0.561	0.801	0.345
John is very nice.	Is John very nice?	0.977	0.592	0.881
Red alcoholic drink.	A bottle of wine.	0.585	0.477	0.307
Red alcoholic drink.	Fresh orange juice.	0.611	0.467	0.274
Red alcoholic drink.	An English dictionary.	0.000	0.237	0.028
Red alcoholic drink.	Fresh apple juice.	0.420	0.389	0.215
A glass of cider.	A full cup of apple juice.	0.678	0.659	0.347
It is a dog.	That must be your dog.	0.739	0.452	0.709
It is a dog.	It is a log.	0.623	0.858	0.497
It is a dog.	It is a pig.	0.790	0.863	0.500
Dogs are animals.	They are common pets.	0.738	0.550	0.377
Canis familiaris are animals.	Dogs are common pets.	0.362	0.458	0.151
I have a pen.	Where do you live?	0.000	0.134	0.158
I have a pen.	Where is ink?	0.129	0.112	0.077
I have a hammer.	Take some nails.	0.508	0.431	0.288
I have a hammer.	Take some apples.	0.121	0.344	0.147

Once more, while the numbers don't match exactly, the results seem intuitively correct. For example, "Red alcoholic drink" is more similar to "A bottle of wine" than "Fresh apple juice", which is more similar than "An English dictionary", etc.

Thats all I have for today. Hope you found this paper (and my implementation) interesting. The (latest) code for this post is available on GitHub here.

Update 2017-03-13: Many thanks to Mathieu Chrétien for updating the code to use Python3 and contributing it back, you can find it on this github gist.