20
$\begingroup$

There is a similarity function particular popular for processing sparse vectors such as textual data (word frequency counts etc.) commonly referred to as cosine similarity.

There are two variants to invert it to a dissimilarity, often referred to as cosine and arccos distance (distance in the weak sense, not the strict mathematical definition though!)

In essence, the similarity function is: $$\text{cosine-similarity}(A,B) = \frac{\left<A,B\right>}{||A||\cdot||B||}$$ Which is then used as a distance function as either $$\text{cosine-dist}(A,B) := 1 - \text{cosine-similarity}(A,B)$$ $$\text{arccos-dist}(A,B) := \arccos(\text{cosine-similarity}(A,B))$$

Obviously, these distances cannot be a distance function on $\mathbb{R}^n$, as they are not well defined for the point $\{0\}^n$, as this leads to $0/0$. What is the proper result then? $1$? $\infty$?

I tried finding a formal proof on Google that these distances do or do not satisfy the triangle inequality. Wikipedia seems to claim only the second is a proper metric, but does not give a reference.

Update: reworked my question from here on, with updated thoughts on this issue.

As confirmed by joriki, the $0$ is a problem for this distance function, as one cannot compute the angle to this vector. There is another issue with this distance, that however in many circumstances is intentional: two vectors that are a positive linear multiple of each other will have the angle of 0, while not being the same. See his reply on why cosine-dist does not satisfy the triangle equality for small angles (I wonder if this issue is comparable to that of $L_p$ with $p<1$).

I have the following ideas in my mind, and again appreciate any pointers to literature, references, errors in these thoughts, extensions:

A) Instead of $\mathbb{R}^n$, lets look at the unit sphere instead, i.e. vectors of length $1=||A||=||B||$. $\arccos(\left<A,B\right>)$ then is the geodesic distance on the unit sphere, which is metric, right? So in this restricted domain, arccos-dist is a proper distance?

B) Assuming I have an injective (not necessarily surjective) map from another domain to the unit sphere, then use this distance function, this becomes also a metric space? After all, any of the distance function properties should still hold, right?

C) Is arccos-dist a pseudo-metric on $\mathbb{R}^n \setminus \{0\}$? (i.e. I accept that $d(x,y) = 0 \not\Rightarrow x=y$, only $d(x,x)=0$)

$\endgroup$
2
  • 3
    $\begingroup$ Completely rewriting a question like this makes it hard for others who find the thread to make use of the existing answer(s). These are really new questions that should have been asked in a new post instead of messing up the existing question & answer. $\endgroup$
    – joriki
    Jul 4, 2016 at 5:50
  • $\begingroup$ Maybe it is called under the name Fubini-Study metric? $\endgroup$ May 30, 2023 at 7:08

3 Answers 3

17
$\begingroup$

Neither of these is a metric on $\mathbb R^n$ for several reasons, some of which you've pointed out. In a sense, the main reason, of which the undefined result for the zero vector is a symptom, is that this value depends only on the direction of the vectors and not on their length (and the zero vector has no direction).

If you want to consider these functions as metrics, you need to consider them on the set of directions (i.e. rays from the origin) in $\mathbb R^n$, or equivalently on the unit sphere $S^{n-1}$ in $\mathbb R^n$.

The second function, the "arccos distance", is just the angle between the two directions/vectors, and this is a metric because it's the geodesic distance on the unit sphere.

The first function, the "cosine distance", isn't a metric because for small angles it approximately calculates (half) the square of the angle, $1-\cos \alpha\approx\frac12\alpha^2$, and if you turn by the same angle $\alpha$ twice, the sum of the two individual "distances" will be approximately $\frac12\alpha^2+\frac12\alpha^2=\alpha^2$ whereas the "distance" between the directions $2\alpha$ apart will be approximately $\frac12(2\alpha)^2=2\alpha^2$.

To answer your questions:

  1. I don't know a source, but I hope the above arguments should be immediate enough to convince without a source.

  2. No, since you'd still get a distance of $0$ for any vectors in the same direction, so this could be at most a pseudometric.

  3. Never heard of those.

  4. There is none; the function will necessarily be discontinuous if you extend it to $0$, and the value at $0$ will necessarily be arbitrary because there are vectors in all directions arbitrarily close to $0$.

$\endgroup$
1
  • $\begingroup$ Thank you, and +1 for this answer. I've rephrased my question substantially due to your input. You got already got me a lot further in getting a grasp on the properties of cosine distances. $\endgroup$ Jan 27, 2012 at 14:45
3
$\begingroup$

A and B are true, but C is not true, because any parallel vectors have length 0. Arccos-dist is just projection onto the sphere followed by the regular metric on the sphere (you can see this because the length of the vector doesn't matter, so you can assume each vector lies in the sphere); so yes, injective maps into the sphere become metric spaces this way, but Euclidean space minus the origin will not.

See this link under "vector version", where we see arccos dist is the spherical metric, and it only depends on the direction.

$\endgroup$
2
  • $\begingroup$ Note that in C I asked about it being pseudo metric: en.wikipedia.org/wiki/Pseudometric_space which does allow non-identical vectors to have distance 0. $\endgroup$ Jun 2, 2013 at 10:54
  • $\begingroup$ Then the answer is yes, and it satisfies the triangle inequality because the spherical distance metric satisfies the triangle inequality. $\endgroup$ Jun 2, 2013 at 13:00
0
$\begingroup$

The cosine-similarity is defined as the inner product of two vectors A & B divided by the product of their magnitudes. This is the definition of the cosine of the angle between two vectors in an inner product space.

Of course if you then take the arccos (which is cos-1) then it will just give you the angle between the two vectors. So the arccos distance isn't really a distance, its the angle between vectors.

A) Yes, the arccos(< A,B >) is a metric. Since all inner products on the reals can be represented by the dot product of two vectors each acted on by an invertible matrix we will just focus on the dot product.
1) d(X,Y) $\geq$ 0 is true as we only allow angles to be positive.
2) d(X,Y) = 0 if X=Y:
the dot product of two vectors in Rn can be calculated by ||a|| ||b|| cos($ \theta $) and since both ||a|| & ||b|| are 1, the only point where cos($\theta$) = 0 is when $\theta$ = 0 meaning that a = b (since we dont have to worry about them being linearly dependent)
3) d(X,Y) = d(Y,X) is trivial.
4) d(X,Z) $\leq$ d(X,Y)+d(Y,Z) :
Consider three vectors X,Y,Z on the sphere. We will project Y onto the span of X & Z, that is we will project it onto the plane that they both lie on. This projection will be called Yo and it should be obvious that d(X,Z) $\leq$ d(X,Y0) + d(Y0,Z) with equality if Y0 falls between X and Z. Next we note that Y=Y0+A for some vector A and my original "proof" I realized isn't all that right, so I am a bit stuck. But I figure that since A is boosting Y0 perpendicularly away from the plane XZ that it would not make sense for the angle to decrease. I am having a hard time proving it.

B) If the former is proven to be true, then this is true. Since the function is injective, you can just restrict yourself to the image of X in S and do d(f(X),f(Y)) (using this as a metric also means f is an embedding of X into S)

C) I believe so yes. Consider a function f: Rn -> Sn by f(X) = $\frac {X} {||X||} $ and then calculating the distance of two vectors using distance for Sn this will produce the psuedo-metric.

$\endgroup$
2
  • 1
    $\begingroup$ Respectfully, your answer doesn't really answer the question that was asked. Maybe you can edit your answer to be more descriptive. $\endgroup$
    – eepperly16
    Feb 9, 2017 at 5:06
  • $\begingroup$ Tried doing so. Sorry about that $\endgroup$ Feb 10, 2017 at 6:45

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .