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
    Commented 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
    Commented 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
    Commented 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
    Commented May 10, 2022 at 17:20
  • 1
    $\begingroup$ see also: mathoverflow.net/q/18084/11260 --- Is the Jaccard distance a distance? $\endgroup$
    – Carlo Beenakker
    Commented 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$

You must log in to answer this question.

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