| Date |
Nov 21, 2013 |
| Speaker |
Assoc. Prof. Marco Cuturi, Graduate School of Informatics, Kyoto Univ.
|
| Title |
Sinkhorn Distances: Lightspeed Computation of Optimal Transport
|
| Abstract |
Optimal transport distances are a fundamental family
of parameterized distances for histograms and points clouds.
Despite their appealing theoretical properties, excellent performance
in retrieval tasks and intuitive formulation, their computation
involves the resolution of a linear program whose cost is prohibitive
whenever the histograms' dimension exceeds a few hundreds.
We propose in this work a new family of optimal transport distances
that look at transport problems from a maximum-entropy perspective.
We smooth the classical optimal transport problem with an entropic
regularization term, and show that the resulting optimum is also
a distance which can be computed through Sinkhorn-Knopp's matrix
scaling algorithm at a speed that is several orders of magnitude
faster than that of transport solvers. We also report improved
performance over classical optimal transport distances on the
MNIST benchmark problem and mention in the end of this talk new work
on Wasserstein barycenters that illustrate the usefulness of
these tools.
|
|
アブストラクト