1
$\begingroup$

Let $\Delta_n$ be the set of all probability vectors on $n$ points, also known as the $n$-simplex. Let $x, y \in \Delta_n$ be two probability vectors, that is, $\sum_{i=1}^n x_i = 1$ and $x_i \geq 0$, and similarly for y.

Define the well-known total variation distance between $x$ and $y$ to be $TV(x, y) = \frac{1}{2} \sum_i |x_i - y_i|$.

The equally well-known Jaccard similarity between two sets $A, B$ is defined by $\frac{|A \cap B|}{|A \cup B|}$. When $|A| = |B|$, this can be viewed as similarity between two probability vectors $x$ and $y$, given by $x_i = \frac{1}{|A|} 1_{i \in A}$ and $y_i = \frac{1}{|B|} 1_{i \in B}$.

The most natural generalization of Jaccard similarity to all pairs of probability vectors is given in this paper by

$$J_P(x, y) = \sum_{i: x_i y_i > 0} \left( \sum_j \max\{\frac{x_j}{x_i}, \frac{y_j}{y_i}\} \right)^{-1}. $$

While total variation distance has an alternative definition in terms of pairwise coupling,

$$TV(x, y) = \inf_{X \sim x, Y \sim y} \mathbb{P}[X \neq Y],$$ $J_P$ can also be defined in terms of a particular coupling scheme, that works for all probability vectors at once (i.e., not just a specific pair of them):

$$ J_P(x, y) = \mathbb{P}[\arg\min_i \frac{- \log h_i}{x_i} = \arg\min_i \frac{- \log h_i}{y_i}],$$

where $h_i \sim \mathbb{U}([0, 1])$ are i.i.d. uniform random variables in $[0, 1]$, that are shared among all probability vectors in $\Delta_n$. In other words, $J_P$ can be viewed as the collision probability between two Gumbel softmax random variables. Note that $\mathbb{P}[\arg\min_i \frac{- \log h_i}{x_i} = j] = x_j$ so indeed the above is a coupling collision probability.

Let's define $JD(x, y) = 1 - J_P(x, y)$. By the coupling definition of $TV$, we trivially have $JD(x, y) \geq TV(x, y)$.

On the other hand, for $x_i = 1_{i \in A}$ and $y_i = 1_{i \in B}$ with $|A| = |B| = k$ and $|A \cup B| = n$, we have $TV(x, y) = \frac{n-k}{k}$ and $ JD(x, y) = 1 - \frac{|A \cap B|}{|A \cup B|} = \frac{2n - 2k}{n}$, so

$$JD(x, y) = \frac{2 TV(x, y)}{ 1 + TV(x, y)}.$$

My simulation shows that this is indeed an upper bound of $JD$ in terms of $TV$. In other words, the following elegant relation is conjectured: $$ TV(x, y) \leq JD(x, y) \leq \frac{2 TV(x, y)}{ 1 + TV(x, y)}. $$ But I don't know how to prove it. Help is greatly appreciated.

$\endgroup$
4
  • 1
    $\begingroup$ Maybe you find the Steinhaus transform based definition of Jaccard helpful for proving the bound because the upper bound you've stated looks like that transform! mathoverflow.net/questions/18084/… $\endgroup$
    – Suvrit
    Dec 27 '20 at 2:05
  • $\begingroup$ @Suvrit thanks for the reference! I don't see immediately how to apply the transform but it brings up an interesting question what's the inverse image of the probability Jaccard distance under the transform. $\endgroup$
    – John Jiang
    Dec 27 '20 at 19:19
  • $\begingroup$ I feel the answer to your question should be simple, but am out of time rn to think; you may find the link interesting: en.wikipedia.org/wiki/… --- also, actually the Jaccard distance wikipedia page states an upper bound of the form 2J/(1+J), so I feel this type of bound should be kinda known. $\endgroup$
    – Suvrit
    Dec 27 '20 at 20:15
  • 1
    $\begingroup$ @Suvrit, yes your hunch is correct. This is already known, in fact proved by my coauthor in the linked paper above already (but in slight disguise)! See Theorem IV.5 of arxiv.org/pdf/1809.04052.pdf $\endgroup$
    – John Jiang
    Dec 27 '20 at 20:40
1
$\begingroup$

As suggested by my coauthor, and proved in the same paper linked in the question, the conjectured upper bound is indeed true. I reproduce the proof here for completeness:

Let $p = TV(x, y)$. We want to show $J_P(x, y) \geq \frac{1-p}{1 +p}$, since $1 - \frac{2p}{1 + p} = \frac{1-p}{1 +p}$.

Observe first that $p = 1 - \sum_i \min\{x_i, y_i\}$. Indeed, write $1 = \frac{1}{2} \sum_i (x_i + y_i)$ (since $x$, $y$ are both probability vectors), the claim follows from $x_i + y_i - 2\min\{x_i, y_i\} = |y_i - x_i|$.

Next we have $1 + p = \sum_i \max\{x_i, y_i\}$ since $\min\{x_i, y_i\} + |x_i - y_i| = \max\{x_i, y_i\}$. Thus $ \frac{1 - p}{1 + p} = \sum_i \min\{x_i, y_i\} / \sum_i \max \{x_i, y_i\}$. This already looks very similar to the definition of $J_P(x, y)$.

Finally we have $$ \frac{1-p}{1+p} = \sum_{i: x_i y_i > 0} \left( \sum_j \frac{\max\{x_j, y_j\} }{\min\{x_i, y_i\}}\right)^{-1} \le \sum_{i: x_i y_i > 0} \left( \sum_j \max\{\frac{x_j}{x_i}, \frac{y_j}{y_i}\}\right)^{-1}.$$

Note that $\frac{1-p}{1+p}$ is known as weighted Jaccard similarity, $J_W$. $1-J_W$ is precisely the Steinhaus transform (see Suvrit’s comment) of the total variation distance $TV$ extended to all non-negative probability vectors, with respect to the $\vec{0}$ vector, defined by $TV(x, y) = \frac12 \sum_i |x_i - y_i|$.

$\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.