Does Mercer's theorem work in reverse?

Question

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.

$$ \begin{align} s(x_i,x_j) &= \exp\left(-\frac{d( m_i, m_j)^2}{r}\right) \\ \sqrt{-r \log s(x_i,x_j) } &= d(m_i,m_j) \\ \end{align} $$

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?

Answer 1

Does Mercer's theorem work in reverse?

Not in all cases.

Wikipedia: "In mathematics, specifically functional analysis, Mercer's theorem is a representation of a symmetric positive-definite function on a square as a sum of a convergent sequence of product functions. This theorem, presented in (Mercer 1909), is one of the most notable results of the work of James Mercer. It is an important theoretical tool in the theory of integral equations; it is used in the Hilbert space theory of stochastic processes, for example the Karhunen–Loève theorem; and it is also used to characterize a symmetric positive semi-definite kernel.

It's a 'many to one mapping' on a Hilbert space. - a gross oversimplification would be to describe it as a hash or checksum that you can test against a file to determine identity or not.

More technical explanation: Disintegration theorem

"In mathematics, the disintegration theorem is a result in measure theory and probability theory. It rigorously defines the idea of a non-trivial "restriction" of a measure to a measure zero subset of the measure space in question. It is related to the existence of conditional probability measures. In a sense, "disintegration" is the opposite process to the construction of a product measure.".

See also: "The Fubini–Tonelli theorem", "Hinge Loss", "Loss Function", and "How Good Is a Kernel When Used as a Similarity Measure?" (June 2007) by Nathan Srebro, the abstract:

"Abstract. Recently, Balcan and Blum suggested a theory of learning based on general similarity functions, instead of positive semi-definite kernels. We study the gap between the learning guarantees based on kernel-based learning, and those that can be obtained by using the kernel as a similarity function, which was left open by Balcan and Blum. We provide a significantly improved bound on how good a kernel function is when used as a similarity function, and extend the result also to the more practically relevant hinge-loss rather then zero-one-error-rate. Furthermore, we show that this bound is tight, and hence establish that there is in-fact a real gap between the traditional kernel-based notion of margin and the newer similarity-based notion.".

A colleague has a function $s$ and for our purposes it is a black-box.

See: kernels and similarity (in R)

It's a black box so you don't know for certain which kernel is used, if it's kernel based, and you don't know the details of the implementation of the kernel once you think you know which one it is. See: Equation of rbfKernel in kernlab is different from the standard?.

On the other hand, this sounds kinda crazy.

It is quick and effective, under a restricted set of circumstances. Like a hammer, if you carry a hammer with you will people call you crazy?

"Kernel methods owe their name to the use of kernel functions, which enable them to operate in a high-dimensional, implicit feature space without ever computing the coordinates of the data in that space, but rather by simply computing the inner products between the images of all pairs of data in the feature space. This operation is often computationally cheaper than the explicit computation of the coordinates. This approach is called the "kernel trick". Kernel functions have been introduced for sequence data, graphs, text, images, as well as vectors.".

Lesson: You (sometimes) get what you pay for.

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$?"

Many, see links above, "Popular Kernel Functions", RBF, and here's one (expensive) example: "A Likelihood Ratio Distance Measure for the Similarity Between the Fourier Transform of Time Series" (2005), by Janacek, Bagnall and Powell.

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

Different spaces and methods can better target comparison (and disintegration) of specific problems, there are many methods for the Hilbert space alone.

Yes, the list is big, see the links above and (for one example): Reproducing kernel Hilbert space.

Answer 2

But it's not obvious that this rather general set of circumstances is sufficient to imply that the triangle inequality is respected.

In fact, it isn't sufficient. Let's work with $d(a, b) = 1 - s(a, b)$. If there are three points $x, y, z$ with $d(x, y) = \frac{1}{3}$, $d(y, z) = \frac{1}{3}$, and $d(x, z) = 1$, then the triangle inequality fails, because $d(x, z) > d(x, y) + d(y, z)$.