In "The Similarity Metric" (Li, Vitanyi, et. al) they define a normalized distance (or similarity distance) as a function $\Omega \times \Omega \to [0,1]$ which is both symmetric and satisfies the density requirement for every $x \in \Omega$ and every constant $c \in [0,1]$:

$\displaystyle |\left \{ y : d(x,y) \leq c \right \}| < 2^{cK(x)+1}$

They give a somewhat convoluted example of a normalized version of the Hamming distance which satisfies this definition, and they prove that their normalized information distance satisfies this definition as well.

It is not at all clear to me that this definition represents a wide variety of "distance" measurements. Their conclusion is that because the normalized information distance is universal in this class of metrics, it is philosophically universal in all metrics we care about. But it's not even obvious to me that Euclidean distance (restricted to $\left \{0,1\right \}^n$) can be modified to satisfy this definition. That's not even close to mentioning distance measures for, say, language sentiment or other distances used in applications.

It would be great if we could say, for instance, that every computable metric has a normalized version which satisfies this definition. Is this known? If not, what is known?

  • $\begingroup$ Perhaps this is not the appropriate place to ask this question? $\endgroup$ – Jeremy Kun Nov 13 '12 at 5:29

The distance should be upper semicomputable. For instance the Hamming distance or Euclidean distance as such is not. One has to turn them into a version that satisfies the requirement above. Read the paper closer.

  • 1
    $\begingroup$ I don't understand. Euclidean (or Hamming) distance is a computable function, and so certainly it is semi-computable, no? Moreover, you did not answer my question: can you always turn a computable metric into a version that satisfies the definition above? $\endgroup$ – Jeremy Kun Nov 24 '14 at 22:51

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.