网站建设需要度搜去,wordpress做漫画,株洲网上购房节,phpstudy搭建本地网站最优传输问题
假设有M堆土#xff0c;每堆土的大小是ama_mam#xff0c;有N个坑#xff0c;每个坑的大小是bnb_nbn#xff0c;把单位土从土堆m运送到坑n的代价是c(m,n)c(m,n)c(m,n)#xff0c;如何找到一种运输方法填满坑#xff0c;并且代价最小#xff0c;这就是…最优传输问题
假设有M堆土每堆土的大小是ama_mam有N个坑每个坑的大小是bnb_nbn把单位土从土堆m运送到坑n的代价是c(m,n)c(m,n)c(m,n)如何找到一种运输方法填满坑并且代价最小这就是最优传输问题optimal transport (OT) problem。
假设有两个概率分布类似上面的情况如何以最小的成本将一种概率分布转换为另一种概率分布这也是最优传输问题。这个最小的成本可以作为度量两个概率分布的距离被称为Wasserstein距离或者推土机距离Earth Mover’s DistanceEMD。
在离散的情况下假设r,c\mathbf r, \mathbf cr,c是两个概率向量也就是所有元素求和为1的向量。1d\mathbf 1_d1d是维度为ddd所有元素为1的向量。 运输多面体transport polytope U(r,c)U(\mathbf r,\mathbf c)U(r,c)被定义为 U(r,c):{P∈Rd×d∣P1dr,P⊤1dc}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∈Rd×d∣P1dr,P⊤1dc} 给定一个费用矩阵M∈Rd×d\mathbf M \in \mathbb R^{d \times d}M∈Rd×dr\mathbf rr到c\mathbf cc的最优传输距离被定义为 dM(r,c):minP∈U(r,c)P,M∑i1d∑j1dPijMijd_{\mathbf M}(\mathbf r, \mathbf c) : \min_{\mathbf P \in U(\mathbf r,\mathbf c)}\mathbf P, \mathbf M \sum_{i1}^d \sum_{j1}^d \mathbf{P}_{ij} \mathbf{M}_{ij} dM(r,c):P∈U(r,c)minP,Mi1∑dj1∑dPijMij对于一般的矩阵M\mathbf MM目前提出的最佳算法在最坏情况下的复杂度是 O(d3logd)O(d^3 \log d)O(d3logd)。在实践中复杂度也被证明是超立方的。
Sinkhorn距离
为上面的最优传输问题加上熵正则化 dMλ(r,c)minP∈U(r,c)∑i,jPijMij−1λh(P)h(P)−∑i,jPijlogPijd_\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)\\ h(\mathbf P) -\sum_{i,j}\mathbf P_{ij}\log \mathbf P_{ij} dMλ(r,c)P∈U(r,c)mini,j∑PijMij−λ1h(P)h(P)−i,j∑PijlogPij dMλ(r,c)d_\mathbf{M}^\lambda(\mathbf{r}, \mathbf{c})dMλ(r,c)被称为dual-Sinkhorn divergenceh(P)h(\mathbf P)h(P)是香浓熵Shannon entropy。 当λ→0\lambda\rightarrow0λ→0时上面问题的解是Pijricj\mathbf P_{ij}\mathbf r_i \mathbf c_jPijricj当λ→∞\lambda\rightarrow\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
