2
$\begingroup$

Define the Jaccard distance between two continuous vectors $a, b\in [0,1]^p$ as \begin{equation} J(a,b) = 1 - \frac{\|a\odot b\|_1}{\|a\odot b\|_1+\|a-b\|_1} \end{equation} where $\odot$ is the Hadamard product (element-wise product).

Is it a metric? Note that $a,b \in [0,1]^p$ rather than $\{0,1\}^p$.

I've tried with the naive approach. After some messy algebra, I need to prove the following \begin{equation} \|a-b\|_1\|a\odot c\|_1\|b\odot c\|_1 + \|a-b\|_1\|b-c\|_1\|a\odot c\|_1 + \|a-b\|_1 \|b-c\|_1 \|a-c\|_1 + \|b-c\|_1\|a\odot b\|_1 \|a\odot c\|_1 + \|a-b\|_1\|b-c\|_1\|a\odot c\|_1 \geq \|a-c\|_1\|a\odot b\|_1 \|b\odot c\|_1. \end{equation}

Improve this question
$\endgroup$
6
  • $\begingroup$ What do you mean by $ab$? $\endgroup$
    – Michael Albanese
    May 10, 2022 at 12:50
  • $\begingroup$ Thanks for pointing it out. Please see the edited version. It is the Hadamard product between $a$ and $b$. $\endgroup$
    – fatpanda2049
    May 10, 2022 at 12:56
  • 1
    $\begingroup$ you do realise that $a-b$ is of different length than $a\odot b.$ Whats the motivation for this definition? $\endgroup$
    – kodlu
    May 10, 2022 at 14:37
  • 1
    $\begingroup$ $a \odot b$ is the element-wise product, not inner product. So $a\odot b$ and $a-b$ are both of length $p$, right? $\endgroup$
    – fatpanda2049
    May 10, 2022 at 17:20
  • 1
    $\begingroup$ see also: mathoverflow.net/q/18084/11260 --- Is the Jaccard distance a distance? $\endgroup$
    – Carlo Beenakker
    May 11, 2022 at 8:33

1 Answer 1

Reset to default
2
$\begingroup$

All norms are supposed to be $1$-norms. Rewrite $J(a,b)$ as $$ J(a,b)=\frac{\|a-b\|}{\|a-b\|+\|a\odot b\|}. $$

Notice that $$ \|b\odot c\|=\sum_i b_ic_i =\sum_i\bigl((b_i-a_i)c_i+a_ic_i\bigr) \leq\sum_i|b_i-a_i|+\sum_ia_ic_i=\|a-b\|+\|a\odot c\|. $$ Similarly, $$ \|a\odot b\|\leq \|b-c\|+\|a\odot c\|. $$ Hence we have $$ J(a,b)+J(b,c) =\frac{\|a-b\|}{\|a-b\|+\|a\odot b\|}+\frac{\|b-c\|}{\|b-c\|+\|b\odot c\|}\\ \geq \frac{\|a-b\|}{\|a-b\|+\|b-c\|+\|a\odot c\|} +\frac{\|b-c\|}{\|b-c\|+\|a-b\|+\|a\odot c\|}\\ =\frac{\|a-b\|+\|b-c\|}{\|a-b\|+\|b-c\|+\|a\odot c\|} \geq \frac{\|a-c\|}{\|a-c\|+\|a\odot c\|}=J(a,c), $$ where the last inequality follows from $\|a-b\|+\|b-c\|\geq \|a-c\|$.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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