11
$\begingroup$

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?

$\endgroup$
  • 3
    $\begingroup$ Note that even if you are given the set of pairwise distances $d(a,b)$ that do satisfy the axioms of distance, it is not guaranteed that there is a Euclidean space with points realizing these distances. Such an embedding is not always possible. See e.g. math.stackexchange.com/questions/1000006. $\endgroup$ – amoeba says Reinstate Monica May 8 '18 at 19:34
  • $\begingroup$ This is a very interesting thread! Thank you for sharing it. It was not my intention to limit myself to a particular distance. (Since, moving in the opposite direction, one might use the RBF kernel with a non-Euclidean distance.) $\endgroup$ – Reinstate Monica May 8 '18 at 19:37
  • $\begingroup$ So your question is just on how to convert $s(a,b)$ into $d(a,b)=f(s(a,b))$ such that $d$ satisfies the triangle inequality? Whether this matrix of distances is embeddable in a Euclidean space, does not matter for you. Correct? My intuition is that for an arbitrary $s$ it won't be possible. $\endgroup$ – amoeba says Reinstate Monica May 8 '18 at 19:40
  • $\begingroup$ This is correct. I suspect that this is not possible, at least not without additional restrictions on $s$. $\endgroup$ – Reinstate Monica May 8 '18 at 19:47
  • $\begingroup$ $f: f(x) = I_{x>0}$ always leads to the discrete metric (en.wikipedia.org/wiki/Discrete_space), but this is probably not intended so some conditions should be added (?) $\endgroup$ – Juho Kokkala May 24 '18 at 18:40
6
+100
$\begingroup$

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.

$\endgroup$
-1
$\begingroup$

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

$\endgroup$
  • 1
    $\begingroup$ I don't see how this proves anything. $\endgroup$ – amoeba says Reinstate Monica May 8 '18 at 19:42
  • $\begingroup$ @amoeba You don't see how it proves that $d$ need not satisfy the triangle inequality? $\endgroup$ – Kodiologist May 8 '18 at 19:43
  • 2
    $\begingroup$ I think this shows that choosing $f(\alpha)=1-\alpha$ doesn't work, but I'm not sure why this shows that the triangle inequality is not respected for an alternative choice of function, such as the (weird) one I outline in my post. $\endgroup$ – Reinstate Monica May 8 '18 at 19:46
  • 1
    $\begingroup$ The question is whether the listed properties of $s$ are sufficient for the existence of an $f$ such that $d$ is a metric, and especially whether such an $f$ can be represented with the RBF kernel with some mapping $m$. This answer seems to ask whether the listed properties of $s$ are sufficient for $d$ being a metric with an arbitrary $f$. $\endgroup$ – Juho Kokkala May 23 '18 at 5:25
  • 1
    $\begingroup$ @Kodiologist but as far as I understand, even the very first version in the edit history contains the part about RBF with an unknown mapping $m$, so I don't see the relevance of working with $1-s(a,b)$. And regarding your previous comment, as I read the question, one is not supposed to "know" anything about how the $x_\alpha$s map to $m_\alpha$s - a counterexample should show that no such mapping can be constructed for the counterexample-$s$. $\endgroup$ – Juho Kokkala May 24 '18 at 18:36

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.