5
$\begingroup$

The intuition behind an optimal transportation problem is rather clear. One aims at finding the best transportation plan $\gamma^{\star}(x,y)$ to match 2 distributions $p_s$ and $p_t$. The cost of the optimal plan gives the Wasserstein-distance:
$$\text{WD}(p_s, p_t) = \text{inf} _{\gamma \in \Pi } \sum C(x,y)\gamma(x,y)$$ where $\Pi$ denotes all distributions, whose marginals are $p_t, p_s$ and $C$ denotes a cost function.

The same problem is considered in literature with an entropy constraint, i.e. one considers: $$ \text{inf} _{\gamma \in \Pi } \sum C(x,y)\gamma(x,y)- \alpha H(\gamma)$$ Where $H(\gamma) = -\sum \gamma \text{ log}(\gamma)$ is the information entropy. I read in literature that this extra term makes the computation of optimal transportations easier but I don't see the intuition behind this term. What does the entropy of a transportation plan represent? How adding this term is affecting the optimal plan? Can someone explain it in the language of information theory? or maybe using the famous example of matching two piles of dirt?

$\endgroup$
2
  • 1
    $\begingroup$ To me, this basically looks like a ridge regression for probability distributions... I don't think of it as being "easier" to solve, but rather as a technique to avoid overfitting. For example, there may be distributions that fit the data perfectly, but they look "weird". Subtracting the $\alpha H(\gamma)$ term basically says "find me a reasonable looking distribution that matches my data well." As opposed to "find me any distribution that matches my data well." The entropy of a distribution should be directly proportional to how under-fit it is. $\endgroup$
    – mm8511
    Commented Jul 6, 2020 at 19:01
  • $\begingroup$ Why is this formulation of regularized OT using entropy of the transport plan $H(\gamma)$, while other versions show the KL-divergence $D_{KL}$ for the regularization term (like the answer below)? Aren't entropy and KL-divergence different? $\endgroup$
    – develarist
    Commented Nov 9, 2020 at 14:49

2 Answers 2

4
$\begingroup$

First of all, notice that for $\alpha=0$ we get our usual optimal cost, which is a Wasserstein distance if our cost function $C$ is the ground metric of our space to some integer power.

As $\alpha$ gets bigger though, the solution of the problem gets further and further away from the Wasserstein distance.

Now let's look at the transport plan $\gamma$ where the infimum is attained:

  • For $\alpha=0$ the infimum is attained for our optimal plan.
  • For $\alpha\to\infty$ however, the infimum is attained when $\gamma$ has maximal entropy.

One can show that the plan (or coupling) with the highest entropy is $p_s\otimes p_t$, the independent joint distribution of $p_s$ and $p_t$, therefore the problem can be rewritten in terms of the KL-Divergence from $\gamma$ to $p_s\otimes p_t$:

$$\inf_\gamma \left(\sum C(x,y)\gamma(x,y)\right) +\left(\alpha \text{D}_\text{KL}\left(\gamma,p_s\otimes p_t\right)\right)$$

So why do we care about $\gamma$ being closer to $p_s\otimes p_t$?

We usually don't want that, but $p_s\otimes p_t$ at least already marginalizes to $p_s$ and $p_t$, i.e. it is a transport plan, albeit usually not a good one.

The Sinkhorn algorithm (or scaling algorithm/IPFP) iteratively ensures that these constraints are satisfied, and numerically solves the entropically regularized problem. However, in that algorithm you have to divide by $\alpha$, so $\alpha$ can't be $0$.

In terms of piles of dirt you can look at the following picture from the Computational Optimal Transport book:

regularized couplings

As $\alpha$ (here $\varepsilon$) gets greater you're less and less sure where to transport which grain of dirt to, one could say your transport plan gets more chaotic.

$\endgroup$
2
  • 1
    $\begingroup$ you've shown that, as the entropy term is weighted more heavily the transport plan gets more chaotic, in other words "Entropic regularization is a way to counteract the tendency of optimal transport to produce nearly deterministic transportation maps by adding a term that favors randomness." I'm trying to understand why a chaotic transport plan would be more desirable? $\endgroup$
    – develarist
    Commented Oct 3, 2020 at 5:17
  • 1
    $\begingroup$ because in the link below, they add "The biggest advantage of including entropic regularization in an optimal transport problem is that the regularized solution can be found very efficiently using a simple iterative algorithm." but they don't explain how so. why would a chaotic open-ended solution using high entropy regularization be better than a deterministic unregularized optimized solution? mindcodec.ai/2018/10/01/… $\endgroup$
    – develarist
    Commented Oct 3, 2020 at 5:18
1
$\begingroup$

I feel

A chaotic transport plan is more desirable because we can use matrix scaling algorithms to solve the entropy-regularized problem. These efficient algorithms can't be used to solve the unregularized problem, because the transport plan does not have a certain structure.

I recommend checking out Cuturi's paper:

Adding an entropy regularization to the optimal transport problem enforces a simple structure on the optimal regularized transport $P^{\lambda}$

This allows us to use the Sinkhorn algorithm, where

...the computations for N target histograms can be simultaneously carried out by updating a single matrix of scaling factors $u \in > \mathbb{R}^{d \times N}_+$ instead of updating a scaling vector $u \in > \mathbb{R}^d_+$. This important observation makes the execution of Algorithm 1 particularly suited to GPGPU platforms.

That being said, it sound's like you're looking for something like the "earth" analogy in "earth-mover's distance". I don't think one exists.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .