Wasserstein距离笔记

Wasserstein距离

Wasserstein距离也叫做推土机距离（Earth Mover's distance），简称EMD，用来表示两个分布的相似程度。EMD是2000年IJCV期刊文章《The Earth Mover's Distance as a Metric for Image Retrieval》提出的一种直方图相似度量（作者在之前的会议论文中也已经提到，不过鉴于IJCV的权威性和完整性，建议参考这篇文章）。这也是由于它的推导过程可以很形象的用挖土填土来解释，这也是因为该距离定义中由一个分布转变为另一个分布所需要的代价和挖土填土的过程十分相似。

假设有两个工地P和Q，P工地上有m堆土，Q工地上有n个坑，现在要将P工地上的m堆土全部移动到Q工地上的n个坑中，所做的最小的功。

每堆土我们用一个二元组来表示(p,w)，p表示土堆的中心，w表示土的数量。则这两个工地可表示为：

每个土堆中心pi到每个土坑中心qj都会有一个距离dij，则构成了一个m*n的距离矩阵。

那么问题就是我们希望找到一个流（flow），当然也是个矩阵[fij]，每一项fij代表从pi到qj的流动数量，从而最小化整体的代价函数：

问题描述清楚了：就是把P中的m个坑的土，用最小的代价搬到Q中的n个坑中，pi到qj的两个坑的距离由dij来表示。fij是从pi搬到qj的土的量；dij是pi位置到qj位置的代价（距离）。要最小化WORK工作量。EMD是把这个工作量归一化以后的表达，即除以对fij的求和。

 EMD公式：

http://www.noobyard.com/article/p-hnrquorl-cv.html

案例sample：考虑两个离散的分布P和Q

为了让两个分布相同，我们一个个变量地观察，

• *为了让P1和Q1相同，我们需要P1把手头上的3分2到P2去，这样P1和Q1都等于1，此时P2=4，其他数保持不变，这个过程是不是十分像挖掉P1的土填到P2上~
• 为了让P2和Q2相同，我们也要做类似的挖土填土工作，但注意，此时P2手头上由P1填的2，因此现在P2是4，但是Q2依然是2，因而P2也要挖2分土给P3，保持和Q2一样。
• P3和Q3也是一样，但此时P3为3，Q3为4，因为我们只能先挖土再填土，因此要Q3挖1分土给Q4，这样P4和Q4也能够一样。

每一步的代价计算公式为 ，第0步我们规定为0，故有

所以最终的总代价，也即Wasserstein距离则为