How do I compute the structural similarity between sentences?

Question

I am working on a problem where I need to determine whether two sentences are similar or not. I implemented a solution using BM25 algorithm and wordnet synsets for determining syntactic & semantic similarity. The solution is working adequately, and even if the word order in the sentences is jumbled, it is measuring that two sentences are similar. For example

1. Python is a good language.
2. Language a good python is.

My problem is to determine that these two sentences are similar.

• What could be the possible solution for structural similarity?
• How will I maintain the structure of sentences?

Answer 1

The easiest way to add some sort of structural similarity measure is to use n-grams; in your case bigrams might be sufficient.

Go through each sentence and collect pairs of words, such as:

• "python is", "is a", "a good", "good language".

Your other sentence has

• "language a", "a good", "good python", "python is".

Out of eight bigrams you have two which are the same ("python is" and "a good"), so you could say that the structural similarity is 2/8.

Of course you can also be more flexible if you already know that two words are semantically related. If you want to say that Python is a good language is structurally similar/identical to Java is a great language, then you could add that to the comparison so that you effectively process "[PROG_LANG] is a [POSITIVE-ADJ] language", or something similar.

Answer 2

Firstly, before we commence I recommend that you refer to similar questions on the network such as https://datascience.stackexchange.com/questions/25053/best-practical-algorithm-for-sentence-similarity and https://stackoverflow.com/questions/62328/is-there-an-algorithm-that-tells-the-semantic-similarity-of-two-phrases

To determine the similarity of sentences we need to consider what kind of data we have. For example if you had a labelled dataset i.e. similar sentences and disimilar sentences then a straight forward approach could have been to use a supervised algorithm to classify the sentences.

An approach that could determine sentence structural similarity would be to average the word vectors generated by word embedding algorithms i.e word2vec. These algorithms create a vector for each word and the cosine similarity among them represents semantic similarity among words. (Daniel L 2017)

Using word vectors we can use the following metrics to determine the similarity of words.

• Cosine distance between word embeddings of the words
• Euclidean distance between word embeddings of the words

Cosine similarity is a measure of the similarity between two non-zero vectors of an inner product space that measures the cosine of the angle between them. The cosine angle is the measure of overlap between the sentences in terms of their content.

The Euclidean distance between two word vectors provides an effective method for measuring the linguistic or semantic similarity of the corresponding words. (Frank D 2015)

Alternatively you could calculate the eigenvector of the sentences to determine sentence similarity.

Eigenvectors are a special set of vectors associated with a linear system of equations (i.e. matrix equation). Here a sentence similarity matrix is generated for each cluster and the eigenvector for the matrix is calculated. You can read more on Eigenvector based approach to sentence ranking on this paper https://pdfs.semanticscholar.org/ca73/bbc99be157074d8aad17ca8535e2cd956815.pdf

For source code Siraj Rawal has a Python notebook to create a set of word vectors. The word vectors can then be used to find the similarity between words. The source code is available here https://github.com/llSourcell/word_vectors_game_of_thrones-LIVE

Another option is a tutorial from Oreily that utilizes the gensin Python library to determine the similarity between documents. This tutorial uses NLTK to tokenize then creates a tf-idf (term frequency-inverse document frequency) model from the corpus. The tf-idf is then used to determine the similarity of the documents. The tutorial is available here https://www.oreilly.com/learning/how-do-i-compare-document-similarity-using-python

Answer 3

The best approach at this time (2019):

The most efficient approach now is to use Universal Sentence Encoder by Google (paper_2018) which computes semantic similarity between sentences using the dot product of their embeddings (i.e learned vectors of 215 values). Similarity is a float number between 0 (i.e no similarity) and 1 (i.e strong similarity).

The implementation is now integrated to Tensorflow Hub and can easily be used. Here is a ready-to-use code to compute the similarity between 2 sentences. Here I will get the similarity between "Python is a good language" and "Language a good python is" as in your example.

Code example:

#Requirements: Tensorflow>=1.7 tensorflow-hub numpy

import tensorflow as tf
import tensorflow_hub as hub
import numpy as np

module_url = "https://tfhub.dev/google/universal-sentence-encoder-large/3" 
embed = hub.Module(module_url)
sentences = ["Python is a good language","Language a good python is"]

similarity_input_placeholder = tf.placeholder(tf.string, shape=(None))
similarity_sentences_encodings = embed(similarity_input_placeholder)

with tf.Session() as session:
  session.run(tf.global_variables_initializer())
  session.run(tf.tables_initializer())
  sentences_embeddings = session.run(similarity_sentences_encodings, feed_dict={similarity_input_placeholder: sentences})
  similarity = np.inner(sentences_embeddings[0], sentences_embeddings[1])
  print("Similarity is %s" % similarity)

Output:

Similarity is 0.90007496 #Strong similarity