Ground Metric Learning on Graphs
- PDF / 4,983,089 Bytes
- 19 Pages / 595.276 x 790.866 pts Page_size
- 3 Downloads / 194 Views
Ground Metric Learning on Graphs Matthieu Heitz1
· Nicolas Bonneel1 · David Coeurjolly1 · Marco Cuturi2 · Gabriel Peyré3
Received: 7 November 2019 / Accepted: 12 October 2020 © Springer Science+Business Media, LLC, part of Springer Nature 2020
Abstract Optimal transport (OT) distances between probability distributions are parameterized by the ground metric they use between observations. Their relevance for real-life applications strongly hinges on whether that ground metric parameter is suitably chosen. The challenge of selecting it adaptively and algorithmically from prior knowledge, the so-called ground metric learning (GML) problem, has therefore appeared in various settings. In this paper, we consider the GML problem when the learned metric is constrained to be a geodesic distance on a graph that supports the measures of interest. This imposes a rich structure for candidate metrics, but also enables far more efficient learning procedures when compared to a direct optimization over the space of all metric matrices. We use this setting to tackle an inverse problem stemming from the observation of a density evolving with time; we seek a graph ground metric such that the OT interpolation between the starting and ending densities that result from that ground metric agrees with the observed evolution. This OT dynamic framework is relevant to model natural phenomena exhibiting displacements of mass, such as the evolution of the color palette induced by the modification of lighting and materials. Keywords Optimal transport · Metric learning · Displacement interpolation
1 Introduction Optimal transport (OT) is a powerful tool to compare probability measures supported on geometric domains (such as Euclidean spaces, surfaces or graphs). The value provided by OT lies in its ability to leverage prior knowledge on the proximity of two isolated observations to quantify the discrepancy between two probability distributions of such observations. This prior knowledge is usually encoded as a “ground metric” [39], which defines the cost of moving mass between points. The Wasserstein distance between histograms, densities or point clouds, all seen here as particular instances of probability measures, is defined as the smallest cost required to transport one measure to another. Because this distance is geodesic when the ground metric is geodesic, OT can also
B B
Matthieu Heitz [email protected] David Coeurjolly [email protected]
1
CNRS/LIRIS, Université de Lyon, Lyon, France
2
Google Research, Brain team, Paris, France
3
CNRS and ENS, PSL University, Paris, France
be used to compute interpolations between two probability measures, namely a path in the probability simplex that connects these two measures as end-points. This interpolation is usually referred to as a displacement interpolation [33], describing a series of intermediate measures during the transport process. When two discrete probability distributions are supported on a Euclidean space, and the ground metric is itself the Euclidean di
Data Loading...
