3
$\begingroup$

Could anybody suggest practically important distances that are significantly non-metric and are not Bregman divergences? For instance, they are non-symmetric and not equivalent to the Euclidean distance.

Thanks!

$\endgroup$
  • 1
    $\begingroup$ I'm guessing then you're also not interested in f-divergences or the alpha-divergences ? Also, I don't know if you're implying that Bregman divergences are equivalent to Euclidean distances, because they're not. $\endgroup$ – Suresh Venkat Jun 21 '13 at 20:36
  • $\begingroup$ Maybe I'm missing something, but aren't distances on any real road network non-symmetric? (due to one-way-roads and so on) $\endgroup$ – Shir Jun 22 '13 at 17:12
  • $\begingroup$ Hi Suresh, Bregman divergences are not equivalent, for sure. I only meant that we worked with Bregman divergences, but also wanted to try divergences of different types. Thank you for suggesting f- and -alpha divergences. Is the alpha-divergence the same as Rényi divergence? $\endgroup$ – Leonid Boytsov Jun 22 '13 at 19:21
  • 1
    $\begingroup$ Maybe distance between nodes in directed graphs would interest you. $\endgroup$ – MCH Jun 23 '13 at 15:03
  • 1
    $\begingroup$ What Shir is talking about is probably the same as what MCH suggests: Shortest paths in directed graphs. For undirected graphs, shortest-path-distances yield metrics, but if the edges are directed, the resulting distance may (depending on the graph layout) be asymmetric. It will still obey the oriented triangle inequality, though; i.e., it's a quasimetric: en.wikipedia.org/wiki/Metric_(mathematics)#Quasimetrics $\endgroup$ – Magnus Lie Hetland Jun 24 '13 at 7:11
6
$\begingroup$

For a really thorough listing of various distances, metric or not, that are in use, I recommend Encyclopedia of Distances by Deza and Deza. (It is also available electronically from Springer.) For a really simple example of a family of non-metric distances, you can simply let $p$ be less than 1 for an $L_p$ distance, for example. For a family that is in heavy, actual use, you could look into various forms of weighted edit distance. There's also the cosine measure, Jeffrey divergence, partial Hausdorff distance, dynamic time warping distance, and domain-dependent distances such as the COSIMIR model, all discussed in Skopal's paper on indexing non-metric distances.

$\endgroup$
  • 2
    $\begingroup$ Second the pointer to the Deza and Deza book. It's a very nice reference. $\endgroup$ – Suresh Venkat Jun 24 '13 at 23:46
  • $\begingroup$ Cool, excellent paper, I have also found a more recent survey by Bustos & Skopal (On nonmetric similarity search problems in complex domains). Do I get it correctly that TriGen is designed for symmetric distances, or, is there a non-symmetric extension? $\endgroup$ – Leonid Boytsov Jun 25 '13 at 3:23
  • $\begingroup$ He discusses how to circumvent the asymmetry, as far as I can recall (e.g., by using $d'(x,y) = d(x,y) + d(y,x)$ or the like). $\endgroup$ – Magnus Lie Hetland Jun 25 '13 at 13:14
  • $\begingroup$ @LeonidBoytsov you might also be aware of the Jensen-Shannon type approaches to symmetrizing the Bregman divergences. $\endgroup$ – Suresh Venkat Jun 25 '13 at 17:41
  • $\begingroup$ Yes, symmetrization is an option. $\endgroup$ – Leonid Boytsov Jun 28 '13 at 2:26

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.