Optimal Transport

Optimal transport is the general problem of moving one distribution of mass to another as efficiently as possible.

This is a VERY old problem.

OT for ML: https://remi.flamary.com/cours/tuto_otml.html

Entropic Regularization

Solving optimal transport

https://pythonot.github.io/quickstart.html?highlight=geomloss The optimal transport problem between discrete distributions is often expressed as

${\gamma }^{\ast }=argmi{n}_{\gamma \in {\mathbb{R}}_{+}^{m\times n}}{\sum }_{i,j}{\gamma }_{i,j}{M}_{i,j}$ $s.t.\gamma 1=a;{\gamma }^{T}1=b;\gamma \ge 0$ where:

• $M\in {\mathbb{R}}_{+}^{m\times n}$ is the metric cost matrix defining the cost to move mass from bin $a_i$ to bin $b_j$.
• $a$ and $b$ are histograms on the simplex (positive, sum to 1) that represent the weights of each samples in the source and target distributions.

This Python library seems to explain:

• https://pythonot.github.io/master/index.html
• A memory efficient implement of Sinkhorn is found in Geomloss

For example, think of using a pile of dirt to fill a hole of the same volume, so as to minimize the average distance moved.

The Earth Mover’s Distance computes the optimal transport.

Also see Sinkhorn Distance

I also see it as Gradient Flow, but I definitely don’t think it’s the same thing.

Related

• Assignment Problem