EMD

EMD距离

假设要把$Q$处的方块排列移动成$P$处模样。

定义：
$d_{i,j}$为将方块从$Q$处的第$i$堆移动到$P$处的第$j$堆途经的距离；
$f_{i,j}$为从$Q$处第$i$堆移动到$P$处第$j$堆的方块的数量。

作出如下约束条件：
$f_{i,j}>0$ 每次移动正数数量的方块；
$\sum_{j=1}^{N}f_{i,j}<=q_{i}$，$\sum_{j=1}^{N}f_{i,j}$为从$Q$中$i$处移动到$P$各处的方块量，显然不能超过$Q$中$i$处本来就有的量；
$\sum_{i=1}^{N}f_{i,j}<=p_{i}$，$\sum_{i=1}^{N}f_{i,j}$为从$Q$中各处移动到$P$种$j$处的方块量，显然不需要超过$P$中$j$处本来就有的量。(假设方块只从$Q$运到$P$处，不在$P$内部进行搬运)

定义优化问题：

$$\mathop{\mathsf{argmin}} \limits_{F = f_{i,j}} d_{i,j}f_{i,j} $$

$s.t.$

$$ f_{i,j}>0$$

$$\sum_{j=1}^{N}f_{i,j}<=q_{i}$$

$$\sum_{i=1}^{M}f_{i,j}<=p_{i}$$

假设存在一个$F$使得约束的$(2)$与$(3)$式可以取等号，且令：

$$\sum_{j=1}^{M}p_{i} = \sum_{j=1}^{M}q_{i} = 1$$

显然$\sum_{j=1}^{M}p_{i} = \sum_{j=1}^{M}q_{i}=\sum_{i=1}^{M}(\sum_{j=1}^{N}f_{i,j})$是自动成立的，现在取为$1$后，$q_{i}$、$p_{i}$和$ f_{i,j}$有了概率的表述。

下面定义$EMD$距离：

$$l_{1}(u,v)=\mathop{\inf} \limits_{\pi \in \Gamma(u,v)} \int_{\Re \times \Re} \vert x-y \vert d \pi(x,y)$$

其中，$\Gamma(u,v)$是一个分布组成的集合，其边缘分布为$u(x)$和$v(x)。$

对比咱改动过后的优化问题

$$\mathop{\mathsf{argmin}} \limits_{F = f_{i,j}} d_{i,j}f_{i,j} $$

$s.t.$

$$ f_{i,j}>0$$

$$\sum_{j=1}^{N}f_{i,j}<=q_{i}$$

$$\sum_{i=1}^{M}f_{i,j}<=p_{i}$$

$$\sum_{j=1}^{M}p_{i} = \sum_{j=1}^{M}q_{i}=\sum_{i=1}^{M}[\sum_{j=1}^{N}f_{i,j}] = 1$$

是不是就知道为什么$EMD$距离距离被叫做推土机距离了吧。