最优传输问题和Sinkhorn

最优传输问题

假设有M堆土，每堆土的大小是$a_m$，有N个坑，每个坑的大小是$b_n$，把单位土从土堆m运送到坑n的代价是$c(m,n)$，如何找到一种运输方法填满坑，并且代价最小，这就是最优传输问题（optimal transport (OT) problem）。

假设有两个概率分布，类似上面的情况，如何以最小的成本将一种概率分布转换为另一种概率分布，这也是最优传输问题。这个最小的成本可以作为度量两个概率分布的距离，被称为Wasserstein距离，或者推土机距离（Earth Mover’s Distance（EMD））。

在离散的情况下，假设$\mathbf{r},\mathbf{c}$是两个概率向量，也就是所有元素求和为1的向量。$1_d$是维度为$d$所有元素为1的向量。
运输多面体（transport polytope ）$U(\mathbf{r},\mathbf{c})$被定义为：
U(r,c):={P∈R+d×d∣P1d=r,P⊤1d=c}U(\mathbf r,\mathbf c) := \{ \mathbf P \in \mathbb R^{d \times d}_+ | \mathbf P \mathbf 1_d = \mathbf r, \mathbf P^\top \mathbf 1_d = \mathbf c\} U(r,c):={P∈R+d×d​∣P1d​=r,P⊤1d​=c}
给定一个费用矩阵$\mathbf{M}\in {\mathbb{R}}^{d\times d}$，$\mathbf{r}$到$\mathbf{c}$的最优传输距离被定义为：
$$d_{\mathbf{M}}(\mathbf{r},\mathbf{c}):=\underset{\mathbf{P}\in U(\mathbf{r},\mathbf{c})}{\min }<\mathbf{P},\mathbf{M}>=\sum _{i=1}^d\sum _{j=1}^d{\mathbf{P}}_{ij}{\mathbf{M}}_{ij}$$对于一般的矩阵$\mathbf{M}$，目前提出的最佳算法在最坏情况下的复杂度是 $O(d^3\log d)$。在实践中复杂度也被证明是超立方的。

Sinkhorn距离

为上面的最优传输问题加上熵正则化：
$$\begin{gathered} d_{\mathbf{M}}^{\lambda }(\mathbf{r},\mathbf{c})=\underset{\mathbf{P}\in U(\mathbf{r},\mathbf{c})}{\min }\sum _{i,j}{\mathbf{P}}_{ij}{\mathbf{M}}_{ij}-\frac{1}{\lambda }h(\mathbf{P}) \\ h(\mathbf{P})=-\sum _{i,j}{\mathbf{P}}_{ij}\log {\mathbf{P}}_{ij} \end{gathered}$$ $d_{\mathbf{M}}^{\lambda }(\mathbf{r},\mathbf{c})$被称为dual-Sinkhorn divergence，$h(\mathbf{P})$是香浓熵（Shannon entropy）。
当$\lambda \to 0$时，上面问题的解是${\mathbf{P}}_{ij}={\mathbf{r}}_i{\mathbf{c}}_j$；当$\lambda \to \infty$时，回到了原始的最优输运问题。
香浓熵要求分配更加均匀， 参数$\lambda$权衡了按花费分配和平分。

加上熵正则的最优传输问题变得更好计算了，因为解变得平滑。
Sinkhorn定理被用来寻找熵正则化最优输运问题的解。

参考资料

Wiki Sinkhorn’s theorem
Notes on Optimal Transport
http://alexhwilliams.info/itsneuronalblog/2020/10/09/optimal-transport/
https://zipjiang.github.io/2020/11/23/sinkhorn’s-theorem-,-sinkhorn-algorithm-and-applications.html