3
$\begingroup$

How to prove that the cosine distance function defined by cosine similarity between two unit vectors does not satisfy the triangle inequality?

$\endgroup$
  • 1
    $\begingroup$ There is a thread stats.stackexchange.com/q/135171/3277 very close to your question. It is about correlation, but correlation is cosine for centered variablers, so it is relevant for your case. $\endgroup$ – ttnphns Feb 23 '16 at 11:29
  • 1
    $\begingroup$ You do this by finding a counterexample. Since cosine similarity is really a squared distance, look at very small, almost straight triangles for possible violations of the triangle inequality. $\endgroup$ – whuber Feb 24 '16 at 1:34
  • $\begingroup$ @whuber Are you sure that a violation of triangle inequality could only be proven in such an extreme case of almost straight triangles? Could you have a look on a counterexample below, because I think that is much simpler, but after two comments above I'm really confused about it. $\endgroup$ – Adam Przedniczek Feb 24 '16 at 10:25
  • $\begingroup$ @Adam I didn't say that at all: my suggestions were made only to show how one could think about the cosine similarity and easily arrive at situations that are likely to violate the triangle inequality. Only one such violation--no matter how "extreme"--is needed to show this inequality does not hold. I would also maintain that this line of thinking is substantially simpler than the one you posted, because (1) yours comes without any motivation and (2) there's really nothing left to show once you observe the cosine similarity is a convex function of distance: the conclusion is immediate. $\endgroup$ – whuber Feb 24 '16 at 13:16
  • 1
    $\begingroup$ @Adam I'm sorry; I never meant to suggest there was anything wrong about your answer. However, I think it could be condensed into a single line in which you show that the $A,B,C$ you chose violate the triangle inequality. I think it would be of greater interest to devote any additional space to explaining how you thought of your counterexample. $\endgroup$ – whuber Feb 24 '16 at 13:30
1
$\begingroup$

$$\text{cos-dist}(A, B) = 1 - \text{cos-sim}(A, B)$$ $$\text{cos-sim}(A, B) = \frac{\langle A, B \rangle}{||A|| \cdot ||B||} = \frac{\sum\limits_{i=1}^n A_i \cdot B_i}{\sqrt{\sum\limits_{i=1}^n A_i^2} \cdot \sqrt{\sum\limits_{i=1}^n B_i^2}}$$

Triangle inequality for cosine distance tooks a form of (of course it doesn't hold): $$\text{cos-dist}(A,C) \nleq \text{cos-dist}(A, B) + \text{cos-dist}(B, C)$$ which is equivalent to: $$1 - \text{cos-sim}(A,C) \nleq 1 - \text{cos-sim}(A, B) + 1 - \text{cos-sim}(B, C)$$ and after simple transformations: $$1 + \text{cos-sim}(A, C) \ngeq \text{cos-sim}(A, B) + \text{cos-sim}(B, C)$$

Now, you're trying to find such three vectors A, B and C that: $$1 + \text{cos-sim}(A, C) < \text{cos-sim}(A, B) + \text{cos-sim}(B, C)$$

Let $A, B, C \in \mathbb{R}^2$ and all of them are of unit length A = [1, 0], B = $\left[\frac{\sqrt{2}}{2}, \frac{\sqrt{2}}{2}\right]$, C = [0, 1]. Note that vectors A and C are orthogonal, so we would get simply $0$: $$\text{cos-sim}(A, C) = \frac{0}{\sqrt{1}\sqrt{1}} = 0$$ Each pair of vectors A & B as well as B & C would give the same value: $$ \text{cos-sim}(A, B) = \frac{\frac{\sqrt{2}}{2} + 0}{\sqrt{1}\sqrt{1}} = \frac{\sqrt{2}}{2},~~~ \text{cos-sim}(B, C) = \frac{0+\frac{\sqrt{2}}{2}}{\sqrt{1}\sqrt{1}} = \frac{\sqrt{2}}{2}$$. Finally, we could defeat primary inequality by proving that: $$ 1 + 0 < \frac{\sqrt{2}}{2} + \frac{\sqrt{2}}{2}$$ $$ 1 < \sqrt{2} \approx 1.41 \dots$$

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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