最优传输问题
假设有 M M M堆土，每堆土的大小是 a m a_m am，有 N N N个坑，每个坑的大小是 b n b_n bn，把单位土从土堆 m m m运送到坑 n n n的代价是 c ( m , n ) c(m,n) c(m,n)，如何找到一种运输方法填满坑，并且代价最小，这就是最优传输问题（optimal transport (OT) problem）。
假设有两个概率分布，如何以最小的成本将一种概率分布转换为另一种概率分布，这也是最优传输问题。这个最小的成本可以作为度量两个概率分布的距离，被称为Wasserstein距离，或者推土机距离（Earth Mover’s Distance（EMD））。
在离散的情况下，假设
r
,
c
∈
R
+
d
\mathbf r, \mathbf c \in \mathbb R^d_+
r,c∈R+d是两个概率向量，也就是元素求和为1。
1
d
\mathbf 1_d
1d是维度为
d
d
d所有元素为1的向量。
运输多面体（transport polytope ）
U
(
r
,
c
)
U(\mathbf r,\mathbf c)
U(r,c)被定义为：
U
(
r
,
c
)
:
=
{
P
∈
R
+
d
×
d
∣
P
1
d
=
r
,
P
⊤
1
d
=
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}给定一个费用矩阵
M
∈
R
d
×
d
\mathbf M \in \mathbb R^{d \times d}
M∈Rd×d，
r
\mathbf r
r到
c
\mathbf c
c的最优传输距离被定义为：
d
M
(
r
,
c
)
:
=
min
P
∈
U
(
r
,
c
)
<
P
,
M
>
=
∑
i
,
j
P
i
j
M
i
j
d_{\mathbf M}(\mathbf r, \mathbf c) := \min_{\mathbf P \in U(\mathbf r,\mathbf c)}<\mathbf P, \mathbf M> = \sum_{i,j} \mathbf{P}_{ij} \mathbf{M}_{ij}
dM(r,c):=P∈U(r,c)min<P,M>=i,j∑PijMij对于一般的矩阵
M
\mathbf M
M，目前提出的最佳算法在最坏情况下的复杂度是
O
(
d
3
log
d
)
O(d^3 \log d)
O(d3logd)。在实践中复杂度也被证明是超立方的。
Sinkhorn距离
直接求解最优传输问题的复杂度非常高。为了解决这个问题，考虑在限定的范围内求解。
定义凸集（convex set）：
U
α
(
r
,
c
)
:
=
{
P
∈
U
(
r
,
c
)
∣
K
L
(
P
∣
∣
r
c
⊤
)
≤
α
}
=
{
P
∈
U
(
r
,
c
)
∣
h
(
P
≥
h
(
r
)
+
h
(
r
)
−
α
}
⊂
U
(
r
,
c
)
U_\alpha(\mathbf r,\mathbf c) := \{\mathbf P \in U(\mathbf r,\mathbf c) | KL(\mathbf P || \mathbf r \mathbf c^\top) \leq \alpha\} = \{\mathbf P \in U(\mathbf r,\mathbf c) | h(\mathbf P \geq h(\mathbf r) + h(\mathbf r) - \alpha\} \subset U(\mathbf r,\mathbf c)
Uα(r,c):={P∈U(r,c)∣KL(P∣∣rc⊤)≤α}={P∈U(r,c)∣h(P≥h(r)+h(r)−α}⊂U(r,c)其中
h
(
⋅
)
h(\mathbf \cdot)
h(⋅)是香浓熵（Shannon entropy）:
h
(
r
)
=
−
∑
i
r
i
log
r
i
h
(
P
)
=
−
∑
i
,
j
P
i
j
log
P
i
j
h(\mathbf r) = -\sum_{i}\mathbf r_{i}\log \mathbf r_{i}\\ h(\mathbf P) = -\sum_{i,j}\mathbf P_{ij}\log \mathbf P_{ij}
h(r)=−i∑rilogrih(P)=−i,j∑PijlogPijSinkhorn distance被定义为：
d
M
,
α
(
r
,
c
)
:
=
min
P
∈
U
α
(
r
,
c
)
∑
i
,
j
P
i
j
M
i
j
d_{\mathbf{M},\alpha}(\mathbf{r}, \mathbf{c}) := \min_{\mathbf P\in U_\alpha(\mathbf{r}, \mathbf{c})}\, \sum_{i,j} \mathbf P_{ij} \mathbf M_{ij}
dM,α(r,c):=P∈Uα(r,c)mini,j∑PijMij这是熵约束的最优传输问题。
上面的熵约束的最优传输问题可以通过拉格朗日乘数法（Lagrange multiplier）转换为
d
M
λ
(
r
,
c
)
=
min
P
∈
U
(
r
,
c
)
∑
i
,
j
P
i
j
M
i
j
−
1
λ
h
(
P
)
(1)
d_\mathbf{M}^\lambda(\mathbf{r}, \mathbf{c}) = \min_{\mathbf P\in U(\mathbf{r}, \mathbf{c})}\, \sum_{i,j} \mathbf P_{ij} \mathbf M_{ij} - \frac{1}{\lambda}h(\mathbf P) \tag{1}
dMλ(r,c)=P∈U(r,c)mini,j∑PijMij−λ1h(P)(1)
d
M
λ
(
r
,
c
)
d_\mathbf{M}^\lambda(\mathbf{r}, \mathbf{c})
dMλ(r,c)被称为dual-Sinkhorn divergence。
通过对偶理论可以知道，对任意
α
\alpha
α，有一个对应的
λ
∈
[
0
,
∞
]
\lambda\in[0, \infty]
λ∈[0,∞]使得
U
α
(
r
,
c
)
=
d
M
λ
(
r
,
c
)
U_\alpha(\mathbf r,\mathbf c) = d_\mathbf{M}^\lambda(\mathbf{r}, \mathbf{c})
Uα(r,c)=dMλ(r,c)。
这可以看成为最优传输问题加上熵正则化。
当
λ
→
0
\lambda\rightarrow0
λ→0时，上面问题的解是
P
i
j
=
r
i
c
j
\mathbf P_{ij}=\mathbf r_i \mathbf c_j
Pij=ricj；当
λ
→
∞
\lambda\rightarrow\infty
λ→∞时，回到了原始的最优输运问题。
香浓熵要求分配更加均匀， 参数
λ
\lambda
λ权衡了按花费分配和平分。
加上熵正则的最优传输问题变得更好计算了，因为解变得平滑。
Sinkhorn定理被用来寻找熵正则化最优输运问题的解。
Sinkhorn定理
Sinkhorn 定理指出每个所有元素为正的方阵都可以写成某种标准形式。
具体而言，假设
A
\mathbf A
A是一个
n
×
n
n \times n
n×n的所有元素为正的方阵，则存在所有元素为正的向量
d
1
\mathbf d_1
d1和
d
2
\mathbf d_2
d2，使得
diag
(
d
1
)
A
diag
(
d
1
)
\text{diag}(\mathbf d_1)\mathbf A\text{diag}(\mathbf d_1)
diag(d1)Adiag(d1)是双随机（doubly stochastic）的。双随机矩阵是非负实数方阵，且每个行和列求和均为1。
d
1
\mathbf d_1
d1和
d
2
\mathbf d_2
d2在常数因子倍上是唯一的。
Sinkhorn算法非常简单，通过迭代的方法，交替地缩放
A
\mathbf A
A的所有行和所有列使其和为 1。
(
d
1
,
d
1
)
←
(
1.
/
A
d
2
,
1.
/
A
⊤
d
1
)
(\mathbf d_1, \mathbf d_1) \leftarrow (\mathbf 1 ./ \mathbf A \mathbf d_2, \mathbf 1 ./ \mathbf A^\top \mathbf d_1)
(d1,d1)←(1./Ad2,1./A⊤d1)
使用Sinkhorn算法求解熵正则化最优输运问题
可以证明公式(1)具有唯一解，且解具有形式
P
λ
=
diag
(
u
)
K
diag
(
v
)
\mathbf P^\lambda = \text{diag}(\mathbf u)\mathbf K \text{diag}(\mathbf v)
Pλ=diag(u)Kdiag(v)，
u
,
v
\mathbf u,\mathbf v
u,v是所有元素为正的向量，
K
:
=
e
−
λ
M
\mathbf K:=e^{-\lambda \mathbf M}
K:=e−λM。
这可以通过Sinkhorn算法求解。注意这不是原始的Sinkhorn算法，因为
P
λ
\mathbf P^\lambda
Pλ的每个行和列的和由
r
\mathbf r
r和
c
\mathbf c
c确定，而不再是1。
(
u
,
v
)
←
(
r
.
/
K
v
,
c
.
/
K
⊤
u
)
(\mathbf u, \mathbf v) \leftarrow (\mathbf r ./ \mathbf K \mathbf v, \mathbf c ./ \mathbf K^\top \mathbf u)
(u,v)←(r./Kv,c./K⊤u)文章来源：https://www.toymoban.com/news/detail-708467.html
参考资料
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文章来源地址https://www.toymoban.com/news/detail-708467.html
到了这里，关于最优传输问题和Sinkhorn的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！
![[足式机器人]Part2 Dr. CAN学习笔记- 最优控制Optimal Control Ch07-1最优控制问题与性能指标](https://imgs.yssmx.com/Uploads/2024/01/818750-1.png)
