15
$\begingroup$

I'm looking to solve the following problem: I have a set of sentences as my dataset, and I want to be able to type a new sentence, and find the sentence that the new one is the most similar to in the dataset. An example would look like:

New sentence: "I opened a new mailbox"

Prediction based on dataset:

Sentence                       | Similarity
A dog ate poop                   0%
A mailbox is good                50%
A mailbox was opened by me       80%

I've read that cosine similarity can be used to solve these kinds of issues paired with tf-idf (and RNNs should not bring significant improvements to the basic methods), or also word2vec is used for similar problems. Are those actually viable for use in this specific case, too? Are there any other techniques/algorithms to solve this (preferably with Python and SKLearn, but I'm open to learn about TensorFlow, too)?

$\endgroup$
  • $\begingroup$ Definitely check Bert. Here is a nice implementation. It does exactly what you are looking for with pretty good results $\endgroup$ – GioGio Dec 30 '19 at 10:42
26
$\begingroup$

Your problem can be solved with Word2vec as well as Doc2vec. Doc2vec would give better results because it takes sentences into account while training the model.

Doc2vec solution
You can train your doc2vec model following this link. You may want to perform some pre-processing steps like removing all stop words (words like "the", "an", etc. that don't add much meaning to the sentence). Once you trained your model, you can find the similar sentences using following code.

import gensim  

model = gensim.models.Doc2Vec.load('saved_doc2vec_model')  

new_sentence = "I opened a new mailbox".split(" ")  
model.docvecs.most_similar(positive=[model.infer_vector(new_sentence)],topn=5)

Results:

[('TRAIN_29670', 0.6352514028549194),
 ('TRAIN_678', 0.6344441771507263),
 ('TRAIN_12792', 0.6202734708786011),
 ('TRAIN_12062', 0.6163255572319031),
 ('TRAIN_9710', 0.6056315898895264)]

The above results are list of tuples for (label,cosine_similarity_score). You can map outputs to sentences by doing train[29670].

Please note that the above approach will only give good results if your doc2vec model contains embeddings for words found in the new sentence. If you try to get similarity for some gibberish sentence like sdsf sdf f sdf sdfsdffg, it will give you few results, but those might not be the actual similar sentences as your trained model may haven't seen these gibberish words while training the model. So try to train your model on as many sentences as possible to incorporate as many words for better results.

Word2vec Solution
If you are using word2vec, you need to calculate the average vector for all words in every sentence and use cosine similarity between vectors.

def avg_sentence_vector(words, model, num_features, index2word_set):
    #function to average all words vectors in a given paragraph
    featureVec = np.zeros((num_features,), dtype="float32")
    nwords = 0

    for word in words:
        if word in index2word_set:
            nwords = nwords+1
            featureVec = np.add(featureVec, model[word])

    if nwords>0:
        featureVec = np.divide(featureVec, nwords)
    return featureVec

Calculate Similarity

from sklearn.metrics.pairwise import cosine_similarity

#get average vector for sentence 1
sentence_1 = "this is sentence number one"
sentence_1_avg_vector = avg_sentence_vector(sentence_1.split(), model=word2vec_model, num_features=100)

#get average vector for sentence 2
sentence_2 = "this is sentence number two"
sentence_2_avg_vector = avg_sentence_vector(sentence_2.split(), model=word2vec_model, num_features=100)

sen1_sen2_similarity =  cosine_similarity(sentence_1_avg_vector,sentence_2_avg_vector)
$\endgroup$
  • $\begingroup$ Thank you! Will work on this over the weekend, but the solution does seem perfect at first glance. Kudos! $\endgroup$ – lte__ Oct 25 '17 at 9:01
  • $\begingroup$ do we need to tokenize the sentences for training $\endgroup$ – pyd Jun 6 '18 at 4:48
  • $\begingroup$ yes @pyd we have to! sentence_1.split() does the same. $\endgroup$ – Harman Jun 6 '18 at 6:10
4
$\begingroup$

Word Mover’s Distance (WMD) is an algorithm for finding the distance between sentences. WMD is based on word embeddings (e.g., word2vec) which encode the semantic meaning of words into dense vectors.

The WMD distance measures the dissimilarity between two text documents as the minimum amount of distance that the embedded words of one document need to "travel" to reach the embedded words of another document.

For example:

enter image description here Source: "From Word Embeddings To Document Distances" Paper

The gensim package has a WMD implementation.

For your problem, you would compare the inputted sentence to all other sentences and return the sentence that has lowest WMD.

$\endgroup$
2
$\begingroup$

You can try an easy solution using sklearn and it's going to work fine.

  • Use tfidfvectorizer to get a vector representation of each text

  • Fit the vectorizer with your data, removing stop-words.

  • Transform the new entry with the vectorizer previously trained

  • Compute the cosine similarity between this representation and each representation of the elements in your data set.

If you have a hugh dataset you can cluster it (for example using KMeans from scikit learn) after obtaining the representation, and before predicting on new data.

This code perform all these steps. You can check it on my github repo.

from sklearn.feature_extraction.text import TfidfVectorizer
from sklearn.cluster import KMeans
from sklearn.metrics import adjusted_rand_score
import numpy

texts = ["This first text talks about houses and dogs",
        "This is about airplanes and airlines",
        "This is about dogs and houses too, but also about trees",
        "Trees and dogs are main characters in this story",
        "This story is about batman and superman fighting each other", 
        "Nothing better than another story talking about airplanes, airlines and birds",
        "Superman defeats batman in the last round"]

# vectorization of the texts
vectorizer = TfidfVectorizer(stop_words="english")
X = vectorizer.fit_transform(texts)
# used words (axis in our multi-dimensional space)
words = vectorizer.get_feature_names()
print("words", words)


n_clusters=3
number_of_seeds_to_try=10
max_iter = 300
number_of_process=2 # seads are distributed
model = KMeans(n_clusters=n_clusters, max_iter=max_iter, n_init=number_of_seeds_to_try, n_jobs=number_of_process).fit(X)

labels = model.labels_
# indices of preferible words in each cluster
ordered_words = model.cluster_centers_.argsort()[:, ::-1]

print("centers:", model.cluster_centers_)
print("labels", labels)
print("intertia:", model.inertia_)

texts_per_cluster = numpy.zeros(n_clusters)
for i_cluster in range(n_clusters):
    for label in labels:
        if label==i_cluster:
            texts_per_cluster[i_cluster] +=1 

print("Top words per cluster:")
for i_cluster in range(n_clusters):
    print("Cluster:", i_cluster, "texts:", int(texts_per_cluster[i_cluster])),
    for term in ordered_words[i_cluster, :10]:
        print("\t"+words[term])

print("\n")
print("Prediction")

text_to_predict = "Why batman was defeated  by superman so easy?"
Y = vectorizer.transform([text_to_predict])
predicted_cluster = model.predict(Y)[0]
texts_per_cluster[predicted_cluster]+=1

print(text_to_predict)
print("Cluster:", predicted_cluster, "texts:", int(texts_per_cluster[predicted_cluster])),
for term in ordered_words[predicted_cluster, :10]:
print("\t"+words[term])
$\endgroup$
  • $\begingroup$ Hey, it would be really nice if you could show an example of using the cosine similiairity? $\endgroup$ – Tido Jan 22 '19 at 19:56
  • $\begingroup$ Hey, shouldn't be part 2 come first, fit on al data and use this to transform each text? It would be really nice if you could show an example of using the cosine similiairity? $\endgroup$ – Tido Jan 22 '19 at 20:02
1
$\begingroup$

There is some recent work based on Variational Auto-Encoder in RNN models.Generating Sentences from a Continuous Space, with pytorch implementations: github code.
they managed to compress the semantic, syntactic global feature of a sentence into some latent space expressed maybe with some finite 10 to 30 independent random variables (factorized distribution).
the novel idea in this work, they interpolate between two sentences. and the results were quite amazing.

$\endgroup$
0
$\begingroup$

The generalized solution consists of the following steps -

  1. Featurization or word embeddings of a sentence.
  2. Applying a similarity metric among sentences.

For 1. word2vec is the best choice but if you don't want to use word2vec, you can make some approximations to it. One ways is to make a co-occurrence matrix of words from your trained sentences followed by applying TSVD on it. Coccurance matrix of $nXn$ dimensionality when converted into $nXd$ dimensionality, makes for word vectors of $d$ dimensions.

Once you get word embedding of each word, you can apply any of the similarity metrics like cosine similarity, etc. on each sentence to measure similarity with others.

$\endgroup$

Not the answer you're looking for? Browse other questions tagged or ask your own question.