Transportation distances have been used for more than a decade now in machine
learning to compare histograms of features. They have one parameter: the ground
metric, which can be any metric between the features themselves. As is the case
for all parameterized distances, transportation distances can only prove useful
in practice when this parameter is carefully chosen. To date, the only option
available to practitioners to set the ground metric parameter was to rely on a
priori knowledge of the features, which limited considerably the scope of
application of transportation distances. We propose to lift this limitation and
consider instead algorithms that can learn the ground metric using only a
training set of labeled histograms. We call this approach ground metric
learning. We formulate the problem of learning the ground metric as the
minimization of the difference of two polyhedral convex functions over a convex
set of distance matrices. We follow the presentation of our algorithms with
promising experimental results on binary classification tasks using GIST
descriptors of images taken in the Caltech-256 set.