Cosine similarity does not satisfy the triangle inequality

The previous post looked at cosine similarity for embeddings of words in vector spaces. Word embeddings like word2vec map words into high-dimensional vector spaces in such a way that related words correspond to vectors that are roughly parallel. Ideally the more similar the words, the smaller the angle between their corresponding vectors.

The cosine similarity of vectorsx and y is given by

If the vectors are normalized to have length 1 (which word embeddings are typically not) then cosine similarity is just dot product. Vectors are similar when their cosine similarity is near 1 and dissimilar when their cosine similarity is near 0.

If x is similar to y and y is similar to z, is x similar to z? We could quantify this as follows.

Let cossim(x, y) be the cosine similarity between x and y.

If cossim(x, y)= 1 - ₁, and cossim(y, z) =1 - ₂, is cossim(x, z) at least 1 - ₁ - ₂? In other words, does the complement of cosine similarity satisfy the triangle inequality?

Counterexample

The answer is no. I wrote a script to search for a counterexample by generating random points on a sphere. Here's one of the examples it came up with.

 x = [-0.9289 -0.0013 0.3704] y = [-0.8257 0.3963 0.4015] z = [-0.6977 0.7163 -0.0091]

Let d₁ = 1 - cossim(x, y), d₂ = 1 - cossim(y, z), and d₃ be 1 - cossim(x, z).

Then d₁ = 0.0849, d₂ = 0.1437, and d₃ = 0.3562 and so d₃ > d₁ + d₂.

Triangle inequality

The triangle inequality does hold if we work with s rather than their cosines. The angle between two vectors is the distance between these two vectors interpreted as points on a sphere and the triangle inequality does hold on the sphere.

Approximate triangle inequality

If the cosine similarity between x and y is close to 1, and the cosine similarity between y and z is close to 1, then the cosine similarity between x and z is close to one, though the triangle inequality may not hold. I wrote about this before in the post Nearly parallel is nearly transitive.

I wrote in that post that the law of cosines for spherical trigonometry says

cos c = cos a cos b + sin a sin b cos

where is the angle between the arcs a and b. If cos a = 1 - ₁, and cos b = 1 - ₂, then

cos a cos b = (1 - ₁)(1 - ₂) = 1 - ₁ - ₂ + _{1 2}

If ₁ and ₂ are small, then their product is an order of magnitude smaller. Also, the term

sin a sin b cos

is of the same order of magnitude. So if 1 - cossim(x, y) =₁ and 1 - cossim(y, z) =₂ then

1 - cossim(x, z) =₁ + ₁ + O(_{1 2})

Is the triangle inequality desirable?

Cosine similarity does not satisfy the triangle inequality, but do we want a measure of similarity between words to satisfy the triangle inequality? You could argue that semantic similarity isn't transitive. For example, lion is similar to king in that a lion is a symbol for a king. And lion is similar to house cat in that both are cats. But king and house cat are not similar. So the fact that cosine similarity does not satisfy the triangle inequality might be a feature rather than a bug.

Related posts

• Jaccard distance
• Ruzsa distance
• Kullback-Liebler divergence

The post Cosine similarity does not satisfy the triangle inequality first appeared on John D. Cook.