How to prove that the cosine distance function defined by cosine similarity between two unit vectors does not satisfy the triangle inequality?
$\begingroup$
$\endgroup$
6
-
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$– ttnphnsCommented Feb 23, 2016 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 ♦Commented Feb 24, 2016 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 PrzedniczekCommented Feb 24, 2016 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 ♦Commented Feb 24, 2016 at 13:16
-
2$\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 ♦Commented Feb 24, 2016 at 13:30
|
Show 1 more comment
1 Answer
$\begingroup$
$\endgroup$
1
$$\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$$
answered Feb 23, 2016 at 13:05
-
2$\begingroup$ so what does that prove afterall? cosine dissimilarity is not a metric measurement? $\endgroup$ Commented Jun 19, 2021 at 10:19