Metric Learning, From Mahalanobis Distances to Transportation Distances
Marco Cuturi, Kyoto University

Area: Machine Learning

Abstract:

K-nearest neighbors methods can be used in a wide variety of supervised machine learning tasks such as regression or classification. A key ingredient of such methods lies in the definition of a distance between observations. It has been widely observed that selecting a relevant distance to compare observations is key to obtaining good performance. For about a decade now, researchers in machine learning have proposed to select such a distance automatically through examples, that is by only using a training set of labeled vectors. To do so, all of these techniques have in common that they consider the parameterized family of Mahalanobis distances as the set of candidate distances to choose from. I will present in the first part of this talk a few of these metric learning methods. I argue however that metric learning is not necessarily limited to Mahalanobis distances, but can also be applied to other families of distances. I consider in this talk the family of Transportation distances, which have been proposed two centuries ago to compare probability distributions and more simply histograms of features. Transportation distances are popular in computer vision, where, under the name of Earth Mover's Distance, they have been used to compare images seen as histograms of colors, SIFT or GIST features. I will show in the second half of this talk that the parameters of Transportation distances can also be tuned automatically through a labeled database of histograms and will present empirical evidence that such algorithms perform better than Mahalanobis metric learning in that case.