harry's blog

1. 基本概念

最优传输是在可分度量空间中，讨论概率测度间最优传输变换的一类优化问题，涉及到偏微分方程和凸几何等多种理论，是多学科交叉的研究领域。直观的一个解释是：假设有两个工地$X$和$Y$，工地$X$上有$m$堆土，工地$Y$上有$n$个坑，现在要将工地$X$上的$m$堆土全部移动到工地$Y$上的$n$个坑中，如何移动才能使做工最少？在最优传输方案下做的功就是最少的功，这在工程上被称为推土机距离。最优传输问题非常复杂，最近在图像处理领域发展迅速，吸引了越来越多学者的重视和关注

1781 年法国数学家 Monge 首先提出了最优传输问题，力求在给定代价函数下寻求将一种分布变换成另外一种分布的有效方式，如图所示。其数学表述如下：

设$X$、$Y$为完备可分的度量空间，其概率测度分别为$\mu\in P(X)$，$\nu\in P(Y)$，现在有一个映射$T:X\to Y$，假设两空间的总测度相同，即:

$$
\int_{X}\mu=\int_{Y}\nu
$$

满足上式，映射就是保测度的，记为$T_{p}\mu=\nu$，设代价函数$c:X\times Y\to [0,+\infty]$，最优传输映射就是在所有保测度映射中，传输代价最小者，即求解:

$$
\inf {M(T):=\int_{X}c(x,T(x))d\mu(x):T_{\pi}\mu=\nu}
$$

在保质量条件$T_{\pi}\mu=\nu$的前提下，将分布$\mu$变换为分布$\nu$，且代价最小的方案就是最优传输方案$T$，但是由于保质量条件的存在，变成了一个难以求解的非凸问题，且最优传输方案不一定存在

Monge形式的最优传输问题求解困难且具有一定的病态性，但是由于18世纪各种数学定理发展不够成熟，最优传输问题一直没有得到很好的解决。直到1942年Kantorovich成功地解决了此问题，如图所示，Kantorovich形式的最优传输可以描述为：不将每一堆土直接填充到坑中，而是将一堆土分为若干部分然后进行填充。其数学表述如下：

设$X$、$Y$为完备可分的度量空间，其概率测度分别为$\mu\in P(X)$，$\nu\in P(Y)$，代价函数$c:X\times Y\to[0,+\infty]$，求解：

$$
\inf {K(\gamma):=\int_{X\times Y} c(x,y) d\gamma(x,y) :\gamma\in \prod(\mu,\nu)}
$$

其中$\prod(\mu,\nu)$为传输计划的集合，即$\prod(\mu,\nu)={\gamma\in P(X\times Y)😦\pi_{x}){\pi}\gamma=\mu,(\pi{y}){\pi}\gamma=\nu}$, 也可以看作是$\mu$，$\nu$的联合概率密度，上式的保质量条件为$(\pi{x}){\pi}\gamma=\mu,(\pi{y})_{\pi}\gamma=\nu$，也可以表示为$\gamma(A\times Y)=\mu(A),\gamma(X\times B)=\nu(B)$，当$\gamma$最小时的传输方案就是所求的最优传输计划。Kantorovich形式与Monge形式不同，Kantorovich的方案可以处理任意的可测集，并且可以将质量进行分解，从一个位置传输到任意多个位置。1991年Brenier证明，当代价函数$c(\mu,\nu)=\frac{1}{2}\left|\mu-\nu\right|^{2}$时最优传输方案存在且唯一，形式为$T(x)=\nabla u(x)$，其中$u$为凸函数

最优传输问题的最小距离被称为Wasserstein距离，也被称为Monge-Kantorovich距离或者推土机距离，数学定义如下：

设$\Omega\subset\mathbb{R}^{d}$，$\mu,\nu\in P_{p}(\Omega)$，Wasserstein距离定义为:

$$
W_{p}(\mu,\nu):=\min{\int_{\Omega\times \Omega}\left| x-y\right|^{{p}d\gamma:\gamma\in\prod(\mu,\nu)}}{\frac{1}{p}}
$$

其中$P_{p}(\Omega)={\mu\in P(\Omega):\int_{\Omega}\left|x\right|^{{p}d\mu<+\infty}$，$p\in[1,+\infty)$。由上式可知，Wasserstein距离的p次方是最优传输问题在代价函数为$c(x,y)=\left|x-y\right|}p$时的最小传输代价，在图像处理领域，Wasserstein 距离表现通常优于其他距离。

本文由 Yonghui Wang 创作，采用知识共享署名4.0 国际许可协议进行许可
本站文章除注明转载/出处外，均为本站原创或翻译，转载前请务必署名
最后编辑时间为: Dec 19, 2024 12:06 pm

最优传输 OT

1. 基本概念