#StackBounty: #kernel-trick #distance #similarities #rbf-kernel Does Mercer's theorem work in reverse?

Bounty: 100

A colleague has a function $s$ and for our purposes it is a black-box. The function measures the similarity $s(a,b)$ of two objects.

We know for sure that $s$ has these properties:

  1. The similarity scores are real numbers between 0 and 1, inclusive.
  2. Only the objects which are self-identical have scores of 1. So $s(a,b)=1$ implies $a=b$, and vice-versa.
  3. We are guaranteed that $s(a,b) = s(b,a)$.

Now he wants to work with algorithms that require distances as inputs, and depend on the inputs satisfying the axioms of distance.

My thought was that we could treat the similarity scores as if they were the result of the RBF kernel with some distance (it could be a Euclidean norm or another distance), i.e. we can just rearrange with algebra and assume that the similarity scores refer to the RBF kernel for a pair of points in some (unknown) coordinate system.

s(x_i,x_j) &= expleft(-frac{d( m_i, m_j)^2}{r}right) \
sqrt{-r log s(x_i,x_j) } &= d(m_i,m_j) \

Where $m_alpha in mathbb{R}^n$ is some unknown vector, and $x_alpha$ is the object of interest and $d$ is some distance.

The obvious properties work out, in terms of respecting distance axioms. The results have to be non-negative, and distances are only 0 for identical objects. But it’s not obvious that this rather general set of circumstances is sufficient to imply that the triangle inequality is respected.

On the other hand, this sounds kinda crazy.

So my questions is “does there exist an $f$ such that $f(s(a,b))=d(a,b)$ for $d$ some distance metric given these properties on $s$, and what is that $f$?”

If $f$ doesn’t exist in these general circumstances on $s$, is there an additional set of requirements for which $f$ exists?

Get this bounty!!!

Leave a Reply