Kernels on histograms through the transportation polytope

Posted in Science on August 04, 2008

Kernels on histograms through the transportation polytope

For two integral histograms and of equal sum, the Monge-Kantorovich distance MK(r,c) between r and c parameterized by a d × d cost matrix T is the minimum of all costs <F,T> taken over matrices F of the transportation polytope U(r,c). Recent results suggest that this distance is not negative definite, and hence, through Schoenberg's well-known result, may not be a positive definite kernel for all t > 0. Rather than using directly MK to define a similarity between r and c, we present in this talk kernels on r and c based on the whole transportation polytope U(r,c). We prove that when r and c have binary counts, which is equivalent to stating that r and c depict clouds of points of equal size, the permanent of their Gram matrix induced by the cost matrix T is a positive definite kernel under favorable conditions on T. We also show that the volume of the polytope U(r,c), that is the number of integral transportation plans, is a positive definite quantity in r and c through the Robinson-Schensted-Knuth correspondence between transportation matrices and Young Tableaux.

Author: Marco Cuturi, Institute of Statistical Mathematics in Tokyo

Watch Video

Tags: Science, Lectures, Computer Science, Machine Learning, VideoLectures.Net, Kernel Methods