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.

Professor Cuturi received his Ph.D. in applied maths in 2005 from the Ecole des Mines de Paris under the supervision of Jean-Philippe Vert. He worked as a post-doctoral researcher at the Institute of Statistical Mathematics, Tokyo, between 2005 and 2007. Between 2007 and 2008 he worked for a hedge fund owned by Credit Suisse in Tokyo. After working at the ORFE department of Princeton University between 2009 and 2010 as a lecturer, he joined the Graduate School of Informatics in Kyoto university as an associate professor.