Computational Information Geometry Wonderland

There are myriads of formula describing distance between two entities. Usually they are parametric in the sense that a closed-form solution allows one to compute the distance/similarity given the two input objects.

To contrast with these hard-coded distances, there is another approach that consists in desiging non-parametric distances by solving algorithmically a problem. For example, the Earth Mover Distance (EMD) is one such famous distance solved by transport optimization technique.

DistBoost (2004) is another approach inspired from machine learning techniques. It consists in learning the distance from like/dislikes constraints. A binary classifier classes objets into similar/dissimilar classes, say 0 and 1. Moreover, the signed real-valued margin that indicates a confidence level on the prediction can be purposely interpreted as a similarity measure. DistBoost is inspired from the renown boosting technique. The weak learners are solved using a sophisticated constrained EM algorithm.

More details by reading the paper:

Boosting Margin Based Distance Functions for Clustering

The future of data analysis is likely to incorporate these algorithmic distances.
Frank.